Distributed Chess Theory Was: Re: [rc5] v3
Eric Gindrup
gindrup at okway.okstate.edu
Wed Oct 29 10:43:05 EST 1997
If the encoding of a position is sufficiently compact, it becomes
better to replace the first few dozen moves of a game with a board
position. Say a board representation is 500bits (wild, round number)
and a move is 12bits. After 41 moves, the board position is smaller
than the move list -- transmit the board position after (say) the last
multiple of 40 moves and any moves since that point. This is similar
to the intermediate position diagrams in published game descriptions
which are interleaved with moves.
The set of pieces can be represented with 32 bits (naively -- 1 bit
per piece) or 22 bits (3 bits for pawns of each color since pawns are
nondistinguishable). Then, as a game progresses, the number of pieces
reduces. Every time the number of pieces is reduced by a factor of
two, the encoding of a move shrinks by one bit (the "piece number"s
have an insignificant leading 0).
If the endgame dictionary is completed to 8-man positions, then there
are two halvings between the opening position and the endgame
dictionary. There are (wildly) 50 plys between the two and so 12 plys
are one bit shorter and 12 more plys are 2 bits shorter. The full
encoding of a ply is 5 bits for piece plus destination (<=6bits) and
thus four whole plys are removed from a complete game description by
this reduction.
It's not clear that this is an improvement.
As an alternative, something like "occupancy formalism" (from Dirac's
quantum mechanical methods) could be used. Then we only encode the
index of the move from a dictionary of every possible legal move (for
some piece). Such a dictionary is constructed by starting with the
64^2 possible start-square end-square possibilities and then heeping
only those possibilities for which there exists a move that some piece
can perform. For example, a1-b4 is removed because no piece can do
that. This simplifies the encoding of "unusual" actions (e.g.
castling) since the code unambiguously indicates which piece went
where (e1-g1 for White king-side castling, if the King is on e1,
otherwise a move by a rook or queen...) The original set of 64^2
transitions only requires 12 bits per ply. Fewer than 1/3 of those
moves can ever be legal, so you can usually get by with about 10 bits
per ply.
Such a play description can also be treated as a composition of
transitions between board positions with the semantics "take the
occupant of position 'x' and put it in position 'y'."
This dictionary could be brute-force applied by a client to any
generated board position... Illegal moves would have to be eliminated
immediately. Movement legalities would probably be most efficiently
evaluated through table lookup into a static array (similar to
"intelligent" non-wchar implementations of isalnum() and isdigit()).
So the array value for the move "a2-a3" would be (K,Q,B,R,N,P) =
(1,1,0,0,1) and would be hard-coded into a client.
Thus all possible 1 ply board continuations could be constructed in a
few thousand cycles (iterate through the table of moves (~1000 times)
* [check for piece at position (~2 cycles) + check for validity of
move (~2 cycles)] = ~4kcycles) The two tables are highly cacheable,
especially if the list of moves is sorted on source square (so that
empty squares can short circuit through slabs of the dictionary).
The most important question, though, is this: What is the goal?
If one intends to enumerate endgames, then one sends board positions
to the clients and forces exaustive analysis of that position by the
client. Different clients get different sets of pieces and different
starting configurations. There is a huge amount of redundant work
unless some way can be found to terminate branching that would result
in identical positions for different clients (which will both
subsequently evaluate the entire subtree from that point of
agreement). Again vertical partitioning of the search space is a
problem.
If one intends to play real-time chess, then reducing the encoding of
a position is vital. In fact, one would attempt to store as much
state information at the client as possible. It's still not clear
what a client could do from there. The best organization (off the top
of my head (which is probably flat)) would be to send different 1-ply
continuations to "personal proxies" and have them coordinate the
vertical partitioning with the clients *because* they probably have
much better bandwidth between eachother than with Bovine. Then the
proxies would have to report *something* every couple of plys back to
the central servers so that if a time constraint is approaching, a
move can be made and also so that deep trees can be farmed out late in
the game by the central server (from the deep tree returned by some
proxy).
If one intends to enumerate all possible chess games, then the problem
is to optimize the generation of board positions. Board size is
irrelevant since one would *have* to use iterative methods to do the
work. (Search depths are too large for recursion to be fast enough.)
Certainly, one doesn't have an evaluation function, but one should be
"back-computing" an evaluation function so that the end result would
be an optimal evaluator for chess. One would have to set up vertical
partitioning and require that clients "call back" every so often
handing back the positions that left their partition of the search
space. This is a highly processor bound operation if some way to
partition the search space can be found. It is I/O bound if one
cannot.
-- Eric Gindrup ! gindrup at Okway.okstate.edu
______________________________ Reply Separator _________________________________
Subject: Re: Distributed Chess Theory Was: Re: [rc5] v3
Author: <rc5 at llamas.net > at SMTP
Date: 1997/10/28 17:35
[snip]
I don't really understand what you're trying to say here. You want to
number the pieces, and have the list of still-active pieces be passed
along with everything else, so that another computer can renumber them
with (perhaps) fewer bits? You've already shot yourself in the foot by
having to pass on a numbered list of pieces. Maybe I'm just missing
your point.
My basic point is, trying to cut down the size by methods like this is
not feasible. They all depend on some prior knowledge. If we just pass
along the move list, we have everything.
--
**Join the largest computer in the world: http://www.distributed.net
1 in 18,446,744,070,000,000,000 keys works. I think we can find it.**
----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the
body.
----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.
More information about the rc5
mailing list