|
||||
|
Title: move list Post by medarch on Dec 3rd, 2005, 2:39am 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. |
||||
|
Title: Re: move list Post by omar on Dec 3rd, 2005, 11:36am 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. |
||||
|
Title: Re: move list Post by doublep on Dec 3rd, 2005, 2:30pm 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. |
||||
|
Title: Re: move list Post by jdb on Dec 4th, 2005, 9:16am 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. |
||||
|
Title: Re: move list Post by 99of9 on Dec 6th, 2005, 6:41pm Gnobot is just like the sample bot. It generates every legal step, with no pruning other than alpha-beta. |
||||
|
Title: Re: move list Post by ntroncos on Dec 21st, 2005, 8:10pm Quote:
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). |
||||
|
Title: Re: move list Post by medarch on Jan 5th, 2006, 6:38pm 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 |
||||
|
Title: Re: move list Post by Janzert on Jan 5th, 2006, 9:42pm 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:
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 |
||||
|
Title: Re: move list Post by medarch on Jan 5th, 2006, 10:18pm 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. |
||||
|
Title: Re: move list Post by Janzert on Jan 5th, 2006, 10:44pm 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 |
||||
|
Title: Re: move list Post by Janzert on Jan 5th, 2006, 10:56pm 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 |
||||
|
Title: Re: move list Post by medarch on Jan 6th, 2006, 12:06am 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? |
||||
|
Title: Re: move list Post by PMertens on Jan 6th, 2006, 8:29am I assume that those are the moves ... not the resulting boardstates (just betting here ;) ) |
||||
|
Title: Re: move list Post by Janzert on Jan 6th, 2006, 9:00am 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 :D). 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:
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 |
||||
|
Title: Re: move list Post by Fritzlein on Jan 6th, 2006, 10:19am Um, it seems to me that Gold has nine rabbits in the position being discussed. :o 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. |
||||
|
Title: Re: move list Post by Janzert on Jan 6th, 2006, 10:43am Heh, oops. Ok, removing Rd3 and moving Dc4 to f5 I get 325447 unique moves. Code:
1w Rh1 Rf1 Rd1 Rb1 Rg2 Re2 Rc2 Rb3 Cg4 Cg7 Df5 Db5 He4 Hd5 Me7 Ec7 1b ra8 Janzert |
||||
|
Title: Re: move list Post by Janzert on Jan 6th, 2006, 10:48am And one more. Shifting the major pieces so every trap has a neighbor. Code:
1w Rh1 Rf1 Rd1 Rb1 Rg2 Re2 Rc2 Rb3 Cf4 Cf7 Dg5 Dc5 Hd4 He5 Md7 Eb7 1b rh8 This has 336488 unique moves. Janzert |
||||
|
Title: Re: move list Post by medarch on Jan 6th, 2006, 2:23pm Thanks for the efforts, Janzert. Not to belabor this issue, but.. would it help if every trap had 2 neighbors? |
||||
|
Title: Re: move list Post by Janzert on Jan 6th, 2006, 2:56pm There was some discussion on this among the spectators of the WC game today. Ryan Cable also mentioned trying to get 2 neighbors to a trap as well as keeping all the pieces off of the a and h file. But nobody tried it out at the time. JDB realised switching the H and M on the d file would allow more positions. After further flipping M and H then the H and C on row 4 to further seperate like pieces it ends up at this position. Code:
1w Rh1 Rf1 Rd1 Rb1 Rg2 Re2 Rc2 Rb3 Cd4 Cb7 Dg5 Dc5 Hf4 Hd7 Me5 Ef7 1b rh8 This has 338034 unique moves. After the game I pursued the 2 neighbors at every trap idea a bit. It does help, if you can keep from interfering with other moves. The best I came up with so far is Code:
1w Rh1 Rf1 Rd1 Rb1 Re2 Rc2 Rg3 Rb3 Cd4 Cb7 Dc5 Dg6 Hf4 Hd7 Me5 Ef7 1b rh8 With 338752 unique moves. Janzert |
||||
|
Title: Re: move list Post by Fritzlein on Jan 6th, 2006, 9:32pm I'm also curious about the effect of Ryan's other idea, i.e. insuring that each piece has four initial steps and each rabbit has three initial steps. In your positions one rabbit always is stuck with only two steps, so I'm interested in something like this: Code:
|
||||
|
Title: Re: move list Post by Janzert on Jan 6th, 2006, 11:53pm Yay, that get's it up to 339806 unique moves. Taking that and splitting up the cats and horses, then rotating the pieces around the a3 trap to cover it and also pull a rabbit back, gives this: Code:
1w Rg1 Re1 Rb1 Rf2 Rc2 Rg3 Rd3 Rb3 Cc4 Cf7 Dg6 Db6 Hf4 Hc7 Me5 Ed6 1b rh8 With 353982 unique moves. [EDIT: Oops, actually moving the cat to the inside and the horse down is even better: Code:
1w Rg1 Re1 Rb1 Rf2 Rc2 Rb3 Rf4 Rc4 Cd3 Cf7 Dg6 Db6 Hg3 Hc7 Me5 Ed6 1b rh8 358513 unique moves.] Janzert |
||||
|
Title: Re: move list Post by medarch on Jan 7th, 2006, 1:42am Amazing. Now that's what I call a branching factor. |
||||
|
Title: Re: move list Post by Fritzlein on Jan 7th, 2006, 3:04am on 01/06/06 at 23:53:31, Janzert wrote:
That suggests that further splitting of the rabbits (i.e. mixing the pieces in among the rabbits to reduce duplicated moves) might give further gains, no? |
||||
|
Title: Re: move list Post by 99of9 on Jan 7th, 2006, 3:40am Sorry about the 9 rabbits Fritz - that was probably my fault, I never was one for calculation over approximation :-). It's good to see you've all developed on the original pattern, the new records look very good. |
||||
|
Title: Re: move list Post by omar on Jan 21st, 2006, 11:13pm on 01/05/06 at 22:56:30, Janzert wrote:
Wow. Thanks for posting this info. I had often wondered what the highest unique moves were for real games. I didn't expect it to be this high. Don Dailey (developer of Occam) had found some games that had around 60,000 unique moves and I thought that was pretty high. This really shatters that record. Another thing I've often wondered about is the average number of unique moves and how it changes as a game progresses. For example find the average number of unique moves for position 2w, then 2b and so on. I would be interesting to see where this peaks and what the actual values are. |
||||
|
Title: Re: move list Post by aaaa on Nov 28th, 2008, 2:43am I'm interested to know how high the number of possible steps can be for a player at any step of his move, including those that would be a start or a completion of a push or a pull. On my own, I can come up with an upper bound of 108 (not counting a possible pass option as a step), corresponding to a board with a checkered pattern of pieces and empty squares with at least four steps lost due to rabbits not being able to step backwards on their own. |
||||
|
Title: Re: move list Post by Oystein on Nov 28th, 2008, 7:29pm I guess you want minimal size for the array of steps. But what exactly do you consider different steps? I treat the 2 steps in a push or pull as independent steps. The search tree expands after the first step if there are several pushes or pulls with the same first step. But I use flags to distinguish them from sliding moves. I looked for a position with many possible steps and found this: +-----------------+Here we have 35 sliding moves 42 first step of a push 17 first step of pull of 25 different pulls Hence I need at least an array of 94 steps (and 103 should be sufficient). |
||||
|
Title: Re: move list Post by aaaa on Nov 29th, 2008, 3:15am I believe your example is flawed since it has a rabbit on the goal row that could have only gotten there if at least three steps have already been made by the side to move, meaning that no start of a push or pull is possible in that position. I'm trying to establish the maximum number of children a step node can have. In that case, steps shouldn't be counted double if they can be the start of a pull, like you have done, since there is no distinction in the resulting position one step later. Positions in the middle of a pull are acceptable as long as the situation is unambiguously described by a mention of the previous step that started the pull; so this can only add up to 3 to the number. For the same reason, being in the middle of a push is obviously not going to be a solution to the problem. |
||||
|
Title: Re: move list Post by Oystein on Nov 29th, 2008, 7:54am You have a point, but it is no problem to rearrange the position +-----------------+Well, for me this position will branch into 94 children:) Pulls and slides are radical different. Thats why I distinguish them. You can of course consider this 77 distinct steps. One could argue that rabbits on goal line should not be allowed at all since there is no need for further search. In that case reduce the numbers with 2. For upper bound: Any first step of a pull could also be a sliding move. So we don't have to consider them. There are maximum 3 and 4 sliding moves for rabbits and non rabbits. Totally 56. There are at most 15 pieces that can be pushed in 3 different direction, however each pushable piece will reduce the sliding moves by 1. So we add 30, and get an upper bound of 86. The exact number of steps have to be smaller because of limited space, but I have not found any good way to utilize the available space information. |
||||
|
Title: Re: move list Post by aaaa on Jun 21st, 2013, 6:43pm on 01/07/06 at 03:04:37, Fritzlein wrote:
I believe the following permutation of the pieces in Janzert's position is optimal: Code:
This allows for 359661 unique moves. |
||||
|
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |