KK partitioning+very cheap compression fit in 8 GB (7-man)

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..

KK partitioning+very cheap compression fit in 8 GB (7-man)

Postby koistinen » Sun May 30, 2010 7:13 pm

Rather than doing something practical I have done some more theorethical optimizing.
When computing black to move (BTM) positions from white to move (WTM) positions you need the following info:
White wins with distance to zeroing (DTZ) = N-1, white wins with DTZ = N-2, white wins with DTZ < N.
Given that info it is possible to compute new black losses for DTZ = N and DTZ = N-1.
To compute new WTM wins from BTM positions you need the recently computed black losses + previous white wins.
Given that info it is possible to compute new white wins with DTZ = N and DTZ = N+1.
Increase N by 2 for next iteration.

If you index using the kings (KK) positions as most signifigant index and then the rest of the pieces have 64^5 possibilities. (Actually less, due to illegal positions and sometimes due to mirroring)
This means that for each KK position there are 1G positions of the other pieces.
When computing the new values for one side, one king can be constant and so used to partition the table into smaller parts. Fix it in one of the squares, a1, b1, c1, d1, b2, c2, d2, c3, d3, d4.
The king that is moving can move at most one step, first load a1..h1, a2..h2 and a3..c3. This is 19*1G positions.Then compute a1..h1 and a2..b2.
After that a1 is not needed and can be replaced by d3. Then c2 can be computed and so on for all squares.
Without compression 3 bits per position is needed when computing BTM positions and 2 bits per position when computing WTM positions (because you only need the the WTM for the positions currently being computed).
The WTM positions can be compressed because there are only 4 possible cases:
win at DTZ < N
win at DTZ = N
win at DTZ = N+1
no win

If you store that with XY as 00 for no win, 10 for DTZ = N+1, 01 for DTZ = N and 11 for DTZ < N, you can compute the 3 win cases by simple logic, X&Y, Y&~X and X&~Y.
That way you need 2 bits per position and so 2*19*1G bits = 38 Gbit < 5 GB leaving a fair amount for result, I/O buffers and operating system if you have 8G.

What do you think, will this simplify computing 7-man tablebases?
Last edited by koistinen on Mon May 31, 2010 6:03 am, edited 1 time in total.
koistinen
 
Posts: 80
Joined: Fri May 02, 2008 7:59 pm
Location: Stockholm

Re: KK partitioning+very cheap compression fit in 8 GB (7-ma

Postby Codeman » Sun May 30, 2010 7:50 pm

hgm has already collected some ideas on the potential of the restricted king on his webpage. Maybe you want to take a look there: http://home.hccnet.nl/h.g.muller/EGT7/Kslice.html

If I understand you correctly, you want to leave all pieces dynamic (all positions they move to reside in ram) and alternatingly declare the kings static (it may not move as the information of the squares around is not in ram) This works for the attacking side (the side which tries to force mate) but not for the defending side. The defending side needs to be able to try all moves to refute the attacking side's move. So it would rather make sense to first make the attacking king static and later on one of the attacking sides pieces.
Codeman
 
Posts: 85
Joined: Fri Oct 19, 2007 7:50 pm

Re: KK partitioning+very cheap compression fit in 8 GB (7-ma

Postby koistinen » Sun May 30, 2010 8:27 pm

The idea of hgm is to examine part of the attacking sides moves at the same time as all the defending sides moves. That leads to different partitioning possibilities and also avoids the need to store partial results for both sides.
If you only compute one side at a time, the defending side is able to try all its moves and then you store the result. Because the result for defender is stored, it need not be computed again for that iteration and so it is not a problem to fix the defenders king when examining the attackers moves.
The key difference is how you partition the computation. The way of hgm is new, innovative and interesting. Perhaps it is easier to construct a working program if you use a more traditional method?
koistinen
 
Posts: 80
Joined: Fri May 02, 2008 7:59 pm
Location: Stockholm


Return to Endgame Tablebases

Who is online

Users browsing this forum: Bing [Bot] and 2 guests