# SME (SAN Kit Minimal Engine)

Minimal CECP engine based on SAN Kit.

It plays a genuine, if deliberately simple, alpha-beta search within
a 0.5s-per-move budget: negamax with iterative deepening, and a
purely material evaluation (no positional terms, no opening book).
Checkmate, being mated, and leaving a piece hanging all fall
naturally out of that search rather than needing their own
special-cased rules — see `engine/README.md` for the full
explanation of how it works, and for two genuine bugs in the
underlying 1994 library it works around along the way (a
checkmate-result inversion, and a false "draw" claim once a
fixed-size internal move-history array fills up).

It still plays instantly — no opening book, no pondering, no time
management beyond a hard per-move budget — but picks its move with
a real, if deliberately simple, search:

- **Negamax with alpha-beta pruning**, iteratively deepened for as
  long as the time budget allows (see "Speed" below).
- **A purely material evaluation** (the SAN Kit's own `valcpv[]`
  piece values; nothing positional) at the bottom of the search.

That combination is what actually makes the engine stronger, and it
does so *generally*: checkmate, being mated, and leaving a piece
hanging all just fall out of playing the position out and comparing
material, rather than needing their own special-cased rule the way
an earlier version of this engine handled them. See "How the search
works" below for the details.

## How the search works

`ChooseMove()` runs `SearchRoot()` at depth 1, then 2, then 3, and
so on (iterative deepening) until either the time budget runs out or
a forced mate is found — since deepening tries shallower depths
first, the first depth that finds a forced mate is guaranteed to be
the *fastest* one available, so there's no point searching any
deeper once that happens. Only a depth that finishes completely is
ever used to update the move actually played; if the time budget
runs out partway through a depth, that depth's (possibly biased,
partial) results are simply discarded and the previous, fully
completed depth's choice stands. Depth 1 is cheap enough to always
finish well within budget, so there's always at least one complete
depth to fall back on.

`SearchRoot()` and the recursive `Negamax()` it calls share the same
core loop: generate the legal moves, and if there aren't any, the
position is either checkmate or stalemate (see below) — otherwise,
if there's no depth budget left, return `Evaluate()`'s material
score; otherwise, try each move in turn with `SANExecute()` (the
lightweight, history-free primitive `SANEnumerate()` itself uses,
not `SANPlayMove()`, which would pollute the *real* game history
with lines that were only ever tried out, not actually played),
recursing one ply deeper and negating the result (the standard
"negamax" trick: a position that's good for me by N points is
worth -N points to my opponent), then undo with `SANRetract()`.
Moves are tried in "checks, then promotions, then captures, then
everything else" order (`OrderMoves()`), so that alpha-beta pruning
— skipping a move's remaining siblings as soon as the opponent is
shown to already have a better alternative elsewhere in the tree —
kicks in as early as possible; without decent move ordering,
alpha-beta pruning barely prunes anything.

Move generation itself uses `GenLegalMoves()` — a two-line local
wrapper around the SAN Kit's own `SANGenFullPL()` (pseudo-legal
moves) and `SANMLPolice()` (removes any that leave the mover's own
king in check, setting `mf_chec` on the survivors along the way) —
rather than the library's `SANGenMoves()`, which is what the rest of
this engine and its sibling `../../demos/xboard-engine` normally
reach for. `SANGenMoves()` does everything `GenLegalMoves()` does
*and then* runs `SANMLScanMate()` (a full extra ply of generation
for every single candidate, purely to flag which ones deliver
immediate mate) and `SANMLDisambiguate()` (SAN text disambiguation).
Neither is needed here: this search works out checkmate and
stalemate for itself from first principles (see below), and moves
are only ever reported to the GUI in coordinate notation, which
needs no disambiguation at all. Skipping both roughly doubles the
node rate for no loss of correctness.

Checkmate and stalemate are detected the same way at *every* node
along the way, not just at the search horizon: if the side to move
has no legal moves at all, that's either checkmate (if they're in
check — scored as a huge loss for them, adjusted by how many plies
deep it was found so that a faster mate always beats a slower one)
or stalemate (an exact draw, scored 0). This is also exactly what
makes the old "does this move deliver immediate mate" and "does this
move let the opponent mate me next" special cases from an earlier
version of this engine unnecessary: they're now just the depth-0 and
depth-1 special cases of the very same rule, discovered by the
search itself rather than checked for separately.

`Evaluate()`, the only thing consulted once the depth budget runs
out, is deliberately as simple as it can be: total White material
minus total Black material (`cpmv[]`), from the point of view of
whoever is to move. `cpmv[]` is read directly rather than
recomputed from the board (`SANSetMaterial()`, a full rescan): the
SAN Kit already keeps it correct incrementally on every capture and
promotion, as part of what `SANExecute()`/`SANRetract()` themselves
update (see `sanmer.c`), so by the time any node is evaluated it's
already up to date at no extra cost — this matters since `Evaluate()`
runs at every leaf. No positional terms (piece-square tables, king
safety, pawn structure...), no quiescence search (extending capture
sequences past the normal depth limit so the static evaluation is
never asked to judge a position that happens to be mid-exchange) —
this means the engine can still misjudge a position that looks
materially fine right at the search horizon but loses material on
the very next, unsearched ply (the classic "horizon effect"). Adding
one or both of those would be the natural next step to strengthen
this further.

```
$ ./xboard-engine
xboard
protover 2
feature myname="SME-F" setboard=1 usermove=1 sigint=0 sigterm=0 colors=0 draw=0 analyze=0 variants="normal" done=1
force
usermove f2f3
usermove e7e5
usermove g2g4
go
move d8h4
0-1 {Black mates}
quit
```

```
force
setboard k7/8/2K5/8/8/8/8/7R w - - 0 1
go
move c6c7
```

And declining an undefended pawn because taking it hangs the queen,
in favor of a quiet, safe move instead:

```
force
setboard 1n4k1/5p2/8/7Q/8/8/P3K3/8 w - - 0 1
go
move h5g5
```
