15

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.)

  • 3
    “In a won position, the answer seems easy: play the line that leads to checkmate fastest” — not necessarily. Syzygy tablebases are organized in a way that while they never surrender a win to the 50 move counter, they sometimes suggest very long and roundabout sequences of moves. This is because storing exact moves to the fastest win would require extra space, which Syzygy aims to avoid. – Roman Odaisky Apr 19 at 10:29
  • Interesting question. Recently I have been using AI Factory's chess on a mobile device at a level that I am able to beat about 50% of the time (I won't embarrass myself and say what that level is) It's Treebeard chess engine frequently allows preventable mates in 1 or 2 in lost positions by playing active moves which have some swindle potential. I don't know if this is an artifact of the way they hobble the engine's full strength at lower levels or clever programming on their part. – John Coleman Apr 19 at 14:02
  • 2
    @JohnColeman: You may be interested in my answer, which is focused on obtaining a strong chess engine that can try to lay traps without requiring inbuilt domain knowledge. To answer your query, the Treebeard engine is said to have human error modelling, and the example given (the Fajarowicz Trap) shows the kind of 'errors' the engine might make to seem more human. It may explain why you feel that it tries to swindle you when losing, because it plays moves based on how it thinks humans would play, not the absolute best line. – user21820 Apr 20 at 5:50
  • @RomanOdaisky: ok but the OP's intent is not asking about endgames and 50-move-rule. – smci Apr 20 at 7:18
19

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 one or plus two. 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.

| improve this answer | |
  • 19
    Typical use case; you setup a winning position against an engine in order to train yourself on "winning a won position" against a strong opponent. There's a mate in 15 -that of course you just can't see- but the engine sees it, and being its turn to play, it gives up its queen getting into a trivially won endgame for you (but with a mate distance larger than 15). – emdio Apr 18 at 19:58
  • I actually don't know about draws. I never really programmed a chess engine myself :) – Glorfindel Apr 19 at 6:57
  • @which-line, the only answer I can think about is just read about the alpha-beta search. It covers also the important topic of good move ordering in order to find -faster- the best move. – emdio Apr 19 at 10:11
7

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.