Arimaa Forum (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
Arimaa >> Bot Development >> Rabbocop
(Message started by: JackeLee on Oct 13th, 2011, 9:39am)

Title: Rabbocop
Post by JackeLee on Oct 13th, 2011, 9:39am
Hi community,
it is about a month since I finished my bachelor education. In my thesis I tried to compare MCTS and AlphaBeta algorithms both using the same static evaluation function. I measured how the winning ratio changes if we increase time per turn, size of hashtables, number of CPUs, ...

Mostly the tests were performed just to confirm some aspects of algorithms or differences between MCTS and AlphaBeta.

The source code is available online. It is as modular as possible, you could turn on/off almost any optimisation/extension or change the evaluation function.
  • Thesis: http://www.ms.mff.cuni.cz/~jaklt/bc-thesis.pdf
  • Source code: https://github.com/JackeLee/rabbocop (avaliable under OSL 2.1)

If you wish, I could upload game logs somewhere (zipped file has about 50 MB).


I present here another tables which are not included in thesis. In each table is first column number of CPUs, second % win rate of MCTS, third average number of iterations of MCTS algorithm, fourth average depth searched (in steps).

Basic tests with goalCheck:

Code:
1 50.27   4775  7.0
2 43.65   8329  8.1
4 64.95  15488  8.5
8 78.88  21421  8.7


Basic tests without goalCheck:

Code:
1 35.50   4566  6.9
2 45.67   8370  8.3
4 54.65  16161  8.8
8 72.25  22083  8.8


PS: Excuse my low language skills and feel free to correct me anytime.

Title: Re: Rabbocop
Post by Hippo on Oct 13th, 2011, 1:26pm
Thanks for presenting it here :). It's a pitty you will not continue in this research.

Title: Re: Rabbocop
Post by Fritzlein on Oct 13th, 2011, 6:06pm
Thank you JackeLee and Hippo for doing this research and sharing the results with us.  If I understand the point of the table correctly, it is that parallelization is more useful to MCTS bots than to AlphaBeta bots.

Of course it is difficult to make a fair comparison between MCTS and AlphaBeta, because each can benefit greatly from a whole array of features and enhancements.  By putting more effort in to one bot and less into the other, you could "prove" that your favorite approach is superior when run on equal hardware.  But it is possible that whatever the playing field, whether tilted intentionally or unintentionally, it remains true that more CPUs help MCTS more than they help AlphaBeta.

The fact that MCTS was worse than AlphaBeta on one core and better on eight cores is intriguing.  The Arimaa Computer Championship is already on four cores and presumably will be on eight cores in a year or two.  It would be exciting if someone coded an MCTS bot, not for academic research, but as an attempt to win the Arimaa Computer Championship.  For the present, I remain in the class of skeptics who suppose that MCTS only beats AlphaBeta when MCTS has been optimized more, regardless of the number of cores, but life is more fun and interesting when people prove me wrong.  :)

Thanks again for sharing this interesting research.  Have you prompted Omar to include this thesis in his repository of research about Arimaa?

Title: Re: Rabbocop
Post by Hippo on Oct 14th, 2011, 1:42am
Yes, of course this proves only what happened in our implementation. Unfortunately the play of the bot's was too far from optimal so what would happen with higher times and optimized evaluation is a question.

It could mean that paralelisation of alpha-beta was not optimal as another reasoning. But sure, MCTS loves a lot of cores and has easier time management as well.

BTW: How do you like our game rules description?

Title: Re: Rabbocop
Post by rbarreira on Oct 14th, 2011, 2:24am
Nice!

I didn't have time to read the whole thesis yet, but I checked the parallelization section and it seems you are locking accesses the transposition table in the alpha-beta search. Do you lock the whole transposition table or smaller sections containing the accessed part?

If you're locking the whole transposition table that could be a source of slowdown when increasing the number of cores. I saw in Appendix A that getHash and addHash don't take too much time (so my theory could be wrong), but there's no mention of how many cores were used for this profile.

Title: Re: Rabbocop
Post by JackeLee on Oct 14th, 2011, 3:03pm
Thanks for your responses.

The basic set of libraries/representation of board was shared for both algorithms. I tried to optimise bottlenecks of both algorithms as much as possible and made both bots competitive to each other. The tests with optimisations switched on/off should show the main differences between algorithms (or advantages/disadvantages).

Tomas Kozelek achieved a better ratio between the time spent in MCTS tree and the time spent in playouts. Improving the board representation could help MCTS significantly because the most of the time of algorithm is spent in playouts which heavily rely on board representation.

I am locking the whole transposition table and I also believe that the locking is a big deal for my parallel AlphaBeta implementation. The results from case with 8 cores (and maybe 4 cores either) is not so valuable; I believe that the muttexing damaged AlphaBeta a lot.

In Appendix are shown statistics when just one core is used for computation.


on 10/13/11 at 18:06:45, Fritzlein wrote:
Have you prompted Omar to include this thesis in his repository of research about Arimaa?
I hoped writing it here is enough.



Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.