Author |
Topic: move list (Read 6177 times) |
|
Janzert
Forum Guru
Arimaa player #247
Gender: 
Posts: 1016
|
 |
Re: move list
« Reply #15 on: Jan 6th, 2006, 10:43am » |
 Quote  Modify
|
Heh, oops.
Ok, removing Rd3 and moving Dc4 to f5 I get 325447 unique moves.
Code:2w
+-----------------+
8| r . . . . . . . |
7| . . E . M . C . |
6| . . x . . x . . |
5| . D . H . D . . |
4| . . . . H . C . |
3| . R x . . 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 Rb3 Cg4 Cg7 Df5 Db5 He4 Hd5 Me7 Ec7
1b ra8
Janzert
|
|
 IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: move list
« Reply #16 on: Jan 6th, 2006, 10:48am » |
Quote Modify
|
And one more.
Shifting the major pieces so every trap has a neighbor.
Code:2w
+-----------------+
8| . . . . . . . r |
7| . E . M . C . . |
6| . . x . . x . . |
5| . . D . H . D . |
4| . . . H . C . . |
3| . R x . . 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 Rb3 Cf4 Cf7 Dg5 Dc5 Hd4 He5 Md7 Eb7
1b rh8
This has 336488 unique moves.
Janzert
|
| « Last Edit: Jan 6th, 2006, 10:49am by Janzert » |
IP Logged |
|
|
|
medarch
Forum Full Member
Arimaa player #1627
Gender:
Posts: 12
|
|
Re: move list
« Reply #17 on: Jan 6th, 2006, 2:23pm » |
Quote Modify
|
Thanks for the efforts, Janzert.
Not to belabor this issue, but.. would it help if every trap had 2 neighbors?
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: move list
« Reply #18 on: Jan 6th, 2006, 2:56pm » |
Quote Modify
|
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:2w
+-----------------+
8| . . . . . . . r |
7| . C . H . E . . |
6| . . x . . x . . |
5| . . D . M . D . |
4| . . . C . H . . |
3| . R x . . 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 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:2w
+-----------------+
8| . . . . . . . r |
7| . C . H . E . . |
6| . . x . . x D . |
5| . . D . M . . . |
4| . . . C . H . . |
3| . R x . . x R . |
2| . . R . R . . . |
1| . R . R . R . R |
+-----------------+
a b c d e f g h |
|
1w Rh1 Rf1 Rd1 Rb1 Re2 Rc2 Rg3 Rb3 Cd4 Cb7 Dc5 Dg6 Hf4 Hd7 Me5 Ef7
1b rh8
With 338752 unique moves.
Janzert
|
| « Last Edit: Jan 6th, 2006, 2:57pm by Janzert » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: move list
« Reply #19 on: Jan 6th, 2006, 9:32pm » |
Quote Modify
|
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:2w
+-----------------+
8| . . . . . . . r |
7| . . C . . E . . |
6| . D x H . x D . |
5| . . . . M . . . |
4| . R . C . H . . |
3| . . x . . x R . |
2| . R . R . R . . |
1| . . R . R . R . |
+-----------------+
a b c d e f g h |
|
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: move list
« Reply #20 on: Jan 6th, 2006, 11:53pm » |
Quote Modify
|
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:2w
+-----------------+
8| . . . . . . . r |
7| . . H . . C . . |
6| . D x E . x D . |
5| . . . . M . . . |
4| . . C . . H . . |
3| . R x R . x R . |
2| . . R . . R . . |
1| . R . . R . R . |
+-----------------+
a b c d e f g h |
|
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:2w
+-----------------+
8| . . . . . . . r |
7| . . H . . C . . |
6| . D x E . x D . |
5| . . . . M . . . |
4| . . R . . R . . |
3| . R x C . x H . |
2| . . R . . R . . |
1| . R . . R . R . |
+-----------------+
a b c d e f g h |
|
1w Rg1 Re1 Rb1 Rf2 Rc2 Rb3 Rf4 Rc4 Cd3 Cf7 Dg6 Db6 Hg3 Hc7 Me5 Ed6
1b rh8
358513 unique moves.]
Janzert
|
| « Last Edit: Jan 7th, 2006, 12:05am by Janzert » |
IP Logged |
|
|
|
medarch
Forum Full Member
Arimaa player #1627
Gender:
Posts: 12
|
|
Re: move list
« Reply #21 on: Jan 7th, 2006, 1:42am » |
Quote Modify
|
Amazing. Now that's what I call a branching factor.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: move list
« Reply #22 on: Jan 7th, 2006, 3:04am » |
Quote Modify
|
on Jan 6th, 2006, 11:53pm, Janzert wrote:| Oops, actually moving the cat to the inside and the horse down is even better: |
|
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?
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: move list
« Reply #23 on: Jan 7th, 2006, 3:40am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: move list
« Reply #24 on: Jan 21st, 2006, 11:13pm » |
Quote Modify
|
on Jan 5th, 2006, 10:56pm, Janzert wrote: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 |
|
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.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: move list
« Reply #25 on: Nov 28th, 2008, 2:43am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Oystein
Forum Full Member
Arimaa player #3272
Gender:
Posts: 21
|
|
Re: move list
« Reply #26 on: Nov 28th, 2008, 7:29pm » |
Quote Modify
|
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:
+-----------------+
| m R h |
| R E h d M d |
| H x c x c |
| r H r R |
| R r D D |
| r x r x r |
| C r C r R |
| R R R |
+-----------------+ 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).
|
| « Last Edit: Nov 29th, 2008, 7:56am by Oystein » |
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: move list
« Reply #27 on: Nov 29th, 2008, 3:15am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 29th, 2008, 3:17am by aaaa » |
IP Logged |
|
|
|
Oystein
Forum Full Member
Arimaa player #3272
Gender:
Posts: 21
|
|
Re: move list
« Reply #28 on: Nov 29th, 2008, 7:54am » |
Quote Modify
|
You have a point, but it is no problem to rearrange the position
+-----------------+
| R h h |
| R m E d M d |
| H x c x c |
| r H r R |
| R r D D |
| r x r x r |
| C r C r R |
| R R R |
+-----------------+ 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.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: move list
« Reply #29 on: Jun 21st, 2013, 6:43pm » |
Quote Modify
|
on Jan 7th, 2006, 3:04am, Fritzlein 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? |
|
I believe the following permutation of the pieces in Janzert's position is optimal:
Code:2g
+-----------------+
8| . . . . . . . r |
7| . . R . . H . . |
6| . H x E . x D . |
5| . . . . M . . . |
4| . . R . . R . . |
3| . R x D . x C . |
2| . . C . . R . . |
1| . R . . R . R . |
+-----------------+
a b c d e f g h |
|
This allows for 359661 unique moves.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print