A single integer N = a complete chess game

[Jonathan Post]

Estimates of the number of legal chess games vary in the literature,
as do those for Go. I speak of formal literature going back to de
Groot, and to Cybernetics [Norbert Weiner, 1948]. The latter work led
to Arthur Samuels, who in the 1950s, developed an expert
checkers-playing program that learned from experience. Forty years
later, IBM Research's chess-playing program Deep Blue made history by
beating world chess champion Gary Kasparov. Today we have, through
monumental work by a well-publicized team, a good estimate of the
number of legal Checkers games (~ 5 * 10^20), and Kasparov founding a
political party that seriously oppsed Putin. [Jonathan Schaeffer,
Yngvi Bjornsson, Neil Burch, Akihiro Kishimoto, Martin Muller, Rob
Lake, Paul Lu and Steve Sutphen. Solving Checkers, International Joint
Conference on Artificial Intelligence (IJCAI), pp. 292-297, 2005.
Distinguished Paper Prize.]

Weiner gave perhaps the first mention of a computer chess algorithm in
the literatures, p.193:

"There is one question which properly belongs to this chapter
[Information, Language, and Society], though it in no sense represents
a culmination of its argument. It is the question whether it is
possible to construct a chessplaying machine, and whether this sort of
ability represents an essential difference between the potentialities
of the machine and the mind... The real problem is... to construct a
machine which shall offer interesting opposition to a player at some
one of the many levels at which human chess players find themselves...
To each sequence of moves it should assign a certain conventional
valuation... not too remote from those which good players would assign
them... At the stage at which the machine is to play once and the
opponent once, the valuation of a play by the machine is the minimum
valuation of the situation after the opponent has made all possible
plays. At the stage where the machine is to play twice and the
opponent twice, the vaulation of a play by the machine is the minimum
with respect to the opponent's first play of the maximum valuation of
the plays by the machine at the stage when there is only one play of
the opponent and one by the machine to follow. This process can be
extended to the case when each player makes three plays, and so on.
Then the machine chooses any one of the plays giving the maximum
valuation for the stage n plays ahead, where n has some value on which
the designer of the machine has decided. This makes as its definitive
play.
Such a machine would not only play legal chess, but a chess not so
manifestly bad as to be ridiculous."

To excerpt from wikipedia:

"Adrianus Dingeman (Adriaan) de Groot (Santpoort, October 26, 1914 -
Schiermonnikoog, August 14, 2006) was a Dutch chess master and
psychologist, who conducted some of the most famous chess experiments
of all time in the 1940s-60. In 1946 he wrote his thesis Het denken
van den schaker, which in 1965 was translated to English and published
as Thought and choice in chess.

"The studies involve participants of all chess backgrounds, from
amateurs to masters. They investigate the cognitive requirements and
the thought processes involved in moving a chess piece. The
participants were usually required to solve a given chess problem
correctly under the supervision of an experimenter and represent their
thought-processes vocally so that they could be recorded.

"De Groot found that much of what is important in choosing a move
occurs during the first few seconds of exposure to a new position.
Four stages in the task of choosing the next move were noted. The
first stage was the 'orientation phase', in which the subject assessed
the situation and determined a very general idea of what to do next.
The second stage, the 'exploration phase' was manifested by looking at
some branches of the game tree. The third stage, or 'investigation
phase' resulted in the subject choosing a probable best move. Finally,
in the fourth stage, the 'proof phase', saw the subject confirming
with him/herself that the results of the investigation were valid.

"De Groot concurred with Alfred Binet that visual memory and visual
perception are important attributors and that problem-solving ability
is of paramount importance. Memory is particularly important,
according to de Groot (1965) in that there are no 'new' moves in chess
and so those from personal experience or from the experience of others
can be committed to memory."

I am not speaking of the literature within the Chess world, as such, i.e.

    * John Nunn (2001). Understanding Chess Move by Move. Gambit.  An
International Grandmaster explains the thinking behind every single
move of many world-class games.
    * Jeremy Silman (1999). The Amateur's Mind: Turning Chess
Misconceptions into Chess Mastery. Siles Press.  A chess teacher
analyzes and corrects the thinking of advanced beginners.
    * James Eade (2001). Chess for Dummies. Gambit.  A comprehensive
guide for beginners.
    * Yasser Seirawan (2005). Winning Chess Strategies. Everyman
Chess. ISBN 1-85744-385-3.

These are deep thoughts, and I think it worth some effort to properly
answer Eric's question, and refine the estimates of Maximilian and
Ralf.

On 4/10/08, Ralf Stephan <ralf at ark.in-berlin.de> wrote:
> You wrote
>
> > >  What would be the most "economical way" to assign a single number
>  > >  to a complete chess game? I guess this number would be of googol-
>  > >  length...
>  >
>  > it is sufficient to use the number obtained from concatenating initial
>  > and final square of each move, i.e.
>  > G = sum( (a.i+64b.i)*64^2i )
>  > where i is the half-move, and a.i, b.i is starting / ending square
>
>
> You'll need additional bits for underpromotion, i.e., creating
>  a rook instead of a ueen from a pawn.
>
>  This scheme, in summary, will need 18 bits per move.
>
>  You can do much better by creating a list of all possible
>  moves from the start position, and choosing a predefined order,
>  finding the move position in that list; and doing so for all
>  possible positions. Now, there is a maximum of moves from any
>  position, should be less than 176 (what is it exactly?).
>  So, you need only 8 bits per move.
>
>  Now with a theoretical maximum of 5000? moves (in practice 200
>  but with the new endgame rules there's more possible) your number
>  is less than 2^200, but certainly less than 2^5000 or so.
>  That is, about 30 and 1500 digits, respectively.
>
>  Regards,
>
> ralf
>