[rc5] Re: Re[2]: Distributed Chess Theory

Eric Gindrup gindrup at okway.okstate.edu
Wed Oct 29 18:13:55 EST 1997


     Who has 2^128 bits of storage lying around?  Not in this universe!
     
     If the evolution graph of chess weren't so tightly connected, then 
     search space partitioning wouldn't be so hard.  If there were a 
     transfrmation of the problem to another problem with looser coupling, 
     this would be a good thing!
     
     I really am starting to think that complete forward enumeration of 
     chess games is impossible.  Reverse enumeration through iteratively 
     increasing endgames would be more likely to have the potential to 
     completely analyze chess because no work is redundant (as long as you 
     work on a large enough set of k-piece initial sets) most moves reduce 
     the problem to a known problem (capturing a piece reduces the problem 
     to one already in the dictionary) and no illegal positions are 
     created.  Stalemate analysis would be a by-product...
     -- Eric Gindrup ! gindrup at okway.okstate.edu
     


______________________________ Reply Separator _________________________________
Subject: [rc5] Re: Re[2]: Distributed Chess Theory 
Author:  <rc5 at llamas.net > at SMTP
Date:    1997/10/29 23:28


Eric Gindrup wrote:
     
# 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. 
(big snip)
     
I wouldn't transmit the moves at all, I'd try a different approach, 
just working on the board positions, and ignore how the position was 
obtained, just where you can go from there.  This is the way I'd see 
it:
     
For each of the 64 squares, you can encode it in 4 bits what it 
contains, and overall have one bit for whose move it was.  So each 
board setup could be encoded with 64*4 +1 = a 257 bit number. 
     
So initially, there would only be one possible board positions.  A 
client would be responsible for downloading a board position, 
calculating all the possible board positions for the next move, and 
returning them to the server.  There is a finite set of possibilities 
for any next move (I estimate about 140) so once that client has 
retuned that block of infomation, the server would know that from that 
board setup, how many alternatves there are, and what they are.  The 
client would then grab another board position and return all positions 
from that.  The server would gradually build up a tree which would link 
all the possible board positions.
     
Eventually a client would get a board position which is in a winning 
position. It would then not calculate sub-boards, but just return that 
board with a flag about the status, and that branch of the tree would 
be ended.  That branch would have a score, and once a board had all 
its sub-boards with a score, it would then recieve a score itself and 
it would propergate back upwards.  Eventually, once all the braches 
had been calculated and scored, you would have a massive database 
where you enter a board setup and you take the move with the highest 
score attached.  Scoring could be complicated, on the simpliest idea 
you score 0 for a draw, 1 for white win, -1 for black win.  So if a 
branch has a combined total of 5, you know that that branch has 5 more 
endings in which white win over black.  If you cut it down that you 
only take the highest score you could eliminate a lot of the database.
     
How this could be implimented in practice could be as follows. 
(I find it easier to explain in pseudo-code)
     
Client reads board B(n)  and  recreates board setup 
Client scores B(n) to check for a win/draw.
     
If not a win/draw
     
1) Client calculated all sub boards SB(x) 
2) Clients tells server B(n) has x children 
3)  for 1 to x
    Sends SB(x)   1. if SB(x) is new server adds SB(x) to database.
                  2. server adds SB(x) to B(n)'s list of children 
                  3. server adds B(n) to SB(x)'s list of parents
     
If a win/draw
     
Returns B(n) with a score (win/draw) 
Server does the following.
1) marks B(n) with a score.
2) for each of B(n)'s parents - P(x) do:
   for 1 to x
     Has all P(x)'s children now got scores?
        Yes? a) Give P(x) a score from a total of its children
             b) connect to server and report P(x) with score (This
                will repeat step 1 and 2 with P(x) )
        No?  Do nothing
   end for
     
This make any sense?
     
The server would give out board positions that have no score and 
sub-boards yet, the clients would return with the score or a list of 
sub-boards.  Each sub-board problem would be independent, but the 
linking of the interboard relationships would be the larger problem.
     
The only major drawback I see is that some of the computing power is 
server side (scoring the parents of the scored children, but this is 
mostly database lookups and adding the total of ~140 children per 
parent, and should be minor because most of the computing would be 
client side calculating scores and next possible moves.  The database 
would be large, I don't know how many possible positions there would 
be, but I'd guess it would be about 2^128 with each position listing 
~140 parents and children
     
I'm almost tempted to write a small version of this to see if the 
algorithm works, I don't see anything wrong with it at first glance. 
Might do it for draughts.
     
The figures I used above were calculated as follows, they are only 
approximations to give an idea about scale.
     
257 bits for board:
7 types of pieces for each side  (R, Kn, B, Q, K, p and mp) where mp 
is a pawn that has just moved (needed for en passant)
= 14 possible pieces + 1 for a blank square = 15 possibilities for 
each square = 4 bits *64 squares = 2^256  (+1 bit for move)
     
~140 possible outcomes for any board position:
     
2 pawns   with ~3 possible moves =  6 
6 pawns   with ~4   "        "     24 
2 rooks   with ~14  "        "     28 
2 knights with ~8   "        "     16 
2 bishops with ~14  "        "     28 
1 queen   with ~28  "        "     28 
1 king    with ~8   "        "      8
                                   ===
                                  ~138
     
Database size ~2^128
     
32 pieces to be placed.  (64 squares (ignoring off the board)
     
  64!
------
(64-32)! (8!) (8!) 6*(2!)
     
~ 2^140  (reduced to 2^128 as a guess as to how many of these 
positions are actually obtainable.  I could be way off.
     
Comments anyone?
     
Martin
     
-- 
Martin Regan                    | email: martin at stheno.demon.co.uk 
"exigo spamos et dona ferentes" | www:   http://www.stheno.demon.co.uk/
     
PGP key at http://www.stheno.demon.co.uk/martin.asc        
----
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