Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> Number of Steps
        
(Message started by: TheVinenator on Nov 1^st, 2011, 10:14am)

Title: Number of Steps
Post by TheVinenator on Nov 1^st, 2011, 10:14am

Ok, a brain teaser..

what is the maximum number of individual steps a single piece an make when calculating all the "moves" a piece can make.

I come up with 13, best case.

if a piece has 3 enemies (lower value), it can move to the empty square, it can pull each of the 3 enemies in one direction, and it can push each of the 3 enemies to 3 empty squares. so, 1 + (3 x 1) + (3 x 3) = 13.

did i miss any?

Title: Re: Number of Steps
Post by Boo on Nov 1^st, 2011, 3:21pm

Move to the empty square is not equal to the pull or push. Pull or push takes 2 steps.
It should be
1+3 + (3 x 1) + (3 x 3) = 16 (two-steps)
I think.

Title: Re: Number of Steps
Post by TheVinenator on Nov 1^st, 2011, 3:40pm

i wasn't interested in the step count, but the unique "single" moves a piece can make.

Title: Re: Number of Steps
Post by Dolus on Nov 1^st, 2011, 5:18pm

Given a full push or pull move is considered a "single move," then I would say 13 is the most.

First, I am assuming our piece is strictly the strongest piece in consideration, and all other pieces are enemy pieces.

If we look at the degrees of freedom a piece has (0-4), there's a very finite number of possible moves.

For 4 degrees of freedom (not surrounded by any pieces), you can't push or pull.
For 0 degrees of freedom, you can't pull, because your piece has nowhere to go.
For 1-3 degrees of freedom, you can pull all pieces into your space, and the number of spaces you can push a piece is equal to their degrees of freedom (maximum of 3).

So from this, we can make a table of how many "single moves" a piece can have.

Degrees of Freedom	Possible Moves
0	4
1	9
2	12
3	13
4	12

Hrmm... I wonder if I can make this into a formula. Probably.

f(x) = (single steps) + (available push moves) + (available pull moves)
f(x) = x + (4 - x) * 3 + (4 - x) * x
Where x = degrees of freedom and f(x) = the total number of "single moves"

And by throwing that into excel and what I came up with in the table, that looks to be true. So we can simplify that to be

f(x) = x + (4-x)*(3+x)
f(x) = -x² + 2x + 12