[ProgClub list] ai-checkers in jj5-test

[John Elliot]

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...