|
Re: the name of a game of chess
|
Tom Ritchford
|
May 25, 2001 13:37 PDT
|
Cliff Harris wrote:
| | Are you trying to find a single "best" naming scheme, or is it reasonable to
have different naming schemes for different situations? E.g., the key to look
up a game in the database may be different from the URL used by an
HTTP client.
That seems perfectly reasonable to me.
|
absolutely. for the moment I want to look at "all" possible names.
"best" isn't going to be clear for a while!
| | | | 1.1. naming by move index
eg: chess/0/5/2/16/5
|
As the game gets longer, the string gets longer. There are at least four
characters per move
|
at least two characters per move! at most three except perhaps
in pathological cases. in fact, you can compress it to about
1.7 characters per move...
but you can do a lot better than that.
see Appendix I.
| | so a 50-move game requires over 200 characters. Also, the
effort to compute the position increases with the number of moves: can we say
O(N), where N is the number of moves? Maybe it gets slightly easier to compute
legal positions as pieces are captured, but still, any technique that requires
significantly more CPU as the length of the game increases seems flawed.
|
ANY mechanism that doesn't have a cache is going have to take
O(N) to at least validate the position.
If we represent the board position, then we have a nasty
conceptual issue that it's very hard to tell the difference
between a legal position (one that can be arrived at by applying
the rules of chess from the root starting position) and a similar but
illegal position (one that could never have been arrived at from
the root).
So we can't readily validate the board position this way.
It could be a clever fake.
And we also have the disadvantage that there's no way to do
simple things like "go back one move"...
| | One advantage, of course, is that the whole game is encapsulated, so the
50-move rule and the "three-repeats" rule (I'm not sure what the
proper name of
this rule is) can be employed.
|
I've lost interest in those! ;-D What I really mean is that
those special cases are unimportant -- it doesn't break the game
one iota if we ignore them and we can put them in later with no
issues. Players will be marking games as drawn anyway...
they can mark the triple repeats as draws and won't even get
into 50 move situations.
| | | | rnbqkbnrpppppppp32PPPPPPPPRNBQKBNR
rnbqkbnrpppppppp20P11PPPP1PPPRNBQKBNR after one move
rnbqkbnrpp1ppppp10p10P11PPPP1PPPRNBQKBNR after two moves
rnbqkbnrpp1ppppp10p1P19PPPP1PPPRNBQKBNR
rnbqkbnrpp2pppp10ppP19PPPP1PPPRNBQKBNR
(can you do this without a board??)
to disambiguate positions, you'd also encode other data
about en passant and castling information some of the time.
c, C means black, white can castle king side
d, D means black, white can castle queen side
s,t,u,v,w,x,y,z are the 8 possible files for ep capture.
so the last position would be completely disambiguated with:
rnbqkbnrpp2pppp10ppP19PPPP1PPPRNBQKBNRcdCDv
|
|
| | Although in the example you give, the string looks quite ugly compared to 1.1
above, in fact the strings in this method are always the same size, roughly.
|
Ugly? I thought they were quite nice looking!
| | (You could make them always the same size, by using x for a blank square:
inserting the number of blank squares instead is just a simple compression
technique.)
This technique allows for transpositions; i.e., the same position
arrived at by
different sequences of moves. If we want to ask, "Has anyone reached this
position before, and what did they do?", this method is the best one.
|
yes. I intend for this to be one of the two database indices!
| |
However, we also need to include history back to the last
irreversible move, if
we want to account for the 50-move and three-repeats rules.
|
as I mentioned before, this is now a moot point because it never affects
non-terminal games.
NB: only die-hard math fans should read beyond this point.
Appendix I: compressing the move sequence.
A very interesting result that I can't find my proof but will
redo here is that with the move sequence notation, you can
make the games of chess "dense" in the space of all finite
bit strings.
By "dense" I mean that there is a representation
of legal games of chess as bit strings such that
1. every game of chess corresponds to a unique finite bit string.
and
2. every finite bit string is either:
a. the initial segment of a game of chess or
b. has an initial segment that's a TERMINAL game of chess
(ie, one from which no legal moves may be made).
sketch of proof.
consider representing the first move.
there are 20 possible bit streams for the 20 possible first moves
00000 through 10011
represented as the following unique segment:
00000 00000
...
01001 01001
01010 1010 (because 10100 is not possible)
01011 1011 (because 10110 is not possible)
...
01111 1111
10000 10000
In other words, you emit bits one at a time until you
end up with an unambiguous move number.
so this in turn maps into the natural numbers in a neat way.
reverse each bit string.
then, put a 1 in front of it.
and read as a binary number!
this gives a one-to-one mapping between natural numbers
and bit strings so each natural number can be thought
of representing a chess position in an unforced way.
so, my guess is that you could represent a sequence moves
in an average of less than 6 bits per move.
almost all famous openings can be represented in 16 bytes.
for that classic 50 move per side game, we are talking 600 bits
or 75 bytes of information.
Appendix II: compressing the board description.
here's a simple way to represent it.
each square has 13 possible values (6 pieces per side and empty)
so we fit each square into a nibble (a nibble, if you remember, is
half a byte, or think of it as a hex digit from 0..15)
and there is one nibble for the en passant square. (1..8 or 0 means
no en passant)
and one bit for: white or black; white q castle; white k castle;
black q castle; black k castle.
damn, that's 5 bits and it's irreducible!
reorg a little...
a nibble for en passant
a nibble for castling
a byte for the move number, mod 256
(really, we only need rely on the least significant bit, which is
white or black...)
64 nibbles of board or 32 bytes. 1 status byte (ep, castling). 1 move byte.
total, 34 bytes.
...electronic a cappella madness <http://volectrix.com>.........
...extreme internet radio <http://extremeNY.com/radio>...
|
|
 |
|
