Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: positions in chess <= 10^40?

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.