| View previous topic :: View next topic |
| Author |
Message |
Daniel Shawul
Joined: 14 Mar 2006
Posts: 2271
Location: Ethiopia
|
 Post subject: Re: Zobrist alternative? Posted: Fri Jun 15, 2012 5:04 pm |
  |
|
| Don wrote: |
| Daniel Shawul wrote: |
| You are rehashing stuff that I suggest, did a frequency test with,and then suggested "addition" instead of "multiplication" as a solution since that will keep the uniform distribution, and is also faster. Glancing over other people's posts will save you from this trouble ... |
XOR is clearly wrong as a sub-hash for the pice/square as everything would cancel but addition as you say may suffice.
I asked a computer science professor at MIT about this and he suggested that a mixing function should be tested if you want the most performance. He did not say it would be faster, but that it might be and it should be checked out. The idea of using addition as a hash function requires 2 indirect memory accesses to tables which could be avoided with some clever mixing function. Personally, I don't think any performance difference would be noticeable but I prefer avoiding having even more data structures when it can be done without giving up performance. |
Well the mix function has to generate two good hash keys for piece and square from scratch. We assumed that those keys are available but how to combine them so that it won't mess up the zobrist hashing. I looked at some integer hashing functions with mixing and they all are complex because they have to "mix" the upper bits with the lower bits. The simple Knuth integer hash function that uses multiplication with golden number has the problem that multiplying the upper bits don't affect the lower ones.
| Code: |
int mix(int a, int b, int c)
{
a=a-b; a=a-c; a=a^(c >>> 13);
b=b-c; b=b-a; b=b^(a << 8);
c=c-a; c=c-b; c=c^(b >>> 13);
a=a-b; a=a-c; a=a^(c >>> 12);
b=b-c; b=b-a; b=b^(a << 16);
c=c-a; c=c-b; c=c^(b >>> 5);
a=a-b; a=a-c; a=a^(c >>> 3);
b=b-c; b=b-a; b=b^(a << 10);
c=c-a; c=c-b; c=c^(b >>> 15);
return c;
}
|
So I think it is better to generate two small size tables for piece/square rather than trying to generate the keys by a hash function performance wise. The zobrist keys for standard chess are as big as these ones so that is a "proof" tables are OK for this purpose. Note that the keys are also 64 bits which require more operations to generate.
_________________
https://sites.google.com/site/dshawul/
https://github.com/dshawul |
|
| Back to top |
|
 |
|
| Subject |
Author |
Date/Time |
 Zobrist alternative? |
H.G.Muller |
Tue Jun 12, 2012 7:35 pm |
| Re: Zobrist alternative? |
Kevin Hearn |
Tue Jun 12, 2012 7:44 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Tue Jun 12, 2012 8:19 pm |
| Re: Zobrist alternative? |
H.G.Muller |
Tue Jun 12, 2012 8:54 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Tue Jun 12, 2012 9:46 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Wed Jun 13, 2012 3:24 am |
| Re: Zobrist alternative? |
Daniel Shawul |
Wed Jun 13, 2012 4:14 am |
| ignored idea here |
Daniel Shawul |
Wed Jun 13, 2012 4:00 pm |
| Re: ignored idea here |
Daniel Shawul |
Thu Jun 14, 2012 1:30 am |
| Re: ignored idea here |
H.G.Muller |
Thu Jun 14, 2012 5:50 am |
| Re: ignored idea here |
Daniel Shawul |
Thu Jun 14, 2012 12:52 pm |
| Re: ignored idea here |
Edmund Moshammer |
Thu Jun 14, 2012 8:21 am |
| Re: ignored idea here |
Edmund Moshammer |
Thu Jun 14, 2012 9:27 am |
| Re: Zobrist alternative? |
Wylie Garvin |
Tue Jun 12, 2012 8:27 pm |
| Re: Zobrist alternative? |
H.G.Muller |
Tue Jun 12, 2012 8:36 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Wed Jun 13, 2012 1:01 pm |
| Re: Zobrist alternative? |
Wylie Garvin |
Wed Jun 13, 2012 10:57 pm |
| Re: Zobrist alternative? |
H.G.Muller |
Thu Jun 14, 2012 5:42 am |
| Re: Zobrist alternative? |
Robert Hyatt |
Thu Jun 14, 2012 1:17 pm |
| Re: Zobrist alternative? |
H.G.Muller |
Thu Jun 14, 2012 2:17 pm |
| Re: Zobrist alternative? |
Wylie Garvin |
Thu Jun 14, 2012 6:11 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 10:05 am |
| Re: Zobrist alternative? |
Reinhard Scharnagl |
Wed Jun 13, 2012 9:52 am |
| Re: Zobrist alternative? |
Edmund Moshammer |
Wed Jun 13, 2012 9:58 am |
| Re: Zobrist alternative? |
Reinhard Scharnagl |
Wed Jun 13, 2012 12:49 pm |
| Re: Zobrist alternative? |
Edmund Moshammer |
Wed Jun 13, 2012 1:15 pm |
| Re: Zobrist alternative? |
Reinhard Scharnagl |
Wed Jun 13, 2012 1:41 pm |
| Re: Zobrist alternative? |
Edmund Moshammer |
Wed Jun 13, 2012 3:55 pm |
| Re: Zobrist alternative? |
Reinhard Scharnagl |
Wed Jun 13, 2012 4:03 pm |
| Re: Zobrist alternative? |
H.G.Muller |
Wed Jun 13, 2012 2:19 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Wed Jun 13, 2012 2:44 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Wed Jun 13, 2012 2:48 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Wed Jun 13, 2012 3:28 pm |
| Re: Zobrist alternative? |
H.G.Muller |
Wed Jun 13, 2012 4:01 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Wed Jun 13, 2012 5:42 pm |
| Re: Zobrist alternative? |
H.G.Muller |
Wed Jun 13, 2012 5:51 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Wed Jun 13, 2012 6:27 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Wed Jun 13, 2012 5:29 pm |
| Re: Zobrist alternative? |
Karlo Bala Jr. |
Thu Jun 14, 2012 9:50 am |
| Re: Zobrist alternative? |
Reinhard Scharnagl |
Thu Jun 14, 2012 8:49 am |
| Re: Zobrist alternative? |
H.G.Muller |
Thu Jun 14, 2012 9:09 am |
| Re: Zobrist alternative? |
Daniel Shawul |
Thu Jun 14, 2012 1:11 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 10:12 am |
| Re: Zobrist alternative? |
Don Dailey |
Thu Jun 14, 2012 4:46 pm |
| Re: Zobrist alternative? |
Don Dailey |
Thu Jun 14, 2012 6:38 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Thu Jun 14, 2012 6:57 pm |
| Re: Zobrist alternative? |
Don Dailey |
Fri Jun 15, 2012 2:39 pm |
| Re: Zobrist alternative? |
H.G.Muller |
Fri Jun 15, 2012 3:46 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Fri Jun 15, 2012 5:22 pm |
| Re: Zobrist alternative? |
H.G.Muller |
Fri Jun 15, 2012 5:38 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 10:17 am |
| Re: Zobrist alternative? |
Daniel Shawul |
Fri Jun 15, 2012 5:04 pm |
| Re: Zobrist alternative? |
Don Dailey |
Fri Jun 15, 2012 6:00 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Fri Jun 15, 2012 7:27 pm |
| Re: Zobrist alternative? |
Don Dailey |
Fri Jun 15, 2012 8:16 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Fri Jun 15, 2012 8:42 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Fri Jun 15, 2012 9:14 pm |
| Re: Zobrist alternative? |
Don Dailey |
Fri Jun 15, 2012 10:59 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 12:17 am |
| Re: Zobrist alternative? |
Don Dailey |
Sat Jun 16, 2012 4:28 am |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 6:30 am |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 10:09 am |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 10:22 am |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 10:42 am |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 10:54 am |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 11:03 am |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 11:08 am |
| Re: Zobrist alternative? |
Don Dailey |
Sat Jun 16, 2012 12:03 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 12:55 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 2:21 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 2:25 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 2:44 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 12:35 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 1:11 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 1:15 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 1:56 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 2:05 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 2:10 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 2:22 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 2:29 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 2:35 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 2:39 pm |
| Re: Zobrist alternative? |
Don Dailey |
Sat Jun 16, 2012 3:49 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 4:35 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 2:11 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 2:13 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 2:19 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 2:29 pm |
| Re: Zobrist alternative? |
Vincent Diepeveen |
Sat Jun 16, 2012 2:32 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 4:19 pm |
| Re: Zobrist alternative? |
Don Dailey |
Sat Jun 16, 2012 4:50 pm |
| Re: Zobrist alternative? |
Daniel Shawul |
Sat Jun 16, 2012 4:25 pm |
| Re: Zobrist alternative? |
Don Dailey |
Fri Jun 15, 2012 8:21 pm |
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
