On Wed, 2007-02-14 at 10:45 +0100, Erik van der Werf wrote:
> > From: Nic Schraudolph <[EMAIL PROTECTED]>
> > Date: 12 February 2007 10:45:50 GMT+11:00
> > To: computer-go <computer-go@computer-go.org>
> > Subject: Re: [computer-go] Zobrist hashing with easy transformation
> > comparison
> >
> >> did you read Anti Huima's paper? The idea looks similar, but
> >> unfortunately it does not work. I provided a proof of the defect
> >> on this list (end of 2002 if I remember well). It's not that easy
> >> to get a working scheme. In fact there is only one combination
> >> with 8 chunks of data. In 2002 I exchanged a lot of email with
> >> Nici Schraudolph, and we found the right scheme. We wanted to
> >> write a paper, but we did not (it takes time, and I had not that
> >> much time - mathematic and computer go is just a hobby for me).
> >
> > The bad news: a colleague here has proven that no standard
> > segmented Zobrist hash can work in less than 8 chunks - and that's
> > without color symmetry. That makes 16 chunks with color, not very
> > attractive!
> >
> > The good news: I've developed a defect-free scheme including color
> > symmetry that works in only 6 chunks, and has a very efficient way
> > to compute a canonical hash (that is: without having to compute all
> > 8/16 candidates). No contradiction to the above proof as it's not a
> > standard Zobrist hash. This is provably the minimal scheme.
> >
> > Do sit on me - I really need to finish writing this up! In the
> > meantime, as long as you don't need color, the 8-chunk scheme Erik
> > posted works fine. Nick's (if I understood it correctly - I took
> > r_x, r_y, r_xy to mean reflection about vertical, horizontal, and
> > diagonal axis, respectively) has a problem though: for all
> > positions p, r_x(r_xy(r_x(r_xy(p)))) == p. Huima's scheme can't
> > work because it's really a 4-chunk scheme doubled up for color
> > symmetry.
Me too:
#define T_X(h) \
( (((h) & 0xaaaaaaaa) >>1 ) \
| (((h) & 0x55555555) <<1 ) \
)
/* { 2,3,0,1,6,7,4,3} */
#define T_Y(h) \
( ( ((h) & 0xcccccccc) >>2 ) \
| ( ((h) & 0x33333333) <<2 ) \
)
/* { 3,1,2,0,7,5,6,4} */
#define T_P(h) \
( ( ((h) & 0x66666666) ) \
| ( ((h) & 0x11111111) <<3 ) \
| ( ((h) & 0x88888888) >>3 ) \
)
/* { 0,2,1,3,4,6,5,7} */
#define T_Q(h) \
( ( ((h) & 0x99999999) ) \
| ( ((h) & 0x22222222) <<1 ) \
| ( ((h) & 0x44444444) >>1 ) \
)
#include <stdio.h>
#include <stdlib.h>
int main()
{
unsigned long val0, val1, val2, val3;
unsigned aa,bb,cc;
unsigned at,bt;
char * legend[4] = { "(X)" ,"(Y)" ,"(P)" , "(Q)" };
val0 = 0x12345678;
at = bt = 4;
for (aa=0; aa <4; aa++ ) {
switch(aa) {
case 0:val1 = T_X(val0); break;
case 1:val1 = T_Y(val0); break;
case 2:val1 = T_P(val0); break;
case 3:val1 = T_Q(val0); break;
}
for (bb=0; bb <4; bb++ ) {
if (bb==aa) continue;
if (bb < bt) at =4;
switch(bb) {
case 0:val2 = T_X(val1); break;
case 1:val2 = T_Y(val1); break;
case 2:val2 = T_P(val1); break;
case 3:val2 = T_Q(val1); break;
}
for (cc=0; cc <4; cc++ ) {
if (cc==bb) continue;
switch(cc) {
case 0:val3 = T_X(val2); break;
case 1:val3 = T_Y(val2); break;
case 2:val3 = T_P(val2); break;
case 3:val3 = T_Q(val2); break;
}
if (aa!=at) fprintf(stdout,"%8lx -%s-> %8lx"
,val0,legend[aa],val1);
else fprintf(stdout," -%s-> "
,legend[aa], val1);
if (bb!=bt) fprintf(stdout," -%s-> %8lx"
, legend[bb],val2);
else fprintf(stdout," -%s-> "
, legend[bb]);
fprintf(stdout," -%s-> %8lx\n",legend[cc],val3);
at = aa; bt = bb; ;
}
}
}
exit(0);
}
/**
Legend: T_X() and T_Y() transform the hash value, when flipping the X
and Y coordinates; T_P() and T_Q()
flipping over the diagonals. The rest is trivial.
HTH,
AvK
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
