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

Martin Regan martin at stheno.demon.co.uk
Wed Oct 29 23:28:44 EST 1997


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.



More information about the rc5 mailing list