Adversarial Games

In the context of puzzles, games typically refer to a scenario where players take turns to make a move, eventually leading to an outcome. The game is called adversarial if the players have conflicting goals. For example, if one player wins, the other must lose; they can’t both win.

For this module, we shall only consider games with the following properties:

• The game involves 2 players.
• Players will take turns to make a single move.
• All sequences of moves eventually lead to one player winning. This means that there are no infinite games.
• It is a zero-sum game: one player winning means the other must lose.
• There are no ties: there must always be one player winning.
• Deterministic: there are no elements of randomness. A particular sequence of moves from a particular game state will always result in the same final game state.

The most general way to solve such games is to draw out the game tree. For instance, this is the game tree of Tic-Tac-Toe.

On the 1st level of the tree, we have one node (we call this the root node) that represents the game’s starting state. Each state branches out into possible states that can be reached as a result of the next player’s move. On the 1st, 3rd, 5th, … levels, the “X” player is next to move. On the 2nd, 4th, 6th, … levels, the “O” player is next to move.

Now that we have an understanding of how a game tree looks, let’s consider a simpler game so we can analyse it:

You and your opponent have a stack of 4 coins: 3 iron coins and 1 gold coin at the bottom. On each player’s turn, they have to take 1 or 2 coins, with the goal being to take the golden coin. You’re going first. How do you ensure you get the golden coin?

Let’s draw the game tree for this game. The red arrows represent the moves you can make, and the blue arrows represent your opponent’s moves.

Each node has a number representing the number of coins left in the pile, with the leaf nodes (the nodes with no children) representing the end state of the game.

Let’s colour the leaf nodes red if you win at that state, and blue if your opponent wins at that state. If any branch nodes only have 1 leaf node below it, we can colour it the same colour.

Consider the game at state $S$S indicated in the diagram above. You have the choice of taking 1 or 2 coins. If you take 1 coin, you end up in a blue node and you lose. If you take 2 coins, you end up on a red node, and you win. Since you can win from this state, you can colour this state red too.

For any node where it is a certain player's turn, it is a winning state for that player if ANY of the possible moves will lead to a winning state for that player too. On the other hand, it is a losing state for that player if ALL of the possible moves will lead to a losing state for that player too.

Let’s use this new rule to colour the rest of the nodes.

It turns out the root node is red! That means that if you play optimally, you can always guarantee a win, no matter what your opponent plays. You can see this play out by traversing down this tree. When it’s your turn, choose a move that leads to a red node. When it’s your opponent’s turn, all his possible moves should only lead to red nodes.

We can summarise your winning strategy as such:

• On your first move, take 1 coin
• If your opponent takes 1 coin on the next turn, take 2 coins.
• If your opponent takes 2 coins on the next turn, take 1 coin.

And that’s it, we’ve solved this game.

Game trees are a powerful tool to solve games. However, analysing a game tree requires us to draw out the whole game tree to compute it. After all, if we leave out some of the branches, we might accidentally exclude a winning strategy that could determine if the first player always wins or loses.

But that doesn’t mean game trees are entirely useless. If we can learn the properties of game trees, we can use them to reason out an alternative solution. In particular, we’ll be using the lessons we learnt from studying game trees.

• We can represent the game as a series of positions.
• A position is a winning position for a player if:
  • It is the player’s turn to move, and he can make a move that leads to another winning position.
  • It is the other player’s turn to move, but all his options lead to a losing position for him (i.e. the first player’s winning position).

If a game is symmetric (that means the rules are the same for both players), we get an additional bonus: if there is a position that is a losing position for you, then it is a losing position for the other player too IF you can get the game to that position on his turn. By extension, a position is a winning position for you if there is a move that leads it to a losing position for the other player.

With that in mind, let’s take a look at the earlier game with the stack of coins. This time, there are 16 coins, a lot more than we can analyse in a game tree, at least by hand. So how can we solve this game?

Let us notice that if the other player takes 1 coin, you can take 2 coins. Likewise, if the other player takes 2 coins, you can take 1 coin. Either way, you can ensure that the stack is exactly 3 coins shorter after 2 moves.

Consider the position where the stack has only 3 coins, and it is the other player’s turn. The other player can only take 1 or 2 coins, and you can take the remaining coins on your turn, winning the game. This means that a position with 3 coins left is a losing position for the player that moves next. If you end up with 3 coins in the stack and it’s the other player’s turn, he loses and you win. Likewise, if there are 3 coins in the stack and it’s your turn, he can use the same strategy to force you to lose, ensuring his win.

Now let’s consider another position, this time with a stack of 6 coins, and it is the other player’s turn. If the other player takes 1 or 2 coins, you take 2 or 1 coins respectively, bringing the other player to the losing position of 3 coins with him moving next. This means that a stack of 6 coins is also a losing position for the player that moves next.

In general, any stack of coins that contains a multiple of 3 coins is a losing position for the player that goes next. If you encounter such a stack, you want to go second.

However, what happens if the number of coins is not a multiple of 3? Then it must be 1 or 2 more coins than a multiple of 3, and the first player can take 1 or 2 coins respectively to leave a stack with a multiple of 3 coins to the other player. That means you want to go first.

To summarise this game:

• A position is a losing position for the player that goes next if the number of coins is a multiple of 3, otherwise it is a winning position.
• From a winning position, the optimal move is to divide the number of coins by 3 and get the remainder. Take that number of coins to leave the other player with a losing position.
• From a losing position, anything you do doesn’t affect the outcome of the game: you lose the game.
• If you get to pick who goes first, choose to go first if the starting position is a winning position. Otherwise, choose to go second.

In this way, we’ve solved this particular game without having to draw the entire game tree. But as you may have noticed, we needed to find a special property of this game that helps us to identify the winning and losing positions of the game.

What is a winning position?	• A position that has already ended, giving the win to the last player that has moved. • A position where there exists a move to put the other player in a losing position.
What is a losing position?	• A game position that has already ended, giving a loss to the last player whose turn it is. • A game position where all possible moves will put the other player in a winning position.
Should you go first?	• Yes, if the starting position is a winning position. • No, if the starting position is a losing position.

Many adversarial game puzzles will ask you something like “can you guarantee a win?” The answer usually depends on whether you get to choose who goes first. If the starting position is a winning position, you want to go first so you can play the winning strategy. If it’s a losing position, you want to go second — because then the starting position is a losing position for your opponent instead. When you encounter an adversarial game puzzle, one of the first things to figure out is whether the starting position favours the first or the second player.

That’s the foundation. You now have the tools to approach adversarial game puzzles: represent the game as a series of positions, classify those positions as winning or losing, and use that classification to play optimally. The puzzles ahead will put these ideas to work — and along the way, you’ll discover more techniques and patterns that make these games tick.