This chapter is about how to win some simple two-person games. The goal is to have some method (i.e. “algorithm”) for deciding what to do so that the eventual outcome is a win.
The key to developing a winning strategy is the recognition of invariants. So, in essence, this chapter is a continuation of Chapter 2. The chapter is also about trying to identify and exploit structure in problems. In this sense, it introduces the importance of algebra in problem solving.
The next section introduces a number of games with matchsticks, in order to give the flavour of the games that we consider. Following it, we develop a method of systematically identifying winning and losing positions in a game (assuming a number of simplifying constraints on the rules of the game). A winning strategy is then what we call “maintaining an invariant”. “Maintaining an invariant” is an important technique in algorithm development. Here, it will mean ensuring that the opponent is always placed in a position from which losing is inevitable.
4.1 MATCHSTICK GAMES
A matchstick game is played with one or more piles of matches. Two players take turns to make a move. Moves involve removing one or more matches from one of the piles, according to a given rule. The game ends when it is no longer possible to make a move. The player whose turn it is to move is the loser, and the other player is the winner.
A matchstick ...
Get Algorithmic Problem Solving now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
