BL2 Bot Player

[jlp_38]

Hi Lieven,

I\'m sorry to not having integrate any part of your code in the present release but i would like to understand better your method first. I know that the present AI is far from perfect. As you may noticed, the AI is quite bad in 3x3xY EXTENDED.
Concerning test in 3x3x6 BASIC i made only few tenth of test (around 50). The present evaluation function is the best one i found for all mode.
I will learn and check your method more in depth.

I will see later to integrate a min-max algo. As i
said, I\'m not sure it will help a lot for a \"single
line strategy\" AI but it\'s clear that it can be
good for multi-line strategy.

An other point would be to not only take into consideration the average of played block but also the standard deviation which should give us an information on the \"regularity\" of the AI.

I let you informed...

[jlp_38]

Re,

I made more tests and I saw that the high average value I\'ve got is linked to the random generator. The public source code of the game use a classic uniform generator (rand function) and the provided binary use a bag generator (more information about this in the README file) this code is not public (for fake score detection) and it has strong impact on the avg value. I\'ve got (in 3x3x6 BASIC) ~550 cubes with the uniform generator and ~900 with the bag generator. I\'m a bit surprised by this big difference.

To Lieven:
I\'m going to try your code with both generator and make more statitics...

A question
Did you use this expression for your stats in
3x3x6 BASIC ?

Code: Select all

return -27*thick-75.0f*nbHole1-3.0f*smooth+17.0f*edgel; //3DMANIA

[Lieven]

Yep that is the one. I am very curious to hear how much you get on average with the new random generator and my code.

[jlp_38]

I\'ve got an average of ~2000 cubes for the bag generator with your evaluation function and i\'ve got also around 1100 with the uniform gene.
Now I understand better your method and i must say that I learned something. At least in 3D Mania, it is good when you have to make a hole to try to make it at the center of the pit. You have more chance to uncover it. I think this is done in the Lieven\'s Edge() function function that prefer to place block on the side.

Great idea ! Seems to be very efficient B)

I won\'t be at home tomorrow,I will continue testing on Sunday.

Good w.e.

[fredjust]

Re,
I\'ve got (in 3x3x6 BASIC) ~550 cubes with the uniform generator and ~900 with the bag generator. I\'m a bit surprised by this big difference.

So, the bag generator is not enough random ;)

je n\'ai pas compris l\'intérêt de se générateur de hasard, avec lui en 3D mania je suis sur et CERTAIN d\'avoir 2 L toutes les 16 pieces

cela permet de prendre plus de risque

[Lieven]

Hi, Thanks for reporting back results.

I am not sure what you mean with making a hole in the centre. My code is not very clear, now that I reread it. So I quickly explain:

1. Thickness=number of blocks. So this function accounts for a bonus when making complete lines/layers.

2. Getnbholes= number of holes

3. Edges. Ok so my code started doing really well after I increased the weight of this function. In 3D mania, it is essential to fill up first the corners and then the edges and leave the middle position open as long as possible. \"If you have to go high, go high on the edges\". Put in other words: when the middle position is higher than the rest, there is a high chance you have to create holes next turn.

4. Smoothness: not nearly as important as I thought it would be (at least in 3x3x6). I think this function can probably be replaced with your smoothness function (getcommonedge); weight will have to be re-tuned though.
I wrote an own smoothness function simply because I didn\'t understand yours.
My smoothness basically counts the difference (squared) in depth of every block with its neighbours. It also awards a bonus for having only \"green\" blocks. Without this bonus it puts all L-shaped pieces vertical due to the edge function.

[jlp_38]

Hi,

I\'m finally at home today, the weather isn\'t good enough :( to ski. Will go tomorrow, weather should be excelent :) and with lot of powder snow :)

Anyway, I updated the source to implement a good AI tester, i will upload changes to sf soon. It plays around 100 games per minute in 3x3x6 (with Lieven\'s evaluation function) on my old P4 1.7Ghz. It should help to improve the stuff.

Some quick results:
(Test done with uniform generator)
3x3x6 BASIC
Avg=1173.84 Min=44 Max=8938 Std=1714.59 nbGame=500 Time=5min 10sec

3D Mania:

P[ 0] = 18279 cubes
P[ 1] = 42484 cubes
P[ 2] = >50003 cubes
P[ 3] = >50004 cubes
P[ 4] = >50001 cubes
Time=2min 44sec

To fredtust:

I\'m don\'t know if we can say that the bag generator is less random (it is also uniform), in fact with a bag generator it seems that you avoid half of fatal sequence (at least in 3x3x6 BASIC).
I think it makes the game a bit more attractive as the building (making multiple line) is favorised.<br><br>Post edited by: jlp_38, at: 2008/01/12 21:42

[jlp_38]

Re,

I updloaded change to source forge.

AI tester compilation (Only Win 32):
-Open the project (provided for VC7 only but it should
be easy to convert it to VC8).
-Update the path of image lib.
-Go to the configuration manager and select AITester.

Don\'t select the 2 projects at the same time.

When you want to switch beetween the projects AI tester and Blockout
to see how your AI works, you have to do the following:
-Select Default project:

-Important: Rebuild solution (not build as the 2 projects share files)

If you want to do some debugging, you can select the Debug configuration, but performance will be lower.


The file AITester.cpp is the main entry point of the AITester and should be easy to adapt.

[Lieven]

This is great, and definitely allows for faster optimisation. However, two questions. I get series like this:

P[423] = 28
P[424] = 28
P[425] = 28
P[426] = 28

The same for other low numbers: they are all repeated at least twice. Any idea what is causing this? In any case, it is lowering the average considerably!

It is very fast:

Avg=1065.69 Min=28 Max=7064 Std=0 nbGame=500 Time=1min 25sec

I\'ll let you know if I make any progress<br><br>Post edited by: Lieven, at: 2008/01/13 01:42

[jlp_38]

The series you get is i think due to the random seed. The seed is fixed by GetTickCount() (which has a resolution of ~10ms) so if a game take less than 10ms you may get the same seed. A work around could be to sleep a bit when a game take less than 10ms.

Hope this helps.
I will go on testing your AI.
I let you informed.

PS: The GetTickCount() call is located at BotPlayer.cpp:648<br><br>Post edited by: jlp_38, at: 2008/01/14 01:40

[jlp_38]

An other point:
When you get a \"bad game\" it could be interesting to try to play this game by hand (just to see if the human can do better) so it can be useful to print the seed for each game.
You can then try the seed in Practice mode by making the following patch.
Game.cpp:472

Replace
srand(GetTickCount());
by
srand(yourSeed);

[jlp_38]

Some suggestions:

I\'m trying to optimize my evaluation function, i choosed a strategy a bit different than the Lieven\'s one.
My evaluation is still not optimum, and does not beat Lieven function yet but the match goes on ;)

I added a GetFlatness() function which computes the standard deviation of the pit surface.

Code: Select all

int BotPlayer::GetDepthAt(int x,int y) {

  BOOL columnEmpty = TRUE;
  int f=0;
  for(int k=0;k<depth && columnEmpty;k++) {
    columnEmpty = GetValue(x,y,k)!=0;
		if(columnEmpty) f++;
  }
  return f;

}

float BotPlayer::GetFlatness() {

  int sum = 0;
  int sumSquare = 0;
  int num = width*height;

  for(int i=0;i<width;i++) {
    for(int j=0;j<height;j++) {
      int d = GetDepthAt(i,j);
      sum += d;
      sumSquare += d*d;
    }
  }

  return 1.0f / (float)num * sqrtf((float)num*(float)sumSquare - (float)(sum*sum) );

}

And the following evaluation:

Code: Select all

  return 0.5f * nbLines - 0.1f * addedHole + 3.75f * commonEdge - 6.6f * flatNess;

Gives in 3x3x6 BASIC:

Avg=822.47 Min=28 Max=5092 Std=1117.39 nbGame=500

The nbLines and addedHole factor are not yet been optimized.(My algo takes long time to find out best values)
The GetFlatness() acts a bit as the Smoothness() lieven\'s function.
The GetCommonEdge() acts a bit as the Edge()+Smoothness()
Lieven\'s functions.<br><br>Post edited by: jlp_38, at: 2008/01/15 04:47

[Lieven]

Thanks for the tricks with srand(yourSeed);
two hards ones are

7774441

and

10135710

The first one is solved if the bot would consider all permutations of rotations and translations.

The second one is tricky. You really have to play it to see. But looking further ahead would definitely take care of that one.

Good luck with the race :) It is actually quite fun. I am convinced though we need at least 3 functions, one for every mode (flat, basic, extended). Like my bot cant even play unlimited in 3x3x6 flat!

[jlp_38]

Hi Lieven,

The seed 10135710 failed at how many cubes ?

[Lieven]

The two codes I gave fail on <32 if I remember well