Today I encountered a little difficulty, when trying to implement the symmetry optimization to my new bitbase-generator code, which uses the idea by h.g.muller that only one white piece is kept in ram at once. I wanted to use the system working in Nalimov's code, where the black king is always restricted to the triangle h1-e1-e4. The problem is now that when I want to do a un-/move with the black king that leaves this triangle I can not as I would have done with my old code just flip all the other pieces accordingly, as not all of them are present in ram at the time.
Does anyone have an idea, how this index-optimization can still be achieved in an efficient way?
symmetry and indexing
-
h.g.muller
- Posts: 223
- Joined: Mon Feb 19, 2007 8:24 am
- Sign-up code: 0
- Location: Amsterdam
- Contact:
Re: symmetry and indexing
If I keep only one white piece dynamic in the slice that is loaded in RAM, (and all black pieces), I usually restrict the white King to this triangle. If it is the white King that is dynamic, and an unmove brings it outside the triangle, you have to mirror it back into it through the appropriate combination of reflecions.
This also reflects all other pieces, of course. For static pieces this means that you have to have all mirror images of the static pieces loaded simultaneously, to have a 'closed set' w.r.t. King moves.
This is no problem. It means that you need to load 8 different constellation of the static pieces (related by symmetry), but you also restricted the whithe King to 1/8 of the board. So in the end it requires the same amount of memory to hold the slice.
This also reflects all other pieces, of course. For static pieces this means that you have to have all mirror images of the static pieces loaded simultaneously, to have a 'closed set' w.r.t. King moves.
This is no problem. It means that you need to load 8 different constellation of the static pieces (related by symmetry), but you also restricted the whithe King to 1/8 of the board. So in the end it requires the same amount of memory to hold the slice.
Re: symmetry and indexing
What do you think of this:
Keep the black king fixed to the triangle and when loading a certain slice to RAM, additionally load the black king on d1,d2,d3,d4,d5,e5,f5,f4,g4,g3,h3,h2 (all squares the black king can go to from the triangle) with all the white static pieces mirrored accordingly. The size of the total table would then be (10+12)/64 the size of the table without optimization. Thus reducing RAM(in your case cache) demand.
The main problem is that we can't verify a potentially btm-black looses position, where the black king is out of the triangle. But as soon as the total escape moves are counted at one point and saved in the table, we simply have to decrement the number.
Furthermore in my case I am planning to hold two tables: one for btm and one for wtm. The wtm only requires entries with the king fixed to his triangle.
Keep the black king fixed to the triangle and when loading a certain slice to RAM, additionally load the black king on d1,d2,d3,d4,d5,e5,f5,f4,g4,g3,h3,h2 (all squares the black king can go to from the triangle) with all the white static pieces mirrored accordingly. The size of the total table would then be (10+12)/64 the size of the table without optimization. Thus reducing RAM(in your case cache) demand.
The main problem is that we can't verify a potentially btm-black looses position, where the black king is out of the triangle. But as soon as the total escape moves are counted at one point and saved in the table, we simply have to decrement the number.
Furthermore in my case I am planning to hold two tables: one for btm and one for wtm. The wtm only requires entries with the king fixed to his triangle.
-
h.g.muller
- Posts: 223
- Joined: Mon Feb 19, 2007 8:24 am
- Sign-up code: 0
- Location: Amsterdam
- Contact:
Re: symmetry and indexing
It seems to me you are only making life difficult for yourself by using the black King for this. Like you say, it is black that has to do two ply in a row, due to verification. With the white King you won't have that problem.
There was another reason why I used only white pieces to determine symmetry in the EGTB generator on my website (which doesn't treat the white pieces one by one, and is threrefore considered obsolete): There are many more WON wtm positions than LOST black positions. So you will be generating many more black moves than white moves. So it is more efficient to not have to worry about symmetry during black moves.
So I used white King in the triangle, and when it was on the diagonal, white 'lieutenant' below the diagonal. So I only would have to do complicated things to the index (redirecting it to the reflected position) on white King moves (and on rare occasion on the white lieutenant moves). As white was by definition the side I was building the wins for, there always had to be a second white piece.
There was another reason why I used only white pieces to determine symmetry in the EGTB generator on my website (which doesn't treat the white pieces one by one, and is threrefore considered obsolete): There are many more WON wtm positions than LOST black positions. So you will be generating many more black moves than white moves. So it is more efficient to not have to worry about symmetry during black moves.
So I used white King in the triangle, and when it was on the diagonal, white 'lieutenant' below the diagonal. So I only would have to do complicated things to the index (redirecting it to the reflected position) on white King moves (and on rare occasion on the white lieutenant moves). As white was by definition the side I was building the wins for, there always had to be a second white piece.