[BIO Logo] The British Informatics Olympiad is
the computing competition for schools and colleges.
We are proud to present BIO 2004, sponsored by Lionhead Studios.
Sponsored by Lionhead Studios

The 2004 British Informatics Olympiad - Round One question 2

Question 2
Four in a Line

In the game of Four in a Line, two players alternate dropping pieces of their own colour into a vertical board. The board consists of seven columns, each of which can hold six pieces. On their turn, a player can choose to drop their piece into any column which still has an empty space. When a piece is dropped into a column, it falls to the lowest unused position in that column.

The winner is the first player to form a line of four adjacent pieces of their own colour; horizontally, vertically or diagonally.

A simple strategy is for a player to choose their moves based on the following rules:

  1. If there is a move which will win the game immediately, this move is played. If several such moves exist, the leftmost one is played.
  2. If rule 1 does not indicate which move to take and there is a move which, if played by the other player would cause them to win immediately, this move is played. If several such moves exist, the leftmost one is played.
  3. If neither rule 1 nor rule 2 indicates which move to take, play in the leftmost column which still has empty space.

The following examples demonstrate the simple strategy on some typical boards. Note that the boards themselves have arisen from an initial sequence of moves that did not follow the strategy.

The first player's pieces are shown using (1) and the second player's pieces are shown using (2). The columns are numbered from left to right, with the leftmost column being number 1.

If it is the first player's turn on the following board, they must play in column 3, according to rule 1, to win with a horizontal line of four pieces.

[ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] (2) (2) (2) [ ]
[ ] [ ] [ ] (1) (1) (1) [ ]
  If it is the second player's turn on the following board, they must play in column 4, according to rule 2, to prevent the first player winning with a diagonal line on their next move by playing in this column.
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
(1) [ ] [ ] [ ] [ ] [ ] [ ]
(2) (1) [ ] [ ] [ ] [ ] [ ]
(2) (2) (1) [ ] [ ] (1) [ ]
(2) (2) (1) [ ] [ ] (1) [ ]
  If it is the first player's turn on the following board, they must play in column 1, according to rule 3.
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] (1) (2) (2) [ ] [ ] [ ]
[ ] (2) (1) (1) [ ] [ ] [ ]
 
2 (a)
[26 marks]

Write a program to play Four in a Line. Both players will be controlled by the computer and play using the simple strategy.

Your program should first read in a single integer, n (1≤n≤10). This will be followed by a line containing n integers, indicating the columns for the first few moves of the game; the first number indicating the first move for player one, the next number indicating the first move for player two, etc. The columns are numbered from left to right, with the leftmost column being number 1. None of these initial moves will generate a winning line.

You should then output the board, indicating empty spaces with a -, pieces belonging to player 1 with a * and pieces belonging to player 2 with an o.

Until your program terminates you should repeatedly wait for input, and then:

  • If you receive the letter n, you should play the next move of the game.
  • If you receive the letter r, you should play the rest of the game, until one player has won or the board is full.
  • Ignore any other input

After each command, you should output the board. If the game has been won you should output Player 1 wins (for a first player win) or Player 2 wins (for a second player win), and then terminate. If the board is full, you should output Draw and then terminate.

[In the sample run, the comments shown in italics in square brackets are for information only. These should not be entered into, or produced by, your program.]

  Sample run
9
3 2 3 4 4 4 2 2 3
 
-------
-------
-------
-o*o---
-***---
-o*o---
 
n [Rule 2]
-------
-------
--o----
-o*o---
-***---
-o*o---
 
n [Rule 3]
-------
-------
--o----
-o*o---
-***---
*o*o---
 
r [Rule 2 then Rule 1]
-------
-------
--o*---
-o*o---
o***---
*o*o---
 
Player 1 wins
2 (b)
[2 marks]
What is the final board position, playing until one player has won or the board is full, if both players follow the strategy, starting with an empty board?
2 (c)
[6 marks]
The following board has arisen after a game in which the two players, using an unspecified strategy, continued to play after the game had been won:

o**oo**
*oo**oo
o**oo**
*o***oo
o*o*o**
*oo*ooo

  What is the smallest number of moves which might have occurred when a winning position was reached? What is the largest number of moves? Justify your answer for the smallest number of moves.
2 (d)
[3 marks]
Suppose player one drops all 21 of their pieces into the board, without player two playing any of their pieces. How many different board patterns can be generated?

The British Informatics Olympiad