Corner the Queen

This page describes the rules and goals of a little game I have presented in my ECS 30A discussion section recently. It also gives some hints how to come up with a strategy that lets the computer win the game as often as possible.

As a special goody, you can download a working C program that allows you to play the game against the computer (it will be tough to beat, though!).

Overview

This game is a very simple, two-person game involving a (generalized) chess board and a chess queen (you don't have to know the rules of chess to read on). Let us denote the two players by Anne and Bob.

At the beginning of the game, Anne places the queen on some arbitrary field of the chess board. Let us break with chess traditions here and name fields on the chess board by pairs of numbers: The field in the lower left corner will be called (1, 1), and the other ones according to a Cartesian scheme - field (x, y) will be x fields to the right, and then y fields up (you get the picture, also see Figure 1).

Now, Anne and Bob move the queen in turns, where the movement of the queen follows the rules of chess. To recap it: The queen can be moved horizontally, as far as one wants, she can be moved vertically, as far as one wants, and she can be moved diagonally, again as far as one wants. In our game we restrict the queen to be moved to the left or downwards, or along the lower left diagonal, see Figure 1. Of course, the queen has to be moved at least one field in each move.

The goal of the game is to move the queen to the "winning field" (1, 1); whoever moves the queen to this field, wins the game.

Figure 1: Valid moves for a queen on a chess board. The queen is represented by the black circle, the black diamond marks the "winning field." The arrows show legal moves of the queen: She can be moved any number of fields along the arrows, but has to be moved at least by one field. (Note that we do not follow the conventions of chess in numbering the fields.)

The Task

The task for the programmer, now, is to implement this simple game on a computer, where the user takes over Anne's part, and the computer takes over Bob's part. We restrict the program to using input / output of field coordinates instead of allowing the user to manipulate a graphical representation of the chess board - we really don't want to mess around with a user interface, especially not a graphical one, at this early stage.

These are the requirements for our program:

  1. The user should be able to play multiple games without restarting the program.
  2. The user should be able to specify the wanted size of the generalized chess board before each game (always sticking with 8x8 becomes a bit boring after a while).
  3. The user has to be asked for the initial position of the queen on the generalized board. The program has to make sure that the user entered a valid position (one that is actually on the board). We allow the user to place the queen in field (1, 1) - and therefore instantly win the game - but we consider it cheating; the program should print an appropriate message in this case.
  4. Afterwards, the computer and the user take turns in moving the queen:
    1. When it is the computer's turn, the program should try to come up with an intelligent move, preferably one that lets the computer win every game (this will not be possible, won't it?).
    2. When the user is asked for her / his move, the program must check that only legal moves are entered.
  5. A game should finish as soon as one player wins; an appropriate message should be printed.

Implementing the Game

From the given requirements, and the description of the game, it is straightforward to create a program completing the task, using the top-down design method and Structograms as presented in the discussion section. The only tricky part is to come up with a strategy which enables the computer to win as many games as possible.

Inventing a Strategy

To come up with an "intelligent" scheme to generate moves for Bob, the automated player, seems difficult at first glance. But, like most problems, it is easy to do as soon as one understands the underlying principles of solving problems.

Overview

First of all, we have to find out which moves we consider "good," and which ones we consider "bad." When we have understood those categories, we attempt to solve the problem by always making the best possible move in any situation; if we can't win that way, there should be no other way to win. (Is this true? Why can we be sure that a combination of moves, all of which seem best at the time we do them, yields the best overall result? There are plenty of problems where this is not the case.)

What Makes a Good Move?

The first answer to this question is the simple one: A move that has the queen in the winning field (1, 1) afterwards is the "perfect" move: It lets you win the game! Alas, such a move is not always possible (otherwise, these games would be very short!): We can only move the queen to the winning field, if it is either in the bottom row of the board, or in the leftmost column, or on the main diagonal (remember the rules how to move the queen?).

So, if the perfect move is not possible, what else can we do? The next best choice would be to move the queen to a position where the other player cannot reach a winning position either. Remembering the rules again, the winning position is reachable from those fields marked by the black lines in Figure 2.

Figure 2: Fields from which the queen can reach the winning field (1, 1) in a single move. If we want to make a good move, we cannot leave the queen on one of the marked fields. The hollow diamonds mark the closest fields which cannot reach the winning field in a single move.

Now assume we leave the queen in one of the fields marked with a hollow diamond in Figure 2. Not only is it impossible for the other player to reach the winning field in a single move, the other player is also forced to move the queen to a position from where we can reach the winning field, see Figure 3! In this sense, the marked fields become winning fields themselves: If we leave the queen in one of those fields, we have already won the game!

Figure 3: If we leave the queen in the given position, the other player is forced to move it to a field from where we can reach the winning field in the next move.

The Winning Strategy

Now we know that the two fields (2, 3) and (3, 2) are winning fields themselves. Applying the above reasoning again, if we cannot reach one of those fields in a move, we have to leave the queen in a field from where no winning field can be reached, and that forces the other player to move the queen to a field from where we can reach a winning position in the next move.

Thus, we again mark "bad"fields by drawing vertical, horizontal and diagonal lines from the two new winning fields; again we will find to fields closest to the origin which are not marked; again, those will be winning fields themselves. Applying this until all fields are either marked or winning fields yields a board as in Figure 4.

Figure 4: All winning fields in an 8x8 chess board.

If you examine the distribution of winning fields closely (see Figure 5 as well), you will find that there is exactly one winning field per row, per column and per diagonal (this results from our construction of winning fields). Furthermore, especially looking at Figure 5, you see that the lower half of the fields lie almost on a line, and the upper half lie almost on a line as well.

Figure 5: All winning fields in a 16x16 chess board.

How to Calculate the Winning Fields

Deeper mathematical insight assures us that the winning fields are in fact as close to two certain lines as possible, even deeper mathematical insight provides the fact that the upper line's slope is exactly
,
whereas the lower line's slope is exactly
.
Now it is easy to calculate the coordinates (x, y) of the n-th lower winning field: y = floor(n * phi) + 1, x = y + n. To get the coordinates for the n-th upper winning field, just exchange the values for x and y.

Interestingly enough, phi and phiHat are exactly the "Golden Ratio" and its inverse; and, not by coincidence, they are also the ratio of width and height of a Legal sized sheet of paper.

Who would have thought...