What does the perfect chess algorithm look like?

Question

Say we have an infinitely powerful computer playing chess. This computer can tell which moves lead to a win/draw/loss with best play. Obviously we want to pick a winning move if available, or a drawing move if not. However, if there are still multiple moves to choose from, some moves may have better "winning chances" than others. My question is, how can we quantify this?

For winning (or losing) moves, this is trivial: each move will lead to forced checkmate in some number of moves, so pick the move with the shortest (longest) checkmate sequence.

However, drawing moves are less obvious. I feel like there should be something involving minimax and the percentage of each move-subtree that leads to a win, but I'm not sure how to formalize that.

Answer 1

If your opponent always plays optimal. You play optimal. Which of several optimal moves you pick doesn’t matter.

If your opponent always plays deterministic and you know the opponent's strategy, you make the move that is optimal based on your opponent’s deterministic move. This isn’t even guaranteed to be an optimal move! If optimal moves would lead to a draw, but a certain losing move on your side causes your opponent to make a total stupid losing move, then you make that losing move and end up winning!

If your opponent randomly chooses their move with given probabilities, you can pick the move giving you the highest chance of winning.

If the time is limited, you’d have to calculate what your winning chances are depending on the time spent so far. You can waste 140 minutes on the first move and then have no time to find good further moves.

Answer 2

I think it's not obvious how to even define the concept of "winning chances". Indeed, there might not be any single precise concept that everyone would agree corresponds to what they mean by "winning chances". I will explore some speculation below, but I don't know whether there is any literature on this subject.

One plausible definition of "winning chances" of a strategy $S$ is that it is the probability of that the strategy $S$ wins, if played against a particular opponent. If we know the (randomized) strategy $T$ that the opponent will use, then the winning chances of $S$ is simply the probability of winning if I play $S$ and the opponent plays $T$. That is well-defined and straightforward enough to compute (at least approximately). And therefore it is straightforward to define the notion of a strategy $S$ that is optimal for this particular opponent, i.e., it is the strategy $S$ that has the highest probability of winning if played against $T$. To compute $S$ algorithmically, it should be easy to adjust minimax search, by computing the probability of winning for each subtree and choosing the best subtree. Here we replace the max for the opponent with an expectation (taken over the known distribution of moves given by strategy $T$).

If we don't know the strategy $T$ that the opponent will use, then under this view of things, "winning chances" is not well-defined. However, if we know a distribution $\mathcal{D}$ over strategies $T$ that the opponent will use, because we know some aggregate information about the population of opponents, then it is possible to define a notion of "winning chances". The "winning chances" of a strategy $S$ against $\mathcal{D}$ is the probability of winning if an opponent randomly picks $T$ according to $\mathcal{D}$, then we play $S$ against $T$. The probability is taken over both the choice of opponent (i.e., the random choice of strategy by the opponent) and over the randomized choices made at each move by the strategy $T$. In this setting it seems harder to design a practical algorithm to compute the strategy $S$ that has highest winning chances against $\mathcal{D}$, because the optimal algorithm is no longer memoryless. Instead, at each move, $S$ should choose the next move that has optimal winning chances against the distribution $\mathcal{D}|H$, where $H$ is the history of past moves and $\mathcal{D}|H$ is a conditional distribution, $\mathcal{D}$ conditioned on $H$. Computing $\mathcal{D}|H$ explicitly might be intractable because it involves summing/integrating over all strategies $T$, so I don't see a straightforward extension of minimax. A heuristic might be to ignore the conditioning and just choose a next move that has highest possible winning chances against $\mathcal{D}$, ignoring $H$ (and any information that past play might provide about what strategy $T$ the opponent is using).

If we want to know the "winning chances" against a human of some rating R, then it might be possible to train an AI model that reflects the distribution $\mathcal{D}_R$ over strategies used by humans of rating R, and then computing the winning chances against $\mathcal{D}_R$. We might be able to use the memoryless heuristic mentioned above of, at each move, ignoring all past history and using the variant of minimax where we replace the max with an expectation over $\mathcal{D}_R$.

If we want to know the "winning chances" against a human of unknown rating, then it might be possible to compute the distribution $\mathcal{R}$ of ratings, then talk about the winning chances against $\mathcal{D}_\mathcal{R}$. To compute the optimal strategy algorithmically, we might be able to use a variant of the memoryless heuristic above, where the information we try to learn from the history $H$ is a prediction of the opponent's rating. Thus, we might build some AI model that predicts the opponent's rating from the history (effectively computing an approximation to the conditional distribution $\mathcal{R}|H$), and then at each move, compute the move that has highest winning chances against $\mathcal{D}_\tilde{R}$, where $\tilde{R}$ is our current prediction of the opponent's rating.

Actual chess engines use a variety of techniques. Some of them have heuristics for evaluation that are intended to (hopefully) approximate the "winning chances", for some vague and undefined notion of "winning chances". See e.g. https://chess.stackexchange.com/q/15261/12996, https://www.chessprogramming.org/Evaluation. Some use a "contempt factor", which reflects that chess has three outcomes - win, lose, or draw - and tries to avoid draws. See https://www.chessprogramming.org/Contempt_Factor, https://matthewsadler.me.uk/engine-chess/setting-up-wdl-contempt-for-leela-in-nibbler/. Another approach is to evaluate the chances of winning assuming the opponent makes no mistakes and assuming they make one mistake.

I'll also share some vaguely related readings that might interest you: https://chess.stackexchange.com/q/26510/12996, https://chess.stackexchange.com/q/29243/12996, https://chess.stackexchange.com/q/45918/12996, https://chess.stackexchange.com/q/32305/12996, https://arxiv.org/abs/2006.01855.

Answer 3

Given your infinitely powerful computer, you can enumerate all of the move trees starting from a given position until the end of the game, and see how they end up.

If there are multiple moves you could make leaving a position such that you can force a win no matter how the opponent plays, then it doesn't matter which one of them you take, except as a matter of style.

Likewise, if there's no way that you can possibly win, but you can force a draw, it doesn't matter how you do so. And if there is no possibility for you to even draw, then it's time to resign.

The remaining "interesting" positions are the ones where the opponent's skill actually matters — that is, there are legal sequences of moves where you win (or at least draw), but only if your opponent responds to your moves in a certain (suboptimal for them) way.

To choose a best play in those positions, you have to have a model of what the opponent will do, assigning a probability to each possible opponent move in each position — and it has to be a model other than "they play optimally every time", because if they played optimally they would deny you the win! This goes beyond the realm of classical chess engines, and if your opponent is human, it goes into the realm of psychology. But if you had such a model, you could assign every node in the game tree a probability of reaching it, and then maximize your expectation (of chances to win, or of wins minus losses, or whatever).

You could model the opponent as moving randomly — not very realistic at all, but it corresponds to an intuitive policy of "keep your options open", i.e. choose the move that has the greatest number of descendants in which you win.

You could model the opponent as having a fixed chance of making a random mistake (say, they choose the optimal move 90% of the time, and a random legal move the other 10%), in which case your algorithm will assign a high score to trees that give them many chances to make a mistake — e.g. endgames in which a long series of perfect moves on your opponent's part will let them force a draw, but any one wrong move lets you checkmate.

Or you could model the opponent as having a fixed "search depth" (for instance, suppose they can see perfectly up to five moves ahead, but if that's not decisive, they resort to well-known heuristics about material and position). Then you will favor gambits where the opponent seems to be gaining something, only to find out more than five moves later that a given move was fatal.

All of these are wrong, but all of them resemble in some way aspects of the way actual humans play — without access to infinitely powerful computers, and with a recognition that both they and their opponents are imperfect.

Answer 4

For every move you can choose from, list the possible responses of your opponent. And for these responses, evaluate the number of winning games you could make. Then you maximize the total number of winning games for every move of yours.