Wednesday, March 03, 2021

[dgmkulmg] verifying an endgame playing program

previously, asking the question.

first, verify positions with white to play and win:

BL = positions black is lost.  BL starts with checkmated positions.

consider all positions with white to move.  WW (white wins) = white plays correctly in these positions, starts empty.  add to WW the positions in which the program's move yields a position in BL.

(a fancier endgame program might give several making-progress winning moves from an input position.  add the position to WW if all such moves yield positions in BL.)

consider all positions with black to move not currently in BL.  if every move from a position yields a position in WW, then add the position to BL.

repeat until sets no longer grow.

repeat for black to play and win.

mark all remaining positions drawn.

for every position in the drawn set, verify that the program's move (or all moves, if a fancy program as above) yields another position in the drawn set.

optionally, these three sets can be compared against ground truth of someone else's WDL tablebase.

this verification algorithm requires testing large set membership, very slow if it does not fit into memory.  can batch sort improve performance?

No comments :