Author |
Topic: bot_akimot update (Read 4106 times) |
|
sleepywind
Forum Junior Member
Arimaa player #3476
Gender: 
Posts: 10
|
 |
Re: bot_akimot update
« Reply #15 on: Aug 1st, 2009, 12:39am » |
 Quote  Modify
|
Hello,
first of alll, thank you for encouragement 
Quote:
Sleepywind, thank you for putting up akimot for public play. It looks like you are only a little short of your goal of 1800 strength (at blitz speed) by the end of July.
|
|
It's difficult for me to estimate the strenght of the engine, as I myself am not very experienced in the game, but I think it's real strength is far below the 1800 (maybe around 1600?).
Quote:
I must say that akimot plays more strangely than any bot except Rat. It is fun to have some extra variety in addition to the range of styles that already exists in the bot ladder.
|
|
Well I am afraid the engine is quite weak in tactics (not that it's any stronger in strategy) and quite often it just "doesn't know" what is it doing.
Quote:
I am curious why akimot is so prone to single-step moves. To say that there are no clear objectives in the position is not enough explanation. A random mover with no objective whatsoever will almost always play a four-step move simply because the four-step moves are most numerous. Therefore akimot must have something biasing it towards single-step moves.
|
|
The reason for this could be following: the UCT tree is step-based and I am treating pass as any other step (except for demotivation to play it in node's initialization). Now comes the catch - in the end of the search when a move to play is to be outputted, I take all the legal moves and select the one with most visits. If the position is rather "calm" then the move with pass on the second level (step1-pass) can get more visits then all the moves on the fourth level (step1-step2-step3-step4) even though their 'shorter version' (step1-step2) outnumbers the passing move by a lot. Solution to this might be different approach to selecting a final move (something like start in the root, take step with most visits and descend until it's not opponent's turn).
For past month and a half I've been writing the thesis and doing some offline performance tests against anchor bots (mostly bot fairy). There was very little progress in the code in this period... I am handing my theses this week and here is what I would like to do (hopefully sometimes in the very near future):
1) provide the thesis for public download (no big discoveries there - summary of MCTS methods, how we applied them in the Arimaa environment, some of our improvements and performance analysis)
2) release the akimot code (GPL?) - if someone is toying around with idea of writing a MCTS arimaa bot this could be a good starting point for him. There is not much documentation though (except for short comments on methods in header files), tragically little unit tests and probably a lot of bugs . On the other hand it should be a use-out-of-the-box bot with reasonable configuration options and hopefully managable code.
3) i have written couple of small apps during the course of work on the project, for instance: simple game replaying GUI, simple positions testing framework. These are written in python and are using excellent AEI module (thanks Janzert). I will "polish" these a bit and provide them for Arimaa developers as well, if there will be interest ...
Quote:
Again, thank you for the public service of offering your bot in the game room.
P.S. If you are supposed to give your thesis at the end of July, does that mean development on akimot stops tomorrow?
|
|
No, the development of akimot doesn't stop here. Even though the overall performance of akimot (coming from my programming inaptitude or impropriety of the MCTS approach or both) was a bit disappointing to me. I learned a lot during its development and I still have some ideas ...
|
|
 IP Logged |
|
|
|
sleepywind
Forum Junior Member
Arimaa player #3476
Gender:
Posts: 10
|
|
Re: bot_akimot update
« Reply #16 on: Dec 6th, 2009, 3:25am » |
Quote Modify
|
Hi everyone,
unfortunately I have been quite busy with work lately and it seems to hold for (near) future as well. Therefore I am not spending much time (hardly any  ) on akimot's development. On the other hand I have finally forced myself to fulfill my promise and provide the resources behind akimot to the community. So here we go:
My masters thesis about akimot can be downloaded at http://kozelek.cz/akimot/mt.pdf, short presentation is at http://kozelek.cz/akimot/mtp.pdf. I have also created an online source code repository for the project at GitHub:http://github.com/tomik/akimot. This repository is a full copy of my development repository for akimot. User manual (http://kozelek.cz/akimot/doc/usr/usr_doc.pdf) gives basic information about the project, it's layout and it's support applications (i.e. the testing suite, the gui, etc.). Programming manual(http://kozelek.cz/akimot/doc/prg), on the other hand, gives brief overview over main classes and their interaction (this manual can be generated with doxygen from the source code). Majority of code is my own except from excellent AEI library by Janzert, perl match scripts by Omar and pieces of C/C++ code from other open source engines. The project is released under GNU GPL, but if the license is too restrictive for someone, let me know and we can talk about that
I guess the project could be useful mainly for beginning Arimaa programmers, but maybe the "experienced guys" can find some ideas as well. I welcome any questions/comments regarding the project. I hope to keep the development alive, but probably in a very slow pace. I think that this way the project is way more useful.
|
| « Last Edit: Dec 6th, 2009, 3:26am by sleepywind » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: bot_akimot update
« Reply #17 on: Dec 6th, 2009, 12:05pm » |
Quote Modify
|
It is very good of you to donate to the community, sleepywind, especially since your bot is a completely different approach. Developers who are interested in getting started with UCT rather than alpha-beta search now have a nice resource.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: bot_akimot update
« Reply #18 on: Dec 6th, 2009, 1:25pm » |
Quote Modify
|
I have now read your thesis. I think it must be an even more valuable contribution than your code, in part because the code would be very difficult to understand without the thesis, but also because many people with no use for the code will be able to benefit from your clear exposition of your motivations and results. It was a good read for me even though I have never developed a bot and probably never will.
I had done some minimal reading about Monte Carlo Tree Search, but now I better understand how unsettled the field is, and how much room remains for optimizing the basic premise. If I had been tuned in to the research all along, I would not have been perpetually expecting David Fotland to return to Arimaa programming. MCTS was not just a one-time surprise that Fotland had to catch up to, it has been an ongoing field for exploration with rich payoffs for optimizers. I will not hope for Fotland to revisit Arimaa until progress in MCTS Go has plateaued.
One nugget of information in your results that quite surprises me is the extreme benefit bot_akimot derived from time doubling. From your graph I infer that it gained about 130 Elo points of playing strength per doubling. This is twice what clueless gained in my one experiment. Also it is apparently more than bot_fairy was gaining per doubling. If the trend continues, then one would expect developers to eventually be forced away from alpha-beta to MCTS when the hardware gets fast enough.
One question which I am extremely curious to have answered was unfortunately not one of your research goals. You seemed focused on comparing MCTS in Go to MCTS in Arimaa. I would be very interested also in comparing MCTS in Arimaa to alpha-beta in Arimaa.
In particular, the strength of bot_akimot is apparently very dependent on the strength of its hand-coded evaluation. Was bot_akimot unable to equal bot_fairy due to fairy's superior evaluation, or due to the the superiority of full-width search over random search? You could have pitted bot_akimot against an alpha-beta searcher with akimot's evaluation and 4-step goal and capture detection. If the alpha-beta searcher did better, then it would seem that MCTS is a handicap rather than a benefit for Arimaa.
To put it another way, my question is whether random playouts must give reasonable evaluations for MCTS to be a valuable technique. When you limit the playouts and introduce static evaluation, have you inherently destroyed the reason to use MCTS? Perhaps you know the answer to this already from reading about MCTS for Lines of Action, Amazons, and Hex.
Thank you again for your interesting research and lucid presentation.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: bot_akimot update
« Reply #19 on: Dec 6th, 2009, 1:30pm » |
Quote Modify
|
on Feb 6th, 2009, 6:51am, sleepywind wrote:| Yes, next year I would like to enter the bot tournament. |
|
Are you still planning to enter the 2010 Computer Championship? I hope so, although the new qualifying procedures increase the work that is required to do so.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: bot_akimot update
« Reply #20 on: Dec 7th, 2009, 12:30am » |
Quote Modify
|
Wow, great Thesis Tomas; very interesting. Thanks for making your bot available for others. It will be a great example for others wanting to try the MCTS approach.
I have added it to the 'Academic Papers' page:
http://arimaa.com/arimaa/papers/
and also to the 'Downloads' page:
http://arimaa.com/arimaa/download/
|
| « Last Edit: Dec 7th, 2009, 12:32am by omar » |
IP Logged |
|
|
|
sleepywind
Forum Junior Member
Arimaa player #3476
Gender:
Posts: 10
|
|
Re: bot_akimot update
« Reply #21 on: Dec 10th, 2009, 6:24am » |
Quote Modify
|
Quote:
One question which I am extremely curious to have answered was unfortunately not one of your research goals. You seemed focused on comparing MCTS in Go to MCTS in Arimaa. I would be very interested also in comparing MCTS in Arimaa to alpha-beta in Arimaa.
In particular, the strength of bot_akimot is apparently very dependent on the strength of its hand-coded evaluation. Was bot_akimot unable to equal bot_fairy due to fairy's superior evaluation, or due to the the superiority of full-width search over random search? You could have pitted bot_akimot against an alpha-beta searcher with akimot's evaluation and 4-step goal and capture detection. If the alpha-beta searcher did better, then it would seem that MCTS is a handicap rather than a benefit for Arimaa. |
|
This is a good point and I probably should have invested more effort in comparing MCTS and alpha-beta approaches. On the other hand experiments against bot_fairy reveal some information. If you check the "Scalability test" you can see that on reasonable time conditions (16s) akimot is almost equal to bot_fairy (over 45% winning rate). Moreover the graph suggests that akimot's winning ratio might have rising tendency for longer times. This variant of bot_fairy has "full" evaluation which, as you said, is superior to the akimot's one (I haven't invested much effort into a good evaluation function). The fact that akimot can match alpha-beta engine with superior evaluation is encouraging for MCTS approach.
Moreover I suspect a lot of potential improvements in the akimot's approach - most of these are described in "future work" section. Just a small example: after I handed my thesis I made a small experiment and I have implemented a "relative evaluation of the position" (position value is taken with respect to value in the root node) - this took around 5 lines of code to be changed and the performance of bot improved significantly (over 90% winning against bot_fairy_3s on 16s/move instead of previous 75%).
But one think is quite clear to me now. MCTS doesn't feel that "right" (or natural if you want) for Arimaa as it does for Go. A lot of factors contribute to this: longer playouts are inaccurate, 4 steps in a move make complications, repetitions are way more difficult to handle, etc.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: bot_akimot update
« Reply #22 on: Dec 10th, 2009, 10:13am » |
Quote Modify
|
Thanks for the additional observations. Clearly the last word on MCTS versus alpha-beta tree search has not been written. It is fun to track the experiments in such an interesting discipline.
From a couple of Google searches, it appears that the level of the best bots in Hex was raised by MCTS, but not in Lines of Action or Amazons, at least not yet. The (champion) MCTS Hex program uses playouts to game end for evaluation, though, which does nothing to help answer the question of how useful MCTS can be when evaluations must be imposed before game end.
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: bot_akimot update
« Reply #23 on: Feb 1st, 2010, 1:50pm » |
Quote Modify
|
It would be interesting experiment to let play two bots with the same evaluation function, but one of them alpha-beta and the other MCTS (of course it is not so easy as the move generators algorithms must differ a lot).
I still think the MCTS will dominate in such game.
The important thing would be in the time planning strategy.
Actually it may be valuable even for MCTS to build time reserve in "easy" situations and go to reserve in the more difficult ones, but stopping in given time is much easier in MCTS than in alpha-beta where it's must to decide at which level of search to stop.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: bot_akimot update
« Reply #24 on: Feb 1st, 2010, 3:41pm » |
Quote Modify
|
on Feb 1st, 2010, 1:50pm, Hippo wrote:| It would be interesting experiment to let play two bots with the same evaluation function, but one of them alpha-beta and the other MCTS (of course it is not so easy as the move generators algorithms must differ a lot). |
|
So, can you use your academic authority to mandate this experiment? BlackKnight is forcing his entire AI class to write alpha-beta searchers, so there is a precedent...
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: bot_akimot update
« Reply #25 on: Feb 3rd, 2010, 12:54am » |
Quote Modify
|
I will certainly try, but we should wait for such thesis to be written.
We can wait 1 or 2 years for results .
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: bot_akimot update
« Reply #26 on: Feb 3rd, 2010, 5:26pm » |
Quote Modify
|
on Feb 1st, 2010, 1:50pm, Hippo wrote:| It would be interesting experiment to let play two bots with the same evaluation function, but one of them alpha-beta and the other MCTS (of course it is not so easy as the move generators algorithms must differ a lot). |
|
Hmm, I expect that an eval developed with one search type and then used in another search type will play worse than an eval developed under the search type it is used with. Whichever direction that development then use transfer was to take place in.
My belief on this arises from the poor experiences of people trying to take chess evals developed with PVS search and use them with MTD-f. Even this relatively minor change in search behavior seems to really require somewhat different evaluation behavior (for instance MTD-f seems to like a larger score granularity). I would expect the change from MCTS to alpha-beta to be even greater.
Janzert
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print