Author: Uri Blass
Date: 14:01:39 11/29/02
Go up one level in this thread
On November 29, 2002 at 15:12:37, S. Loinjak wrote: >Hi, > >many people mix the number of positions in chess with the number of games or >think they're of the same magnitude. > >All possible chess positions can be distinguished by: >- position on board >- color to move >- castle flags >- ep flag (pawn which has moved last - maybe no one!) >(I wouldn't take into 3 fold repetition and the 50 moves rule as they seem >artificial for me - they are not defined by the pure rules of chess itself.) > >Now imagine a network containing all possible positions. And all positions p1 >and p2 where p1 can be transformed into p2 by a legal chess move are connected >together by an arrow from p1 to p2. This is called a directed graph. It's now >easy to see that there are much more games (all the directed paths from the >initial position to any other position) than positions. In paractical chess you >can see the difference most easily in a king vs king endgame. Although there are >at most 64x64 = 4096 positions the lone kings could produce 4^100 games if you >assume in the average 4 possible moves per king in each postion (most time they >have 8 alternatives!). > >You can compare chess to languages: with a set of given words (comparable to >positions) you can construct almost an infinite number of sentences (comparable >to complete games). If there was no 50 move limit in chess the number of >possible games would also be infinite (by infinite move repetition). > >Another similar example is from set theory: the power set of a given set with n >objects has 2^n objects. > >It can be easily proven that there are at maximum about 10^46 (10 raised to the >power of 46) positions in chess. If you take into account specific knowledge >(about king positions and underpromotion) you can also show that there are at >most about 10^44 positions. Maybe you've heard about better limits but they're >often too optimistic (they underestimate the true number of positions) as in >most cases people simply 'forget' to take into account all possible >underpromotions (8 pawns can promote e.g. into a queen, 2 rooks, 4 bishops and a >knight - and there are many other combinations with 8 pawns). > > > >Regards, >Sini > > >P.S: I hope I will be able to prove exactly that there are less than 10^42 or >even less than 10^40 positions. This requires a combination of techniques from >operations research with classic tree search algorithms and combinatorics >theory. > >P.S.2: Please correct me if I express sthg in the wrong way - english is not my >primary language. I do not know the number and it is only a guess but my guess is that you are going to be unable to prove that there are less than 10^40 position for the simple reason that there are more than 10^40 positions. I believe that if you are interested in this subject then it is possible to get an estimate for the number of legal position by a program that choose random pseudo legal position(when you give every position the same probability) If you have an upper bound of 10^46 and you find that you get 17 legal positions out of 100000 random positions then the estimate for the number of legal positions is 10^46*(17/100000) and it is clearly bigger than 10^40. It is not a trivial task to write a program that choose pseudo random position that has material structure that is theoretically legal(the bound that is bigger than 10^46 was obtained by removing illegal material structures like a structure that there are 32 pieces that are not the original pieces or structures that there are 31 pieces and white has more than 2 promoted pieces or structures when there are 31 pieces including 8 black pawns and white has more than 1 promoted piece). It is also not an impossible task to write a program because you need to know the number of positions for every material structure and after choosing a random interval with defined probabilities that are proportional to the size of the intervals you can choose a random number in the interval. I believe that most of the 10^46 positions are going to be discovered as illegal because of impossible pawn structure so in order to get a better upper bound for the number of positions you may need to count the number of positions for every material structure and pawn structure and calculate the sum of these numbers. I guess that the number of legal pawn structures are a small minority of less than 1/1000 but still a minority of more than 1/100000 and it is the basis for my guess that there are more than 10^40 positions It is only a guess and the problem was not important enough for me to investigate it because it seems to me that it is not an important problem and I doubt if it has a scientific value. I investigated problems in combinatorics(problems that the answer for them is an integer and the target is to find better bounds) but I know that mathematicians are not interested in the problems of knowing the number of positions in chess. Uri
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.