Improved corner painting

[hgm]

I am trying to improve the 'corner painting' algorithm that Fairy-Max uses to checkmate a bare King in KBNK and similar end-games. The problem is that the normal centralization table gives equalpenalty to all corners (it contains just the square of the distance to the board center), so that there is a 50-50 chance that Fairy-Max will drive the bare King to a corner where it cannot be checkmated. (And an even largerchance against a knowledgeable opponent!) Unless special action is taken Fairy-Max would then never allow the bare King to leave that corner, as it is easy enough to avoid repetitions by shuffling the pieces that trap it.

So I had added a simple algorithm that, once a bare King is detected and its centralization weight increased (so that it would consider it most important to corner that King, even if it has to decentralize 4 other pieces to achieve that), the bare King started to decrease the penalty for every square it visited. So that when Fairy-Max failed to mate it in the corner where it was trapped, it would actually get a bonus to be in that corner after some time, so that Fairy-Max would start to drive it out of there again, to the nearest other corner. (Where it then would find a checkmate.) This worked to some extent, but had still several problems:

• It took about 10 turns to turn the penalty in a corner into a bonus, and this often wasted too much time to meet the 50-move requirement.
• During this period not all pieces were needed to keep the King trapped, and one of the pieces then started freely diffusing over the board, and thus could be far away. (E.g. when Bb3 and Nd3 have the bare King trapped on a1/b1, the other King could easily wander to h8, as it would always be back on e4 in the leaf to reap the full center bonus.)
• If the corner painting went on too long after that corner turned positive for the bare King, because the strong side had to recall his dispersed forces again to drive that King away, the bonus in that corner became so large that it started to act as a trap for the pieces of the strong side (as all pieces use the same centralization table, just with different weights), so that they rather dwelled there than drive the bare King to the other corner.

So I was looking for an improvement that would circumvent these problems. The following seems to achieve that:

• When a bare King is detected, its centralization weight is not switched from 1 to 5 immediately, but increases linearly with the 50-move counter from 1 to 10. This gives the strong side the opportunity to amass its forces in the center, before it starts to worry too much on hindering the King. This prevents it chasing the bare King only with its fast pieces, leaving a slow one behind in a corner, where it is of no use in driving the King from the safe corner to the deadly one, so that it escapes in the attempt.
• The normal (corner-color-blind) centralization table stays in use until the bare King actually visits a corner square, and the 50-move counter is at least 10 (ply). This prevents concluding too early that you cannot mate the King in that corner.
• Once the bare King is forced into a corner, or sufficiently much material is present near that corner to drive it out, a checkmate in that corner would usually be within the horizon, and then the centralization table no longer matters, as mate scores are not based on static eval.
• So when in the corner after at least 10 moves, a 4x4 area in that corner is immediately painted in the following way: The penalty in all non-edge squares in it is set to -2, where 0 would be the normal valuein a center square. This attracts the pieces of the strong side in range of the bare King.
• The edge squares get penalties 0, 3, 6, 9, increasing away from the corner, defining a monotonous path along the board edge along which the bare King is to be driven. Once it gets outside the 4x4 area, the normal centralization table makes the penalty increase further towards the deadly corner. E.g. for a bare King on a1:
  

  Code: Select all

  28  21  16  13  12  13  16  21
  22  15  10   7   6   7  10  15
  18  11   6   3   2   3   6  11
  16   9   4   1   0   1   4   9
   9  -2  -2  -2   0   1   4   9
   6  -2  -2  -2   2   3   6  11
   3  -2  -2  -2   6   7  10  15
   0   3   6   9  12  13  16  21

• The hash table is invalidated, making Fairy-Max also forget the game history, so that it would not shy away from making a first repetition if this is necessary in view of the new goal.

This seems to cause a quick switching, and purposeful driving of the King towards the deadly corner, and does not seem to interfere too much with detecting a checkmate in the current corner even after the switch. Usually the strong King is on c3 in this case, so there never is a chance the bare King could reach one of the -2 squares (which might discourage the drive), so that even temporary escapes to e2 or f3 would not look worse than allowing the bare King to stay on a1/b1.

There is one tricky case, which is a Knight plus two (Ferz) Queens on the same color. In principle mate is possible in corners of both colors, but the mate in the color opposite to that of the Queens is so difficult to find that at blitz TC Fairy-Max would not find it even with the bare King in that corner and the normal corner penalties. This because the Queens are typically far away as a result of driving the King there, and would have to be moved near the edge, which normally is a bad location:

[d]8/8/8/8/8/KN6/2Q5/2kQ4 b

coming from something like

[d]8/8/8/1Q6/4Q3/2KN4/k7/8 w

and involving zugzwang. So it now treats this case by driving the bare King to the other corner as well, which it usually manages within the available time.

[bob]

I simply have two PSTs for these kinds of endings. One for a light-squared B, one for a dark-squared B. Makes the endings trivial even at impossibly fast time controls.

[hgm]

Indeed, but that requires pre-programmed knowledge. In particular that the engine would have to know when to use which table. Now try how well that works when the user for a change specified that a Bishop can only jump 2 or 3 diagonal, and a Knight can only jump 2 diagonal or step 1 orthogonal...

[hgm]

Funny, but the centralization table that seems to work best if (X,Y) is a corner where it cannot find a checkmate is the straightforward PST[x][y] = -abs(abs(x-X)-abs(y-Y));, which ramps down linearly from the diagonal between the safe corners to the deadly corners. Any attempt to be smarter, e.g. by giving extra penalty for being on the edge, so far backfired. If it worries too much about the bare King escaping from the edge, this will make it shy away from driving the bare King along the edge towards the deadly corner at fast TC, where it does not have the depth to see that it will always be able to force it back to the edge.

I guess this assumes that the length of all board edges is even. On a 9x8 board if a1 is of the wrong color i9 would be of the wrong color too, and it would have to drive the bare King specifically towards a8.

Another point is that this assumes the pieces are totally symmetric. If that is not the case it would also break the equivalence of the corners. E.g. if a strongly forward-aiming piece is involved, it is conceivable that white can checkmate a bare King on a8 and h8, but not on a1 and h1. Then corner color would have nothing to do with it.

So in general you cannot predict in what other corners you would be able to checkmate, if you cannot do it in the current corner. So I might as well let it pick its own alternative corner. All variants supported by Fairy-Max so far have boards of even dimensions anyway (8x8, 10x8, 12x8, 10x10 or 12x12).

[Evert]

• When a bare King is detected, its centralization weight is not switched from 1 to 5 immediately, but increases linearly with the 50-move counter from 1 to 10. This gives the strong side the opportunity to amass its forces in the center, before it starts to worry too much on hindering the King. This prevents it chasing the bare King only with its fast pieces, leaving a slow one behind in a corner, where it is of no use in driving the King from the safe corner to the deadly one, so that it escapes in the attempt.

What I do for Makruk (and maybe in SjaakII as well, but I have to check if I implemented that) is penalise the attacking side based on the largest distance of any of its pieces. This encourages the program to keep all its pieces close to the king (and works better than trying to optimise the average distance, because then one of the pieces can still get trapped in a local minimum in the centre).
The case I was interested in for this was KFFFK, which is a slightly different problem from KBNK (where I don't think it's very useful to always keep pieces close to the lone king).

Of course SjaakII does some fancy retrograde analysis at startup to detect "mating pairs"; I could probably detect the appropriate corner as well (but it requires a bit more work; it's possible that mate can be delivered but not forced) but at the moment I don't. On the other hand, I also quite like the emergent knowledge that comes from this algorithm.

[hgm]

Indeed, ganging up on the King is always a good idea. I remember that in my first Chess program (Usurpator I) the King was attracted to the piece that moved last. Just to make sure it would be able to win KQK with just 3 ply look-ahead. But it is really helpful for all leapers.

I don't think it would be necessary to put a '3-body potential' in the eval to do this, however. If the penalty grows quadratic with the distance to the King, it would naturally move the most remote piece towards the King, because that would gain the most.

The probem with Fairy-Max is that I try to do it with a PST that is shared by all pieces. And if the bare King has to be driven to a place with a high penalty, short-range pieces that have to drive it there will have to go there too. But this can be solved by making the weight of the bare King so much larger as that of the other pieces that it effectively becomes the only concern.

Makruk remains a problem. Some of these mates are just very hard to see. I wonder if I should cheat a bit, and create hash entries for the mate-in-N positions of KNMMK and KMMMK at the start of the game, protected from overwrite (like they are game history, but with a mate score instead of a draw score). With N so small that it will be able to find the mate from there in 0.1sec or so. Especially the KNMMK mate in the difficult corner seems to obligatory go through the same sequence of moves:

[d]4Q1k1/8/4N1QK/8/8/8/8/8 b

1... Kh8 2. Nf4 Kg8 3. Mgf7+ Kf8/h8 4. Ng6#

So having this position stored as mated-in-3 in the hash table would trim 6 ply off any search that would be able to find the mate. That would probably be enough to see it just as easily as mate in the other corner.

Of course this is a bit at odds with Fairy-Max' design goal of a knowledgeless engine.

[hgm]

The case I was interested in for this was KFFFK, which is a slightly different problem from KBNK (where I don't think it's very useful to always keep pieces close to the lone king).

It turns out that LMR is extremely detrimental, when you have to go against the grain of the PST. Which is sort of necessary in KFFFK, where all F have to approach the bare King in a corner, if you don't have special attraction terms to the bare King. When I switch off LMR it doesn't have much problems with KFFFK, in either corner, at 40moves/min.

I found a nice improvement for seeing the mate: the corner-leaving extension. Whenever a bare King leaves a corner, I extend two ply. This can happen only once every 4 ply, so it doubles the search lines along the path that keeps the bare King trapped in a corner, at the expense of lines where you allow it to roam free. All other extensions and reductions are switched off in the bare King case.

With this improvement it also finds the KNFFK mate in the difficult corner much faster, but not nearly fast enough for 40moves/min. I equiped Fairy-Max with a nice feature now: persistent hash! I added a button option "Save on hash file", which saves the hash key and score of the current position on a file with the same name as the current variant when you press it during analyze mode. On initializing the variant, after clearing the hash table, it reads the file, and stuffs all positions there in the table, with exact score and depth 99 (which is protected from overwrite, normally used to store the game history with 0 score).

When I use this to make a file 'makruk', I only have to store two mated-in-5 positions for the wrong corner (times 8 symmetry-equivalent ones, times two colors) to make it catch the mate in the difficult corner before it decides it should strat driving the bare King to the other corner, at 40 moves/min:
[d]1k1Q4/8/1QKN4/8/8/8/8/8 b
and
[d]1k1Q4/8/1Q1N4/1K6/8/8/8/8 b
This might be a bearable concession to the no-knowledge principle, as it could be used for any variant, and doesn't store the knowledge in the binary. People could add the knowledge themselves if they are not happy with Fairy-Max' end-game play!

BTW, this finally found an application for a facility in CECP that I never used before: the "askuser" command. It is a bit of a chore when you have to select Engine -> Engine #1 settings -> Save on hash file -> OK for every position you want to add to the persistent hash, when entering positions in large numbers because of all the symmetry-equivalent copies they have. So I added a checkbox option "Automatic persistent-hash dialog" to Fairy-Max, that when you tick it, emits the "askuser" command at the start of every analysis search. This pops up the question whether you want to save the current position to the persistent hash, and you then just have to press 'OK' to send an (empty) reply to Fairy-Max, which then triggers the saving (or press 'Cancel'). That allows you to save with only a single mouse click!

[Evert]

The case I was interested in for this was KFFFK, which is a slightly different problem from KBNK (where I don't think it's very useful to always keep pieces close to the lone king).

It turns out that LMR is extremely detrimental, when you have to go against the grain of the PST. Which is sort of necessary in KFFFK, where all F have to approach the bare King in a corner, if you don't have special attraction terms to the bare King. When I switch off LMR it doesn't have much problems with KFFFK, in either corner, at 40moves/min.

Neither SjaakII nor my private Makruk program have any issue with it at that time control either; I'd like them to solve it at 40/0:10 though, which SjaakII more or less manages to do, but which the Makruk program seems to struggle with (which is of course slightly embarrassing).

I found a nice improvement for seeing the mate: the corner-leaving extension. Whenever a bare King leaves a corner, I extend two ply. This can happen only once every 4 ply, so it doubles the search lines along the path that keeps the bare King trapped in a corner, at the expense of lines where you allow it to roam free. All other extensions and reductions are switched off in the bare King case.

That's an interesting idea. Does it need to be the exact corner square, or do you define a general area near the corners?

With this improvement it also finds the KNFFK mate in the difficult corner much faster, but not nearly fast enough for 40moves/min. I equiped Fairy-Max with a nice feature now: persistent hash! I added a button option "Save on hash file", which saves the hash key and score of the current position on a file with the same name as the current variant when you press it during analyze mode. On initializing the variant, after clearing the hash table, it reads the file, and stuffs all positions there in the table, with exact score and depth 99 (which is protected from overwrite, normally used to store the game history with 0 score).

When I use this to make a file 'makruk', I only have to store two mated-in-5 positions for the wrong corner (times 8 symmetry-equivalent ones, times two colors) to make it catch the mate in the difficult corner before it decides it should strat driving the bare King to the other corner, at 40 moves/min:
[d]1k1Q4/8/1QKN4/8/8/8/8/8 b
and
[d]1k1Q4/8/1Q1N4/1K6/8/8/8/8 b
This might be a bearable concession to the no-knowledge principle, as it could be used for any variant, and doesn't store the knowledge in the binary. People could add the knowledge themselves if they are not happy with Fairy-Max' end-game play!

Hehe. A sort-of poor-man's tablebase. Interesting that it doesn't lose the mate when it actually starts searching from the mate-in-five. I've seen that happen occasionally, and it's annoying.

BTW, this finally found an application for a facility in CECP that I never used before: the "askuser" command. It is a bit of a chore when you have to select Engine -> Engine #1 settings -> Save on hash file -> OK for every position you want to add to the persistent hash, when entering positions in large numbers because of all the symmetry-equivalent copies they have. So I added a checkbox option "Automatic persistent-hash dialog" to Fairy-Max, that when you tick it, emits the "askuser" command at the start of every analysis search. This pops up the question whether you want to save the current position to the persistent hash, and you then just have to press 'OK' to send an (empty) reply to Fairy-Max, which then triggers the saving (or press 'Cancel'). That allows you to save with only a single mouse click!

There's a whole host of options that I've never actually used, but when you think about it it's really quite cool that XBoard can act as a GUI front-end to a program, rather than a program acting as an analysis generator for the GUI.

[Evert]

Neither SjaakII nor my private Makruk program have any issue with it at that time control either; I'd like them to solve it at 40/0:10 though, which SjaakII more or less manages to do, but which the Makruk program seems to struggle with (which is of course slightly embarrassing).

Interesting.
What seems to make the big difference here is the evaluation term SjaakII uses to position the two kings. It doesn't just try to minimise the distance between the two kings (if you do that it will happily drive the defending king from the edge to the centre), but it also tries to keep the attacking king more centralised than the defending king. The term it used to do this is (from the defender's point of view):

Code: Select all

eval += centre_table2[defending king] - 3*centre_table2[attacking king];

where centre_table2 just holds the squared-distance to the centre:

Code: Select all

centre_table2[sqr] = offset - (rank-RANKS/2)*(rank-RANKS/2-1) - (file-FILES/2)*(file-FILES/2-1);

[hgm]

That's an interesting idea. Does it need to be the exact corner square, or do you define a general area near the corners?

I use the exact corner square, because I want to be able to see the King stepping on and off it once it is maximally trapped. This can be a problem in KFFFK in the difficult corner, btw, as the easy way to do that is trap the bare King on a2/b1 with Kc3 and Fb2, and then just march your other-colored Ferzes to attack both a2 and b1. But then these have to march up without the King ever hitting a1...

Hehe. A sort-of poor-man's tablebase. Interesting that it doesn't lose the mate when it actually starts searching from the mate-in-five. I've seen that happen occasionally, and it's annoying.

I piked mated-in-5 because from there it could find the mate in under 1 sec. After it visited the position it will become part of the game history, meaning its score in the hash table will be set to 0, so it won't try to revisit it. But if it has no clue how to proceed from there, it was in vain. You could solve that by also including mates-in-2 etc.