Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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.)

Could you please help?
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.

For more information, see the free checkers interface, CheckerBoard: 
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.

Here are a few comments on your ideas.

* 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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/