Author: KarinsDad
Date: 08:56:45 10/20/99
Go up one level in this thread
On October 19, 1999 at 19:34:54, Dann Corbit wrote:
>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 is NOT really that different then things such as having a bitboard (which
is what a lot of the algorithms have).
If I have 64 bits indicating whether a piece is on a given square, then that is
the same as asking the question "Is a chess man on this square?" 64 times. And,
of course, you could save bits if ALL 32 pieces are on the board and the 32nd
piece is found before h8 (assuming h8 is the last square checked).
And, 179 is nowhere NEAR 161. However, you have given me an idea on how to
handle some of my weirder cases (actually, I have used the idea before, but I
discarded it a LONG time ago, but there may be a way to make it work).
I'll let you know if it works out.
Thanks,
KarinsDad :)
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.