Author: Tony Werten
Date: 13:09:02 04/06/03
Go up one level in this thread
On April 06, 2003 at 15:37:12, Russell Reagan wrote: >I am trying to understand the details of how EGTB indexing works. I think I >understand the basic idea of computing a godel number and using that as the >index, but when it comes to improvements in the indexing scheme, I can't figure >out how they work in practice. I'll give an example. > >Let's use the following position: > >[D]4k3/8/4K3/8/8/8/8/R7 w > >If we use a1=0, h1=7, a2=8, h8=63 for determining our indexes, then we have >pieces on the following indexes: 44, 60, 0. And if we use 0 for white to move >and 1 for black to move, then our index should be: > >WK,BK,WR,w >44,60, 0,0 > >Which comes out to: > >101100 111100 000000 0 = 368128 > >So I assume that this is the index we use to lookup the result in the tablebase >file. So the tablebase file will look something like this: > >For simplicity, let's use: > >00=draw >10=white wins >01=black wins > >index result >====== ====== >368128 10 >368129 10 >... > >The above is how I understand "simple" EGTB indexing to work. Ernst Heinz >describes improvements to old indexing schemes in one of his papers that I read, >but I don't understand how you can use certain knowledge to improve the indexing >scheme. I understand that it can result in fewer combinations of positions, but >not when you construct a godel number. > >For instance, this scheme would seem to require an index range of >64*64*64*2=524288. But you know that after you place the white king, the black >king only has a maximum of 60 squares available (if white king is in a corner), >so that should reduce to 64*60*62*2=476160, but I can't understand how this >leads to an improvement because you still have the same size godel numbers, so >the tablebase file shouldn't be smaller (as far as I can tell). I'm not really sure what godel numbers are but from what I understand: we don't use them. For simple EGTB: After placing the white king, there are only 63 squares left, after placing the white king there are only 62 squares left. So the index would be calculated ((((SQWK*64)+SQBK)*63)+SQWR) SQBK (square black king ) would be adjusted as follows: if SQBK<SQWK then dec(SQBK) SQWR would be adjusted: if SQWR<SQWK then dec(SQWR); if SQWR<SQBK then dec(SQWR) That's the trick that saves space (well, to start with) Of course it has 1 nasty side effect: You can go from a position to an index, but it's quite impossible to get the position back from an index. cheers, Tony
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.