Hash table transformation

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Dann Corbit
Posts: 10128
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Hash table transformation

Post by Dann Corbit » Wed Oct 05, 2016 5:58 pm

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.
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.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Hash table transformation

Post by Evert » Wed Oct 05, 2016 6:04 pm

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.
Doubt it.
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.

Sven
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Hash table transformation

Post by Sven » Wed Oct 05, 2016 8:15 pm

Evert wrote:
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.
Doubt it.
It only helps if the number of symmetric positions is significant, which is unlikely as long as there are multiple pawns on the board.
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.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Hash table transformation

Post by Evert » Wed Oct 05, 2016 8:37 pm

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.
That's how I took it as well.
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.

Pio
Posts: 119
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: Hash table transformation

Post by Pio » Wed Oct 05, 2016 9:14 pm

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

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Hash table transformation

Post by Gerd Isenberg » Thu Oct 06, 2016 2:47 pm

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.
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.

Pio
Posts: 119
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: Hash table transformation

Post by Pio » Thu Oct 06, 2016 8:49 pm

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

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Hash table transformation

Post by Gerd Isenberg » Fri Oct 07, 2016 8:32 am

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
Hi 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?

AlvaroBegue
Posts: 920
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Hash table transformation

Post by AlvaroBegue » Fri Oct 07, 2016 11:18 am

So you are using 192 bits to describe the board, but 153 bits should be enough. See http://tromp.github.io/chess/chess.html .

Pio
Posts: 119
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: Hash table transformation

Post by Pio » Sat Oct 08, 2016 9:44 pm

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

Post Reply