Today we will explore some mathematical games involving two players who move alternately. In many games, one of the players has a winning strategy, which guarantees victory regardless of the opponent’s moves. We now describe a systematic approach that can be very helpful, though it is not needed all the time.
Let’s say you are at a stage of the game where you can win in one move and it is also your turn. Then that position is called a winning position. We can now make the following definition for all states of the game.
A losing position is one where all your moves give the other player a winning position. A winning position is one where you can make a move that gives your opponent a losing position.
We can analyze from the end of the game backward and figure out whether each possible state is a winning position or a losing position. The first player has a winning strategy if the starting position is a winning position. The winning strategy belongs to the second player if the starting position is a losing position.