17
Nov
Posted by jack as gdrw.com
Chess is a finite game - the 50 move rule and the 3 repeating
positions rule mean that no game can go on forever (in fact the
maximum game is something under 6000 moves I think?).
Therefore there are a finite number of distinct possible games (a
distinct game being characterised by a distinct sequence of moves).
However this is clearly a very big number :). I want to find the
smallest upper bound of this number.
In a book by Hardy he claims in a footnote that this number is around
10^(10^50) - however I'm sure this is far too big!
To answer the question please state the smallest upper bound you can
find - and justify it sufficiently that others can verify it is
correct.
If this is answered, I may repost the question with the aim being to
find a new lower number.
Thanks - DelardFurthermore, after 8 moves each pawns can promote to queens, rooks,
bishops, or knights. For purposes of calculating an upper bound, the
greatest number of permutations is most likely to result from
promotion to queens. This leads to a maximum of 18 queens on the board
assuming both sides promote all of their pawns to queens. However,
they do tend to get in each others' way which reduces the number of
possiblities quite a bit. Also you have to be careful not to checkmate
(or stalemate) your opponent as this reduces the length of the game
and thus the number of moves and permuatations.
PS racecar-On a side note, the a and h pawns can move towards the
center by capturing, where they can then potentially move to four
squares like the other pawns.I figured it was an interesting question - people may have a look more
out of curiosity than money. Anyway - OK then - I'll up it a bit.Some slight improvements:
The a and h pawns never have more than 3 moves available, so the
maximum number of possible pawn moves available at any given time may
be taken as 30 rather than 32.
Each player can castle at most once, with 2 choices of how to do it.
So we can get an upper bound for number of games without castling, and
then multiply by the maximum number of moves, because that is the
number of places we can 'insert' the castling move. We also multiply
by 2, because of the 2 ways to castle. So an upper bound is: (upper
bound w/o castling)*6300*2*6300*2. (multiply each factor twice, once
for each player).
Since we have taken away 4 moves (2 pawn moves and 2 castling) the
maximum number of moves available is 135.
So my new upper bound is 135^12600 * 12600^2, which is less than 10^26851.PPS and sometimes pawns can move to 5 possible squares, (once for the
six middle ones of each color)The king never has more than 8 moves available even with castling, so
we can take out the castling factors. At most one queen can cover 27
squares. The next one can cover at most 25, and the next one at most
24. So we can knock off 15 moves from the total.
302^12600 ~ 10^31248Also, the queen and bishops only command their maximum number of
squares (27 and 13 respectively) from the central 4 squares of the
board. The queen and both bishops cannot all simultaneously occupy
these squares without blocking each other. From any other square, the
queen commands at most 25, and bishops at most 11 squares. So we can
drop the maximum number of available moves by 2. Actually by 4, if
you check it out. So that's 131 moves total.
But I just realized I forgot about pawn promotion. If you have more
queens, say, you have more moves available. I'm sure this number can
be improved upon, but with 9 queens, there are certainly never more
than 317 moves available. (I just took out the pawn moves and added
27 for each queen).
So now my answer is 317^12600*12600^2, which is less than 10^31522.Seems to me, on a pawn's first move, it has at most 4 possible
choices: forward one, forward 2, capture left, capture right. Any
time after the first move, there are at most 3 possible moves for each
pawn, if we don't count promotion to different pieces as different
moves. Only three of the four starting moves are available to the a
and h pawns. Yes they can move to a more central file by capturing,
but then the forward two option will no longer be available, any they
will still have only at most 3 moves available at any time, same as
any other pawn.Here's a very interesting essay that discusses an algorithm for
finding the number of possible games (scroll about halfway down the
page to "THE SECOND WANT"):
http://www.iw.net/~a_plutonium/File127.htmland its not that hard to come up with an upper bound - it doesn't have
to be that complicated...Great work so far! I've upped the money to encourage someone to take
this a step further - ie improve on the smallest number so far. Please
express results as 10^n for ease of comparison.First the maximum game length: I don't know what this number is, but
an upper bound is easy. The 50 move rule states that a game is drawn
after 50 moves (by each player) during which no capture is made and no
pawn is moved. There are 16 pawns which can each be moved at most 6
times. There are 30 pieces which can be captured. Therefore a game
cannot be longer than (6*16 + 30)*50, or 6300 moves for each player.
That's 12600 moves total.
Second, the maximum number of distinct moves possible at any given
time: each player has 8 pawns which can each make a maximum of 4
possible moves (forward 1, forward 2, capture left, captured right).
That's 32 possible pawn moves. Each knight commands at most 8
squares, for a total of 16 possible knight moves. Each bishop
commands at most 13 squares, each rook at most 14, the queen at most
27, and the king at most 8. Then there are 2 possible castling moves.
So the maximum number of moves which could ever be available is:
32 pawn moves
16 knight
26 bishop
28 rook
27 queen
8 king
2 castling
--------------
139
Therefore, a (not very low) upper bound on the total number of
possible games is 139^12600, which is slightly less than 10^27002
So, my upper bound is 10^27002.Hello Delard,
I wonder if you've seen this website already. Someone seemed to have
tried calculating the maximum number of moves. I'm not sure if the
number stated here is definite for you already:
Sensei's Library: Number Of Possible Outcomes of a Game:
http://senseis.xmp.net/?path=Speculation&page=NumberOfPossibleOutcomesOfAGame
http://senseis.xmp.net/?diff=NumberOfPossibleOutcomesOfAGameFound a reference that says the max game length is 5949 moves.
If you believe this, then a better upper bound is 302^11898 ~ 10^29507
There are only 20 possible first moves (for white and black), which
further drops the total to 10^29505.
http://membres.lycos.fr/albillo/cboard01.htm
has the maximum number of moves possible for a variety of combinations
of pieces, but not for 9 queens.
