BL2 Bot Player

[Lieven]

Hi,

For what it is worth; I have quickly tried to improve the OCC score of my bot. The reason why it played so bad was in the smoothing function. (thanks a lot for the advice on the secret of OCC!)

Changes I have done:

In the smoothing function

pow(......,1)

4 times, instead of pow(......,2) (or just leave out pow altogether)

then the parameters
return -17*thick-500.0f*nbHole1-40.0f*smooth+11*edgel;

give

Avg=8211.4 Min=952 Max=41787 Std=0 nbGame=20 Time=3min 53sec

Testing is slow, so I didn\'t try to optimise.

Lieven

[jlp_38]

Hi,

I don\'t manage to get the average you got with the mods you
propose. Results are even worst than the previous one ????
May something is not clear or i didn\'t understand something ??
Could you post the whole file ?

Anyway, I almost done optimization. I\'m a bit disapointed, I got
a speed up factor of ~3 on Linux but only ~2.3 on windows.
It is better than nothing ;)
I modified a bit your code. It gives exactly the same result
but a bit faster. I simply avoided some floating<->integer
conversions which were not necessary.

I\'ll post the code ASAP on sf ...<br><br>Post edited by: jlp_38, at: 2008/02/07 22:24

[Lieven]

Hi,

in AItester :

int nb = bot->Test(5,5,10,BLOCKSET_EXTENDED,500000);

the botplayer is attached, I didn\'t clean it up, but I don\'t think anything else has changed since i previously submitted. (apart from the mentioned changes)

Lieven

PS: for speed improvment, the abs(pow(x,2)) in my code can simply be replaced with x*x

[file name=BotPlayer-7b07562c678c50fce27dcfd87ca4ca13.txt size=17073]http://www.blockout.net/components/com_ ... a4ca13.txt[/file]<br><br>Post edited by: Lieven, at: 2008/02/07 22:43

[jlp_38]

OK, thanks, In fact my code was correct, it was just a bad
serie.
Here are temporary results:

[319] Cube=10830 Avg=7285.1
[320] Cube=13196 Avg=7303.52
[321] Cube=1955 Avg=7286.91
[322] Cube=5276 Avg=7280.68
[323] Cube=8193 Avg=7283.5
[324] Cube=3482 Avg=7271.8
[325] Cube=647 Avg=7251.48
[326] Cube=2872 Avg=7238.09
[327] Cube=8125 Avg=7240.79
[328] Cube=8547 Avg=7244.76
[329] Cube=3601 Avg=7233.72
[330] Cube=2476 Avg=7219.34
[331] Cube=2840 Avg=7206.15
[332] Cube=12211 Avg=7221.18
[333] Cube=18703 Avg=7255.56
[334] Cube=4068 Avg=7246.04
[335] Cube=10109 Avg=7254.57
[336] Cube=8296 Avg=7257.66
[337] Cube=7981 Avg=7259.8
[338] Cube=18495 Avg=7292.94
[339] Cube=436 Avg=7272.77

Anyway, i committed the modifs to sourceforge. You can get
the new source there. I added 2 files BotMatrix.cpp and
BotMatrix.h.

[jlp_38]

Results for 1000 games:

Avg=7568.92 Min=219 Max=40356 nbGame=1000
115min 40sec, 1090.58 bps

[jlp_38]

I managed to improve a bit the AITester (~15% faster). Now i
think that it will be very difficult to optimize the code by
classic ways.
The only great improvement that can be done is to study the
isometry group of each blocks and create the \"possible
orientations array\" for each one. Today the algo evaluates
always the 24 possible orientations for each block which is
of course not always necessary.
A simple cube requires only 1 (out of 24) evalution.

I have 2 questions for fredjust:

1) Do you know a formula that we can use to calculate the error
range made on an average calculation of a random serie (n terms)
when you know its standard deviation ?
(I don\'t know if such a formula exists)

2) Do you have an idea, of the average number of symmetry
for each block (FLAT,BASIC,EXTENDED) or do you know a way to
calculate it ?
Note: Here we consider only isometry that \"conserve the vectorial
product\" => transform with det=-1 not allowed => 24 symmetry
for a cube.<br><br>Post edited by: jlp_38, at: 2008/02/08 14:39

[jlp_38]

Result of the last code:

3x3x6 BASIC with Lieven\'s eval:
Avg=1054.5 Min=28 Max=5699 nbGame=500
0min 42sec, 12418.2 cps

On a Dual-Core AMD Opteron(tm) Processor 2218

I\'ll post changes on sf.net ASAP...

[jlp_38]

I managed to improve a bit the OOC eval by reintroducing the
\"emergency mode\".
With the following eval:
holeF = -2.0f * freeDepth - 1.0f;
return 0.5f * nbLines + holeF * nbHole1 + 4.5 * commonEdge - 5.0f * flatNess;

The idea is to give less importance to hole when you play
at the top of the pit.

freeDepth=1.0 => empty pit
freeDepth=0.0 => full pit

Here are temp results:

[400] Cube=26495 Avg=15567.2
[401] Cube=8518 Avg=15549.7
[402] Cube=37780 Avg=15604.9
[403] Cube=12420 Avg=15597
[404] Cube=11813 Avg=15587.6
[405] Cube=16624 Avg=15590.2
[406] Cube=73031 Avg=15731.3
[407] Cube=20916 Avg=15744
[408] Cube=26480 Avg=15770.3
[409] Cube=24504 Avg=15791.6
[410] Cube=2454 Avg=15759.1
[411] Cube=6039 Avg=15735.5
[412] Cube=17414 Avg=15739.6
[413] Cube=12985 Avg=15733
[414] Cube=18084 Avg=15738.6
[415] Cube=10903 Avg=15727
[416] Cube=9812 Avg=15712.8
[417] Cube=14148 Avg=15709.1
[418] Cube=8940 Avg=15692.9
[419] Cube=4105 Avg=15665.3
[420] Cube=19867 Avg=15675.3
[421] Cube=15491 Avg=15674.9
[422] Cube=6233 Avg=15652.5
[423] Cube=32043 Avg=15691.2
[424] Cube=33818 Avg=15733.8
[425] Cube=1776 Avg=15701.1
[426] Cube=18082 Avg=15706.7

[Lieven]

Hi, Thanks for the updated source. It runs perfectly. One comment,

I use srand(GetTickCount()+rand()*100);

instead of srand(GetTickCount());

to prevent duplicated short games.

I am working now a bit on the statistics of the problem; I\'ll let you know if I find anything interesting.

[jlp_38]

Avg=15544.2 Min=147 Max=121455 nbGame=1000
127min 42sec, 2028.72 cps

[jlp_38]

I use srand(GetTickCount()+rand()*100);
instead of srand(GetTickCount());


Good ;) , to avoid this problem i use the private BL2 srand()
function which has not the problem but i can\'t post
this code. It is an essential part of the fake score detection
algo.

[Lieven]

1) Do you know a formula that we can use to calculate the error
range made on an average calculation of a random serie (n terms)
when you know its standard deviation ?

Did some quick checking, and I think the distribution of the number of blocks fits some kind of poisson distribution. See post below.<br><br>Post edited by: Lieven, at: 2008/02/09 10:26

[jlp_38]

Thanks for the info. Sounds good :)
I will have a look at that tomorrow...

[fredjust]

> have 2 questions for fredjust:

2) Do you have an idea, of the average number of symmetry
for each block (FLAT,BASIC,EXTENDED) or do you know a way to
calculate it ?
Note: Here we consider only isometry that \"conserve the vectorial
product\" => transform with det=-1 not allowed => 24 symmetry
for a cube.

a part les vérifier toutes pour chaque block et de les stocker
je ne vois pas de méthode globale
c\'est complexe comme problème !
Sur les 41, combien de pièces ont 24 orientations différentes ?

[Lieven]

Ok; I think I have modelled the problem.

For a Poisson distribution, you need to have x number of events in a certain time. For the number of average blocks, one can use for instance the number of restarts necessary to play out 25000 blocks. (This is hypothetical, the game doesn\'t really need to restart-just for modelling purposes). In calculating this afterwards, suppose 15 restarts give 26123 blocks, you need to remember 1123 blocks to add to your next run. For 3x3x6 basic I let it run 20000 times, giving an average of 1067 blocks. Recalculating this as a function of the number of restarts per 25000 blocks gives

restarts count
9 1
10 0
11 0
12 1
13 1
14 11
15 14
16 21
17 36
18 40
19 55
20 48
21 69
22 78
23 64
24 70
25 65
26 73
27 59
28 42
29 27
30 27
31 16
32 13
33 10
34 5
35 1
36 1
37 2
38 1
39 0
40 2
41 0
42 1
Total 854

So 854 restarts or thus an average of 20000/854=23.41 restarts in 25000 blocks (which in case of Poisson distribution should be its mean, and this seems to be the case!)

Now an 68% confidence interval can be calculated using sqrt(total restarts)
after going through the maths we get number blocks is 68% certain in interval [1031,1104].

I included an excel sheet with the details.

Finally the comparison theory/experimental results (using matlab):
cc=23.41
zzz(x)=exp(-cc)*cc^x/GAMMA(x+1)








Reading: http://www.hep.fsu.edu/~harry/Public/Morelia2002-1.ppt
http://en.wikipedia.org/wiki/Poisson_distribution

Post edited by: Lieven, at: 2008/02/09 10:27

Post edited by: Lieven, at: 2008/02/09 23:42<br><br>Post edited by: Lieven, at: 2008/02/09 23:43