Author: Guido
Date: 06:56:40 11/01/99
Go up one level in this thread
On November 01, 1999 at 00:07:07, Ratko V Tomic wrote:
>I see now, you need the shortest worst case position. You goal of 160 bits is
>just about as big as the entropy of the all chess positions. Namely, if, to
>start with, you take 32 regular pieces (without promotions and captures), you
>could first encode in 64 bits the occupied/empty square bitmap, then for the 32
>occupied squares you can look at all the permutations of the 32 symbol string
>KQRRBBNNPP...kqrr...pp which gives you NP (number of distinct permutations) =
>32! / (swap symmetry), where the swap symmetry removes double counting whenever
>identical pieces are exchanged among themselves, and which contains factors
>(2!)^6=64 for {R, B, N, r, b, n} and (8!)^2=1.6*10^9 (for pawns). So the total
>symmetry divisor is about 1.04*10^11, while 32!=2.6*10^35, which gives total
>distinct permutations of NP=2.52*10^24, which fits in 81.6 bits. So the total of
>bits for the fully occupied board (without captures, promotions, castle or ep
>status bits) is 82+64=146 bits, leaving 16 spare bits to cover other cases (i.e.
>the remaining cases are allowed to contain as many positions as 65535 times the
>number of full board positions).
.......
As I said in a message, I follow your discussion with KarinsDad, also if not all
is clear for me.
But this part of your computation seems wrong to me (or did you do this
intentionally for reasons that I don't understand?).
The number of different positions, starting with 32 regular pieces (without
captures, promotions, castling, ep) should keep into account that pawns can
occupy only 48 squares, and therefore IMHO should be computed as follows:
Different dispositions of pawns: 48! / (32!*8!*8!)
Different dispositions of remaining pieces: 48! / (32!*(2!)^6)
(Here 48 = 64-16 are the squares not occupied by pawns)
Total dispositions: (48!/(32!*8!))^2 / 64 = 2.14 10^40 ===> 134 bits
I hope to give an help to your arguments, but the problems arise with promotions
and the worst case is when 12 promotions (if 12 is the max) are equally divided
among White and Black and make almost equal the number of Q, R, N and B in each
side (e.g. 4, 3, 3, 3).
Regards
Guido
This page took 0.01 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.