A strategy is a function from states to actions: intuitively, it guides a player through a game. Formally:

• a strategy for the MAX player is a function $\sigma: \mathcal{S} \rightarrow \mathcal{A}$ that satisfies
  $\sigma(s) \in \text{Actions}(s)$ for all states $s \in \mathcal{S}$ for which Player$(s)$ is MAX .
• a strategy for the MIN player is a function $\sigma: \mathcal{S} \rightarrow \mathcal{A}$ that satisfies
  $\sigma(s) \in \text{Actions}(s)$ for all states $s \in \mathcal{S}$ for which Player$(s)$ is MIN .

Winning Strategies

A winning strategy is a strategy that guarantees a win for the player who uses it, irrespective of how the opponent plays. A few questions should feel fairly natural once this definition is presented:

• Does a game always have a winning strategy for some player?
• How do we find a winning strategy for a given game?
• Given a strategy, how do we know if it is winning?

In fact, the idea of a winning strategy feels really ambitious, so it would be fair to wonder if we could ever come up with one. Note that there are two slightly distinct questions here: the existence of a winning strategy vs the availability of one that we can actually put to use. It’s nice to have concrete examples of winning strategies, so try figuring out one for Nim.

As a warm up, try the following variation on Nim, where there is only one heap, and you can only take one, two, or three tokens from a heap at a time.

Existence of Winning Strategies

For the kinds of games we are working with right now, it turns out that there is always a winning strategy for one of the players.

Here’s a version for games that can possibly end in a draw:

Computing Winning Strategies

Although winning strategies exist, they are not always easy to find. Indeed, it is often computationally intractable to find winning strategies for many games. Up next, we will look at a technique that assigns utility values to states in a game tree, which can help us determine which player has the upper hand.