![[BIO97 Logo]](../../../images/flag97s.gif)
Sponsored by Data Connection.
![[Data Connection logo]](../../../images/dc_logo3.gif){kind=logo}
| |
The British Informatics
Olympiad Sponsored by Data Connection. |
|
 |
The 1997 British Informatics Olympiad Round One Question 2 |
| Question 2 Othello (Reversi) |
Othello is a game played on
an 8 by 8 board with two players (White and Black). Each
player has 32 pieces which are white ('0') on one side
and black ('*') on the other. Play alternates between the
two players, with White playing first. A move is made by placing a piece, with the colour of the current player visible, on an unoccupied square of the board which has at least one of its eight neighbouring squares occupied. Any enemy pieces which are in a direct line between this piece and another of the player's own colour (horizontally, vertically or diagonally) are turned over so that they show the current player's colour. A piece may change colour several times during a game. |
Example |
|
-> |
|
-> |
|
| 2 (a) [25 or 17 marks] |
Write a program to play Othello. Both White and Black will be controlled by the computer, according to a fixed strategy. There are two strategies you may choose from. Implementing the first can earn you a maximum of 17 points for this question, whereas the second strategy is worth a maximum of 25 points. | |
Strategy |
Each player will always make the move which changes the largest number of pieces to their colour. If there are several equally good moves the one lowest down the board (on the screen) will be made, and if there are several of these the one furthest to the right will be chosen. | |
Strategy |
Each player always considers the possible next move of their opponent. The move played is the one which guarantees that the largest number of pieces will be their colour after their opponent's next move. With several equally good moves, the lowest/rightmost on the board is chosen as explained in strategy (1). | |
| For example, if it is Black to play, and the board looks like: |    |
|
| Under the first strategy Black will play the move that turns over two White pieces: | |
|
| Under the second strategy Black will play the move that turns over a single White piece: | |
| White can now change the colour of at most one Black piece, leaving two on the board. If the first strategy's move had been played White would be able to change the colour of all four Black pieces on the board, leaving none. | ||
| Your program should first
read in a 4x4 board, which will be in the form of four
lines of four characters - '*' for a black piece, '0'
(zero) for a white piece, and '.' for an empty square. At
least one of these squares will be non-empty. This 4x4
board should be used as the centre section of the 8x8
board the game is played on. Once the central section has been input you should print which strategy your program is using, and display the board. Until your program terminates you should repeatedly wait for input, and then:
If playing a move takes you to the end of the game, you should print out which player has won and by how much (or print 'Black and White draw.'), and then terminate. |
Sample run |
Sample run |
| 2 (b) [2 marks] |
What is the largest number of pieces (excluding the one being placed on the board) that can be turned over in one move? |
| 2 (c) [5 marks] |
Suppose we start with the centre 4x4 squares all occupied. If it is White to play next, is there a strategy for Black that will ensure at least one corner is Black at the end of the game? Justify your answer. |
| 2 (d) [8 marks] |
The following
board position has been reached at the end of a game, and
Black has just played. If you had been watching the last
move there are 97 different games you may have observed.
Black may only have played a piece on one of the 35 Black
squares, but depending on the board's layout on the
previous turn some of these moves may also have turned
over additional pieces. If you have been watching for the last two moves how many different games might you have observed? |
|