Conference rusure::math

No, but I worked out once that the number of positions with White to play
is different from the number with Black to play.   This was as part of my
grand and unsuccessful campaign to prove that chess is not a win for Black,
or to prove that it's hard to prove it.   Another (easier) spin-off: after
each side had made a move, there are 400 possible positions.   Prove that
at most 76% of them are wins for Black.

    I haven't heard about anyone even trying.  The fan out of the game
    tree is huge.   With 20 legal moves on the first move, and 20 more
    on the second you are already at 400 possible boards.
    
    Martin H.

>>    Has anybody fixed how many chess games are possible ?
     
     With cooperating opponents, the number of possible chess
     GAMES is infinite.  The two sides just keep playing and
     never checkmate or stalemate the other, and never agree
     to a draw or claim a draw.  There are rules which allow
     a player to claim a draw, but they don't require it.
     This "loophole" allows a single game to reach an arbitrary
     number of moves.
     
     On the other hand, only finitely many chess POSITIONS
     are possible.  I think I have seen two attempts (in computer
     chess books) to place a loose upper bound on the number.
     I think they were more trying to show carefully that
     there were only finitely many positions, as opposed to
     trying to get a "good" upper bound.
     
     One example at a loose bound:
     
          the possible pieces are:
     
          Unmoved King, moved King [for castling, it matters]
          Queen
          Unmoved Rook, moved Rook [for castling, it matters]
          Bishop
          Knight
          Pawn immediately after double advance [and so perhaps
               subject to en passant capture], Pawn not
               immediately after double advance
     
     So, the possible contents of a square are one of nine
     "pieces" of either color, or empty, for a total of nineteen
     possibilities for each of the sixty-four squares.  This
     gives a bound of 19^64 (approx. 6.9 * 10^81) "positions".

          Lisp> (expt 19.0l0 64.0l0)
          6.9219819261370875766369566654042L81
     
     But wait!  This doesn't take into account repetitions,
     the fifty move draw rule, the exceptions to the fifty
     move draw rule, and anything that I may have forgotten
     to include.  So to each of these positions you have to
     attach a small number of move counts.  Say one count
     for previous occurrences, with values 0, 1, and "2 or
     more".  Another count of moves without a capture or pawn
     advance, with values up to 100 or more (I believe this
     is the current limit in the rules).  This multiplies
     the above number by 3 * 101.
     
     I vaguely recall that one of the estimates I read was
     in the 10^60 to 10^70 range, but I'm not sure.
     
     Anyway, it is a lot, but it seems to be less than a "googol"
     (10^100).
     
     Dan

    Of course one can reduce Dan's count by noting that there can be
    only 1 king per side, only 8 pawns, 10 rooks/bishops/knights or
    9 queens on a side, only 8 squares where _en passants_ are allowed,
    1 square permitted for a castleable King, etc., etc.
    
    But discussions of this sort belong in the CHESS conference.  (KP7).
    
      John

    Even cooperating players cannot produce an infinite game.  The 50
    move rule draw may be forced by tournament director, i.e. this draw
    need not be claimed.
    
    CWS

>    But discussions of this sort belong in the CHESS conference.  

I disagree - what is of interest here (at least to game theoreticians) is
estimating the size of the game tree. As computers grow more powerful, the
extent to which they can deal with (i.e. form a game value estimate on) a
tree of this size is at least of passing interest, and this has little to
do with the way people play Chess. 

I think the estimate of 10^81 positions is off by about 50 orders of 
magnitude, but I haven't had time to complete my analysis yet. Finding an 
upper bound with that kind of improvement is good mental exercise and quite 
worthwhile.

Lynn Yarbrough 

The number of optional placements of Chess pieces is maximized when all the
original pieces are on the board. This is easily established by computing
the change in number of positions when one or more pieces is removed from
the full set. With all pieces on the board, there are 120 legal pawn
configurations (8 files* 15 positions for each pair of B&W pawns). Of the
remaining pieces we need to distinguish: 2K, 2Q, 2WB (the B's that run on
White squares), 2BB, 4N, 4R. Once a pawn configuration is set, there are 48
squares left and they can be filled in 

	48!  4!   4!   2!   2!   2!   2!
	--------------------------------- = 48!4!4!/32! ways,
	32! 2!2! 2!2! 1!1! 1!1! 1!1! 1!1! 

and 120*48!4!4!/32! is about 3.2*10^30.

The sum of all the positions over all numbers of pieces is dominated by 
this term, and the total is less than 4*10^30.

Lynn Yarbrough 

While there are only 15 positions of a single white pawn and a single black
pawn in a file (ignoring the "en passant" flag), this gives 15^8 total
pawn positions, which is ~10^7 times as big as 15*8...

Also, once pieces are captured it is common for there to be more than two
pawns of the same color on a given file, so this increases the number of
possible pawn positions; this may actually cause the number of positions
with a few pieces missing to exceed the number of "bloodless" positions.

By the way - I know this is MATH and not CHESS, but counting positions
requires understanding the rigor in the chess rules, hence the following
question:

	When a pawn reaches the 8th rank, can you "promote" it to a pawn?
	(I know its stupid, but is it LEGAL?)
	(and of course, if its legal, someone has to come up with a
	 puzzle in which its the key move...)

     Re .8,
     
>>     	When a pawn reaches the 8th rank, can you "promote" it to a pawn?
>>	(I know its stupid, but is it LEGAL?)

     No, it's not legal.  It can promote to a Queen, Rook,
     Bishop, or Knight, but not to a King or Pawn.
     
     Dan
     
     P.S.  There are no restrictions limiting you to one Queen,
     or one Bishop on each color, or anything like that -- you
     can promote to a Queen, Rook, Bishop, or Knight no matter
     how many of them you already have on the board. 

        Sorry Lynn, but I have to disagree also.
    
    There are 2 points that I disagree with:
    
    1)  You account only for those positions without captures, on the
    basis that it dominates all other postions.  I believe that the
    sum of all other positions from all other valid piece combinations
    is far greater than the number of positions for any single piece
    combination.
    
    2)  >The number of optional placements of Chess pieces is maximized when all the
	>original pieces are on the board. 
    Not true.  Allowing the capture of a single enemy pawn allows up
    to 2 of your own pieces to become Queens and one of the enemy's.  The 
    combinations gained are far greater than those lost.

    3)  Its an arguable point, but I would agree with Dan's implications
    that certain 'state' aspects (able to en-passant, able to castle, etc)
    should be counted as part of the position.

    I would say rather that your number (3.2*10^30) is a good lower bound
    on the number of chess positions.
    
    --  Barry

     From my modest library at home:  :-)
     
     N. A. Krinitskii, in M. M. Botvinnik's Computers, chess,
     and long range planning, gives a formula which Botvinnik
     evaluates to approx.
                                      55
          2.5 * 64! / 32!, or 1.6 * 10
                               
     Botvinnik claims that Shannon had arrived at the figure
       43
     10  ; this was probably in Shannon's original paper on
     playing chess by computer.  Botvinnik was (three times) the
     world chess champion.  The 64! / 32! is the first term
     of a sum which Botvinnik evaluates or estimates at being
     2.5 times the first term.
     
     David Levy in Chess and Computers comes up with on the
     order of
                           2       6        43
          64! / (32! * (8!)  * (2!) ), or 10  
                                          50 
     without pawn promotions, about 2 * 10   allowing for
     promotions.  Levy's first figure is just the dominant term
     of a sum which he doesn't evaluate. 

     If you are curious I can type in some of their reasoning.
     
     Dan

Right, I miscalculated the number of P configurations, and did not 
calculate the promotion possibilities well. Still, ...

>    1)  You account only for those positions without captures, on the
>    basis that it dominates all other postions.  I believe that the
>    sum of all other positions from all other valid piece combinations
>    is far greater than the number of positions for any single piece
>    combination.

With two lone K's there are 64*63 positions (some not legal); with each 
added piece the number increases *by an order of magnitude or more*, to
reach 10^~40; so the total for <= 31 pieces is < 11% of the figure for 32.
(Compare 100 with 10 + 1 + .1 + ...) 
    
>    3)  Its an arguable point, but I would agree with Dan's implications
>    that certain 'state' aspects (able to en-passant, able to castle, etc)
>    should be counted as part of the position.

Positions in which castling is legal must be about 1/100000 of the total.
The K must be on 1 of 64 squares AND the R must be on the board AND on one
of 64 squares AND all intervening squares must be empty AND the K square
and all intervening squares must not be attacked AND the move history of K
must be empty AND the move history of R must be empty. 
En passants are far more common but still in the noise. 

    How many positions are possible when one player is acting to limit
    them?  (While still playing reasonably.)
    
    
    				-- edp 

     Oops, I left something out of .11.
     
     The first formula, which wasn't listed, was only 1/16
     of the number of positions.  It was this which was
     approximated by Botvinnik to be 2.5 * 64! / 32!, or
               54
     approx. 10  .  When multiplied by 16 this gave his final
                         55
     estimate of 1.6 * 10  .
     
     The 16 is the castling state, which is a factor of 4
     per player:
     
          left castling only available
          right castling only available
          castling both sides available
          castling not available on either side
     
     So the position count can be computed ignoring castling;
     then just multiply by sixteen.
     
     Finally, Krinitskii/Botvinnik explicitly ignored
     repetitions because they were discussing a solution of
     the complete game tree.  With full information, "best
     play" means you don't bother to repeat a position.  (I
     don't think that is obvious except when the side with
     the full information already has a won position.)  I
     can't remember if the other estimates mentioned repetitions.
     
     Dan

    
    	I know this Note is very old, but I was looking for the answer
    	to this very question, and the ol' dire/titl=chess found this
    	Note.  Anyway, I heard on PBS (I think that's where I heard it)
    	way back, that there were more possible chess games than there
    	are atomic particles in the known universe.  That seems like a
    	lot.  :^)
    
    								  Mike
    

   Re:       <<< Note 914.15 by BRAT::SMITH "Never say never, I always say." >>>

Mike,

   I won't attempt to quote specific numbers because
   
      1) I don't have them and
      2) You would just have to take my word for it,
      
   but, here's a general explanation of why its that way.
   
   The number of chess games is calculated from the number of
   possible end positions times the number of possible move
   sequences for white and black that get to each position.
   Both of these numbers are combinatorials, functions which
   grow so fast that they quickly outpace any mere physical
   number.
   
   Just calculate n! for a few terms and you'll see a very
   limited version of this so-called "exponential growth".
   Next, imagine calculating 64! divided by 16! divided by 48!.
   This is the number of different patterns of 16
   indistinguishable pieces on the 8x8 board.  When you
   distinguish between the pieces, it gets bigger!
   
   Now imagine calculating something to the 64! power.  That is
   the kind of outrageous calculation that is needed to start
   calculating the number of possible chess games.
   
   I hope you can understand why the assertion you questioned is
   true, even if you can't (like I can't) quote the numbers.
   
fwiw,

   Dick

    on a side comment, it is known that computer chess programms get
    much stronger in end games than humans, this is due to less pieces
    on the board, hence less positions to examin relatively, hence the
    depth of the tree search is more for the same amount of time used as
    compared to the depth of the tree in early stages of the games.
    
    it is like a trade of between breath of the tree to that of the depth.
    
    i read somewhere about a poor human player who played some chess
    programm, where the chess program saw a mate in 50 or so moves ahead
    in an end games ! i.e on best replies by the human, mate will happen
    in 50 moves, offcourse if the human playes worst moves, mate will be
    in less moves.
    
    /nasser

    re .17
    
    >it is known that computer chess programms get much stronger in end
    >games than humans, this is due to less pieces on the board, hence less
    >positions to examin relatively
    
    eh?
    
    All the computer chess programs I've ever played have been rubbish in
    the endgame. And for why? Well, quite often the line to take in the
    next 20 moves is 'obvious'. It requires very little calculation for me
    or any other competent human. The computer still has to calculate all
    the rubbish variations to see the light at the end of the tunnel - eg a
    queened pawn.
    
    While that is often true in the endgame in the middle game things are
    very different. Seeing 6 or 7 moves ahead for me requires a lot of hard
    calculation because each position along the way has lots of 'good'
    candidate moves I have to consider. This is no skin off the computers
    nose because it was always going to calculate these variations along
    with the garbage anyway.
    
    The net result of all this is that I can 'see' a lot further ahead in
    the end game and the computer can 'see' a lot further ahead in the
    middle game.
    
    Brian
    

    
>   The net result of all this is that I can 'see' a lot further ahead in
>   the end game and the computer can 'see' a lot further ahead in the
>   middle game.
    
    so do i  !
 
    Georg

    
      p.s. :  Brian, i would have wrote the same reply
                     - but my english isn't to good
    

    Re .17, .18
    
    Though the reduction in number of pieces allows computer programs to
    search more deeply it alone is not sufficient to make computers
    stronger than humans. There are two techniques that do:
    
    1) Some simple endgames have been analyzed completely using retrograde
    analysis, allowing computers to play them 'perfectly'. This analysis
    is available on CDs covering most endings with up to 5 pieces on the
    board.
    
    2) Transpostion tables by which computers avoid analysing the same
    position twice are much more effective in the ending than earlier in
    the game. Computers that have large enough tables are generally
    stronger in the endgame than in the earlier stages. Most older/cheaper
    computer chess games do not have the RAM needed for the tables.
    
    Peter

>    1) Some simple endgames have been analyzed completely using retrograde
>    analysis, allowing computers to play them 'perfectly'. This analysis
>    is available on CDs covering most endings with up to 5 pieces on the
>    board.
    
    Any of these CD's for sale?

    The CD's are on sale. There are two of them. I have the details at
    home.                                                  
    
    Peter

    The price of volume 2 is $10 cash, or cheque payable to Bell
    Laboratories, sent to
    
    Ken Thompson
    Bell Telephone Labs, Room 2C579
    600 Mountain Avenue, Murray Hill
    New Jersey 07974/USA
    Email: [email protected]
    
    Volume 2 contains the following 5 piece endings
    BBvB, BBvN, BNvB, BNvN, NNvB, NNNv, PBvB, PNvB, PRvQ, QBvB, QBvN, QNvB,
    QRvQ, RBvB, RBvN, RBvQ, RNvB, RNvQ, RRvQ.
    
    Peter