Author: martin fierz
Date: 14:55:13 04/19/02
Go up one level in this thread
On April 19, 2002 at 13:21:08, Dieter Buerssner wrote:
>On April 19, 2002 at 12:49:10, Alvaro Jose Povoa Cardoso wrote:
>
>>I'vv been studing Jonathan Schaeffer's EGTB paper and I got stuck in the
>>indexing functions.
>>Before I red the paper I had a basic vague idea on EGTB indexing.
>>My naive scheme was reserving 5 bits for each piece. So for all 4 piece
>>databases I have 20 bits. This scheme has indices larger than the number of
>>positions possible. But what about 8 piece databases? I would need 40 bits.
>>This just don't look good.
>
>I am not Martin, and I neither do no much about checkers. But you seem to miss
>one idea: that the pieces are indistinguishable. Arguing for Chess and an
>illegal QQ position (both Qs same color, no Ks for this example). How many
>different positions are there? Ignoring symmetry, the naive answer would be
>64*64 (or 64*63, doesn't matter for this). But Qa1,b1 is the same as Qb1,a1. So
>you only need 64*63/2 indices. For 3 Qs, it would be 64*63*62/3!, etc. You might
>ask, how to index them then. For example by a precalculated helper array:
>
>index = precalculated_index[sq1][sq2]... // instead of sq1 + sq2*64 + ...
>
>Regards,
>Dieter
i am martin :-), but of course dieter is right on target with his remark.
to put indexing in a more mathematical form, here's what you do:
if you have k identical pieces which you can put on n squares, and they reside
on squares numbered x_0, x_1, ... ,x_k-1, where x_i is in the range 0....n-1,
and the x_i are ordered from small to big, the "canonical" index for this
configuration is given by:
index = | x_0 | + | x_1 | + ... + | x_k-1 |,
| 1 | | 2 | | k |
where my notation is trying to show | n |, the binomial coefficient, given
| k |
by n!/(k!(n-k)!). if you have multiple types of pieces, as you would in a
realistic case, then you will need to find such an index for each piece type,
and put them together.
aloha
martin
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.