Author: S. Loinjak
Date: 12:12:37 11/29/02
Go up one level in this thread
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.
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.