Problem Solving Through Games

For each game below, describe a general strategy that another person unfamiliar with the game can follow to win the game as the player to go first (if you cannot win as player 1, explain when to pass your turn). When describing your strategy, you should be as precise as possible about what the state of the game is and what move to make for that state. To reduce the amount you need to write, your strategy should be as general as possible (i.e., cover many cases in the game, not just one or two). If you get stuck, try follow these problem solving steps.

Note, it is easy to find solutions to these games by simply googling for them. Please try to solve them on your own instead.

Laser Robots

Two laser robots are placed on two opposite corners of a rectangular city; the first starts on the south-west corner and the second starts on the north-east corner. The city street map is a grid of horizontal and vertical roads. The robots move in alternating turns, where each move is either one street horizontally (left / right) or vertically (up / down), but not both. The goal of each robot is to have its opponent enter its line of fire (vertically or horizontally). In this game, the first player is guaranteed to win only in specific city configurations.

This game can be easily set up as a pencil and paper game, just by drawing a rectangular grid and drawing each robot's current position on the grid.

Start simply: describe the winning configurations for a city grid that is 2xN (i.e., where changing N is the only change that determines the outcome of the game). Then describe those for a city grid that is 3xN (i.e., how does the extra flexibility the third row gives you change your strategy). Keep adding more rows to the city until you find a pattern or at least you can determine when to start as the first player.

Chomp

Chomp is usually played with a Hershey's chocolate bar (i.e., one that is divided in smaller rectangular sections). A move consists of selecting any sub-piece of the chocolate bar and breaking the bar there, removing that piece along with all the pieces to the right and above it. The goal of the game is not to eat, remove, the last piece of chocolate (the bottom-left most piece in the bar).

Here is an example online that allows you to play against the computer.

If you do not have several chocolate bars handy (to play repeatedly because the chocolate bar gets broken or eaten), try simulating it on graph paper.

Start simply: describe the starting move that guarantees you a win for a grid of size: 2x2, 2x3, 3x3, and 2x4. What is common about all of these starting moves? Next, describe the strategy that is guaranteed for you to win on a square grid of any size (i.e., NxN). From these examples, state, as generally as possible, the situations you want to avoid putting your opponent in (i.e., those where she is guaranteed to win). Next, consider a grid of size 3x4. What is the starting move that guarantees a win? Finally, try to come up with a general strategy that covers as many cases as you can.

Lights Out

Lights Out, the first official game for the iPhone, is a single player game with the objective of turning off all 25 lights on the game board from any initial configuration of lights on or off. The board is a 5×5 grid of squares, each square representing one of the 25 lights. The game begins with some initial configuration of lights on or off. Selecting a square will "flip" the light switch for that square and the squares to the north, south, east and west, if they exist (i.e., if one of those lights was on, they will now be off and if one was off it will now be on).

Here is an example online that allows you to play increasingly complex scenarios.

Most, but not all, initial configurations are solvable; you do not need to determine which ones cannot be solved without playing (like we have in the other games).

Start simply: describe the simplest way to turn all of lights off in a single row (by selecting squares in other rows). Next, for each light in the top row, describe the moves needed if it is the only light turned on (i.e., all other lights in all other rows are turned off). Keep turning on single lights until you find a pattern or general strategy. Are there any other interesting patterns you notice during this exercise?