Re: Fwd: [computer-go] Zobrist hashing with easy transformation comparison
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) 0x) 1 ) \
| (((h) 0x) 1 ) \
)
/* { 2,3,0,1,6,7,4,3} */
#define T_Y(h) \
( ( ((h) 0x) 2 ) \
| ( ((h) 0x) 2 ) \
)
/* { 3,1,2,0,7,5,6,4} */
#define T_P(h) \
( ( ((h) 0x) ) \
| ( ((h) 0x) 3 ) \
| ( ((h) 0x) 3 ) \
)
/* { 0,2,1,3,4,6,5,7} */
#define T_Q(h) \
( ( ((h) 0x) ) \
| ( ((h) 0x) 1 ) \
| ( ((h) 0x) 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/
Re: [computer-go] Effective Go Library v0.101
?ukasz Lew wrote: Generally http://en.wikipedia.org/wiki/Disjoint-set_data_structure In my program it's a tree for each group of stones. In the root is number of pseudoliberties. Joining is cheap and checking group membership is cheap. Look at chain_t class. in board.cpp Best, ?ukasz Lew I had done similar once upon a time in my bot and later moved away from the disjoint set approach because of the headache that undo created. Out of curiosity, is this library intended to support MC clients specifically or other types of searches (such as alpha-beta that tends to back up its search frequently? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
On Wed, Feb 14, 2007 at 10:57:38PM +0100, ?ukasz Lew wrote: Basically I wanted to implement a board in a hope that more people get attracted to Computer Go. But now this is more or less accomplished. So I decided to implement some kind of set canonical algorithms. But only those most common, I do not intend to make another GnuGo :) I just started UCT, as majority voted for it. Maybe patterns will come next. If You have something to propose, just go ahead :) I have a question about your philosophy. Do you mean us - the users of your library - to take the current version of the code, and start modifying it to our needs? Or do you want us to link with the library, so that we can upgrade to a later version without branching? I am asking because I would need a bit different playout routine. I could easily hack the library to do what I want, but that would in effect be a branch, and lead to maintenance problems later if/when you release a better version. I could also inherit from your classes, and override what I need. That would probably require a new header file, or something. Or I could abstract my needs into a more general interface, submit that as a patch, hope you accept it, and then use that. To get down to earth, I would like to look at the board at the end of each playout, calculate something more than just win/loss, and pass that info back to who ever called playout. One way to do that would be to pass a function pointer and a (void?) pointer to playout, and have it call back the function with the board, winner, and the void pointer. If that sounds more like C than C++, it is because I am a C programmer. If some other C++ idiom could do the same thing, all the better. Also, you have implemented the mercy rule in the playout code. If the library should be used without duplicating the code, this might be better left as a settable parameter. Like I said, I could easily write my own playout. But then I'd have to modify the gtp code to call that, and probably change a bit more here and there. In the end I would have forked your code, and when you release the next version, I would have to merge the changes in, and/or decide to go our separate ways. Perhaps I am worrying too much at such early state. I am just about considering to start my own project. But I'd like to do the right thing from the beginning. What do you think? Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
