How do chess engines decide which best line to play when the game outcome is within their horizon?

Question

Inspired by the Hot Network Question "In this puzzle, why does white play dxe5?", when a chess engine is in a position that it can definitively call lost, drawn, or won, what policy is used to decide among lines that lead to the same outcome?

In a won position, the answer seems easy: play the line that leads to checkmate fastest. But in a lost or drawn position, the engine's opponent may not realize the situation, so it should continue fighting, ideally playing a complicated line and setting traps in hopes of swindling a draw or win. But it is not clear to me how the code could identify such a line from a game tree and evaluation scores alone.

(In a game with time controls, the answer may be more complicated; I am okay with an answer that ignores considerations of time pressure.)

Answer 1

If the engine can choose between getting mated in 2 or mated in 3, it'll choose the line where it is mated in 3 (even though the mate in 2 might be 'more difficult' to spot for humans).

It can't really set traps, because it doesn't know what things might be difficult to spot for a human (or other engine) opponent. It just evaluates the position, without really knowing it's playing a game against somebody; a notable exception is the implementation of contempt, basically a slight modification of the evaluation in order to prevent drawing too early.

For example, in Stockfish, scores for won or lost positions are computed with the function mated_in (and, more rarely, its negated form mate_in). As you can see in the code, a loss is scored as a large negative value plus the number of ply until the loss, so the engine favors winning lines that are fast and losing lines that are slow.

The tie-breaking for draws is usually arbitrary. For instance, in Stockfish, scores for drawn positions are either the constant VALUE_DRAW or computed by the function value_draw to be VALUE_DRAW plus or minus one. The bonus depends on the thread's node counter, which is essentially up to luck, so the variations in scores for drawn positions are not really based on the positions themselves. This small bit of noise in draw scoring is more to keep the search from fixating on certain three-fold repetitions than to help it choose among lines.

Answer 2

The other answer is wrong; we can in fact program the chess engine to favour traps! As you already noted, when the engine thinks it is winning it should simply choose the best move. So the question is how to aim for the sharpest lines for the opponent when it is losing. This is of course subjective, and depends on the kind of opponent we are pitting it against, but there are a few obvious ways to achieve this.

Firstly, we could compute the best play assuming the opponent makes exactly one mistake (as seen from our game tree). Best play assumes that both players make zero mistakes, but we are aiming to trick the opponent to make a mistake, hence we need to know what are the best lines if the opponent does make a mistake. We now have two evaluation scores for each move X, one for the best play and one for the best play with one opponent mistake. Denote these by E0(X) and E1(X) respectively. We can then combine these two scores by some heuristic to obtain an overall score. The safest heuristic is to choose the move X with E1(X)≥0 such that E0(X) is maximum. This heuristic in fact agrees with choosing the best move X if E0(X)>0, since E1(X)≥E0(X). A slightly less safe heuristic is to choose the move with E1(X)>0 such that E0(X) is maximum, which might occasionally choose an inferior move if the best move X has E0(X)=0, in order to try for a win. You can of course design your own heuristic if you want your engine to play more dangerously.

Another way is to incorporate some probabilistic evaluation, by treating opponent play as a random process that occasionally makes mistakes with the distribution of the chosen move depending on the scores of the available moves. I do not think that this is a good general approach, because although it may do well against humans (humans being careless creatures), it is not going to do well against other computer players, as compared to the other approach I gave above.

I also want to emphasize that for this question ("when the game outcome is within their horizon"), any 'hack' such as 'contempt factor' is simply not applicable, because all the terminal nodes in the game tree have known outcomes. Also, many chess engines use a 'contempt factor' instead of the kind of technique I described because it is computationally cheap ('contempt' can be implemented simply as a slightly negative score for a probable forced draw). But if you can already see all the outcomes from a position onwards, it is trivial and costs almost nothing to implement the technique I gave above. The reason it is expensive if the outcome is beyond the search horizon is that, since alpha-beta pruning may prune branches with mistakes, we would frequently need to search substantially more branches to compute E1 correctly.