BL2 Bot Player

Discuss about Blockout II from Jean-Luc, post your feature requests etc.
Post Reply
jlp_38
Posts: 264
Joined: Tue Jun 26, 2007 9:09 am

BL2 Bot Player

Post by jlp_38 »

Hi there, B)

I\'ve just ended the basic programmation for the BL2 DEMO mode. Now, i\'m looking for a good evaluation function. If you are insterred in testing and designing an evaluation function for BL2, grab the source from cvs (D3D/WIN32 only) and recompile it. I added a \"Demo Mode\" menu item on the main page and all code concerning the AI is located in the file BotPlayer.cpp.

All the path finding and move enumeration stuff is already coded. The function which need improvements is especially the function BotPlayer::Evaluate().

Here is an example of such a function:
(This one plays rather well in OOC)

Code: Select all

float BotPlayer::Evaluate() {

  // Drop the block
  float descent = DropBlock();

  // Number of hole before adding the block
  float nbHole0 = GetNbHole();
  
  // Add the block to the pit
  AddBlock();

  // Get the ratio of common edge between the block and the pit
  // This greatly increase the building efficiency
  float commonEdge = GetCommonEdge();

  // Remove lines
  float nbLines = RemoveLines();

  // Number of hole after the move
  float nbHole1 = GetNbHole();

  // Number of added Hole (can be negative)
  float addedHole = nbHole1 - nbHole0;

  // Free depth (free space at the top of the pit)
  float freeDepth = GetFreeDepth();

  // Evaluation function
  /* GOOD in 3D Mania
  if( freeDepth > 0.4f )
    return -addedHole + 2.0f*commonEdge + descent;
  else
    return nbLines + commonEdge + descent;
  */

  return nbLines - 3.0f*addedHole + commonEdge + descent + 0.5f*freeDepth;

}
All your ideas are welcome :)

If you have any questions, don\'t hesitate....
fredjust
Posts: 66
Joined: Fri Jun 29, 2007 3:59 pm

Re:BL2 Bot Player

Post by fredjust »

Very interesting

But I make a ghost on my disk and I can\'t compile BL2 on this time

for compare bot player, they must stop at level 10
if not infinite score is possible<br><br>Post edited by: fredjust, at: 2007/09/01 08:40
Lieven
Posts: 55
Joined: Sun Aug 05, 2007 6:31 am

Re:BL2 Bot Player

Post by Lieven »

Great news indeed!

The demo is already very good, well done!!

I managed to get 3Dmania on the lowest depths (3x3x6) a bit better (gets around 300-500 cubes average, which is better than what it was and also a bit better than the original BL). Ideally, the comp should be able to run infinitely in this mode (like humans would if the level wouldn\'t increase). I also believe that if we get this mode right, all BASIC-set modes will be good.

Two questions:
a) Getvalue(i,j,k) gives information about the position. Is 0=empty, 1=occupied? But what is the meaning of 2?

b) What exactly does descent (== DropBlock()) represent?<br><br>Post edited by: Lieven, at: 2007/09/03 01:18
jlp_38
Posts: 264
Joined: Tue Jun 26, 2007 9:09 am

Re:BL2 Bot Player

Post by jlp_38 »

Hi,

> I managed to get 3Dmania on the lowest depths
> (3x3x6) a bit better (gets around 300-500 cubes
> average, which is better than what it was and also > a bit better than the original BL).

Great :)

> Ideally, the comp should be able to run infinitely > in this mode (like humans would if the level
> wouldn\'t increase). I also believe that if we get > this mode right, all BASIC-set modes will be good.

Yes It would be great to find an algorithm that
can play infinitely but I\'m not sure that such
a program exists with the BASIC block set.

a) Getvalue(i,j,k) gives information about the position. Is 0=empty, 1=occupied? But what is the meaning of 2?

2 means (as 1) occupied but occupied by the last added piece. It allows to calculate the number of common edge. See GetCommonEdge().

b) What exactly does descent (== DropBlock()) represent?

This is the vertical translation that the block need s to reach its definitive position at the bottom of the pit.
The value if given in the range [0=>no translation,1=>translation=pit depth]
Lieven
Posts: 55
Joined: Sun Aug 05, 2007 6:31 am

Re:BL2 Bot Player

Post by Lieven »

Thanks a lot for your answers.

Ok this might be a bit much to ask, but on the other hand it might also be easy to do. I am not sure.

Would it be possible to create a silent demo mode (which could be removed in the release version) for demo-testing and parameter tweaking. This mode would do:

A simulation without graphics of say a fixed 10.000 (or 100.000) blocks in the current mode. So nothing happens on the screen. This should be pretty fast. After that it would print the following info:

1. number of restarts (in case the game has ended)
2. average number of freedepth
3. number of empty pits
4. total score

In that way it would be very easy to see whether given parameters are better/worse while tweaking, without having to sit through 10 min of display.

If this wouldn\'t be possible, is there any way to remove all delay in graphics display?

I am mainly working on basic set, with small dimensions. it plays 3Dmania pretty well (averaging around 10.000 blocks before ending). I will post the code here once it is tweaked and cleaned up properly (hopefully i get it to play indefinitely at least in 3Dmania).

Best regards,

Lieven<br><br>Post edited by: Lieven, at: 2007/09/04 03:55
jlp_38
Posts: 264
Joined: Tue Jun 26, 2007 9:09 am

Re:BL2 Bot Player

Post by jlp_38 »

> I am mainly working on basic set, with small
> dimensions. it plays 3Dmania pretty well
> (averaging > around 10.000 blocks before ending).
> I will post the code here once it is tweaked and
> cleaned up properly (hopefully i get it to play
> indefinitely at least in > 3Dmania).

Thank you very much for your work :)

Unfortunately i don\'t have time now to change the program to get a fast demo mode. I\'m on holiday until the next week ;) What you can do to get quickly a fast demo mode is to make the following
modifications:

In the file Game.cpp:

Code: Select all

// Drop time (seconds)
//const float dropTime = 0.16f;
const float dropTime = 0.0f;
In the file SetupManager.cpp:

Code: Select all

float SetupManager::GetAnimationTime() {

  float min = 0.05f;
  float max = 0.15f;
  float speed = min + (max-min) * (float)(ASPEED_FAST - animationSpeed) / ((float)ASPEED_FAST);
  //return speed;
  return 0.0f;

}
Lieven
Posts: 55
Joined: Sun Aug 05, 2007 6:31 am

Re:BL2 Bot Player

Post by Lieven »

Thank you so much, this helps a lot.

Getting an average of 700 blocks now (over 80 runs, low 35! high 3598!) in 3x3x6 basic (compared to around 200 blocks in the cvs version); and played 3Dmania once with these setting and got 40000 blocks. Still a lot of room for improvement left.

Lieven<br><br>Post edited by: Lieven, at: 2007/09/05 17:40
Lieven
Posts: 55
Joined: Sun Aug 05, 2007 6:31 am

Re:BL2 Bot Player

Post by Lieven »

Hi,

Don\'t worry about the fast demo mode anymore, I managed to patch it myself to let it auto-restart and keep track of the average cube count.


However there is something else I am wondering. Have a look at this


Somehow I have the feeling that not all possible combinations of translations/rotations are done, especially not when the depth is low.
It could be bug in my evaluation code, but I don\'t think so.
Is this something you agree on, on the basis of these two examples? Also, is this fixable? Image
Lieven
Posts: 55
Joined: Sun Aug 05, 2007 6:31 am

Re:BL2 Bot Player

Post by Lieven »

Just to say I am still working on this, got the average up to around 800 blocks in the smallest mode on BASIC (average over 2500 games, took more than 10 hours to run them). My goal is to get the average over 1000.

Jean-Luc, if you plan to release a new blockout version, please do say so, so I can post my code.

Lieven
User avatar
Herc
Posts: 174
Joined: Sun May 20, 2007 12:54 pm

Re:BL2 Bot Player

Post by Herc »

cool stuff! Lieven, keep on working on the bot, i am very eager to see it in a new release!
Lieven
Posts: 55
Joined: Sun Aug 05, 2007 6:31 am

Re:BL2 Bot Player

Post by Lieven »

Jean-Luc, where are you? I am progressing steadily but give us a sign of life!
Lieven
Posts: 55
Joined: Sun Aug 05, 2007 6:31 am

Re:BL2 Bot Player

Post by Lieven »

Hi,

Ok here is included a version of the botplayer: [file name=BotPlayer.txt size=12842]http://www.blockout.net/components/com_ ... Player.txt[/file] . It averages around 1100 blocks on 3x3x6 Basic (thus on average it reaches level 10 with ease). So, I reached my goal, and I think it plays a good game. I also included params that are good for flat and out of control mode, but especially out of control could use tweaking.

Here is the evaluation function:

Code: Select all

float BotPlayer::Evaluate() {

  DropBlock(); // Drop the block
  AddBlock(); // Add the block to the pit
  RemoveLines();   // Remove lines

  float thick=Thickness(); //Number of blocks
  float nbHole1 = GetNbHole(); // Number of holes
  float smooth = Smoothness(); // How smooth is the pitch
  float edgel = Edges(); //if you have to go high, go high on the edge
 
  return -27*thick-75.0f*nbHole1-3.0f*smooth+17.0f*edgel; //3DMANIA
  //return -27*thick-75.0f*nbHole1-3.0f*smooth+2*edgel; //FLAT FUN 
  //return -27*thick-500.0f*nbHole1-20.0f*smooth+2*edgel; //OUT OF CONTROL
}
Two things (excuse my english):
1. I made it depth independent: it plays 3x3x6 the same as 3x3x10, so if you get the params right for one mode, they are ok for every depth in that mode.
2. The original evaluation looked at the pitch before and after (so at the difference). Now it looks only at the pitch after. This has two advantages:
a) It is conceptually simpler: the evaluation function simply attaches a score to every pit.
b) In principal this makes it possible to think ahead: one could for instance think about looking one step ahead:

You start with your PIT, call it PIT 1
You have your basic for loop over all possible rotations and translations
-> execute it, so you have PIT 2
Then you have a for loop over every possible next block type
Then you have a for loop again over all possible rot and transl of this new block
-> execute it, so you have PIT 3
-> then here remember the value of the minimum evaluation of PIT 3.
-> here, remember which PIT 2 achieves the highest, minimum evaluation of PIT 3

The block you pick guarantees an \"easy ride\" for your next block. Basically it is the minmax algorithm (http://en.wikipedia.org/wiki/Minmax), also used in chess (which also has a evaluation function for every position). I didn\'t implement it because I don\'t understand enough of the code, but should be easy. One could even look further ahead. I think this is the way forward for perfect play (and would be very keen to see it playing 3x3x6 BASIC or out of control)!


Lieven

Post edited by: Lieven, at: 2007/10/23 22:58<br><br>Post edited by: Lieven, at: 2007/10/23 22:59
User avatar
Herc
Posts: 174
Joined: Sun May 20, 2007 12:54 pm

Re:BL2 Bot Player

Post by Herc »

very interesting! it would be interesting how deep we could look ahead in \"out of control\" without having too long thinking times. i could imagine that search times explode quite fast.

lets hope jean luc will find some time to continue with blockoutII.
jlp_38
Posts: 264
Joined: Tue Jun 26, 2007 9:09 am

Re:BL2 Bot Player

Post by jlp_38 »

Hi there,

Sorry for this very late answer but I got much job during the last 2 or 3 months.
Thank you Lieven for your improvement tips :)
I have few remarks:

- It seems that your evaluation function gives much importance to holes. I don\'t
think that this always good, I rather think that there should be in fact to playing
mode. One building mode and one emergency mode. When you are at the top of the
pit (in emergency mode), holes shouldn\'t be take into consideration. You have
to make line and \"optimize the depth\". 6 depth pits are typically \"always emergency
playing mode\" . The following emergency evaluation function averages around 910 cubes
in 3x3x6 BASIC.

Code: Select all

return nbLines + 2.0f * commonEdge + descent;
In building mode, when the depth is not critical, you can consider holes.

- Concerning the min-max algorithm, i\'m not sure it will bring a good improvement,
this kind of algorithm evaluates 2 (or more) players moving strategy. Blockout is
a single player game. OK we can assign the second player to the random generator
(which chooses block), but it doesn\'t choose the worst block for you. A good
improvement to bring would be a best path finding algo, as you mentioned not
all possible paths are evaluated by the present algorithm. At the top of the
pit, when there is collisions, some positions may be lost. This is due to the fact
that the present algo, first rotate and then translate. Normally, the algo should
be able to evaluates all possible translation and rotation permutations.

To Lieven: I didn\'t understand what your GetValue() represents. You make floating
point tests on this value ( GetValue(i,j,k)>0.1 or GetValue(i,j,k)>0.5 ) but
i don\'t see what this value means.

I\'m currently working on bug fixes and Linux port. I think a new release should
be available soon.
Lieven
Posts: 55
Joined: Sun Aug 05, 2007 6:31 am

Re:BL2 Bot Player

Post by Lieven »

Great news on the new version! I thought you deserted the project :) I also very much like the practice mode and the keyboard control options, which now look just like the original blockout.

I must admit I was quite disappointed you didn\'t use any of my code; since it took me weeks to optimise.
I ran the current demo 150 times on 3x3x6, and got an average of around 500 blocks. Quite a bit lower then what you wrote, and about half of what my code gets. You average was over how many runs? The parameters might seem strange, but I carefully tuned them based on the averaged results..and the proof of the pudding is in the eating! But hey, I enjoyed playing around with the code and of course in the end, it is your child.

The minmax algorithm applies. The second player is the one giving you the block, and of course the second player ought to give you the worst possible block. In any case, there is no doubt that looking further ahead by whatever algorithm would improve its gameplay!

About the fractions: I am not used at programming in C, and practically only program in Matlab, where 0 is never quite zero. So basically, I have the bad habit of putting >0.1 or >0.5 when I mean >0 or >=1 (since getvalue is an int).

It would be great if the next version would consider all permutations of rotations and translations (at least when the freedepth is low). This would already make a big difference on the average value.

Lieven
Post Reply