kuzminsk at taussky.cs.colorado.edu
Sun Oct 26 18:15:20 EST 1997
Sebastian Kuzminsky <kuzminsk at cs.colorado.edu> wrote:
] There are some fancy high-pack schemes, but a rough BOTE calculation
] will do for now. There are 64 squares, so it takes 6 bits to uniquely
] identify a square. There are sixteen pieces and sixteen pawns on the
] board. If each one has a 6-bit square identifier, then thats 32 * 6 =
] 192 bits. The 16 pawns may have been promoted to any of four pieces, or
] be un-promoted in which case they may be allowed to en-passant right or
] left or not at all, that's seven options for another another 3 bits
] each, 16 * 3 = 48. Finally, both sides may be allowed to castle long or
] short, 2 bits per side, 2 * 2 = 4 bits. What did i forget?
] That's 192 + 48 + 4 = 244 bits, or 30.5 bytes.
JP Rosevear <webmaster at usjc.uwaterloo.ca> wrote:
] This is true, however for chess engines this smallest way is not always the
] fastest way. Some sort of mailbox representation or bit board
] representation is necessary. In addition, encoding by the above method
] makes the evaluation function extremely difficult to write as information
] extraction is an involved process.
I agree that we want to make the evaluation function efficient by
having it process easily digested information. It will most likely be
beneficial to use different encoding formats 'on the network' and 'in
core'. The worker clients get a board from the server in a high-pack
format, decode it to a larger, easily processed format, and do the
processing. The resulting boards are encoded in the dense network
format and sent to the server.
For this chess engine we benefit from trades that increase CPU load
while decreasing network load. The tighter we can pack the board, the
more boards we can consider fully. We're I/O bound, every bit helps.
That said, how about this encoding:
First, a 64-bit occupancy grid, with each bit representing a square
on the board. Following the occupancy grid are a variable number of
pieces, one piece for each marked bit in the board occupancy grid. Each
piece has 1 bit for color, then 3 bits to select between rook, knight,
bishop, queen, king, pawn, pawn allowed right en-passant, and pawn
allowed left-enpassant. After all the pieces there are a final 4 bits,
for white and black allowed to castle long and short.
With all 32 pieces on the board, that's 64 + (32 * 4) + 4 = 196 bits,
or 24.5 bytes. For every missing piece, you save 4 bits.
Open problem: how do you keep track of draw-by-repetition? Does
this information need to be encoded in the board sent between the worker
clients and the server?
Sebastian Kuzminsky wrote:
] There is a tradeoff between having the clients go deep into their own
] little branch of the search tree and having them go shallow. If the
] clients go deep and only return, say, the best 25 positions three ply
] ahead, then the intermediate search (all the other 27000 positions
] examined) are lost. If there was a long-term payoff sacrifice in one of
] the non-returned branches, we'll never find it. On the other hand, we
] cant return all 27000 positions, becuase the network would choke. (Hm,
] or we could all go buy fiber connections to the backbone.
JP Rosevear wrote:
] Your right, there is a serious IO problem. I'm not sure this is the right
] way to approach it though. A computer like Deep Blue wouldn't lose those
] branches, and hence we're at a disadvantage.
I cant think of any other way to do it. Either the clients tell the
server what they have found, or they dont. The distributed.net computer
doesnt have the internal bandwidth to support communication of the
magnitude required for sending back all the branches. There has to be
imperfect, premature client-side pruning. (I'm no computer chess
expert, and i'd love to be proven wrong here.)
I dont know how serious this I/O disadvantage is. The more i think
about it the worse it seems...
JP Rosevear wrote:
] I emailed Remy de Ruysscher looking for information and offering
] help. In addition the distributed.net home page lists it only as a
] possible project and states that he is organizing programmers at this time.
I mailed him too, but havent heard back. I dont know how his
development is going.
Tangentially, development with the 'bazaar' model is frustrating to
enthusiastic outsiders. For some great observations on the open
development model, see:
JP Rosevear wrote:
] Perhaps another project that could be considered would be the continuation
] of the table base classes generated by Ken Thompson. We could probably
] knock out 6 and 7 man classes in very short order.
These projects are similar enough that if we do one, we get the other
almost for free.
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.
More information about the rc5