A110907 has been deleted

[N. J. A. Sloane]

----- Original Message ----- 
From: "Maximilian Hasler" <maximilian.hasler at gmail.com>
To: "David W. Wilson" <wilson.d at anseri.com>
Cc: "SeqFan" <seqfan at ext.jussieu.fr>
Sent: Monday, April 14, 2008 11:04 AM
Subject: Re: Re: A single integer N = a complete chess game


> On Mon, Apr 14, 2008 at 10:06 AM, David W. Wilson wrote:
>>  Concerning 176: The largest known number of possible [plys] from a legal
>>  position is 218:
>>
>> [FIDE definition of legal position elided].

I said the largest known number of plays, not plies. There is a position 
from which White can choose from 218 possible plays. The position, shown at

http://www.chessbox.de/Compu/schachzahl2_e.html

is, as far as I can tell, legal.

In other words, we can exhibit a legal position from which 218 plays are 
possible. This means that the branching factor of a chess game is 
potentially at least 218 > 176. Note that 218 is not a proven maximum, just 
the maximum known. It was found in 1964, and I have to believe a modern 
computational effort could dethrone it.

By promoting all pawns to queens and summing the optimal number of moves of 
each piece on an open board, we arrive at 321, which is an upper bound on 
the branching factor, although it can easily be reduced by interference 
analysis. For example, if two queens are both placed in optimal position 
(one of the four center squares), they lose 8 plays through interference. If 
one is placed on a nonattacked nearby suboptimal square, the loss can be 
reduced to 2 plays. This is the best you can do, so 321-2 = 319 is an upper 
bound.

The best 8-queens solution loses 34 plays to 8 optimal queens. It is 
possible that an 8-queen position with interference might do better, but 
probably not much, so we can confidently conjecture that the branching 
factor is probably < 321-34 = 287 based on queen interference alone.

The magic number is of course 256. If we can prove that no legal position 
admits more than 256 plays, we can shoehorn a play into a byte. It's a 
tantalizing computational problem.