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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.