![[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 Solution to Question 2: Othello (Reversi) |
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 1. 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 2. 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).
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.
We will work through the solution to strategy 1 first, then adapt it to strategy 2. Example code will be given on this page in Pascal only; documented Java code is also available.
Reading in and displaying the board. The
first part of the solution is to read in the supplied starting
board. (One common version of this game has the starting board
blank apart from the pattern
at the centre.) We define simple types and structures to
represent the board:
type
TPiece = (Blank, White, Black);
TBoard = array[1..8, 1..8] of TPiece;
const
Symbol: array[TPiece] of Char = ('.', '0', '*');
The code to initialise and read in a board (taking the bottom left as (1,1)) is then as follows.
for x := 1 to 8 do for y := 1 to 8 do Board[x,y] := Blank;
for y := 6 downto 3 do
begin
for x := 3 to 6 do
begin
Read(c);
case c of
'.': Board[x,y] := Blank;
'0': Board[x,y] := White;
'*': Board[x,y] := Black;
end;
end;
ReadLn;
end;
(For testing your program it is often convenient to avoid having to type in the starting data every time you run it by hard-coding one example case. But do remember to re-enable the proper input routine before you run out of time!)
A procedure for displaying the state of a board is going to be useful, and the following does the job.
procedure ShowBoard(var Board: TBoard);
var x, y: Integer;
begin
for y := 8 downto 1 do
begin
for x := 1 to 8 do
Write(Symbol[Board[x,y]]);
WriteLn;
end;
WriteLn;
end;
Reading the board in and displaying it with the appropriate strategy picks up useful, easy marks, even if the program does nothing else.
Checking if a piece has a neighbour. Before moving, we need to know if square 'has at least one of its eight neighbouring squares occupied'. There are a number of ways of doing this. For example, this function returns false if all the squares are blank and takes the edges into account.
function HasNeighbour(x, y: Integer): Boolean;
var Found: Boolean;
begin
Found := False;
if (x > 1) and (y > 1) then
if (CurrentBoard[x-1, y-1] <> Blank) then Found := True;
if (x > 1) then
if (CurrentBoard[x-1, y ] <> Blank) then Found := True;
if (x > 1) and (y < 8) then
if (CurrentBoard[x-1, y+1] <> Blank) then Found := True;
if (y < 8) then
if (CurrentBoard[x , y+1] <> Blank) then Found := True;
if (x < 8) and (y < 8) then
if (CurrentBoard[x+1, y+1] <> Blank) then Found := True;
if (x < 8) then
if (CurrentBoard[x+1, y ] <> Blank) then Found := True;
if (x < 8) and (y > 1) then
if (CurrentBoard[x+1, y-1] <> Blank) then Found := True;
if (y > 1) then
if (CurrentBoard[x , y-1] <> Blank) then Found := True;
HasNeighbour := Found;
end;
A more elegant way to do this is to extend the size of array TBoard to [0..9, 0..9] and initialise the edges to blanks. This removes the need to check if we are at the edge before checking the squares.
It will also be useful to have a function that returns the opposing player to a specified player.
function Enemy(Piece: TPiece): TPiece;
begin
if (Piece = Black) then
Enemy := White
else if (Piece = White) then
Enemy := Black
else
Enemy := Blank;
end;
Making a move. The hardest part of the solution to strategy 1 is probably writing the procedure to make a move in a specified square, turning over opposing pieces which are in a direct line between this another piece of the player's own colour (horizontally, vertically or diagonally), so that they show the current player's colour. One competitor misinterpreted this as including the case when the 'direct line' is broken by blanks, but this point was made clear in the example provided. The turning over process consists of the following steps, repeated for each of the eight directions (including diagonals).
The count of pieces turned over will be a key requirement for picking the best location to go according to the strategy. The following procedure Move places a piece of the current player's on the specified square, then calls sub-procedure CheckSwap to investigate each direction for opposing pieces to be turned over. The code is annotated to explain it.
procedure Move(x, y: Integer);
{ Make a move on CurrentBoard, turning pieces over as necessary. The
number of pieces turned over is counted in global variable Turned. }
procedure CheckSwap(dx, dy: Integer);
var
Search: Boolean;
Found: Boolean;
x1, y1: Integer;
begin
x1 := x + dx;
y1 := y + dy;
{ Only search if the line would not take us off the board and
there is at least one enemy piece. }
Search := (x1 >= 1) and (x1 <= 8) and (y1 >= 1) and (y1 <= 8);
if Search then Search := (CurrentBoard[x1, y1] = Enemy(Player));
Found := False;
while Search do
begin
x1 := x1 + dx;
y1 := y1 + dy;
{ Stop searching if we're off the board }
Search := (x1 >= 1) and (x1 <= 8) and (y1 >= 1) and (y1 <= 8);
if Search then
begin
{ Stop searching if we find a blank or one of Player's pieces }
Search := (CurrentBoard[x1, y1] = Enemy(Player));
{ Check if one of Player's pieces }
Found := (CurrentBoard[x1, y1] = Player);
end;
end;
if Found then
begin
{ There are enemy pieces to turn over }
while (x1 <> x) or (y1 <> y) do
begin
x1 := x1 - dx;
y1 := y1 - dy;
CurrentBoard[x1, y1] := Player;
{ Add one to the count of pieces turned }
Inc(Turned);
end;
Dec(Turned); { Corrects for counting the piece placed at (x,y) }
end;
end;
begin
Turned := 0;
CurrentBoard[x, y] := Player;
{ Check each of the 8 directions }
CheckSwap(1, -1);
CheckSwap(1, 0);
CheckSwap(1, 1);
CheckSwap(0, 1);
CheckSwap(-1, 1);
CheckSwap(-1, 0);
CheckSwap(-1, -1);
CheckSwap(0, -1);
end;
Calling procedure Move will add the player's token to the board and turn over opposing pieces as appropriate.
Choosing the best place to move according to strategy 1. The strategy is to pick a legal square that turns over the maximum number of opposing pieces. This is simply accomplished by
FindBestMove_1 does this. The best number of pieces turned and the location of the best move are stored in tb, xb and yb; by starting from the bottom right and working upwards, we will automatically save the appropriate location if more than one equally good move exists.
procedure FindBestMove_1(var x, y: Integer);
{ Implements strategy 1.
Selection between equal best moves is performed by
trying moves in the required order. }
var
x1, y1: Integer;
tb, xb, yb: Integer;
begin
{ Back up the current board }
OldBoard := CurrentBoard;
{ Start with a 'best' move of -1 so a valid move will be returned }
tb := -1;
for y1 := 1 to 8 do for x1 := 8 downto 1 do
if CurrentBoard[x1, y1] = Blank then if HasNeighbour(x1, y1) then
begin
{ Try moving on this square }
Move(x1, y1);
if Turned > tb then
begin
{ This is the best move seen so far }
xb := x1;
yb := y1;
tb := Turned;
end;
CurrentBoard := OldBoard;
end;
{ Return the co-ordinates of this square }
x := xb;
y := yb;
end;
Completing the program. All that remains is to write code to take an instruction from the keyboard, either move to the specified location or make the required number of moves according to strategy 1, and terminate appropriately. The program must check if the end of the game has been reached, and if so, print which side wins and by how much. This code can be found in the Pascal solution b97q2st1.pas or the Java solution Reversi1.java.
Extending the program to strategy 2. The solution to strategy 1 forms part of the solution to strategy 2, as the final move on the board should be made according to strategy 1 (since no opposing move can be made). For all other moves, the solution follows the same process, but it is now necessary, for each possible move of the player's, to consider all possible moves that the opponent could make in the next turn. The best move is the one which guarantees the largest total after the opponent has moved. Code to do this can be found in procedure FindBestMove_2_b in b97q2st2.pas. The rest of the program is unchanged apart from displaying "Strategy 2" and calling the new procedure rather than the old.
Marking question 2(a) [25 marks available]
There are two multiple part tests used to check 2(a). Marks are given within the tests, to the left of the expected output from the program. Comments are given on the right-hand side, indicating why the marks are being given. Incorrect output at any stage gets no marks for that stage. If the program crashes/hangs part way through a test, or takes longer than two minutes, the rest of that test should be discarded.
Note: Test 2 will produce different output depending on which strategy has been implemented, although the input will remain the same. There are more marks available for implementing the second strategy. The strategy implemented should be displayed after the initial data has been input, and you should follow the marking scheme indicated for this strategy.
Test 1 (both strategies)
| Test 1 | Program text | Comments |
[1] [1] [2] [2] |
.... .*0. .0*. .... Strategy 1 (or 2) ........ ........ ........ ...*0... ...0*... ........ ........ ........ 0 3 5 ........ ........ ........ ..000... ...0*... ........ ........ ........ 0 3 6 ........ ........ ..*..... ..0*0... ...0*... ........ ........ ........ -1 |
Printing strategy Displaying initial board Playing a correct white move Playing a correct black move |
[1] Mark for program terminating cleanly.
Test 2 (strategy 1)
| Test 2 (strategy 1) | Program text | Comments |
[2] [2] [2] [2] [2] |
0.0* 0000 0*00 ..0* Strategy 1 ........ ........ ..0.0*.. ..0000.. ..0*00.. ....0*.. ........ ........ 1 ........ ........ ..0.0*.. ..0000.. ..0*00.. ....00.. ......0. ........ 1 ........ ........ ..0.0*.. ..000*.. ..0*0*.. ....**.. .....*0. ........ 10 .....0*. .....0.. ..0.*0.. ..0*0*.. 0000***. ....0**. .....**. .....*** 39 *0000000 0*****0* 00***0** 000***0* 0000**** 00000*** 0000**** 00000*** White wins by 4. |
Playing first move Playing second move Playing 10 moves ahead Playing to the end of the game Printing the correct conclusion |
Test 2 (strategy 2)
| Test 2 (strategy 2) | Program text | Comments |
[3] [3] [5] [5] [2] |
0.0* 0000 0*00 ..0* Strategy 2 ........ ........ ..0.0*.. ..0000.. ..0*00.. ....0*.. ........ ........ 1 ........ ........ ..0.0*.. ..0000.. ..0000.. ..0.0*.. ........ ........ 1 ........ ........ ..0.0*.. ..00*0.. ..0*00.. ..*.0*.. .*...... ........ 10 ........ .*0..... ..0.0*.. ..0**0.. ..00**.. ..0.***. .00.**.. 0...000. 39 ***0**** 0*000**0 0000*0*0 0000**00 00000**0 00000*00 0000**00 00000000 White wins by 26. |
Playing first move Playing second move Playing 10 moves ahead Playing to the end of the game Printing the correct conclusion |
Total 17 marks available for strategy 1; 25 marks available for strategy 2.
(Supplementary 1 (both strategies): A program may play according to one of the strategies but fail to print which strategy it is using, or incorrectly print the strategy. In these cases mark using the scheme that most closely matches the program’s output, but debit [1] mark.)
(Supplementary 2 (both strategies): If the final board position is incorrect, but the conclusion given is correct for the board position output, then the [2] marks for the conclusion should be given.)
| |
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?
The answer is 19, which gets 2 marks. This is for boards such
as
Where a move by black to (4,4) would turn over 19 white pieces.
| |
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.
Yes, there is a strategy. One mark is available for making this assertion, and one mark each (up to a maximum of four) for making any one of the following points:
A maximum of 5 marks are available.
| |
| 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? |
|
The reasoning behind this problem is as follows. Given the observed final position, the number of possible games that could have been observed is found by counting, for each location that black could have gone on, the number of permutations of pieces that could have been turned over. This gives the total 97. To solve the problem and arrive at the figure of 8037, which gets 8 marks, it is necessary to identify each of these permutations, and perform the same comparison one move further back for all possible moves white could have made that would have led to that board.
No example program solving this problem is available at this stage, but it is hoped to provide one soon. Few competitors attempted this question, which was designed to be very challenging given the time available.
| |
| |