[ProgClub list] ai-checkers in jj5-test

[John Elliot]

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.