# Re: Which is faster - hash or array lookup

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

No, not necessarily...

because the game is not invariant under rotations or flipping. In
fact, one goal of the game is to make the common piece end on the
opponent's back row (the five squares closest to him). So if the
squares occupied by (34567,12345) (in either order) would allow the
common piece to be moved to 1's back row, 2 would be winning, whereas
if it was 1's turn, he would have a chance to avoid losing.

There is one symmetry that might be exploited; the game is mirror
symmetric around the axis joining (1,3)--(5,3). So one might at any
time assume that the common piece is in one of the 9 squares spanned
by (2,1),(2,3),(4,3),(4,1) (no need to memorize positions where the
common piece is at either back row, because those are game over
positions).

From my experience of playing this game in real life, I have
discovered some heuristics that I plan to implement. It is almost
always a good idea to make a move so that the opponent has as few
places to move the common piece, so that would be one way to avoid
completely random play. There are a few others. If I restart the game
often enough (say, the first 10 million games are declared a draw if
no winner is found within 10 moves), many of the positions one would
need to go through to reach the unrealistic ones will have been marked
as winning, and so will be avoided in any subsequent games.

I have thought about doing it that way, but the number of have-won
boards is rather huge (by the above, at least any board where the
common piece is at one of the 10 back row squares, which makes 2e7;
there are other ways to win, also). The problem of determining if
there is a winning strategy (nothing in the rules prevents the players
from entering a cycle which can only be broken if one of the players
resign) is "just" a question of coloring a huge graph by some
recursive algorithm.

We are quite OT. If you like I'd gladly tell you the exact rules of
the game, but then I think we should continue by private email or find
a more suitable group.

--
Rasmus Villemoes
<http://rasmusvillemoes.dk/