EGT-driven practice applet for 3-men checkmating

[h.g.muller]

I set up a web applet where one can practice checkmating with various pieces, including custom designed pieces, by playing against a (3-men) EGT. See http://hgm.nubati.net/rules/EGT.html .

The applet is powered by JavaScript, and generates the required EGT on the client machine. I had expected this to be slow, so I used a rather fast algorithm from the outset (with the additional handicap that JavaScript doesn't support a 64-bit int type, so that bitboard techniques are not really possible). In hindsight this might have been overkill, as the EGT turns out to be generated almost instantly. But that means I should perhaps set my sights higher, and create a similar page for practicing arbitrary 3+1-men end-games.

Anyway, the algorithm I used is based on 'escape counting'. Each EGT entry contains 7-bits for the black-to-move DTM code, and a 1-bit flag to indicate white-to-move won positions. DTM codes start at 10 for 'checkmated', so that lower numbers are available for indicating unresolved positions with 0-8 'escapes' to non-won positions. (As we are dealing with a bare King there can never be more than 8.)

This makes the retrograde propagation arther fast: from every DTM=N position (found by simple scanning through the EGT, something that could still be improved on), it generates white unmoves to see if there are new positions where the 'won' flag should be set, and for each such position generate the bare King unmoves (i.e. find the on-board neighbor squares) to decrease their escape count, and declare it lost with DTM=N+1 if that hits 0. Generation of King moves is done by maintaining a list of the allowed steps for every board square, so that no testing is needed for whether the move stayed on board, and one can directly probe the EGT (where for a black King move the index changes by the same amount as the board-square number).

The most time-consuming part of this algorithm is usually the initialization of the escape counts. To make this efficient I use 'bulk counting': I calculate the number of escapes from each board square in the presence of a white King (for each of its 64 possible locations), and mark the squares attacked by it as 'won' (as moving there would have been an illegal move for black). Similarly the number of escapes that are interdicted by the presence of the other white piece (on an otherwise empty board), in all 64 possible locations, and its checks are marked. Then the number of escapes for a board with both white men present is caluclated by subtracting the relevant piece board from the relevant King board, (each piece or King board thus being used 63 times), the result being copied to the 64 EGT entries corresponding to different black King locations for this white constellation. This reduces the work for the actual counting by a factor 63.

The result is in general incorrect, however, because it does not take into account blocking of moves by its own King, and discounts escapes to squares that are attacked by both the King and the piece twice. Note that white King moves that hit the piece actually remain valid for interdicting escapes that would capture the piece. But piece moves that hit the white King should not in any way discourage black from saving the day by capturing this King. So we only have to correct for double counting and piece blocking. For sliding pieces this blocking would also extent downstream of the white King.

Fortunately only a small fraction of all squares is unjustly or doubly counted (the more the stronger the piece is). For these the extra 'won' mark would have to be removed, and the positions with the black King adjacent to them would get their escape back. To make it easy to remove blocked slider moves the calculation of the checks by the piece on an empty board in each location not only generates a board with blocked-escape counts, but also one with the slider base step and remaining range (taking the board edge into account), which can then be consulted whenever a white King is placed on one of the squares a sliding move passes over, to know what 'downstream' is.

Unless the piece is super-strong only a minority of the white constellations would have the King in its path, and even then only the squares on the ray behind it would have to be corrected. Also, the number of doubly-attacked squares is usually quite low (mostly 0, and sometimes 2 if a sliding move passes through the King's 'footprint'), and at most 8 in any case. So only a very minor fraction of the positions needs to be corrected this way. When, after adding the piece and King boards and applying the corrections the DTM hits 0 and the 'won' bit for the position is set (which at that point can only mean black is in check), the position is a checkmate, and the DTM is altered into 10.