Problem Solving Through Games

For each game below, describe a general strategy that a 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).

To get the most out of these exercises to prepare you for programming, practice following the problem solving steps introduced in class.

It is easy to find solutions to these games by simply Googling for them — try to solve them on your own instead.

Laser Robots

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.

• Two laser robots are placed on two opposite corners of a rectangular city; the first on the south-west corner, and the second 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 horizontal (left/right) or vertical (up/down), but not both.
• The goal of game is to have the other robot enter your line of fire (vertically or horizontally).

The first player is guaranteed to win only in specific city configurations.

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).

• Players move in alternating turns.
• A move consists of selecting any sub-piece of the 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).

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. Try to come up with a general strategy that covers as many cases as you can.

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.

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

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 typically a 5×5 grid of squares, each square representing a light.
• 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).

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?

Here is an example online that allows you to play a variety of scenarios.

LightBot Game

LightBot is a game that may seem simple, but foreshadows many interesting aspects of more sophisticated computer programming. It was programmed by Coolio Niato (aka Danny Yaroslavski), a 19-year-old college student in Toronto, Canada; the game was developed for Armor Games, an on-line game repository and player community, and is linked to by many other gaming forums.

The goal is to move a robot around a grid world; you “win” a level by lighting up all the special blue squares in the grid. The actual lighting happens when the bot squats on the squares via special command. The robots movements are controlled by a program which you “write” by dragging command tiles into a scripting area of the interface.

It provides a good introduction to programming by encouraging you to explore the world to figure out how things work rather than reading a "manual". Thus, while playing this game, spend some time exploring the world and the commands to see what kinds of things are possible in addition to just getting the "right" answer.

Play all 18 levels in LightBot's Hour of Code (note, only available on iOS or Android). At the end of each level, take a screenshot of your solution to include with your submission.