Author |
Topic: move list (Read 6173 times) |
|
medarch
Forum Full Member
Arimaa player #1627
Gender: 
Posts: 12
|
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:
Posts: 1003
|
 |
Re: move list
« Reply #1 on: Dec 3rd, 2005, 11:36am » |
 Quote  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:
Posts: 82
|
|
Re: move list
« Reply #2 on: Dec 3rd, 2005, 2:30pm » |
Quote 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:
Posts: 682
|
|
Re: move list
« Reply #3 on: Dec 4th, 2005, 9:16am » |
Quote 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)
 
Gender:
Posts: 1413
|
|
Re: move list
« Reply #4 on: Dec 6th, 2005, 6:41pm » |
Quote 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
Gender:
Posts: 9
|
|
Re: move list
« Reply #5 on: Dec 21st, 2005, 8:10pm » |
Quote 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:
Posts: 12
|
|
Re: move list
« Reply #6 on: Jan 5th, 2006, 6:38pm » |
Quote 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:
Posts: 1016
|
|
Re: move list
« Reply #7 on: Jan 5th, 2006, 9:42pm » |
Quote 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. 
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:
Posts: 12
|
|
Re: move list
« Reply #8 on: Jan 5th, 2006, 10:18pm » |
Quote 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:
Posts: 1016
|
|
Re: move list
« Reply #9 on: Jan 5th, 2006, 10:44pm » |
Quote 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:
Posts: 1016
|
|
Re: move list
« Reply #10 on: Jan 5th, 2006, 10:56pm » |
Quote 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:
Posts: 12
|
|
Re: move list
« Reply #11 on: Jan 6th, 2006, 12:06am » |
Quote 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
Gender:
Posts: 437
|
|
Re: move list
« Reply #12 on: Jan 6th, 2006, 8:29am » |
Quote Modify
|
I assume that those are the moves ... not the resulting boardstates (just betting here  )
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: move list
« Reply #13 on: Jan 6th, 2006, 9:00am » |
Quote Modify
|
Yes. No. 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  ).
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 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
Gender:
Posts: 5928
|
|
Re: move list
« Reply #14 on: Jan 6th, 2006, 10:19am » |
Quote Modify
|
Um, it seems to me that Gold has nine rabbits in the position being discussed.  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 |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print