Ken Thompson's 1996 paper

[syzygy]

I am re-reading Ken Thompson's 1996 paper on generating 6-piece endgame databases:
https://ia800405.us.archive.org/21/item ... ndgame.pdf

It seems to me the algorithm he presents contains an unnecessary (sub)step.

In Figure 3 he presents an improved version of his 1986 algorithm:

1. initial mates over all positions

B = btmmate(~0)
BTM = 0
WTM = 0
n = 0

2. record last pass

BTM |= B
RES |= res(B, n)
n += 1

3. White to move and win in n

W = wunmove(B)
WTM |= W

4. Black to move and might lose in n

X = bunmove(W & ~WTM)

5. verify Black to move and lose in n

B = bmove(X & ~BTM) => WTM
goto 2

(The improvement consisted in moving the "& ~WTM/BTM" operations from steps 3 and 4 to steps 4 and 5. As far as I understand, this was important for his implementation because his PC did not have enough RAM to store a complete 6-piece bitmap, and in this way some random I/O was replaced with sequential I/O.)

In his algorithm, B, W , BTM, WTM are all bitmaps:
W = white-to-move wins in n
B = black-to-move losses in n
WTM and BTM are "summation" bitmaps, i.e. WTM = white-to-move wins in <= n, BTM = black-to-move loses in <= n.

In step 3/4, the wtm wins in n are found by "unmoving" the btm losses in (n-1) and (in step 4) removing the wins in <= n-1 found earlier ("& ~WTM").

In step 4/5, the bitmap X of potential losses in n is calculated by "unmoving" the wtm wins-in-n and (in step 5) removing the losses in <= n-1 found earlier ("& ~BTM").

However, a btm position found by unmoving from a win-in-n wtm position has at least one move to a win-in-n position and therefore cannot lose faster than in n. It is therefore impossible that the "& ~BTM" operation, which removes losses in <= n-1, removes any positions from bunmove(W). In other words, step 5 can be simplified to:
B = bmove(X) => WTM

Note that Figure 12 of the paper, which shows code for step 5, indeed contains two lines corresponding to "& ~BTM":

Code: Select all

   BTM = ioinit("BTM, RAND|IN);

and

Code: Select all

   if(bittst(BTM, &g) continue;

The first line should clearly have read "BTM = ioinit("BTM", SEQ|IN);".
See also the text describing Fig. 12, which mentions "and test it for a new Black-to-move position".
I suppose the actual code of his generator is not available. Otherwise we could check if he could have saved a few days of generation time. (Generating KRBvKBN apparently took three months.)

[syzygy]

Regarding his lack of RAM:

In 1986 he used a machine with 16 MB of RAM. This was indeed just about sufficient for a full bitmap of 462x64x64x64 positions = 121110528 bits = 14.4375 MB.

In 1996 he used a machine with 250 MB of RAM. But now his scheme would have required 924 MB of RAM to store a full bitmap (the paper mentions 970 MB; his MBs are apparently 1000x1000 bytes). So the random-access passes of his algorithm will have run quite slowly. But with kings as the leading pieces in his indexing scheme, access locality should not have been too bad.

With my current K-slicing scheme, 40 MB of RAM (20x64x64x64x64/8 bytes) would have been enough, so a 48 MB PC could have run his algorithm essentially without random I/O. (With more compact indexing it would have been 31.92 MB.)

[towforce]

Worth asking him: he might want to be left alone in retirement, or he might be happy to answer!

https://en.wikipedia.org/wiki/Ken_Thompson

[syzygy]

In step 4/5, the bitmap X of potential losses in n is calculated by "unmoving" the wtm wins-in-n and (in step 5) removing the losses in <= n-1 found earlier ("& ~BTM").

However, a btm position found by unmoving from a win-in-n wtm position has at least one move to a win-in-n position and therefore cannot lose faster than in n. It is therefore impossible that the "& ~BTM" operation, which removes losses in <= n-1, removes any positions from bunmove(W). In other words, step 5 can be simplified to:
B = bmove(X) => WTM

Even better, the whole BTM "summation" bitmap can be removed from the algorithm.
So also step 2 simplfiies.

The 1986 paper is less detailed and does not explicitly mention "removing" known losses, but it does mention adding new losses B_i to the (summation) bitmap B (which is BTM in the notation of the 1996 paper). The only reason to maintain this bitmap B is to be able to remove known losses (but as we have seen, the candidate losses will never include known losses).

In their various papers Wu and Beal do not seem to have noticed (or otherwise neglected to mention) that BTM/B is not necessary when they describe Thompson's algorithm. The Wu and Beal algorithm contains a similar step of filtering candidate losses, but they also filter out known wins, which does make sense. Thompson cannot do this because he generates only white wins and black losses, so does not keep track of black known wins.

I have started with Wu and Beal, but their frequent updating of a 1-byte (or 2-bytes) per position file does not make sense from an efficiency point of view. So what I am ending up with is basically Thompson's algorithm, but without the "BTM" summation bitmap and for both sides at the same time, which makes it easier to merge everything into a single file at the end (but requires more intermediate disk space, depending on how the merging is done).

Both sides at the same time also allows me in principle to filter out the "known" btm wins from the btm candidate losses before verifying them, and the same for wtm wins and candidate losses. But at the moment I'm not convinced this is worth it because it means loading from disk two more huge tables on every iteration just to reduce the amount of computation. Probably the optimal solution is to let the generator dynamically choose the verification method depending on the number of positions to be verified.

[syzygy]

Worth asking him: he might want to be left alone in retirement, or he might be happy to answer!

https://en.wikipedia.org/wiki/Ken_Thompson

Agreed, I might do that (if I can convince myself that I will not be the 100th person bugging him with this ).

[towforce]

Worth asking him: he might want to be left alone in retirement, or he might be happy to answer!

https://en.wikipedia.org/wiki/Ken_Thompson

Agreed, I might do that (if I can convince myself that I will not be the 100th person bugging him with this ).

Not sure if you'll be the 100th person bugging him, but I'm VERY confident that you won't be the 100th person bugging him about his 1996 6-man tablebase paper!