# [ProgClub list] ai-checkers in jj5-test

John Elliot jj5 at progclub.org
Tue Oct 18 08:23:54 AEDT 2011

```OK, I'm going to dive into a "sub problem". That is: given any
particular board configuration, and whose move it is, what is the upper
bound on the number of potential antecedent board states? That is, at
most how many new board configurations can result given all the legal
ways a player might choose to move their pieces?

A few examples might help. So at first there is the starting board

.x.x.x.x
x.x.x.x.
.x.x.x.x
........
........
o.o.o.o.
.o.o.o.o
o.o.o.o.

In checkers red moves first and there are 7 possible antecedent states.
If it happened to be white's move there would be 7 states too.

It's red's move:

.X......
..o.O.O.
........
....o...
........
....o.o.
........
........

Red has to make a jump. Having made a jump it can choose which piece to
jump next but has to jump something again. It will then need to make a
third jump. There are 3 possible outcomes.

I don't think I'll continue with examples. What I think I'll do is
revert to my thinking about 5 ^ 32 possible board states. There aren't
quite that many states. Some of the things represented by 5 ^ 32 would
have too many pieces on the board, or have normal pieces (not kings) on
the last row. Some of the things represented might be board states that
are impossible to reach in a valid game (although I don't think that
would be easily determined). But it's comforting to know that there are
absolutely no more than 5 ^ 32 board states, about 30 million.

So what I think I'll do is write a program that starts at board state 1
(board state 'zero' is an empty board with no pieces on it) and then
enumerates each possible board state up to 5 ^ 32, and for each state
generates the set of possible moves. I'll count those possible moves for
each board state and remember the maximum number found. Doing it this
way means I won't have to think too hard about it, and knowing the
maximum number of possible 'next states' might help me come up with a
data structure (or file structure) that I can use to model games trees.

(Note: I will only have to check possible moves for red, because I'm
enumerating each possible board state, and white's possible moves would
simply mirror red's possible moves.)

So that seems like a tractable sub problem, and I think that's what I'll
work on next. Once I know the maximum number of possible 'next states'
I'll pick up the rest of the problem and get back to considering that.

```