Author: Les Fernandez
Date: 17:24:23 10/19/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.
Hello Dann,
Well to start things off one might consider wasting 2 questions at the very
beginning of your question tree to help "squish" your data set down by asking
the following: Question 1 are there any blank rows on the chess board, Question
2 are there any blank columns on the chess board. ie lets say that question 1's
response is "no" then we have only wasted 1 question however, in which case we
would not have to ask whether or not that particular row is blank. However if
the answer is yes then we must add one question at the beginning of each row to
determine if the current row is blank. With a yes we are assured of there being
atleast 1 blank row (close break even point) since we would not have to concern
ourselves with any question regarding any of the 8 squares in that blank row.
This saves 7 questions since we needed to ask 1 question whether the row was in
fact blank. Savings begin to get realized when more then 1 blank row exists.
This could perhaps be applied to columns also. It will be interesting to see
what other tricks people out here have up there sleeves <s>.
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.