Author |
Topic: New paper and thesis on Arimaa (Read 2011 times) |
|
omar
Forum Guru
Arimaa player #2
Gender: 
Posts: 1003
|
 |
New paper and thesis on Arimaa
« on: Oct 29th, 2009, 2:57pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: New paper and thesis on Arimaa
« Reply #1 on: Nov 5th, 2009, 2:13pm » |
Quote Modify
|
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...
|
| « Last Edit: Nov 5th, 2009, 6:05pm by Fritzlein » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: New paper and thesis on Arimaa
« Reply #2 on: Nov 10th, 2009, 10:37pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
asfaklive
Forum Senior Member
Arimaa player #4922
Gender:
Posts: 30
|
|
Re: New paper and thesis on Arimaa
« Reply #3 on: Jan 27th, 2010, 10:13pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: New paper and thesis on Arimaa
« Reply #4 on: Jan 28th, 2010, 4:27am » |
Quote Modify
|
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".
|
|
IP Logged |
|
|
|
asfaklive
Forum Senior Member
Arimaa player #4922
Gender:
Posts: 30
|
|
Re: New paper and thesis on Arimaa
« Reply #5 on: Jan 29th, 2010, 8:57pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: New paper and thesis on Arimaa
« Reply #6 on: Feb 8th, 2010, 12:36pm » |
Quote Modify
|
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 ...
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: New paper and thesis on Arimaa
« Reply #7 on: Feb 8th, 2010, 2:47pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: New paper and thesis on Arimaa
« Reply #8 on: Feb 8th, 2010, 11:26pm » |
Quote Modify
|
on Feb 8th, 2010, 2:47pm, 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.
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: New paper and thesis on Arimaa
« Reply #9 on: Feb 9th, 2010, 4:56am » |
Quote Modify
|
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  .
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.
|
| « Last Edit: Feb 10th, 2010, 12:59am by Hippo » |
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: New paper and thesis on Arimaa
« Reply #10 on: Feb 10th, 2010, 12:50am » |
Quote Modify
|
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 Feb 10th, 2010, 4:44am, 99of9 wrote:
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.
|
| « Last Edit: Feb 10th, 2010, 11:41am by Hippo » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: New paper and thesis on Arimaa
« Reply #11 on: Feb 10th, 2010, 4:44am » |
Quote Modify
|
on Feb 10th, 2010, 12:50am, Hippo wrote:| 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. |
|
Indeed. This thread may be of interest to you:
http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=devTalk;action=display ;num=1232078487;start=
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print