Author: Dan Ellwein
Date: 23:03:47 01/13/00
Go up one level in this thread
On January 13, 2000 at 21:39:49, Ricardo Gibert wrote: >On January 12, 2000 at 18:34:49, Dan Ellwein wrote: > >>Hi >> >>Just wanted to bounce this off of the group and see if this is an accurate >>representation of how many (non redundant) pawn positions there are in chess... >> >> >>(0,8)(1,7)(2,6)(3,5)(4,4) 8P 48x47x46x45x44x43x42x41 x5 = _______ >>(0,7)(1,6)(2,5)(3,4) 7P 48X47X46X45X44X43X42 x4 = _______ >>(0,6)(1,5)(2,4)(3,3) 6p 48X47X46X45X44X43 x4 = _______ >>(0,5)(1,4)(2,3) 5P 48x47x46x45x44 x3 = _______ >>(0,4)(1,3)(2,2) 4P 48x47x46x45 x3 = _______ >>(0,3)(1,2) 3P 48x47x46 x2 = _______ >>(0,2)(1,1) 2P 48x47 x2 = _______ >>(0,1) 1P 48 x1 = _______ >> >> >>Number of non redundant pawn postions in chess -- TOTAL: _______ >> >>haven't done the math on it yet, but it looks like about 75 trillion... >> >>thanks... >> >>PilgrimDan > >I wrote a short little program that calculates the number of pawn positions to >be 8e10. The vast majority of positions represented by this number are illegal. >so this is an upper bound. However, I'm a C newbie so I probably made an error. > i agree... what this represents here is an 'upper bound' because of what you said... illegal positions... and also because of like pieces being calculated... three pawns on the board will not have as many positions as a knight, bishop, rook on the board... the total number of pieces are the same (3) but a different number of possibilities will occur... on a 3x3 board with a P,N,B there are 9x8x7 different positions that can occur.. but with P,P,P on a 3x3 board the number of different positions is less... (504 as oppose to 210 positions) the (1,1) in the above chart is 48x47 but the (0,2) is 47x24 (one half)... and this does not even take into account illegal positions... >In any case, there is a quite simple argument that shows the upper bound to be >less than 1.8e19: Consider a 48 bit bitmap giving the locations of all the pawns >on the board. Since at most 16 of these bits can be set, we can use a 16 bit >bitmap to give color. That's 64 bits total or 1.8e19 pawn positions. > >Of course, we are overcounting like crazy. The 48 bit location bitmap includes >positions with 17 to 48 pawns! Also, the 16 bit color bitmap includes those >positions with more than 8 white or 8 black pawns. > >Taking all this into account I calculated the 8e10 result. With a little >friendly cajoling, I may be persuaded to explain how I calculated this result. >In the meantime, I will double check my result.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.