Author: Reinhard Scharnagl
Date: 07:12:33 03/05/05
Hi all,
there is a second approach for a compact encoding having only a
very small restriction to positions compared to before.
Regards, Reinhard.
Compact Encoding of Chess Positions (estimated Average 152.5 Bits)
==================================================================
We handle here valid chess positions of the traditional chess game
and calculate codelengths for a special subset of RELEVANT positions
matching ONE simple restriction (without relevance for practice):
"If there are 9 or more promoted pieces there should be at most
5 knights standing on squares from line 2 to 7."
You hardly would find a notation of a played game including positions,
which could not be encoded by this method using at most 172 Bits, because
you would choose to promote into a knight only if a near mate is seen.
The encoding consists of two parts A and B.
Part A (common data)
--------------------
Here positions of kings, castling rights and e.p. pawns will be encoded:
1) we have three different variants of position encoding:
a) no king has castling rights (standard)
b) one king has castling rights
a) both kings have castling rights
a) no king has castling rights (standard):
Bit 0 - 5: white king coordinate
Bit 6 - 11: black king coordinate
Bit 12 : active color (w = 0, b = 1)
Bit 13 : flag if an e.p. pawn exists or not
code length = 14 Bits
b) one king has castling rights:
To mark this situation there will be used two neighboured positions,
by replacing the coordinate of the castling enabled king by a neighbour
a) left or right <=> left castling right (will include rook's position)
b) above or below <=> right castling right (will include rook's position)
c) diagonal <=> both castling rights (will include rooks' positions)
Bit 0 - 11: both such coordinates
Bit 12 : side having castling rights (w = 0, b = 1)
Bit 13 : active color
Bit 14 : flag if e.p. pawn exists
Because the castling enabled rooks has not to be encoded twice later,
in part B there will be savings of at least three Bits.
=> effective length < standard code length
c) both kings have castling rights:
To mark this situation instead of the original kings' positions
two identic pseudo-coordinates will be used
Bit 0 : white's left castling right (will include rook's position)
Bit 1 : white's right castling right (will include rook's position)
Bit 2 : black's left castling right (will include rook's position)
Bit 3 : black's right castling right (will include rook's position)
Bit 4 : active color
Bit 5 : flag if e.p. pawn exists
Bit 6 - 11: identic to Bit 0 - 5
Because the castling enabled rooks has not to be encoded twice later,
in part B there will be savings of at least three Bits.
=> effective length < standard code length
2) e.p. file number (only if need be)
if an e.p. pawn exists (priorily marked), here will follow:
Bit 0 - 2 : file number of the affected column
Because the e.p. pawn has not to be encoded twice later,
in part B there will be savings of at least three Bits.
=> effective length is unchanged
Teil B (left pieces' data)
--------------------------
All pieces not yet encoded in part A will be encoded here:
(thus no kings, castling enabled rooks or e.p. pawns to encode)
1) Filling matrix: (max 62 Bits)
For each undefined square will be encoded, whether it is filled or not.
The enumerating sequence is starting with A1, H8, A2, H7, ... until
the center of the board will be reached.
2) Color Bits: (max 30 Bits)
going from square to square marked by the filling matrix one bit is
added specifying the local used color.
3) Only if less then 28 pieces at lines 2 to 7;
coding mode (specific to lines 2 to 7):
a flag whether: 2*(number of pawns) < (number of sliding pieces)
4) Piece codes: (max 58 Bits) (max 30 pieces)
for each square marked by the filling matrix:
a) at the base lines (1 and 8) encode:
Queen = 11, Rook = 10, Bishop = 01, Knight = 00
b) at the inner lines (2 to 7) encode:
if no more pawn selection needed, see at a) for coding.
Mode 0:
Pawn = 0, Queen = 111, Rook = 110, Bishop = 101, Knight = 100
Mode 1:
Pawn = 000, Queen = 11 , Rook = 10, Bishop = 01 , Knight = 001
Extra savings
-------------
If 32 piece placements are known, the filling matrix will stop.
If 16 piece placements of one color are known, color bits will stop.
If 8 pawns of one color are known, the pawn selection is ommitted for
that color (also at inner lines). Of course second queens and bishops
upon same colored squares will be counted as promoted pawns like third
Rooks, Bishops or Knights.
No savings when encoding a 16th piece of one color, because the set
of used officers has not been reduced to the initial piece set to
make the coding scheme more flexible in general.
Coding Length
-------------
1) Maximum length 172 Bits:
Worst cases are where all non king pieces are placed at lines 2 to 7:
Pieces Pawns Officers Part A Part B (max)
30 16 14 14 + 62+30+0+58 = 164 ( 0 promotions)
29 14 15 14 + 62+29+0+59 = 164 ( 1 promotion )
29 13 16 14 + 62+29+0+59 = 166 ( 2 promotions)
29 12 17 14 + 62+29+0+63 = 168 ( 3 promotions)
28 8 20 14 + 62+28+0+68 = 172 ( 6 promotions)
27 4 5+18 sliding 14 + 62+27+1+63 = 167 ( 9 promotions)
26 0 5+21 sliding 14 + 62+26+1+57 = 160 (12 promotions)
2) Average length for 32 pieces 150.5 Bits:
Average code length at officers (16*2 + 48*3)/64 = 2.75;
Average saving of color Bits = 2;
Average saving of piece code Bits: = 6;
This will lead to an average length calculation:
14+62+(30-2)+0+(54.5-6) = 152.5.
Verification
------------
The results could lead to claim an estimated upper bound for
existing relevant chess positions:
average length (>= 31 pieces): 152.5 Bits
filling matrix redundances: - 1.1 Bits
e.p. bit redundances: - 1.0 Bits
passive king illegally in check: - 1.0 Bits
=> 2^149.4 = 9.416*(10^44)
But there still are a lot of impossible positions (e.g. pawn structure).
This page took 0 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.