Author: Dieter Buerssner
Date: 04:02:55 04/21/02
Go up one level in this thread
On April 21, 2002 at 06:33:51, Alvaro Jose Povoa Cardoso wrote:
>>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
>
>
>Hi Dieter,
>first of all thanks for you help.
>
>Could you please elaborate a little more on that precalculated index array?
>Please remember I'm a novice :)
>How do I construct that array?
A snippet from my code, for 2 pieces and 2 pawns:
These are the helper arrays. It is not taken into account, that already squares
may have been taken by other pieces (so, starts with 64). BTW. Martin's
formulation looks better, but mine may be easier to understand for this simple
case, and for me, it really does not matter (didn't have a need for more than 2
same pieces).
/* The precalculated index arrays */
static unsigned short pppos[64][64]; /* waste some space here */
static unsigned short xxpos[64][64];
void init_...(void)
{
int wk, bk;
short n;
/* ... */
n=0;
for (wk=0; wk<64; wk++)
for (bk=wk+1; bk<64; bk++)
xxpos[wk][bk] = n++;
for (wk=0; wk<64; wk++)
for (bk=0; bk<wk; bk++)
xxpos[wk][bk] = xxpos[bk][wk];
/* The pppos array is indexed by [sq1-8][sq2-8] */
n=0;
for (wk=A2; wk<=H7; wk++)
for (bk=wk+1; bk<=H7; bk++)
pppos[wk-8][bk-8] = n++;
for (wk=A2; wk<=H7; wk++)
for (bk=0; bk<wk; bk++)
pppos[wk-8][bk-8] = pppos[bk-8][wk-8];
>Will the very same array serve for all piece types/color?
Yes. Although I made a difference for pawns and pieces.
>Suppose I have 3Qs and 3Bs (all white), could I use that same array for the 3
>queens and the 3 bishops the same time?
Yes. But while in theory, you would (for example, 3Qs, 3Bs) need (without the
Ks, that are allways there anyway)
62*61*60/3! * 59*58*57/3! indices, with my simple approach, you would need
64*63*62/3! * 64*63*62/3! indices
>Should I have a one dimension array for 1 piece, and a two dimension array for 2
>piece, and a 3 dimension array for 3 piece and so on?
For one piece, you wouldn't need any array. I find the 2 dim array for 2 pieces
most straightforward, but a one dimensional array would also do. Note, that I do
not claim, that all this is extremely effiecient. For me, it was enough, and
needed the least brain power :-)
Regards,
Dieter
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.