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