Has anyone tried doing the rotate trick used for EGTB to increase hash table scope?
IOW, store the unique transformed/rotated position into the hash instead of the raw position.
Probably it is a loss most of the time since most positions on the board are closely related.
It seems to me that if the searches were long, the hash table were huge, and the values retained, that it could be a win.
Hash table transformation
Moderators: hgm, Rebel, chrisw
-
- Posts: 12550
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Hash table transformation
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Hash table transformation
Doubt it.Dann Corbit wrote:Has anyone tried doing the rotate trick used for EGTB to increase hash table scope?
IOW, store the unique transformed/rotated position into the hash instead of the raw position.
Probably it is a loss most of the time since most positions on the board are closely related.
It seems to me that if the searches were long, the hash table were huge, and the values retained, that it could be a win.
It only helps if the number of symmetric positions is significant, which is unlikely as long as there are multiple pawns on the board.
Not to mention that engines probably have a chiral bias (do they scan to the left or to the right first?). It would be interesting to have test positions for that.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Hash table transformation
I understand Dann's idea differently, he wants to normalize positions by mirroring and/or rotating. So all btm positions are mirrored vertically (also swapping colors) to corresponding wtm positions, and from the set of all positions that can be mirrored horizontally (i.e., all positions where no castling rights are present) you only need about half of them. Finally positions without pawns and with no castling rights can also be rotated by 90 or 270 degrees.Evert wrote:Doubt it.Dann Corbit wrote:Has anyone tried doing the rotate trick used for EGTB to increase hash table scope?
IOW, store the unique transformed/rotated position into the hash instead of the raw position.
Probably it is a loss most of the time since most positions on the board are closely related.
It seems to me that if the searches were long, the hash table were huge, and the values retained, that it could be a win.
It only helps if the number of symmetric positions is significant, which is unlikely as long as there are multiple pawns on the board.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Hash table transformation
That's how I took it as well.Sven Schüle wrote: I understand Dann's idea differently, he wants to normalize positions by mirroring and/or rotating. So all btm positions are mirrored vertically (also swapping colors) to corresponding wtm positions, and from the set of all positions that can be mirrored horizontally (i.e., all positions where no castling rights are present) you only need about half of them. Finally positions without pawns and with no castling rights can also be rotated by 90 or 270 degrees.
It will only actually do something for you if such mirrored positions are at all common in the search, which seems unlikely given the number of possible ways in which the symmetry can be broken. It's neat that you can use the information found in equivalent positions, but if you never encounter those it doesn't actually matter.
-
- Posts: 335
- Joined: Sat Feb 25, 2012 10:42 pm
- Location: Stockholm
Re: Hash table transformation
Hi Dann!
I store the board so that black and white does not matter. That can be good in the beginning if you make your own opening database. I store the entire board in 3*64 bits, do copymake and fix the color and board mirroring branch less so I do not need to do Zobrist hashing. One more advantage is that I do not need special routines for black and white nor need to do legality checking for the hash move
/Pio
I store the board so that black and white does not matter. That can be good in the beginning if you make your own opening database. I store the entire board in 3*64 bits, do copymake and fix the color and board mirroring branch less so I do not need to do Zobrist hashing. One more advantage is that I do not need special routines for black and white nor need to do legality checking for the hash move
/Pio
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Hash table transformation
In the color agnostic white to move only approach I tried a few years ago, I color flipped the board (quad-bitboard) after each move made, and flipped the 64-bit Zobrist-key by bswap (zobrist[piece][sq] == bswap(zobrist[piece^1][sq^56]). It worked quite well with some extra hits in symmetric positions.Dann Corbit wrote:Has anyone tried doing the rotate trick used for EGTB to increase hash table scope?
IOW, store the unique transformed/rotated position into the hash instead of the raw position.
Probably it is a loss most of the time since most positions on the board are closely related.
It seems to me that if the searches were long, the hash table were huge, and the values retained, that it could be a win.
-
- Posts: 335
- Joined: Sat Feb 25, 2012 10:42 pm
- Location: Stockholm
Re: Hash table transformation
Hi Gerd! Thank you so much for the chess programming wiki. I love it. My color agnostic way uses the board representation I invented and described http://www.talkchess.com/forum/viewtopi ... 93&t=49575
I made my board representation color agnostic by traversing the board in such that I start and end in the same rank. Since my board representation is so compact (and I do not bother so much about performance) I do not hash. Another thing I do is to save my scores in a probabilistic manner. That also saves space since the scores only need to be fine graned where it is needed.
/Pio
I made my board representation color agnostic by traversing the board in such that I start and end in the same rank. Since my board representation is so compact (and I do not bother so much about performance) I do not hash. Another thing I do is to save my scores in a probabilistic manner. That also saves space since the scores only need to be fine graned where it is needed.
/Pio
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Hash table transformation
Hi Pio,Pio wrote:Hi Gerd! Thank you so much for the chess programming wiki. I love it. My color agnostic way uses the board representation I invented and described http://www.talkchess.com/forum/viewtopi ... 93&t=49575
I made my board representation color agnostic by traversing the board in such that I start and end in the same rank. Since my board representation is so compact (and I do not bother so much about performance) I do not hash. Another thing I do is to save my scores in a probabilistic manner. That also saves space since the scores only need to be fine graned where it is needed.
/Pio
thanks for your kind words. Wow, what a freaky board rep - refreshing. I guess bmi2 pext/pdep with the occupancy bb is helpful to get the piece-codes from the four 32-bit words.
How do you index the trans table?
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Hash table transformation
So you are using 192 bits to describe the board, but 153 bits should be enough. See http://tromp.github.io/chess/chess.html .
-
- Posts: 335
- Joined: Sat Feb 25, 2012 10:42 pm
- Location: Stockholm
Re: Hash table transformation
Thanks Gerd for the suggestions!
Those two instructions could come very handy when applying the move on the board (and in many other places). I am just doing this for fun in C# in more or less C way (no important objects) doing the bit masking and shifting myself instead of the much smarter chip instructions you suggested. If I ever switch to C I will use your much much smarter way along with the popcnt.
I said that I went through the board starting and ending in the same rank but I ment file.
I have just finished the move generation and Perft (not optimized in any way).
I plan to use ANN in the evaluation in a hopefully very smart, unique, generalizable and simple way.
I plan to use my own probibalistic search that is like a hopefully smarter type of CNS search which will be feasible since my engine will be so slow so that saving the entire search tree is okay.
BR
/Pio
Those two instructions could come very handy when applying the move on the board (and in many other places). I am just doing this for fun in C# in more or less C way (no important objects) doing the bit masking and shifting myself instead of the much smarter chip instructions you suggested. If I ever switch to C I will use your much much smarter way along with the popcnt.
I said that I went through the board starting and ending in the same rank but I ment file.
I have just finished the move generation and Perft (not optimized in any way).
I plan to use ANN in the evaluation in a hopefully very smart, unique, generalizable and simple way.
I plan to use my own probibalistic search that is like a hopefully smarter type of CNS search which will be feasible since my engine will be so slow so that saving the entire search tree is okay.
BR
/Pio