Author |
Topic: bot_akimot update (Read 4097 times) |
|
sleepywind
Forum Junior Member
Arimaa player #3476
Gender: 
Posts: 10
|
 |
bot_akimot update
« on: Feb 2nd, 2009, 2:13am » |
 Quote  Modify
|
Hi all,
I am the author of bot_akimot which recently showed up on the bot rating list ...
I have started working on akimot in 09/2008 from scratch as a subject of my master thesis. This thread is meant as an update on what akimot is capable of.
Akimot
*is developed in C++ under Unix environment
* is a UCT-based bot with static evaluation.
Classical UCT tree is build up in the progress of the search, while to-the-end-of-the-game Monte Carlo simulations are replaced by fixed-length simulations followed by static evaluation. Search is step-based with simple transposition table for the UCT tree. Program runs in multiple threads - speedup is +- 1.6 in 2 threads so far. There is a simple 1-ply goal check extension done by narrowed exhaustive search.
* uses bitboard representation
Originally integer-board representation was used, but like a month ago I refactored it to use the bitboards - not like it is much faster, but the code is more elegant and in the time of 64-bit processors it is difficult to resist temptation for almost free speedup.
* uses aei interface
Getmove is implemented as well (mostly for testing against other source open bots), but for connection to the gameroom only aei is used.
* is capable of (hopefully) correct play
I haven't performed much testing so far ( basically just series of one-to-one bot matches with sample_c bot and very little bot-human games), but all rules of arimaa should be handled correctly.
Highest on todo list right now:
* static evaluation function
I don't aim for powerfull, fancy evaluation functions strong bots around are having, but something better than material sum up used now would be good. Originally I intended to let the constants in evaluation function get automatically tuned by something like SA (I have already downloaded and parsed games archive to particular positions for that purpose), but after reading about negative experiences on this forum I guess I will stick with hand tuning for now.
* knowledge to guide playouts/uct tree
Hooks for these are already done, it's the knowledge that needs to be filled. Actually in previous version of board representation I had the knowledge here as well and it showed positively in the program performance.
* simple trap search extension
I plan to apply search extensions in the uct tree right now, thus they don't have to be superb speedy.
*find a reasonable server (64-bit 2 cores) to run the bot in the gameroom for longer time ( my laptop is just too old for that  )
Performance
Initial testing was done with previous version of akimot using the integer board representation (I used adapted Fairy evaluation function + simple knowledge in playouts/tree)
* performance scales well
Not a surprise - more time makes program stronger ( 25s/move akimot defeated 5s/move akimot in more than 75% cases ).
* akimot is still very weak
Biggest success so far is 20% winning rate against sample_c bot with 2-ply search (akimot was in 5s/move) , which is rather pathetic I know .
Small overview:
So far I have worked on the bot "parttime" (1. work, 2. school, 3. akimot ) - with like end of march this will change (1. akimot 2. akimot 3. akimot).
I expect most of the coding work to be finished ( board implementation, rules + testing, search startup, protocol implementation, ... ). Ahead is knowledge input, debugging, tweaking, testing, etc. Right now there is about 10000 loc given by wc -l (around 6000 effective I guess).
Goal
I am supposed to deliver my master thesis till end of July. I hope to achieve > 1800 with akimot till then.
|
| « Last Edit: Feb 2nd, 2009, 2:14am by sleepywind » |
 IP Logged |
|
|
|
arimaa_master
Forum Guru
Arimaa player #2010
Gender:
Posts: 358
|
|
Re: bot_akimot update
« Reply #1 on: Feb 2nd, 2009, 5:07am » |
Quote Modify
|
Nice,
good luck with your bot (you will definitely need some - 1800 rating to achieve in less then 6 months will be quite an achievement I guess).
|
|
IP Logged |
|
|
|
tize
Forum Guru
Arimaa player #3121
Gender:
Posts: 118
|
|
Re: bot_akimot update
« Reply #2 on: Feb 2nd, 2009, 8:55am » |
Quote Modify
|
This sounds like what I'm planing for my bot_carlos, good luck with akimot.
Hopefully it will prove to be, at least, as good as alpha-beta pruned minimax.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: bot_akimot update
« Reply #3 on: Feb 5th, 2009, 9:56pm » |
Quote Modify
|
Hi sleepywind,
Thanks for giving us some information about your bot. It is always interesting to see what new ideas are being tried out. Best of luck with Akimot. Hope you will enter it into the bot tournament next year. BTW what university are you in?
|
|
IP Logged |
|
|
|
sleepywind
Forum Junior Member
Arimaa player #3476
Gender:
Posts: 10
|
|
Re: bot_akimot update
« Reply #4 on: Feb 6th, 2009, 6:51am » |
Quote Modify
|
Thank you. Yes, next year I would like to enter the bot tournament. I study at Charles University at Prague/Czech Republic, my master programme is Artificial Intelligence.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: bot_akimot update
« Reply #5 on: Feb 14th, 2009, 10:09pm » |
Quote Modify
|
It will be interesting to see if an Arimaa bot using UCT will be competitive with some of the other top bots. UCT has been somewhat of a break through for Go programs, but I think jdb's attempts to use it with bot_clueless did not go well. Karl mentioned to me that in Arimaa random play would tend to encourage advancing rabbits without support; generally a bad thing. Some enhanced to UCT would probably be required to apply it to Arimaa.
|
| « Last Edit: Feb 17th, 2009, 5:51pm by omar » |
IP Logged |
|
|
|
sleepywind
Forum Junior Member
Arimaa player #3476
Gender:
Posts: 10
|
|
Re: bot_akimot update
« Reply #6 on: Feb 16th, 2009, 2:46am » |
Quote Modify
|
Actually, main motivation for me to start a work on a UCT-based arimaa program was to try out sucessful approaches in computer go (UCT) in a fundamentally different board game. I can only confirm what was previously written couple of times in this forum, that to-the-end-of-the-game playouts just don't work in arimaa becouse of overrated rabbit values. But in my opinion combination of (a) UCT tree + (b) short playout + (c) static evaluation might provide a good base for reasonably playing program. This way, in theory, bot could benefit from : more human-like approach of move selection (=a) than in alpha-beta, ability of potential further lookahead (=b playouts right now are set to length of 3 moves) + reasonable evaluation of positions based on piece values, trap evaluations, etc. (=c). Tactical weakness (compared to alpha beta bots) will be an issue though ...
|
|
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: bot_akimot update
« Reply #7 on: May 2nd, 2009, 9:30am » |
Quote Modify
|
May I kindly ask whether you have any new information about Akimot for us? Thanks.
|
|
IP Logged |
|
|
|
sleepywind
Forum Junior Member
Arimaa player #3476
Gender:
Posts: 10
|
|
Re: bot_akimot update
« Reply #8 on: May 20th, 2009, 1:00am » |
Quote Modify
|
Sorry for such a late reply. I was away for a while ...
So here is what is new:
- I made some progress in akimot's performance. Now he is able to win over 95% of games against 2-ply sample C bot and 50% of games against 3s/move fairy. However (!) in both cases akimot gets a time handicap of 10s/move.
- I guess I have to reevaluate my goals. To achieve 1800 till the end of the summer is probably not realistic
 I have stated a new goal - to match the fairy bot without the time handicap .
- I tried out the UCT-RAVE algorithm which ended up as a failure (somehow I wasn't surprised). The reason is I believe the little information gained from the RAVE playouts ... while the playouts are not that long (3-4 half moves) and are pressured to be quite local there are quite little moves adding RAVE infomation.
- Quite a (relative) success was adding a history heuristic. The implementation is trivial - I update statistics on all the steps throughout the tree and use these as a part of exploration formula in UCT descend.
- Dropping FPU and using virtual games instead (node is initialised with d games and 0 value) also made a nice improvement.
- I believe the biggest potential for further improvement is in better (yet somehow random) playouts. So far I have just couple of hardcoded weights (step killing a piece is good, step with an elephant is good, step with rabbit in the end of the game is good, push/pulls are good) and when a step is supposed to be played in the playout I randomly choose a few steps and play the one with the highest weight.
- Also I noted that the weakness of the program is not that it cannot find the good moves (or rather reasonable moves), but it blunders often. In a situation where there is no clear candidate it might play a blunder because the simulations get spread too wide in the tree and the final move doesn't get that much attention to reveal potential problems deeper in the tree. So it might easily happen that in relatively calm situation the program plays a move and loses a piece the very next move.
- I fixed the threaded version so the playouts speedup is approximately linear, but it's strength is not up to the expectation (maybe still some bug in there ... ). I am using the "root" model - all threads run separately in their UCT trees and in the end the trees are merged and final move is selected - this was reported to work well up to 16 threads in some paper on computer go I read.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: bot_akimot update
« Reply #9 on: May 20th, 2009, 1:34am » |
Quote Modify
|
on May 20th, 2009, 1:00am, sleepywind wrote:
I fixed the threaded version so the playouts speedup is approximately linear, but it's strength is not up to the expectation (maybe still some bug in there ... ). I am using the "root" model - all threads run separately in their UCT trees and in the end the trees are merged and final move is selected - this was reported to work well up to 16 threads in some paper on computer go I read.
|
|
This doesn't feel right to me. All threads should work together to build a single tree. This allows much more information sharing between the threads.
|
|
IP Logged |
|
|
|
sleepywind
Forum Junior Member
Arimaa player #3476
Gender:
Posts: 10
|
|
Re: bot_akimot update
« Reply #10 on: May 20th, 2009, 3:30am » |
Quote Modify
|
That's my first feeling as well. The reason why I decided to implement the mentioned model is it's very positive evaluation in this paper http://www.cs.unimaas.nl/g.chaslot/papers/parallelMCTS.pdf and also it's simplicity compared to other models.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: bot_akimot update
« Reply #11 on: May 20th, 2009, 5:42am » |
Quote Modify
|
I just read the paper you indicated. Their results do look good for the root parallel method. It still does not make sense to me, so I'll think about it some more.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: bot_akimot update
« Reply #12 on: May 27th, 2009, 6:42pm » |
Quote Modify
|
on May 20th, 2009, 1:00am, sleepywind wrote:| Also I noted that the weakness of the program is not that it cannot find the good moves (or rather reasonable moves), but it blunders often. In a situation where there is no clear candidate it might play a blunder because the simulations get spread too wide in the tree and the final move doesn't get that much attention to reveal potential problems deeper in the tree. So it might easily happen that in relatively calm situation the program plays a move and loses a piece the very next move. |
|
I am curious about this point. If a bot can find a good move for itself, then why can't it find a good move for the opponent too? A blunder which loses a piece on the very next move should get refuted quickly and fall out of favor, right? Unless the tree doesn't get deep enough to see the refutation move, but I thought that UCT actually would build a deeper tree than vanilla alpha-beta by being more selective.
Hannoskaj has expressed great optimism about what Monte Carlo methods will be able to do, which makes me eager to understand why randomized methods haven't been able to catch up to full-width searching so far.
|
|
IP Logged |
|
|
|
sleepywind
Forum Junior Member
Arimaa player #3476
Gender:
Posts: 10
|
|
Re: bot_akimot update
« Reply #13 on: May 28th, 2009, 1:26am » |
Quote Modify
|
Quote:| I am curious about this point. If a bot can find a good move for itself, then why can't it find a good move for the opponent too? A blunder which loses a piece on the very next move should get refuted quickly and fall out of favor, right? |
|
If the position is "calm" then a lot of moves (the tree is step-based so I mean sequences of steps here) would get a similar evaluation by UCT (the granularity is not as fine as in alpha beta). This I believe prevents selectivity and results in rather shallow wide tree. Of course that a stupid blunder gets refuted quite quickly, however if there are a lot of possible blunders it might very well happen that the time runs out during exploration of one of them. The problem then is the low confidence (number of visits) of the node representing the final move. With approx. 70000pps and 5s/move, final move with less than 5000 visits (which happens in a "calm" position) is not explored enough.
Another (maybe critical) factor is that I was doing most of the tests with fairly short time settings (3s/move or 5s/move). Well, I put up the bot online for some time now with 15s/move so we shall see
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: bot_akimot update
« Reply #14 on: Jul 31st, 2009, 5:11pm » |
Quote Modify
|
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.
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.
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.
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?
|
| « Last Edit: Jul 31st, 2009, 5:12pm by Fritzlein » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print