webmaster at usjc.uwaterloo.ca
Sun Oct 26 14:02:12 EST 1997
> First of all, how much data does it take to encode a chess position?
> 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.
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.
> What would the high-level architecture be like?
> You would probably have the master server distribute board positions
>to the proxies and clients. The clients would get a board position,
>move a few ply ahead and evaluate, basically doing a few steps of a
>breadth first search from a given starting position. After a while the
>client stops searching and returns the best of the positions it's found
This would cause inappropriate pruning of the search tree, as you would be
eliminating all but one branch based on only, say, 8 ply of searching.
Positions in the pruned tree would be missed, even if they are better.
That being understood, I understand your concerns due to the IO problem
> The I/O problem.
> Chess has a high enough branching factor that you cant return all the
>positions you find. You have to select the best few. The branching
>factor of chess is position and context dependent, as an estimate of the
>mid-game branching factor lets use 30. If the clients does a 1 ply
>search, then for each position retrieved from the server, the client
>would send back about a kilobyte. For a 3 ply search the response is
>almost a megabyte. A full 3 ply breadth first search takes no time at
>all. In the distributed application we're not CPU bound, we're I/O
> 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.
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.
> The official distributed.net chess engine has been under development
>for some time. When will we get to see it?
Really? 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.
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.
I look forward to this discussion continuing
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.
More information about the rc5