How to find the shortest possible path to mate?

[klx]

Hi, I'm currently creating an app that, given a chess position, should return the shortest possible forced path to mate (both number of moves and the PV line). I'm wondering how I can achieve this?

My thinking is that, if I use alpha-beta search, I can not use things like quiescence search or depth extensions / reductions, since then the first win found is not necessarily shortest. Or perhaps I can still use them, but need to keep searching after a win is found to ensure it's shortest.

Can I even use a transposition table? I feel like this might not guarantee shortest win if there are exact hash hits?

For retrieving the PV line, I found this old topic which seems relevant; does this still seem like the best way to do it?

Am I complicating things -- does alpha-beta with heuristic evaluation function even make sense, or should I skip that and just search for win/loss?

Btw, my priorities in creating this app are:

1. Correctness / optimality -- This is a must!
2. Simple code / algorithm
   -- This is a small project, I want to finish it in about 2 weeks.
   -- With more complicated code I'm afraid I'll introduce bugs.
   -- Prefer to focus engineering effort on concurrency rather than fast single-core performance, since I'll run on a 16 core machine.
3. Efficiency -- Not top priority, but ideally I can solve 10-20 ply mates within a few minutes.

[Chessnut1071]

Hi, I'm currently creating an app that, given a chess position, should return the shortest possible forced path to mate (both number of moves and the PV line). I'm wondering how I can achieve this?

My thinking is that, if I use alpha-beta search, I can not use things like quiescence search or depth extensions / reductions, since then the first win found is not necessarily shortest. Or perhaps I can still use them, but need to keep searching after a win is found to ensure it's shortest.

Can I even use a transposition table? I feel like this might not guarantee shortest win if there are exact hash hits?

For retrieving the PV line, I found this old topic which seems relevant; does this still seem like the best way to do it?

Am I complicating things -- does alpha-beta with heuristic evaluation function even make sense, or should I skip that and just search for win/loss?

Btw, my priorities in creating this app are:

1. Correctness / optimality -- This is a must!
2. Simple code / algorithm
   -- This is a small project, I want to finish it in about 2 weeks.
   -- With more complicated code I'm afraid I'll introduce bugs.
   -- Prefer to focus engineering effort on concurrency rather than fast single-core performance, since I'll run on a 16 core machine.
3. Efficiency --
   Not top priority, but ideally I can solve 10-20 ply mates within a few minutes.

That's not a small project. If you have to finish it in 2 weeks you will need to copy code in the public domain. Good luck

[klx]

That's not a small project. If you have to finish it in 2 weeks you will need to copy code in the public domain. Good luck

Huh? My point is I'm not trying to build Stockfish, I'm fine trading some major performance for simplicity. I can hack up a simple solution based on the below in a couple of hours (which I think would solve my problem if used with iterative deepening). Now I'm wondering what can I do in a few weeks. And yes, public domain is absolutely an option, if anyone knows of relevant code solving this problem. Thanks for your thoughts.

Code: Select all

bool negamaxBoolean(GameState state)
  if (state.isTerminal())
    return state.eval()
  foreach (successor s of state)
    if (!negamaxBoolean(s))
      return true
  return false

[hgm]

Conventional heuristic evaluation is not very useful for mate searching. It is more directed at finding long-time wins. Although it is certainly true that delivering checkmate in general becomes more difficult when the attacking side wastes material for no purpose. It would probably be best to base the evaluation mainly on King Safety, and attach very little value to pieces not involved in attacking or defending the King fortress.

Doing a quiescence search should not be a problem. You might find a longer mate earlier, but no one says you have to stop searching when finding a mate. You should just refrain from any reductions or forward pruning (e.g. null move) in the full-width part of the search. Then, when this full-width search reaches a depth of 2*N-1 ply, you can be sure it will have seen any mate-in-N or faster. Just don't stop before that.

The idea that you could reach 20 ply without forward pruning seems highly optimistic, though. 10 ply seems more realistic.

[klx]

Doing a quiescence search should not be a problem. You might find a longer mate earlier, but no one says you have to stop searching when finding a mate.

Thanks, that makes a lot of sense.

One remaining question is around the transposition table. As far as I can tell, it would not be safe to use that in a standard way. Imagine this example:

- We're doing iterative deepening.
- We're currently searching depth 6 (depths 1-5 did not produce a win).
- At depth 5, we reach state X, an "OR" node. If either successor is a win, the game is won, and we have a mate-in-6-plies.
- The successors are Y and Z.
- Y is not a win.
- Z is recorded as a win in the transposition table.
- Hence, we have a mate-in-6-plies.

However -- Z was actually a win-in-3. So there is no mate-in-6.

Now, we can overcome this specific example by saying that we have found a mate-in-9, not mate-in-6. But I imagine it's not always so easy; I imagine that transposition table entries can combine in ways that will make it very hard to keep track of the mate distance.

Am I thinking about this correctly? If so, how can it be overcome? Would it be enough to only accept transposition table entries whose depth is identical to the current depth?

[hgm]

The standard solution to the problem you sketch is to not just have a single 'mate score', which indicates the position is a win, but different scores to distinguish all possible mating distances. So the hash probe would tell you the position was a mat-in-3-ply, and because you made it 6 ply from the root, the search knows it is dealing with a mate-in-9-ply. Even though you might have been searching only deep enough to find mate-in-6-ply without TT use.

[klx]

The standard solution to the problem you sketch is to not just have a single 'mate score', which indicates the position is a win, but different scores to distinguish all possible mating distances. So the hash probe would tell you the position was a mat-in-3-ply, and because you made it 6 ply from the root, the search knows it is dealing with a mate-in-9-ply. Even though you might have been searching only deep enough to find mate-in-6-ply without TT use.

Hmm, I don't think it's that easy though?

In the example above, if Z was stored as a win-in-3-ply in the TT, X would then be stored as a win-in-4. But at a later point, it might turn out that Y was a win-in-1. So the mate distance we had for X (and possibly other positions influenced by X) is incorrect.

Perhaps we could let the mate distance mean "win-in-4-or-less"? Though that doesn't seem particularly useful.

[federico]

The standard solution to the problem you sketch is to not just have a single 'mate score', which indicates the position is a win, but different scores to distinguish all possible mating distances. So the hash probe would tell you the position was a mat-in-3-ply, and because you made it 6 ply from the root, the search knows it is dealing with a mate-in-9-ply. Even though you might have been searching only deep enough to find mate-in-6-ply without TT use.

Hmm, I don't think it's that easy though?

In the example above, if Z was stored as a win-in-3-ply in the TT, X would then be stored as a win-in-4. But at a later point, it might turn out that Y was a win-in-1. So the mate distance we had for X (and possibly other positions influenced by X) is incorrect.

Perhaps we could let the mate distance mean "win-in-4-or-less"? Though that doesn't seem particularly useful.

It is exactly as HGM says. Maybe this helps:
https://www.ics.uci.edu/~eppstein/180a/990202a.html

[yurikvelo]

https://github.com/jhellis3/Stockfish/tree/mate_finder

http://talkchess.com/forum3/viewtopic.php?t=69148

[hgm]

Hmm, I don't think it's that easy though?

In the example above, if Z was stored as a win-in-3-ply in the TT, X would then be stored as a win-in-4. But at a later point, it might turn out that Y was a win-in-1. So the mate distance we had for X (and possibly other positions influenced by X) is incorrect.

Perhaps we could let the mate distance mean "win-in-4-or-less"? Though that doesn't seem particularly useful.

Results from shallow searches in general are less accurate than results of deeper searches. That holds for mate scores as well as heuristic evaluation scores. The whole design of a TT should be resistant to that: you would only accept a stored score if the depth of the search that originally found it is at least as large as the depth you need now. The stored win-in-4 would at some point no longer be accepted, because it was found with a search that was not deep enough. Then you search deeper, and will be able to correct it to mate-in-1 (and store that).