2

I'm thinking about sequential, rules-based games where both players have perfect information about each other and what moves they'll be able to make (such as Chess, Connect 4, tic-tack-toe, Nim, etc.).

In such games, it is typical that either one player has a winning strategy (or a strategy to draw). This leads to a position in the game being declared "winnable" or "unwinnable".

I've been reading about the solutions to such games. Connect 4 is an example of a solved game, whereas Chess and Go are not solved yet.

The problem is that, while for the player in the winnable position some strategies can be said to be strictly better than others, for the player who isn't in the winning position, this makes no sense. The definition cannot be used for that player since there are no good moves that they can make.

It is common in this subject to hear things like: "if both players play with their optimal strategy, here is how the game will end up". Like in Numberphile's YouTube video about Connect 4 for example (I suggest you watch it, but anyways), how can they compare strategies for losing player? From a strict perspective their moves don't matter, but it if you're playing Connect 4 against a fellow human than A) you typically don't know which player has the advantage and B) it's idiotic to resign on move 1 just because you are the second player - if your playing against a human you could still win. The concept of winning strategy becomes totally irrelevant in games where you don't know if you're winning or not; if you're probably losing, then perhaps you should make moves to throw off you're opponent, or to survive as long as possible. But the point is that to play "optimally" in such games you must know whether you're winning or losing (which again as humans neither us nor our opponents tend not to know), because they have possibly separate objectives. It would be better imo if the best moves in any position (winning or losing) could fall under the same definition too, but that's a bonus I suppose.

What are these objectives? What are some of the ways in which optimal strategies are defined for losing players?

4
  • 1
    Many algorithms prefer moves that win more quickly or that lose more slowly. Delaying the inevitable loss is certainly how computers play chess once the outcome (with perfect play) is known (likewise choosing mate-in-3 over mate-in-5 moves). But those are just artificial/spurious goals placed into the game by the programmers. They don't reflect the reality of the game: a win in any number of moves is equally good as any other win. Likewise a loss is a loss no matter how delayed. Sep 22, 2021 at 18:27
  • Well, there'd definitely be optimal losing strategies for a misere game where you win if you lose.
    – nick012000
    Sep 23, 2021 at 8:38
  • 1
    I think you might get some traction asking a similar question over on the math stack exchange. At its heart, I think this is an applied game theory question
    – neph
    Sep 23, 2021 at 19:06
  • 2
    This reminds me of a learning AI that learned to play Tetris. The developers gave it access to all of the same controls a human player would have, and let if find the best solution. The AI quickly learned when it became unable to score more points that it could pause the game thus preventing it from ever losing. This particular Optimal Losing Strategy is called a Rage Quit and is the optimal solution for not loosing in most games.
    – Nosajimiki
    Oct 1, 2021 at 20:10

4 Answers 4

5
  • Maximising the number of turns until the loss occurs is a common one.
  • Chess endgame tablebases often use "distance to zeroing" – the number of turns until either a reset of the count towards the fifty-move rule (that is, a capture or a pawn move) or the end of the game. This can be thought of as optimising for how close to being a draw in that way the game gets. It is useful because under this criterion, the optimal move does not depend on the existing count towards the fifty-move rule.
3

This is mostly just intuition, but it might be helpful. The "winnable" and "unwinnable" position definitions are based on the assumption that the player in the winnable position always makes a move that puts the other player in an unwinnable position. But, if you do not assume a priori that either player plays optimally, then you have to consider all of the possible moves in a winnable position, not just the best move.

For simplicity, I'll define a "winning" move as one that puts the opponent in an unwinnable position.

That gives us a way to compare winnable positions: one winnable position is better than another winnable position if a greater proportion of the available moves are winning moves. So, you could say that the optimal move in any "unwinnable" position is the move that puts the opponent in the worst available winnable position, i.e. maximizing the opponent's opportunity to blunder away the win.

We can easily generalize that to both players: the optimal move in any position is the one that gives the opponent the smallest proportion of winning moves out of all of their available moves. By definition, the winning player always has at least one move that gives the opponent zero winning moves, and those are exactly the optimal moves under the existing definition.


If you have or can calculate a probability distribution over the opponent's moves, you can alternatively define optimal play as maximizing the probability of ever being in a winnable position, which can be calculated by recursively evaluating every subtree for every possible move. This again lines up with the existing optimal move definition: if a player is already in a winnable position, a winning move puts them in another winnable position with probability 1.

11
  • 3
    This analysis is pretty much the only thing I could come up with as well, but I wasn't happy with it because it assumes all moves by the opponent are equally likely; in reality, that's not going to be the case - I think you'll actually win more from a losing position by setting a "trap" which is sprung in 3 moves time than a blatant threat which is trivial to counter. For example, playing a third piece into a line in Connect 4 gives the opponent only 1 in 7 moves which are winning, but given an even reasonably competent opponent they're going to block that. Sep 22, 2021 at 8:54
  • 2
    @PhilipKendall, yes, you need to meta-analyse the opponent, to figure out how likely they're going to find the correct move in each situation and then play the one they're most likely to miss. Of course, depending on the game and the situation, that might well be different for different opponents...
    – ilkkachu
    Sep 22, 2021 at 11:33
  • The "optimal" in "optimal losing strategy" precludes the "if you do not assume a priori that either player plays optimally" conjecture (aka "hope chess"). Sep 22, 2021 at 15:39
  • 1
    If the player in the winning position plays optimally, the other player can never possibly win, so the whole exercise is pointless. That's the issue raised in the question that I'm trying to address. I never said to assume that either player plays badly, or even that they don't play optimally. You just have to allow for the possibility that a player can ever make a mistake for the other player to even potentially have the opportunity to win in what would otherwise be a losing position.
    – murgatroid99
    Sep 22, 2021 at 18:40
  • 1
    An answer can challenge the premise of the question, and I believe that in this case, doing so by presenting that alternate assumption is a useful way to answer the question.
    – murgatroid99
    Sep 22, 2021 at 18:59
1

The definition of "optimal" varies from game to game, but I see similarities in definitions across different game types. Generally speaking, "optimal" play is taking a game action that maximizes the likelihood of victory in the given situation, with the resource available. As you have noticed, in games that mix luck and skill (like Magic, poker, backgammon) optimal plays give you more opportunities ("outs") to get lucky and win, while simultaneous reducing the number of ways you can get unlucky and lose.

So how does this translate to a purely deterministic game like chess? The fact that people do not play perfectly at all times allows for some moves in "lost" positions to be better than other moves. Moves that require your opponent to play more perfectly are optimal. Or put another way, optimal play makes it harder and more tedious for you opponent to win from the current position, even if the current position is a losing position. It's easier to get "lucky" if your moves offer more opportunities for your opponent to make a mistake. Or if you examine a search tree, there will be a higher proportion of "bad decision" for your opponent to make.

For any chess players, this analogy will make a lot of sense. It is widely known that certain endgames are a force win with perfect play. King and Rook (KR) vs King is an easy win for the side with rook. King, Knight, Bishop (KNB) vs King is a harder to execute forced win. That is, the percentage of players who can for checkmate with KR is much higher than the percentage who can for KNB. So if you find yourself in a situation where you have a choice between playing a move that turns the endgame into either KR or KNB, you should choose the move that lets you defend the KNB endgame.

1
  • "optimal" in perfect information games is well-defined (note the CGT tag), and has nothing to do with hoping the other player plays sub-optimally. When not considering optimal play, then yeah, players (especially human players) may choose to play some moves over others in the hopes that this gives rise to error (aka "hope chess"). Sep 24, 2021 at 12:03
0

This question can only have a defined solution with reference to a particular fault injection model to be applied to the move selection algorithm of the player in the won position. The way to optimize against a perfect player who has a 1% chance of moving at random instead is very different from the way to optimize against a perfect player who has a 1% chance of making the second-best move instead.

I think that latter case is more interesting, so here's an attempt at a definition with respect to fault-injection models that worsen play without throwing out the baseline evaluation entirely:

Optimal play from a losing position is the move that maximizes the value of the highest-value losing move the opponent could make in response.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .