Author: Dann Corbit
Date: 16:34:54 10/19/99
A C.A.P. team member found an interesting way to encode a board position. It
seems competitive to the other methods I have seen for the worst case positions
and possibly can do much better. It seems to be a simple variation of the
methods of J. Nievergelt: Information content of chess positions, ACM SIGART
Newsletter 62, 13-14, April 1977.
Imagine (if you will) a game like 20 questions, but we ask it of the chess
board.
We start off with 64 questions, 1 for each square:
"Is a chess man on this square?"
If no, then we are done with the square.
If yes, we ask:
"Is the man white?"
So now we know the color.
Then (assuming the following ranking) [pnbrqk] we ask:
"Is it greater than a bishop?"
if (yes)
{
"is it geater than a queen?"
if (yes) then king
else
"is it less than a queen?"
if (yes) rook else queen
}
else
{
"is it greater than a knight?"
if (yes) then bishop
else
"Is it less than a knight?"
if (yes) pawn else knight
}
using the above scheme, we have 64 original questions for the squares,
followed up up to 32 questions * (1=color, up to 3 =piece) {The actual question
count is 2.584962500721 questions to determine piece on average}
That would be 192 questions = 192 bits if we don't try to squish the bits with
arithmetic compression and 179 bits if we do.
But we can have some savings. For instance, on the 1st and 8th ranks we do not
need to ask about pawns. There are some other minor savings as well (e.g. if
there is no king of one color and we are down to the last piece we know what it
is. e.g. if one king is in check and two pieces are left and one of them would
be in check we know which is the king...)
We need to add in e.p. and stm, but it seems that this method may have some
merit.
I suspect that some of the very, very clever types here might be able to squish
it even more.
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.