Games and Invariants


Loop invariants provide a means to effectively determine the correctness of iterative solutions by helping one reason about the changes from one iteration to the next. A loop invariant is a boolean expression that is true each time the loop condition is evaluated. Typically the boolean expression is composed of variables used in the loop and evaluated each iteration of the loop. In particular, the initial establishment of the truth of the invariant helps determine the proper initial values of variables used in the loop condition and body. In the loop body, some statements make the invariant false, and other statements must then re-establish the invariant so that it is true before the loop condition is evaluated again.

The general structure of a loop is:

while (!done) { // check loop invariant: what is true at every step // body // update to maintain invariant }

Invariants can serve as both aids in recalling the details of an implementation of a particular algorithm and in the construction of an algorithm to meet a specification. You can also use invariants to characterize a variety of iterative processes.

As practice, consider the following puzzles as an introduction to the use of invariants as a tool for reasoning about a problem.

Bean Can

You and a friend are given a can containing N black beans and M white beans initially. The can is emptied according the following repeated process:

The player who chooses the color of the remaining bean wins the game.

Bean Can Algorithm pseudocode (where N represents the number of white beans and M the number of black beans)
while (N + M > 1) do { pick 2 beans randomly if bean1-color == bean2-color then put-back black bean else put-back white bean }

In order to win, you clearly need to analyze the link between the initial state and the final state. The key is to identify the invariant that characterizes the removal process by determining what property is preserved as beans are removed from the can. To help get you started, answer the following questions.

  1. How does the number of white beans change each turn?
  2. How does the number of black beans change each turn?
  3. How does the total bean count change each turn?
  4. What is the loop invariant?
  5. What is the the final state for the simple cases where N+M ≤ 3
  6. Give an overall strategy to determine the final state (the color of the last bean) from the initial state (N & M)?

N coins

You and a friend have a stack of N coins. On each person's turn, either 1 or 2 coins can be taken from the stack. The person who removes the last coin wins. Given N, should you go first or second? What is the loop invariant?

Hint: Consider the case where N=3

Laser robots

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). The goal of each robot is to have its opponent enter its line of fire (vertically or horizontally); distance is not a factor. A robot loses when it cannot move without getting shot.

  1. What is the loop invariant?
  2. What is the strategy for winning the game?