Welcome, Guest. Please Login or Register.
Sep 23rd, 2019, 6:31am

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 3942 times)
Janzert
Forum Guru
*****



Arimaa player #247

   


Gender: male
Posts: 1014
Re: move list
« Reply #15 on: Jan 6th, 2006, 10:43am »
Quote Quote Modify 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: male
Posts: 1014
Re: move list
« Reply #16 on: Jan 6th, 2006, 10:48am »
Quote Quote Modify 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: male
Posts: 12
Re: move list
« Reply #17 on: Jan 6th, 2006, 2:23pm »
Quote Quote Modify 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: male
Posts: 1014
Re: move list
« Reply #18 on: Jan 6th, 2006, 2:56pm »
Quote Quote Modify 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

   
Email

Gender: male
Posts: 5928
Re: move list
« Reply #19 on: Jan 6th, 2006, 9:32pm »
Quote Quote Modify 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: male
Posts: 1014
Re: move list
« Reply #20 on: Jan 6th, 2006, 11:53pm »
Quote Quote Modify 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: male
Posts: 12
Re: move list
« Reply #21 on: Jan 7th, 2006, 1:42am »
Quote Quote Modify Modify

Amazing.  Now that's what I call a branching factor.
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: move list
« Reply #22 on: Jan 7th, 2006, 3:04am »
Quote Quote Modify 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)

  toby_hudson  


Gender: male
Posts: 1412
Re: move list
« Reply #23 on: Jan 7th, 2006, 3:40am »
Quote Quote Modify Modify

Sorry about the 9 rabbits Fritz - that was probably my fault, I never was one for calculation over approximation Smiley.  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: male
Posts: 974
Re: move list
« Reply #24 on: Jan 21st, 2006, 11:13pm »
Quote Quote Modify 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: 758
Re: move list
« Reply #25 on: Nov 28th, 2008, 2:43am »
Quote Quote Modify 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: male
Posts: 21
Re: move list
« Reply #26 on: Nov 28th, 2008, 7:29pm »
Quote Quote Modify 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: 758
Re: move list
« Reply #27 on: Nov 29th, 2008, 3:15am »
Quote Quote Modify 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: male
Posts: 21
Re: move list
« Reply #28 on: Nov 29th, 2008, 7:54am »
Quote Quote Modify 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: 758
Re: move list
« Reply #29 on: Jun 21st, 2013, 6:43pm »
Quote Quote Modify 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
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.