Welcome, Guest. Please Login or Register.
Aug 23rd, 2019, 2:58pm

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum move list


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   move list
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: move list  (Read 3897 times)
medarch
Forum Full Member
***



Arimaa player #1627

   


Gender: male
Posts: 12
move list
« on: Dec 3rd, 2005, 2:39am »
Quote Quote Modify Modify

I've been reading some threads here but don't see the info I need yet, so...
 
I'm wondering if these existing bots actually exhaustively generate the legal moves (not steps) at each ply.
Thanks.
IP Logged
omar
Forum Guru
*****



Arimaa player #2

   


Gender: male
Posts: 972
Re: move list
« Reply #1 on: Dec 3rd, 2005, 11:36am »
Quote Quote Modify Modify

Yes, I think they generate all the unique moves at each ply, but then prune away a lot of them after static evaluation.
 
There is a sample bot in the Download section if you want to experiment with your own bot.
IP Logged
doublep
Forum Guru
*****



Badger author

   


Gender: male
Posts: 82
Re: move list
« Reply #2 on: Dec 3rd, 2005, 2:30pm »
Quote Quote Modify Modify

Aami-ra generates all legal moves at the first ply, but then only searches step-by-step.  Of course, step-by-step search finally generates all legal moves each time the search depth is divisible by 4.
IP Logged
jdb
Forum Guru
*****



Arimaa player #214

   


Gender: male
Posts: 682
Re: move list
« Reply #3 on: Dec 4th, 2005, 9:16am »
Quote Quote Modify Modify

Clueless generates all legal moves on the first ply, then slide/push/pull moves after that. It generates capture moves on the first or second step separately.
IP Logged
99of9
Forum Guru
*****




Gnobby's creator (player #314)

  toby_hudson  


Gender: male
Posts: 1412
Re: move list
« Reply #4 on: Dec 6th, 2005, 6:41pm »
Quote Quote Modify Modify

Gnobot is just like the sample bot.  It generates every legal step, with no pruning other than alpha-beta.
IP Logged
ntroncos
Forum Junior Member
**



Weiser's trainer

   
WWW

Gender: male
Posts: 9
Re: move list
« Reply #5 on: Dec 21st, 2005, 8:10pm »
Quote Quote Modify Modify

Quote:

Gnobot is just like the sample bot.  It generates every legal step, with no pruning other than alpha-beta.

 
Weiser does the same thing. Though Nicolas B and i have been trying incomplete search. Using Gnecetic algorithims and HillClimbing.
 
We have encountered much trouble, especialy when it comes to generate legal moves (its very expensive).
IP Logged
medarch
Forum Full Member
***



Arimaa player #1627

   


Gender: male
Posts: 12
Re: move list
« Reply #6 on: Jan 5th, 2006, 6:38pm »
Quote Quote Modify Modify

Another question for the bot-makers:
 
What's the most legal moves (not steps) ever seen at any position?
 
And, does anyone know a low but safe upper bound on the maximum possible legal moves in a position?
 
Thanks again,
medarch
IP Logged
Janzert
Forum Guru
*****



Arimaa player #247

   


Gender: male
Posts: 1014
Re: move list
« Reply #7 on: Jan 5th, 2006, 9:42pm »
Quote Quote Modify Modify

Ooh, I can answer this one since I just finished calculating the number of replies possible from every move made in the current game database on Wednesday. Smiley
 
The most possible replies to a position currently occured in game 5975 before move 58w with 219909 unique moves possible.  
 
After a recent WC game I was talking with 99of9 (I believe anyway, sorry if I'm remembering the wrong person. I have a truly horrid memory.) and mentioned that the highest number of replies for a position that I had found so far was 290603 when requiring pieces from both sides were on the board and 292398 for only one. He was able to quickly come up with the following position that has 373935 replies with both sides and 373985 when removing the rabbit at a8.
 
Code:
2w
 
 +-----------------+
8| r . . . . . . . |
7| . . E . M . C . |
6| . . x . . x . . |
5| . D . H . . . . |
4| . . D . H . C . |
3| . R x R . x . . |
2| . . R . R . R . |
1| . R . R . R . R |
 +-----------------+
   a b c d e f g h

 
1w Rh1 Rf1 Rd1 Rb1 Rg2 Re2 Rc2 Rd3 Rb3 Cg4 Cg7 Dc4 Db5 He4 Hd5 Me7 Ec7
1b ra8
 
One caveat to the above numbers though, while I've double checked all the positions mentioned here against the official move generator, I haven't checked a large enough number to be confident my move generator is bug free yet. So further checking may discover a bug that turns up a position with higher replies.
 
Janzert
« Last Edit: Jan 5th, 2006, 9:42pm by Janzert » IP Logged
medarch
Forum Full Member
***



Arimaa player #1627

   


Gender: male
Posts: 12
Re: move list
« Reply #8 on: Jan 5th, 2006, 10:18pm »
Quote Quote Modify Modify

Thanks!  That's great, Janzert.  I believe 373935 or so is close to the actual maximum.
 
I don't yet have a program with which to test this yet, but I think the number can be increased by moving the silver rabbit in your diagram from a8 to h7.  Adding more silver rabbits (at c8 and a5, for example) where they can be pushed and pulled may add even more moves.  Anyone care to verify?
 
The question of maximum number of moves is of interest to people like me who are trying to build a move-based rather than step-based search.  I know opinions vary on the merits of this, but I feel much more comfortable sorting and pruning moves rather than steps.  It's probably trickier in several ways, but I think it will prove to be the best way to do it ultimately.
IP Logged
Janzert
Forum Guru
*****



Arimaa player #247

   


Gender: male
Posts: 1014
Re: move list
« Reply #9 on: Jan 5th, 2006, 10:44pm »
Quote Quote Modify Modify

Moving ra8 to rh8 cuts it back to 372898 moves.  
 
Instead adding rc8 results in 358543 moves or ra5, 357719 moves. Basically anytime there is a push or pull added it adds a constraint to a step that wouldn't have been there otherwise. For instance when adding rc8, the move Ec7n has to be preceded by either rc8w or rc8e.
 
Janzert
IP Logged
Janzert
Forum Guru
*****



Arimaa player #247

   


Gender: male
Posts: 1014
Re: move list
« Reply #10 on: Jan 5th, 2006, 10:56pm »
Quote Quote Modify Modify

Ahh, finally finished double checking the high move position for hvh and bvb games with the official move generator. So here they are:
 
The highest unique moves for a bvb game is game 18358, 47w with 142418 moves.
 
For a hvh game it's game 13011, 66w with 117059 moves.
 
Janzert
IP Logged
medarch
Forum Full Member
***



Arimaa player #1627

   


Gender: male
Posts: 12
Re: move list
« Reply #11 on: Jan 6th, 2006, 12:06am »
Quote Quote Modify Modify

Interesting.  I figured since, when an E is next to an r like that, there are two different pushes and three different pulls that it would result in more moves.  But the fact that they require two steps, where one is the same as if the rabbit wasn't there, more than cancels the effect.
 
Janzert, are these numbers definitely non-duplicate moves.. that is, they all result in different board states?
IP Logged
PMertens
Forum Guru
*****



Arimaa player #692

   
WWW

Gender: male
Posts: 437
Re: move list
« Reply #12 on: Jan 6th, 2006, 8:29am »
Quote Quote Modify Modify

I assume that those are the moves ... not the resulting boardstates (just betting here Wink )
IP Logged
Janzert
Forum Guru
*****



Arimaa player #247

   


Gender: male
Posts: 1014
Re: move list
« Reply #13 on: Jan 6th, 2006, 9:00am »
Quote Quote Modify Modify

Yes. No. Wink Those are the unique board positions possible to reach by legal moves. At least assuming my program and the official program don't have the exact same bug resulting in the same duplicate or illegal positions being generated (the chance of that is probably somewhere around the sames as the chance of me getting hit by a meteor today Cheesy).  
 
For example here is the first part of the output by the official generator for the position diagramed above when only positions are set to be output.
 
(Apparently even code tags still mess up whitespace so this is a bit garbled)
Code:
1w
 
 +-----------------+
8| r     |
7|     E   M   C   |
6|       |
5|   D   H    |
4|     D   H   C   |
3|   R   R    |
2|     R   R   R   |
1|   R   R   R   R |
 +-----------------+
   a b c d e f g h
 
58 choices for initial step
8788011 total move combinations
373935 unique moves
4.25% are unique
 
[r    E M  D H D H C R  R R R R  R R  RR]
[r    E M C    D  H D H C   RR R R R  R R  RR]
...

 
Continuing with 373954 lines of output total. While I haven't manually checked the resulting positions Wink my program will generate the same list of positions, although in a different order.
 
Janzert
« Last Edit: Jan 6th, 2006, 9:05am by Janzert » IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: move list
« Reply #14 on: Jan 6th, 2006, 10:19am »
Quote Quote Modify Modify

Um, it seems to me that Gold has nine rabbits in the position being discussed.  Shocked  If you are allowing positions that can't occur in an actual game, I think I might be able to break the record by adding yet more pieces.
IP Logged

Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB 2000-2003. All Rights Reserved.