blockout.net

Hi Lieven,

My bot fails at 40.
By hand, after 4 or 5 tries (different start), i found out a solution and played more than 200Cubes (I didn\'t play up to the game over). I even don\'t reach the top of the pit and none of my rotation has been blocked.
Depend a lot on how you start...

Hi,

I\'m currently wondering how to improve the path finding:
Implementing a perfect algorithm, would require a considerable work, will make the code more complex and will slow down statistics computation. The present algorithm can be seen as a tree search. To implement a good path finding, we should implement a graph search including cycle detection,
shortest path finding,...
I think that something that can help and that shouldn\'t be too complex is to implement such a method for translation only. That should already improve a bit playing at the top of the pit.

Tell me what do you think ?

I am not 100% sure I understand what you mean. Here is a naive algorithm (for 3x3) that might work, consider a sequence:

1. do all possible translations
2. do all possible rotations
3. do all possible translations
4. do all possible rotations

In total there are max 3(?) translations and max 12(?) rotations. So we have 9x144=1296 combinations. Obviously, a lot of combinations will be impossible, and others will yield the same result. If this is the case keep the ones with the least moves (trans + rot) and proceed as usual.

This probably will not cover all paths, but should already an improvement and easy to implement. Of course depends how fast this will be. If it is reasonable fast, it can be extended with 5. do all possible translations, etc...

If this is not too much work, could you check if the average is increasing?

(an upper bound is given by the average number of blocks on 3x3x7)

Lieven

Hi Lieven,

There is fact 24 possible rotations, not really rotations, I would rather say \"orientations\". 6 faces * 4 rotations.

The problem, when playing at the top of the pit, is that you may need to rotate once, to translate and to rotate in the other wise to reach the desired position.

This end in a possibly infinite algorithm as cycles are possible. So \"already evaluated positions\" has to be marked.

Of course, this new algorithm should be executed only if the freeDepth is lower than the maxDim of the block otherwise the present algorithm is perfect (if my code is correct ;)).

The method you propose cover more case than the current algorithm but i don\'t know yet the best way to implement this in a comprehensive and simple manner.

Anyway, I\'m still looking for best values of the evaluation function. I managed to improve a bit last result, I will launch a simulation this night.

I let you informed.<br><br>Post edited by: jlp_38, at: 2008/01/17 06:52

Here is the result of the simulation.
3x3x6 BASIC,
Evaluation: nbLinesF * nbLines - nbHoleF * nbHole1 + 3.75 * commonEdge - 6.6 * flatNess



Each point represents 1000 games.

The simulation is still running (going to higher nbLines factor)

Interesting to see that the nbHole factor does not have a strong impact (except for a nbLinesF = 0.1 )

I will do the same for the Lieven\'s evaluation.<br><br>Post edited by: jlp_38, at: 2008/01/17 23:44

Thanks a lot, this will be interesting. I tuned the parameters manually, but the result will be interesting in any case.

After further testing, I don\'t see an easy way to improve my code. The only thing I can really think of, is adding a function that checks if the pit guarantees no holes for the next block. (which would be an alternative of looking ahead)

More results, It seems that it will saturate around 900.
Seems that the optimal nbHole factor is around 0.06.
I\'ve got result for 0.35 and it seems to confirm.
I let the simulation run this night again.



To Lieven:

Adding such a function is equivalent to implement a min-max, isn\'t it ? Or may be you have an other idea for \"next run hole\" checking ?<br><br>Post edited by: jlp_38, at: 2008/01/18 05:57

Yeah, true it is another way of looking ahead. I really believe it will improve results drastically, since this is the way human plays (or at least I play). Sorry to keep on repeating this, but it might eventually convince you to implement it :)

I\'m working at this time a bit more on the new score registration
procedure and the championship mode for the new release. I will definitely add the min-max too. It will recall me the university,
we\'ve had a project topic: write a strategy game. I wrote an awele (or Mancala)
game. I never manage to win my program ;) . But here, a good evaluation is quite simple (seeds difference) and a tree search is sufficient, no path finding).
Concerning stat, my evaluation seems to saturate at ~900 cubes, with an optimum line factor around 0.35. For 3D Mania, I think i will have to modify the commonEdge function to reach 1100 or more ;).
During the week-end, I hope find time to simulate your evaluation.

I restarted to work on the AI :)
I made a chart representing the evolution of the average in
function of number of played game. This shows that to get significant results, the avg must be computed on at least
5000 games. This will not ease the optimization.
Here is some result for the Lieven\'s evaluation in 3x3x6 BASIC:

Avg=1043.18 Min=26 Max=7228 nbGame=5000



I\'m going to make further tests.
I let you informed.

Here is the result of my last simu for the Lieven\'s 3DMania eval.
Interesting to see that the hole and thick factor does not
have a strong impact.
May be the edge and smooth factor can be slightly retuned.






Anyway, I made few tests in OOC, I made only test on 50 games
(OOC tests are very long) but it already gives some trends.

Lieven\'s eval: -27*thick-500.0f*nbHole1-20.0f*smooth+2*edgel; //OUT OF CONTROL
gives:
Avg=2298.02 Min=379 Max=8155 nbGame=50

Eval: 0.5f * nbLines - 3.0f * nbHole1 + 2.0f * commonEdge - 5.0f * flatNess;
gives:
Avg=10525.5 Min=542 Max=44168 nbGame=50

Here it seems that the commonEdge+flatNess is more efficient...<br><br>Post edited by: jlp_38, at: 2008/02/05 19:19

I ran the simulation for OOC over 1000 games and i got the
following results:

Lieven\'s eval: Avg=2569.63 Min=256 Max=14836 nbGame=1000
Jean-Luc\'s eval: Avg=11527.8 Min=310 Max=67263 nbGame=1000



To Lieven:

Do you think the factor of your eval can be omptimized to
reached ~11500 cubes in OOC ?

The parameters of my eval has not been optimized yet. I will
launch a simulation this night. The 1000 games for my eval took
4h30m on an Dual-Core AMD Opteron(tm) Processor 2218 !

Hi Jean-Luc,

Thanks a lot for the testing. I spend over 3 weeks on the 3x3x6 basic; but only 2 minutes on the other ones, so please don\'t post these embarrassing results :). 3x3 is very special since there is only 1 non-edge grid point, and giving a high bonus to dropping on the edge is really the secret to a high average. I don\'t know the secrets for the other modes.

What I am pretty sure of is that we should have at least 6 different sets of parameters/functions depending on the mode:

3 x >=3 x >=6 flat/basic/extended
>=4 x >=4 x >=6 flat/basic/extended

and that should be it. My code is depth independent, but a small depth dependency shouldn\'t be a problem.

I am too busy with work now; but programming good functions for these six types would make for a nice programming contest!


Lieven

OK, I don\'t think that the depth is really important, if
we manage to get a good eval from small depth, it will
work also for higher depth.
I coded my eval as I play. I\'m rather an OOC player ;). So
it seems logic that my eval is better in OOC. The GetCommonEdge
function acts in fact as a puzzle solver, simply by counting
the number of common edge (faces) between the block and the filled
pit. If the GetCommonEdge gives 1, It means that the \"puzzle piece\"
perfectly matches. I think that this is essential in OOC.
If i find time, i will try to optimize your eval for OOC
and see what it gives.
Concerning 3x3xX pit, I must say i didn\'t make much test. I will
do this. I know that my original eval is quite bad in 3x3xX
EXTENDED.
I totally agree that programming such functions would make a
great programming contest, unfortunately, not much people seem
interested in. That\'s too bad.

I managed to improve a bit the avg in OOC.
It has even play 1 game with more than 100000 cubes.

Avg=13913.5 Min=220 Max=100005 nbGame=1000

The simulation is not yet ended...

Anyway, I also optimized the AI player, no it plays ~3 times
faster. I still have to optimize the matricial calculus.
When I end the speed optimization, I\'ll post the code.