Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> New paper and thesis on Arimaa
        
(Message started by: omar on Oct 29^th, 2009, 2:57pm)

Title: New paper and thesis on Arimaa
Post by omar on Oct 29^th, 2009, 2:57pm

Please check the 'Academic Papers and Presentations' section of the site for two new postings:

http://arimaa.com/arimaa/papers/

Researching and Implementing a Computer Agent to Play Arimaa by Sam Miller

Plans, Patterns and Move Categories Guiding a Hihgly Selective Search by Gerhard Trippen

If you know of any others which are not listed, please let me know. Thanks.

Title: Re: New paper and thesis on Arimaa
Post by Fritzlein on Nov 5^th, 2009, 2:13pm

Thanks for the heads up, Omar. Sam's paper wouldn't give anyone reason to be more hopeful about UCT bots, but Gerhard's paper about plan-based bots is very intriguing. I didn't quite realize the extent to which bot_Rat is in a class by itself. It is a hoot that Gerhard is mining the ideas that were tried for chess by Botvinnik in the 1960's and ultimately discarded in the 1970's. How could we say a priori that such ideas won't work best for Arimaa, even though they weren't best for chess? Perhaps if bot_Rat learned enough strategies, it would actually become quite strong.

Since Rat's planning is similar to what I do, it is intuitively easy for me to understand. I can imagine condensing what I know about Arimaa into a manageable set of patterns which could be matched, prioritized, and executed. On the other hand, writing Beginning Arimaa has given me a very intimate acquaintance with how hard it is to squeeze my Arimaa knowledge into hard-and-fast rules. Indeed, I say explicitly that a game isn't a great game unless we can do it without knowing how we do it. If I may quote myself:

Quote:

If I could tell you precisely how it is that I play Arimaa better than any computer, it would no longer be true, because the knowledge I expressed could be put into a computer program that does it more accurately and faster than I do.

It always piqued my curiosity that Rat could beat Bomb2005 more often than not while having difficulties against all the other alpha-beta searchers. Somehow I classed Rat's powers along with Gnobot's ability to repeat wins picked up from the game database, i.e. I considered it a narrowly useful trick that could be circumvented by anyone who takes the time. Now I understand that Gerhard's approach is more general and potentially more robust. I hope he has time to add more patterns to Rat and attempt to qualify it for the 2010 Computer Championship.

Omar, how would you feel if Gerhard's approach won the Arimaa Challenge? I am sure you would be disappointed that no machine learning was involved, and that the main process was a painstaking transferal of human knowledge into hard-coded patterns. On the other hand, such a thing was at one time considered the essence of artificial intelligence, so it would be very ironic to now say that a bot built on this method would not be intelligent...

Title: Re: New paper and thesis on Arimaa
Post by omar on Nov 10^th, 2009, 10:37pm

Yes, Gerhard's paper is quite interesting. I hope he gets more time to improve this bot. I am really curious now to see how far this technique can go.

A technique which did not work for chess might just work for Arimaa. If it does prove to be good enough to win the challenge, it would definitely be considered a break through in much the same way as MC which doesn't work for chess is considered a break through when shown to work much better for Go.

Title: Re: New paper and thesis on Arimaa
Post by asfaklive on Jan 27^th, 2010, 10:13pm

From the paper "Methods of MCTS and the game Arimaa"

Quote:

First programs playing Arimaa have taken the so called move-based-approach -
i.e. generating all possible unique moves from the position and evaluating them.
As it was mentioned, due to the large branching factor this option has proved
to be infeasible. Therefore, the step-based-approach has been widely adopted. In
this scenario, programs iteratively generate all legal steps from the position.

Surely it's my limitations to understand.

What's the basic difference between "move-based-approach" and "step-based-approach"?

To me moves and steps are being the same thing. What's the basic difference here?

Regards.

Title: Re: New paper and thesis on Arimaa
Post by Fritzlein on Jan 28^th, 2010, 4:27am

The way he is using the words, one Arimaa move is composed of four steps. The way some other people use the words, one Arimaa turn is composed of four moves. The problem here is that "move" is ambiguous. To avoid ambiguity, in Beginning Arimaa I generally tried to say that one turn is composed of four steps, and use "move" only in the more general sense of changing place, i.e. not as a synonym for either "turn" or "step".

Title: Re: New paper and thesis on Arimaa
Post by asfaklive on Jan 29^th, 2010, 8:57pm

Thanks for your reply.

MCTS is getting complex to me.

What should be the learning curve I can follow to understand MCTS and its implementation in Arimaa smoothly?

Regards.

Title: Re: New paper and thesis on Arimaa
Post by Hippo on Feb 8^th, 2010, 12:36pm

I have read Miller's Thesis.
I am sorry, but I don't recommend it's reading ... a lot of experiments before discovering there is a bug and it plays first chosen random move. Author is satisfied with reduction of illegal moves (new stones created) roughly from in 50% to in 25% games ...

Title: Re: New paper and thesis on Arimaa
Post by 99of9 on Feb 8^th, 2010, 2:47pm

What I find strange is that after he discovered the illegal moves, he played around 5500 games to get the statistics you mentioned, rather than fixing the problem.

Title: Re: New paper and thesis on Arimaa
Post by Hippo on Feb 8^th, 2010, 11:26pm

on 02/08/10 at 14:47:55, 99of9 wrote:

What I find strange is that after he discovered the illegal moves, he played around 5500 games to get the statistics you mentioned, rather than fixing the problem.

I hope the proper word is Cargocultistic. Gant diagrams (waterfall), test cases does not test these particular bugs so no need for repairing. But may be he has only limited access to The Computer.

Title: Re: New paper and thesis on Arimaa
Post by Hippo on Feb 9^th, 2010, 4:56am

Finally I have read the Carlini thesis.
It's nice to use bitboard representation for a lot of purposes.
It seems to me there is problem with the pull implementation. The thesis is short but otherwise it's OK.

[edit]
near(not_frozen(bitboard)&pullFull(bitboard))&EMPTY
should be replaced by
near(not_frozen(bitboard)&near(pullFull(bitboard)))&EMPTY
[/edit]

At first look it seems that computing stone distances ..., trap dominance, stones under attack ... would be complicated, but at the second look it is not. I hope this will not be changed on the third look :D.
I would prefer maintaining stone counts separately and not to compute them from the bitmaps. It was not mentioned but I suppose it's implicit.

Title: Re: New paper and thesis on Arimaa
Post by Hippo on Feb 10^th, 2010, 12:50am

About move reduction in Haizhi's Thesis. It is not clear, but move Ca3e Rc1n Rc2n Rc3n resp. Rc1n Ca3e Rc2n Rc3n either is discarded or the first 2 steps must be considered being combo (suppose there is no gold stone at d3). I thing especially such moves are very important in the endings and discarding them may be an issue.

on 02/10/10 at 04:44:12, 99of9 wrote:

Indeed. This thread may be of interest to you:

http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=devTalk;action=display;num=1232078487;start=

Thanks for the link ... I haven't seen 4 step dependencies with first 3 steps independent. So definitely hashing all positions (except halfpush~~/halfpull~~) in turn is the safest way not to miss an important move (with almost the same complexity) except not pruning 4 independent steps ... if one needs this pruning, he can use BFS with counting the number of ways the position is obtained and remove these with count equal to 24. ... This is of course OK only when you generete moves first and than you start working with them.

Title: Re: New paper and thesis on Arimaa
Post by 99of9 on Feb 10^th, 2010, 4:44am

on 02/10/10 at 00:50:25, Hippo wrote:

Indeed. This thread may be of interest to you:

http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=devTalk;action=display;num=1232078487;start=