[ProgClub list] ai-checkers in jj5-test

John Elliot jj5 at progclub.org
Tue Oct 18 07:13:48 AEDT 2011

```Well I didn't think too hard about it, but I got my homework for the
first week of the AI class submitted, so that means I can spend a little
while this morning thinking harder about the checkers problem.

I was thinking: there are 32 spaces on the board, and each of these
spaces could be either empty (the board '.'), or occupied by a red piece
('x'), a red king ('X') a white piece ('o') or a white king ('O'). So
that's five possible values, which can be represented in 3 bits: '.'
000; 'x' 001; 'X' 010; 'o' 011; 'O' 100; with 101, 110, 111 unused. That
would make it pretty easy to pack 2 board positions into a byte (high
four bits and low four bits) giving a 16 byte data structure to
represent the state of a board. Using 3 bits you could pack the state of
all 32 board positions into a 12 byte data structure (3*32=96). Or
(assuming you could have between 0 and 32 pieces on the board, which you
can't) you could have a maximum of

5 ^ 32 = 33,554,432
= 10 0000 0000 0000 0000 0000 0000 (in binary)

board states, which is a 4 byte data structure (with 6 bits to spare).
At the moment in my simulation I'm using a 65 byte data structure, which
is way larger than necessary.

Coming at this from a different direction, given the state of the board
that we're starting with, there are 9 red pieces and 7 white pieces for
a total of 16 pieces on the board. Any piece could be located on one of
33 different locations, being any valid square (32) or 'off the board'
(1). A piece can also be either normal or a king, which is an extra bit.
So there are 34 states to model for each piece, being whether it is a
king or not, whether it is on the board or not, and where on the board
it is. You can represent 34 states in 6 bits, which you could pack into
8 bits having a 16 byte data structure for the location/state of each
piece, or a 6*16 = 96 bits = 12 byte data structure to model pieces and
their location.

So that's a 4 byte data structure representing board states, or a 12
byte data structure representing piece states. So, assuming I haven't
made a mistake, it's cheaper to model the state of a board (what
occupies each square) than it is to model the state of a set of pieces
(which location/king-state each piece is in).

I'm not sure how I would actually pack the board state into 4 bytes
though. I guess it would have something to do with representing numbers
in base 5. So if I had a (signed or unsigned) 32 bit value, and
converted it into a base 5 string representation, the digit in position
n would give me the state of board position n. That makes this problem
almost seem tractable. There are no more than 33,554,432 states. Many of
those states are impossible, and of those that are possible many of them
aren't possible given the starting configuration of this particular board.

So essentially I've established that we can pack a board state into a
single 32-bit integer, but I'm not sure yet about what sort of
algorithms, data structures or state management system I would need to
compute and model game trees. I'm starting to feel like this problem
might be computationally intractable. I'll think more about it in our
next instalment...

```