Associated Topics || Dr. Math Home || Search Dr. Math

Checkerboard Combinations

```
Date: 03/21/2001 at 03:26:44
From: Ryan White
Subject: Possible Number of combinations on a checkers board

Dr. Math,

I am thinking of creating a large checkers database with the 'best'
move for each game combination. The database will be computer-
generated, but how large will it be?  To know the size of the database
I need to know the following question:

What is the possible number of combinations on a checkerboard with
12 (or fewer) red pieces and 12 (or fewer) black pieces (where each
piece can be normal or king)?

The only answer I could come up with was 5^32 combinations, where 32
is the number of places on the board, and 5 is the number of possible
combinations for each place. (Normal Red, Normal Black, Red King,
Black King, and empty.)  But that would include combinations of more
than 12 per color.  (23,283,064,365,386,962,890,625 combinations, to
be exact.)

Thank you,
Ryan
```

```
Date: 03/21/2001 at 09:39:08
From: Doctor Rob
Subject: Re: Possible Number of combinations on a checkers board

Thanks for writing to Ask Dr. Math, Ryan.

The number of ways of choosing r squares for red pieces and b squares
for black pieces on the checkerboard is

C(32,r)*C(32-r,b).

Here C(x,y) = x!/(y!*[x-y]!).  Multiply this by 2^r and 2^b to allow
for the possibility of kings or men at each occupied square.  Now
sum this over all values of r and b from 1 to 12, to get the total:

12  12
N = SUM SUM C(32,r)*C(32-r,b)*2^(r+b),
r=1 b=1

12  12
= SUM SUM 32!*2^(r+b)/(r!*b!*[32-r-b]!).
r=1 b=1

There is no nice closed form for this sum.  I used a computer to add
up these numbers, and got

N = 2,308,487,698,984,342,680,192

or about 2.3 sextillion. While this is less than 1/10 of your number,
it is still very large. That means that your project is doomed unless
you somehow restrict the positions you put into the database to ones
that are commonly encountered.

By the way, how can you pick the "best" move from each configuration?

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 03/22/2001 at 07:31:33
From: Ryan White
Subject: Re: Possible Number of combinations on a checkers board

WOW!  Thank you so much!  It's only going to take two billion
one-terabyte drives to make this database now.

I found a page on this topic:  Its total is:
500,995,484,682,338,672,639 (possible combos)
329,847,169,676,858,217,781 (possible combos where
r=b, r=b-1, or r=b+1)

Total Number of Checker Positions
Department of Computing Science, University of Alberta
http://www.cs.ualberta.ca/~chinook/databases/total.html

About your question: The best move in checkers can be calculated using
one of the many checkers engines. The time it takes ranges from several
days to less then a second, depending on the situation. The Cake checkers
engine, for example, will return one of three values, 2000, 0, or -2000
when in infinite time mode. 2000 is a guaranteed win and the end of the
game is in sight. No matter what moves the opponent makes, he or she
cannot win. The second type is a return of 0, a guaranteed draw as long
as the opponent does not make any mistakes.  If the opponent does make
a mistake, however, it changes to 2000 (a guaranteed win). Finally, a
return of -2000 is a guaranteed loss as long as the opponent keeps making
the best move. The best move of a -2000 value is the one that postpones
the draw as long as possible. I should note that there is no return of 0.
The engine will run indefinitely looking for a win, but will not find one.

Also, there are three types of opening moves classified by a WWC.
Class A is a guaranteed win, Class B is a guaranteed draw, and Class C
is also a guaranteed draw but much more difficult to achieve. A while
ago there was a match of the top checkers player vs. a supercomputer,
and all 17 games were a draw.

http://www.fierz.ch/checkers.htm   .

I was talking to my brother last night and he reminded me that a "man"
could only be on 28 places on the board. When the man gets to the end
he turns king. I am guessing this is the cause of the difference in
totals.

What now? Well the size of the database is still very large. I have some
thoughts about how to shrink it:

*Don't count boards where a man/king has to jump someone, since you have
to jump them anyway. (This should shrink it a lot.)
*Count with only 8 kings.
*Divide the total count by 2 because there are two records of every setup
when exchanging colors.
*Don't count boards with no pieces of one color.
*A way to represent each board with only 2 bits (not bytes).
*Use/find a math formula to represent each board setup with a number. Then
use that number as a pointer in the database so every board combination
does not have to contain a piece layout.

If there are 30 combinations, for example, it will take 20 bits.

The database I have will support around 30 gigabytes, or 120,000,000,000
2-bit codes. With that criterion, do you think it will fit?

Thank you for helping,
Ryan
```

```
Date: 03/22/2001 at 12:31:26
From: Doctor Rob
Subject: Re: Possible Number of combinations on a checkers board

Thanks for writing back, Ryan.

By not allowing r or b to be 0 in my summation, I have taken care of
removing positions with no players of one (or both) colors.

It sounds like even if you could store the database (and I am not
optimistic about that), you would take an infinite or virtually
infinite amount of computer time to figure out the "best" move for
all of them.

I could count again using a more complicated sum taking into account
that men cannot occur on the last rank, but it will only reduce the
count by a small amount. It will still be in the quintillions range.

* If you don't count boards where a jump is forced, how do you deal
with a situation where two different jumps are possible, of which
you can choose either?

* Is there are rule that you can only have at most 8 kings?

* Yes, the total count can be divided by 2.

* I can't imagine how you could store a board with only 2 bits.  If
you could you would still have quintillions of bits to store.

I don't think any of your ideas (or any I could devise) can get the
number of bits to store less than a quintillion. Remember, you have to
store not only the board position, but also the description of the best
move. This is still four orders of magnitude greater than your storage
capacity. I am also worried about the amount of time needed to create
this beast.

Keep working on your project.  It is clearly making you think very
hard about the practicalities of programming!

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search