Explaining heuristics with computer science, graph theory.

[Evert]

To add to what I just wrote, "looking for an alternative to end-game tables" is a good way to phrase my problem. Specifically lighter on computation so a smartphone can do at least something in a few seconds.

In SjaakII, I do the first step of tablebase generation on startup, to determine if the king can be mated in a corner or not, and which pieces/pairs of pieces have mating potential.

[zulban]

Well it would be far worse than 100 times slower.

1) Lets say the smartphone is 100 times slower.
2) My nodes/s will not be anything close to stockfish or a truly polished system (for one thing, it's written in C#). Let's be very generous to myself and say it will only be 10 times slower on classic chess.
3) As I said my rules are flexible... for example there's piece state (like mana for spells) I haven't really discussed yet. Being generous again, maybe another 10 times slower?
4) 8x8 boards have a little less than 64*63*62*61 combinations for KBNK, about 15 million. 16x16 boards have some 4 billion, 275 times more. This is not even counting the combinatoric problem of "bishop with 1 mana" and "bishop with 2 mana" and "bishop with x mana".

So we're not talking about 100 times more work. If we're generous we are talking about 2,750,000 times more work. That's 76 hours instead of 100ms. The board size was worst case scenario but still.

This is a good discussion tho and I'd like you to know I am not totally dismissing the possibility of EGTs in the future. In my mind you've moved EGTs from "probably not doable" to "future thing to consider". I understand this leaves my AI vulnerable to KBNK-like endings. But honestly, as a mediocre human player I would struggle to convert a KBNK ending too, so that doesn't trouble me so much. I am in good company:

http://chess-news.ru/en/node/11943

Again, the goal is for my AI to beat amateur players, not to lock a win in every case. If I can come up with more guidance than just "kings in corners" I will probably solve many easier but difficult cases with weird 6 men endings.

Maybe I could compute an "incomplete EGT"? I would start by looking at tiles with few king moves, and only compute the possibilities where the remaining enemy pieces are nearby.

Once I find a few possible checkmate locations, make a heatmap to lure the king towards there? Not a bad idea I think... I think this would even work for KBNK.

[zulban]

to determine if the king can be mated in a corner or not, and which pieces/pairs of pieces have mating potential.

How do you determine which pieces have mating potential? Sure it could be brute forced, but are there any tricks you do to speed things up?

[Evert]

to determine if the king can be mated in a corner or not, and which pieces/pairs of pieces have mating potential.

How do you determine which pieces have mating potential? Sure it could be brute forced, but are there any tricks you do to speed things up?

Sure. There are a couple of things.
First, there are symmetry considerations that you can exploit, but you have to be careful: the board might have asymmetries, but pieces may also have left/right or north/south symmetries.
Then, there is the order in which you try positions. Try the King in the corner first. Try positions where it is off the edge last (or not at all; pieces that can mate the king in the middle of the board but not on the edge are contrived anyway).
Skip positions where the attacking king takes no squares away from the defending king (be careful: it can happen that it takes all of them so you only need to check the king, but in this case the position prior to mate would have been stalemate; I think I catch those by doing a single ply retrograde analysis).
Skip positions that are not checks (use an attack generator that tells you where to place a piece such that it attacks a given square). For sliders/riders, you can eliminate a ray if any single square on that ray is not mate. Doesn't work for compound that also has leaper moves.

Beyond optimisations like that, it's brute-force though. You don't have to do it at the start of the game though, since it only affects the end game. Just queue it for when you have time to do it (obviously, if the search starts hitting positions where it matters, you need to dinish the work first to get the evaluation correct).

[hgm]

If you have 'piece state' it doesn't sound very much like Chess anymore. Unless you map it on a 3-dimensional 'board', where the 3rd coordinate represents the mana of the piece. That indeed drives up the 'board' size to a value way too large for EGTs.

Maybe I could compute an "incomplete EGT"? I would start by looking at tiles with few king moves, and only compute the possibilities where the remaining enemy pieces are nearby.

Once I find a few possible checkmate locations, make a heatmap to lure the king towards there? Not a bad idea I think... I think this would even work for KBNK.

This is basically what Sjaak II does, assuming boards have corners. It sets up all mate positions with the King in or next to a corner, and then does one or two steps of retrograde moving to see whether mate-in two and mate-in-3 positions exist. If there are no mate-in-3 positions, you know the mate cannot be forced except in a negligible fraction of the positions.

You can get false positives this way, however. On 8x8 Ferz + Wazir is a general draw, but there are a few very long forced mates when the bare King is already close to a corner, and the Wazir approaches it along one edge, and the Ferz along another. So you would have to require some minimal strength of the pieces in order to be able to drive the King into a corner.

This can depend on the board size; many short-range leapers lose their mating potential when you make the board larger. To successfully force the King to an edge the group of pieces that can confine it there must be able to keep up with a King. Otherwise he just keeps running away to where you have no power. E.g. King + Commoner can force mate on boards up to 14x14 IIRC. A single King or Commoner cannot confine a King to an edge with moves to spare for another piece to approach, so you would need the pair of them. But the pair moves at half the speed. So for every step you displace the (K,C) pair, the bare King gains one step on you. The pair spans about 6 squares, however, so the bare King needs to gain about 7 moves to get clear of it, i.e. move 14 while the pair moves only 7, before it bumps against the opposite edge.

[zulban]

Interesting, thanks. I like the idea of including the attacker king in the check... though it's possible only one side has a king, like horde chess. Attack generator seems like a good way to go, I guess that's one thing we mean when we say retrograde analysis. I'm learning a lot of vocabulary for the things I think about, in this forum :o

Then, there is the order in which you try positions. Try the King in the corner first. Try positions where it is off the edge last (or not at all; pieces that can mate the king in the middle of the board but not on the edge are contrived anyway).

It just occurred to me that there could be a board like this:

https://i.imgur.com/M33inSJ.png

Where if it's king versus rooks endgame, you actually don't want the king slipping into the left for its "corner" and "edge" tiles. Rooks cannot enter. That would be a draw. This may seem contrived but I can think of lots of configurations like this that would be fun.

So there's more to the story than luring the king towards its low move tiles... Lets say power(rook,x,y) represents how much move power a rook has on (x,y). So in classic chess power(king,a,1) is low and power(king,d,4) is higher. Maybe my formula for king lures in a K vs RRN endgame could be:

(power(rook,x,y)+power(rook,x,y)+power(knight,x,y)) / power(king,x,y)

Where higher values is where we want the king to go. That doesn't seem too bad... it passes my sanity check with classic chess - it will still lure the king towards the 8x8 corners / edges. It also feels very important in this formula that power(king,b,2) < power(king,c,3). This is already how I calculate my PST, actually.

[hgm]

The lesson is that inaccessible squares do not just suffocate a King, but also can protect it from attack. The case you just mentioned is in fact just a generalization of color binding: you have a piece that cannot reach every board square. Chinese Chess also has that for some pieces, due to the board zoning. In Omega Chess the Rooks cannot go on the Wizard squares either, and lose their general mating power because of that. It would in any case be useful to analyse which squares are reachable for each piece type, and consider the King more safe when it cannot be checked by some of the pieces, or squares next to it cannot be attacked by some of the pieces.

[zulban]

The case you just mentioned is in fact just a generalization of color binding

That was a slight communication gaff on my part. I could equally have made the left side only accessible to knight jumps - and the king moves like a knight. So it's not color binding exactly, but a "disconnected graph" for the rooks. Still, same idea.

[hgm]

No disagreemet there. But disconnection of the graph is not the only issue. Color-binding of a Bishop splits the board graph in two. But there at least the Bishop can cover squares next to a King that is on the 'safe' color, taking away some of its moves, wherever he is. In the Rook example there are squares where you cannot even do that. Limiting the number of escape squares of the King might not be much less important than the actual checking, so a Bishop isn't hurt much, in terms of its contribution to mating potetial. It is really the graph section the piece is in, 'embossed' by (retrograde) King moves which efines the part where the piece represets a danger. For a Bishop this 'closure' of the accessibility graph covers the entire board.

[zulban]

Oh my, that is a fine point. "Embossed" is an interesting choice of words but it does a good job illustrating what you mean.

I will try putting together a graph system for mate checking and report back here.