# matefinder — forced checkmate search

A command-line tool that searches for a forced checkmate, of the
side to move, in at most a given number of moves (default 4),
starting from an arbitrary FEN position.

"Mate in N moves" is a much harder question than "does any legal
move deliver mate right now" (which is all
`../xboard-engine-tactical` ever checks, one ply ahead): it means
that *every* legal defensive reply, at every intermediate step,
still lets the attacker complete the mate within the remaining
budget. This is a two-player AND/OR search — OR over the attacker's
own move choices (only one needs to work), AND over the defender's
replies (every single one of them must fail to escape) — not a
simple lookahead.

## Building

```sh
make
```

## Usage

```
matefinder [-d MAXMOVES] [-t SECONDS] "FEN"
```

- `-d MAXMOVES` — search up to this many moves of the attacker
  (default 4). The shortest forced mate within that budget is
  always the one reported: mate in 1 is checked before mate in 2 is
  ever attempted, and so on.
- `-t SECONDS` — give up after this many seconds per depth searched
  (default 10), rather than run indefinitely on a position with no
  short forcing continuation. If the budget is exhausted mid-search,
  the tool says so plainly rather than claiming "no mate" — a timed-
  out search proves nothing about depths it didn't finish checking.

## Examples

The "fool's mate" (mate in 1, Black to move):

```sh
$ ./matefinder "rnbqkbnr/pppp1ppp/8/4p3/6Pq/5P2/PPPPP2P/RNBQKBNR b KQkq - 0 2"
```

Wait — that FEN is already the *mated* position (Black's queen has
already landed on h4). To search *for* the mate, give the position
one move earlier instead, with Black still to move having just
seen White play 2.g4:

```sh
$ ./matefinder "rnbqkbnr/pppp1ppp/8/4p3/6P1/5P2/PPPPP2P/RNBQKBNR b KQkq - 0 2"
Position: rnbqkbnr/pppp1ppp/8/4p3/6P1/5P2/PPPPP2P/RNBQKBNR b KQkq - 0 2
Side to move: Black
Searching for a forced mate in 1..4 moves (time budget: 10s)...

Mate in 1 found (1 nodes):

2... Qh4#

Final position: rnb1kbnr/pppp1ppp/8/4p3/6Pq/5P2/PPPPP2P/RNBQKBNR w KQkq - 1 3
```

A genuine mate *in two*, requiring the search to prove a forced win
rather than just spot an immediate one — the classic king+rook
technique, White to move:

```sh
$ ./matefinder "k7/8/2K5/8/8/8/8/7R w - - 0 1"
...
Mate in 2 found (5 nodes):

1. Kb6 Kb8 2. Rh8#
```

(1...Kb8 is Black's only legal reply here, so this particular
example doesn't show off the "every reply must fail" part of the
search — see `README.md`'s algorithm section below for how that's
verified, and the file header comment in `matefinder.c` for how it
was tested against a position with real branching.)

## How it works

See the (fairly detailed) header comment in `matefinder.c` for the
full explanation; in short:

- `SANGenMoves()` already flags every candidate move that delivers
  *immediate* mate (`mf_chmt`, computed by `SANMLScanMate()` in
  `sanmlm.c`), so a mate-in-1 needs no search of its own at all —
  just a scan of already-generated flags, exactly as in
  `../xboard-engine-tactical`.
- For deeper searches, each of the attacker's candidate moves is
  tried in turn with `SANExecute()`/`SANRetract()` (the same
  lightweight, history-free primitive pair `SANEnumerate()` itself
  uses — never `SANPlayMove()`, so none of the search touches the
  real game history); for each one, *every* legal defensive reply is
  recursively checked to still lead to a forced mate within the
  remaining budget. A move is only accepted once every single reply
  has been proven to fail; the first reply that escapes rejects that
  attacker move immediately (short-circuiting the search) and the
  next candidate is tried.
- Moves are tried checks-and-captures first, since a checking move
  sharply limits the defender's replies (fewer branches to verify at
  the next level) and is simply far more likely to be part of an
  actual mating sequence — this is what keeps the search fast enough
  for a simple demo tool on typically forcing positions, with no
  real evaluation function or transposition table. The full starting
  position, searched to depth 4 (where no forced mate exists and
  every one of White's twenty first moves has to be individually
  disproven), still finishes in under half a second.
- Once a solution is found, it's replayed on a fresh copy of the
  position with `SANPlayMove()` purely to print it with proper SAN
  notation and move numbers.
