Introduction to Puzzles

What is a puzzle?

One way to think about a puzzle is as a game that a person plays against themselves. Game theory is a well-developed branch of mathematics that focuses on describing how multiple actors in given situations interact with each other, either socially or competitively. One of the great successes of game theory is a description of how good higher-level strategies can emerge from a low-level description of the rules or setup of the game.

What is a Game?

The word "game" in game theory is not meant to imply that the theory only applies to diversionary endeavors, but rather alludes to the fact that when the details of many real-world situations are abstracted away, the resulting mathematical formalism is indistinguishable from a game children might play with tokens or coins. For instance, today, we mostly think of chess as an innocent game divorced of all real-world significance. The object or winning condition of the game is to capture the enemy's king at all cost. It doesn't matter if the winning party loses almost all of their forces or if the winning party has a perfect game, losing nothing - they still win just as much (or just as little). However, during the late dark ages, chess (though in a marginally different form than we know today) was considered the "game of kings" and was very seriously thought of as a loose simulation of contemporary warfare. Training to become proficient at chess was considered a necessary component of becoming a strategic thinker and military general.

The central idea of a game is that there are some set number of players, and all of the players make choices about how to play. These choices can interact with each other in complex fashions. The choices that one player makes can affect the subsequent options open to other players or to themselves at later dates. Also essential to games is the idea that games end. Not every game must end, but at least the possibility (or threat) of the game ending must exist, and when games end, all of the involved players get a payoff, which is a positive or negative numerical representation of how well they did in the game. A player's objective while playing the game is to maximize their payoff at the end. In multi-player games, oftentimes the payoff at different endpoints for the game are different for different players, and players have a conflict of interest and are motivated to work against each other. Such games are called competitive. Some of the most interesting of these are where players' interests are mostly aligned but have subtle conflicts of interest. In such games, players do much better when working together, but they must actively police each other to prevent back-stabbing. Another kind of game is cooperative, where the payoffs for the players are perfectly aligned, and they are all motived by self-interest to work together.

Zero Sum Games

If the sum of all of the payoffs of a game is constant, we call the game zero-sum. A poker game where the house does not take a rake is an example of a zero-sum game because money is neither created, nor destroyed, only redistributed. Chess is another example of a zero-sum game if we assign a payoff of 1 to wining, 0 to losing, and 0.5 to ties, as most tournaments do. No one can win without another losing and ties happen in pairs, so the sum of the payoffs from any particular game is always 1. Notice that the name zero-sum is somewhat of a misnomer since the payoffs can sum to nonzero values. The essential property of a zero-sum game is that no player can do any better without another player doing correspondingly worse.

Extensive Form

Good representation of data is essential for concise (and precise) mathematical analysis. There are many different ways in game theory to represent the structure of the game being played. One of the most intuitive descriptions of a game where choices (or moves) are made in a turn-based fashion, rather than continuously, is an extensive form of the game.

In extensive form, the state of the game is represented by nodes in a graph. Each node is labeled with with which player's move it is at that state. Edges coming out of that state going to other states represent choices that the player can make to move the game forward. Extensive form representation has severe liabilities, such as not effectively representing choices made continuously over time, but they are especially adept at describing descrete finite choices sequentially made by a finite number of players.

The extensive form of the game makes it clear who makes choices and when they make them, and what other choices a certain choice depends on to bring it to the fore, and this makes them especially useful for thinking about mathematical puzzles, which we will model as one-player games.

Puzzles as One Player Games

One quite useful way to view mathematical puzzles is as games where only one person (the person playing the game) makes moves. We can borrow all of the theoretical tools of game theory to analyze puzzles. For instance, we can use the same backtracking algorithm that proves that there is a winning strategy in finite multi-player games with finite choices to show that in finite-state puzzles where all states are achievable, there is also a winning strategy. But a winning strategy in a one-player game isn't what we typically think of as a strategy at all - it is just a path from the initial state to the final state - exactly a solution to the puzzle.

Extensive Form Description of One-Player Games

The extensive form description of the puzzles we discuss in these pages is a useful abstraction to give theoretical insights into the problem-solving process. However, we will never actually write down what these descriptions look like. For any reasonably challenging puzzle, the extensive form description will be far too large to write down. The extensive form description must have one node for every possible state of the puzzle. Take, for instance, the Rubik's Cube, which we will discuss in a later section. The Rubik's Cube has 88,580,102,706,155,225,088,000 possible positions from which it is solvable (there are many more positions from which it is unsolvable for reasons which are covered on the relevant page), and there isn't enough paper on earth to write a dot for every state.

What Makes Puzzles Interesting?

If a puzzle is just a one-player game, and a one-player game is just a graph where you have to find a sequence of moves from the initial state to the end state, then what could possibly be so interesting about a puzzle? After all, the correct sequence of moves is just a path from one vertex, labeled as the initial state of the puzzle to the ending state, which is the solved puzzle.

What makes interesting puzzles interesting is that the abstract graph of the extensive form of the game is never seen. The player (or solver) can never see very clearly beyond the first few jumps away from their current position. Instead, the solver must try to move in the general direction of the solution, without seeing precisely where the moves will lead them. In order to do this effectively, the solver must somehow generate ideas for which positions of the puzzle are closer to the solution state than others, and which moves are likely to result in dead-ends. Dead-ends are impossible in solving a Rubik's cube, because all moves are reversible, and if one makes a mistake and realizes it several moves later, one can always undo the mistakes. This is not the case with other, non-reversible games, such as peg-jumping.

These ideas about which states are better or worse are known as heuristics. In general, what makes games fun is the development and use of player-derived heuristics.