Author |
Topic: Rabbocop (Read 2177 times) |
|
JackeLee
Forum Newbie
Arimaa player #5130
Gender: 
Posts: 2
|
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.
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.
|
|
 IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
 |
Re: Rabbocop
« Reply #1 on: Oct 13th, 2011, 1:26pm » |
 Quote  Modify
|
Thanks for presenting it here  . It's a pitty you will not continue in this research.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Rabbocop
« Reply #2 on: Oct 13th, 2011, 6:06pm » |
Quote Modify
|
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?
|
| « Last Edit: Oct 13th, 2011, 6:08pm by Fritzlein » |
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Rabbocop
« Reply #3 on: Oct 14th, 2011, 1:42am » |
Quote Modify
|
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?
|
| « Last Edit: Oct 14th, 2011, 1:51am by Hippo » |
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Rabbocop
« Reply #4 on: Oct 14th, 2011, 2:24am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
JackeLee
Forum Newbie
Arimaa player #5130
Gender:
Posts: 2
|
|
Re: Rabbocop
« Reply #5 on: Oct 14th, 2011, 3:03pm » |
Quote Modify
|
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 Oct 13th, 2011, 6:06pm, Fritzlein wrote:| Have you prompted Omar to include this thesis in his repository of research about Arimaa? |
|
I hoped writing it here is enough.
|
| « Last Edit: Oct 14th, 2011, 3:10pm by JackeLee » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print