Tic-Tac-Toe Hash
Karl Meissner
I am writing a genetic algorithm that breeds tic-tac-toe players.
One of the representations that I would like to try is a
hash table. Given a tic-tac-toe board, index into a table
of moves. Then the string dna can just be the interpreted as
the enteries in a hash table.
Genetic algorithms are sensitive to the length of
of the strings that they are operating on. Generally, the shorter
the better.
Since there are only three states, empty, x and o, there are
not more than 3^9 = 19683 possible boards. But many of those
boards are illegal, such as a board with all X's. This
also does not take into account rotation and reflection.
xo. xox ..x ...
o.. ..o ..o o..
x.. ... .ox xox
ox ... x.. xox
.o ..o o.. ..o
.x xox xo. ...
Can all be treated as the same (x goes in the center and forks)
So my question is ..
What is a hash function that encodes all tic-tac-toe boards,
so that it ranges over the shortest possible interval
without colliding unique boards and thus I have a small hash table?
A good function would probably fold in rotation and reflection,
and maybe even ignore the illegal boards (for example all boards
where the difference between the number of x and o is 2 or
greater are illegal)
The best that I have come up with so far is
using a polynomial. Encode empty=0 x=1 o=2, label
the places b0..b8.
h = b8*3^8 + b7*3^7 + b6*3^6 +
b5*3^5 + b4*3^4 + b3*3^3 +
b2*3^2 + b1*3^1 + b0
Find h for all 8 reflections and rotations. The
hash is min value of h.
But I don't like this function because 1) I have to compute it 8
times for each board 2) It leaves all these ugly gaping
holes (of unused boards) in my hash table but still ranges over
several thousand. I am hoping I can get something under a 1000.
Thanks
Karl
Pitbull
>
>
> I am writing a genetic algorithm that breeds tic-tac-toe players.
> One of the representations that I would like to try is a
> hash table. Given a tic-tac-toe board, index into a table
> of moves. Then the string dna can just be the interpreted as
> the enteries in a hash table.
> Genetic algorithms are sensitive to the length of
> of the strings that they are operating on. Generally, the shorter
> the better.
>
> Since there are only three states, empty, x and o, there are
> not more than 3^9 = 19683 possible boards. But many of those
> boards are illegal, such as a board with all X's. This
> also does not take into account rotation and reflection.
>
>
> o.. ..o ..o o..
> x.. ... .ox xox
>
> ..o ..o o.. ..o
> ..x xox xo. ...
>
> Can all be treated as the same (x goes in the center and forks)
>
> So my question is ..
> What is a hash function that encodes all tic-tac-toe boards,
> so that it ranges over the shortest possible interval
> without colliding unique boards and thus I have a small hash table?
>
Well i actually think the crux of your problem is to find a method of
distinguishing rotated or mirrored boards.
Let us try this encoding:
o=-1 x=+1 .=0
and use number the edges as -1..+1 :
Compute
dx(board)=sum over all squares( occupant(square)*xvalue(square)
dy(board)=sum over all squares( occupant(square)*yvalue(square).
This gives us the following laws for boards a,b:
symmetry in x: dx(a)=-dx(b)
symmetry in y: dy(a)=-dy(b)
skewness : dx(a)= dy(b) and dy(a)=-dx(b)
Now, based on this function, mirror boards
with dx<0 on the x-axis,
with dy<0 on the y-axis,
'skew boards on the xy axis.
I haven't really thought this thru, because i think tictactoe really
is trivial after you have found a way to compress it(sic!), so here
is a piece of C to help you. tell me what you find.
<source>
#include <stdio.h>
#define D(i,j) (( b[(i)+1][(j)+1]=='o' )?-1:( b[(i)+1][(j)+1]=='x'?+1:0 ))
#define sc(k) scanf("%s",&b[k]);
void main() {
char b[3][4];
int i,j,dx,dy,dxy;
while (!0) {
printf("enter\n");
sc(0);sc(1);sc(2);
printf("\n");
dx=0;dy=0;dxy=0;
for(i=-1; i<2; i++)
for(j=-1; j<2; j++)
{ dx+=i*D(i,j); dy+=j*D(i,j); dxy+=i*j*D(i,j); printf("%i",D(i,j)); }
printf("\n");
printf("dx=%i,dy=%i,dxy=%i\n",dx,dy,dxy);
}
}
</source>
examples:
ox.
x..
o..
.x
.o
..
stop with CTRL-C.
Peter
> Karl
Melle Koning
Friday February 02 1996 15:21, meis...@cns.bu.edu wrote:
> I am writing a genetic algorithm that breeds tic-tac-toe players.
Does anybody have any readings about how to implement this in a programming
language? Evolutionary creating players sounds very interesting.
--
Greetings from the Netherlands,
Melle me...@rtbbs.iaf.nl
http://www.geocities.com/Colosseum/1334
+--------------------------------------+
| Not tonight dear, I have a modem... |
+--------------------------------------+
Wray Ferrell
In article <4fd12d$q...@news.bu.edu>, meis...@cns.bu.edu (Karl Meissner) writes:
|> Melle Koning (me...@rtbbs.iaf.nl) wrote:
|> : Hello meis...@cns.bu.edu!
|>
|> : Friday February 02 1996 15:21, meis...@cns.bu.edu wrote:
|>
|> : > I am writing a genetic algorithm that breeds tic-tac-toe players.
|>
|> : Does anybody have any readings about how to implement this in a programming
|> : language? Evolutionary creating players sounds very interesting.
There is an article about using genetic algorithms for computer
AI in the latest Game Developer's magazine.
Wray
Karl Meissner
: I am writing a genetic algorithm that breeds tic-tac-toe players.
: One of the representations that I would like to try is a
: hash table. Given a tic-tac-toe board, index into a table
: of moves. Then the string dna can just be the interpreted as
: the entries in a hash table.
: Genetic algorithms are sensitive to the length of
: of the strings that they are operating on. Generally, the shorter
: the better.
In case anyone was interested, the solution that I finally used
has a brute force one. I simply found all the unique legal boards and
stored them. The hash value is the index to that board.
It turns out that you only to need store responses to 627 unique boards,
and can ignore everything else. So my dna string is 627 units long.
If I set the game up so that it plays 'obvious wins' where it
can win in 1 move, like
xx.
o..
o..
with x to go, the number of boards is even smaller, about 175 boards.
This is pretty good compression, considering that there
are 19683 possible boards.
Karl
Norman Richards
>
>I am writing a genetic algorithm that breeds tic-tac-toe players.
>One of the representations that I would like to try is a
A few months back, I implemented a tic-tac-toe program that learns by
evolving small neural networks using the SANE algorithm, (see
http://www.cs.utexas.edu/users/nn/neuro-evolution) I had pretty good
results using a relatively simple network. You might want to look at the
method.
______________________________________________________________________________
o...@cs.utexas.edu "Two roads diverged in a wood, and I -
I chose to climb the nearest tree.
And that has made all the difference."