Introduction
：
/
To change this license header, choose License Headers in Project Properties.
To change this template file, choose Tools | Templates
and open the template in the editor.
/
/
File: main.c
Author: TG
Created on March 9, 2017, 9:02 PM
/
#include
#include
#include
#include
const int dr[8] = { -1, -1, -1, 0, 1, 1, 1, 0 };
const int dc[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
void printBoard(char board[][26], int n){
int i,j;
printf(“ “); //Print first two spaces in the beginning
for (i = 0; i= n) return 0;
if (col= n) return 0;
return 1;
}
int searchLine(char board[][26], int n, char row, char col, char colour, int deltaRow, int deltaCol, int num)
{
if (!positionInBounds(board, n, row, col)) return 0;
if (board[row][col] == ‘U’) return 0;
if (board[row][col] == colour)
{
if (num>0) return 1;
else return 0;
}
return searchLine(board, n, row + deltaRow, col + deltaCol, colour, deltaRow, deltaCol, num + 1);
}
，aipart1（），
，
Requirement
APS 105 — Computer Fundamentals
Lab #7: Reversi Game-Playing Program
Winter 2017
The goal of this lab is to build upon your work in Lab #6 to create a program that actually
plays the Reversi game against a human opponent. There are two parts to this lab. In the
first part, the exact algorithm to use for the computer moves is completely specified. In the
second part, you are free to make your own algorithm.
The course material necessary for completing this lab will be the same as Lab #6, and can
be found in Chapter 5 (User-defined Functions) and Chapter 6 (Arrays) of the zyBooks
textbook, especially Chapter 6.9 (Two-dimensional arrays). This is a two-week lab, due
Friday March 24 / Monday March 27. The TAs will be in the lab in the middle week,
Friday March 17 / Monday March 20.
Objective: Complete the Implemention for a Reversi Game
In Lab #6, you developed a program that represents the board of a Reversi game, and
that computes, for a given board state, the possible moves for the Black and White player.
Your solution also accepts a move as input and flips the tiles accordingly. In this lab, you
will build upon your work to create a Reversi game where a human can play against the
computer, with the computer making intelligent decisions about where to place its tiles.
Recap: The Rules of Reversi
The rules of the game were presented in the Lab #6 handout, and are briefly repeated
here. Reversi is played on a board that has dimensions n × n, where n is even and ranges
from 4 to 26. In the picture below n = 4. The game uses tiles that are white on one
side, and black on the other side (they can be “flipped” over to change their colour). One
player plays white; the other player plays black. The picture below shows the initial board
configuration, which has two white and two black tiles pre-placed in the centre. Observe
that rows and columns are labelled with letters.
APS 105 — Computer Fundamentals
Lab #6: Reversi Game – Board Configuration and Move Legality Checking
Fall 2015
The goal of this lab is to write code that sets up the input and does move legality checking
foraboard-typegamecalledReversi(alsocalledOthello). Itmakesuseoftwo-dimensional
arrays, and all of the previous material covered in this course, and requires some careful
thinking about how to convert human-thinking into working software. The relevant ma-
terial necessary for this lab can be found in the Carter text up to the end of Chapter 6.
Lab 6 will be due in the week of November 2.
Objective - Part of the Code for a Reversi Game
The goal of this lab is to write a program that will be used (in Lab 7) as part of a Reversi
game, as well as a little bit of the ’thinking’ code that will be used in that lab to have the
computer play against a human opponent.
Here is a brief description of the full Reversi game. Reversi is played on a board (like a
chess board or a checkers board) that has dimensions n⇥n, where n is even. In the picture
below n = 4. The game uses tiles that are white on one side, and black on the other side
(they can be “flipped” over to change their colour). One player plays white; the other
player plays black. The picture below shows the initial board configuration, which has
two white and two black tiles pre-placed in the centre. Observe that rows and columns are
labelled with letters.
!”
#”
$”
%”
!” #” $” %”
A “turn” consists of a player laying a tile of his/her own colour on a candidate empty
board position, subject to the following two rules:
1. There must be a continuous straight line of tile(s) of the opponent’s colour in at least
one of the eight directions from the candidate empty position (North, South, East,
West, and diagonals).
2. In the position immediately following the continuous straight line mentioned in #1
above, a tile of the player’s colour must already be placed.
After playing a tile at a position that meets the above critera, all of the lines of the oppo-
A “turn” consists of a player laying a tile of his/her own colour on a candidate empty
board position, subject to the following two rules:
1. There must be a continuous straight line of tile(s) of the opponent’s colour in at least
one of the eight directions from the candidate empty position (North, South, East,
West, and diagonals).
2. In the position immediately following the continuous straight line mentioned in #1
above, a tile of the player’s colour must already be placed.
After playing a tile at a position that meets the above critera, all of the lines of the oppo-
nent’s tiles that meet the criteria above are flipped to the player’s colour.
The turns alternate between the players, unless one player has no available move, in which
case the only player with an available move is allowed to continue to make moves until a
move becomes available for the opponent. At this point, the opponent is allowed to take a
turn and the alternating turns between the players resumes. The game ends when either:
1) the entire board is full, or 2) neither player has an available move. The winner of the
game is the one with more pieces on the board.
The Game Flow and Prescribed Algorithm
Your program must first ask the user for the board dimensions. Then, the program asks
the user if the computer is to be the Black or White player. For this lab, we will assume that
the Black player always gets the first move. So, if the computer is black, then the computer
should make the first move; otherwise, the program prompts the human player to make
the first move. The board is printed after every move.
Once the first move is out of the way, the turns proceed as described above, alternating
between Black and White unless one of the players has no move to make, which case your
program should print a message such as “W player has no valid move.” (i.e. for the case
of the White player) and should prompt the Black player for another move. After each
turn, your program must print the board, and must detect whether the game has been
won, or whether there is a draw. If your program detects the game is over (i.e. a win or
a draw), a message is printed and the program terminates. The specific messages to print
are: “W player wins.”, “B player wins.” or “Draw!”. If the human player makes an illegal
move, your program must detect this, print an error message, and end the game, declaring
the winner (with the corresponding message above).
Part 1: Implementing the Prescribed Algorithm
How Should the Computer Make Moves?
The method for the computer to make a move is as follows: for each possible place it could
make a move, it should compute a number, called a “score” that is larger when a square is a
better place for the computer to lay a tile. As these scores are computed for each square, it
should keep track of which one is the highest, and use that square as the move. (See below
on what to do in the event of a tied score).
The score for each candidate position is defined as the total number of the human player’s
tiles that would be flipped if the computer were to lay a tile at that position. The figure
below shows the scores if the computer were the White player.
2
!”
#”
$”
%”
!” #” $” %”
” ‘“ ‘“
A few important notes:
• It is likely that two or more squares may end up having the same score. In that case
your program must choose the position with the lower row. If there are two positions
with the same score in the same row, your program must choose the solution with
the lower column. You can ensure this happens easily by the order in which you
compute the score and test to see if it is the best.
• Your program must be able to work with the computer being either the Black or the
White player.
• You do not need to use error check on whether the computer is playing B or W.
• Write your program in a file called Lab7Part1.c
Here is a sample execution of the program (your program must conform. to this output).
Notice that, close to the end, the computer (playing White) has no valid move, and the
turn returns to the human player (playing Black).
Enter the board dimension: 4
Computer plays (B/W) : W
abcd
a UUUU
b UWBU
c UBWU
d UUUU
Enter move for colour B (RowCol): ba
abcd
a UUUU
b BBBU
c UBWU
d UUUU
Computer places W at aa.
abcd
a WUUU
b BWBU
c UBWU
d UUUU
3
A few important notes:
1. It is likely that two or more squares may end up having the same score. In that case
your program must choose the position with the lower row. If there are two positions
with the same score in the same row, your program must choose the solution with
the lower column. You can ensure this happens easily by the order in which you
compute the score and test to see if it is the best.
2. Your program must be able to work with the computer being either the Black or the
White player.
3. Write your program in a file called Lab7Part1.c.
Here is a sample execution of the program (your program must conform. to this output).
Notice that, close to the end, the computer (playing White) has no valid move, and the
turn returns to the human player (playing Black).
Enter the board dimension: 4
Computer plays (B/W) : W
abcd
a UUUU
b UWBU
c UBWU
d UUUU
Enter move for colour B (RowCol): ba
abcd
a UUUU
b BBBU
c UBWU
d UUUU
Computer places W at aa.
abcd
a WUUU
b BWBU
c UBWU
d UUUU
Enter move for colour B (RowCol): ab
abcd
a WBUU
3
b BBBU
c UBWU
d UUUU
Computer places W at ac.
abcd
a WWWU
b BBWU
c UBWU
d UUUU
Enter move for colour B (RowCol): bd
abcd
a WWWU
b BBBB
c UBWU
d UUUU
Computer places W at ca.
abcd
a WWWU
b WWBB
c WWWU
d UUUU
Enter move for colour B (RowCol): da
abcd
a WWWU
b WWBB
c WBWU
d BUUU
Computer places W at cd.
abcd
a WWWU
b WWWB
c WBWW
d BUUU
Enter move for colour B (RowCol): dd
abcd
a WWWU
b WWWB
c WBWB
d BUUB
Computer places W at db.
abcd
a WWWU
b WWWB
c WWWB
d BWUB
Enter move for colour B (RowCol): dc
abcd
a WWWU
b WWWB
c WWWB
4
d BBBB
W player has no valid move.
Enter move for colour B (RowCol): ad
abcd
a WWWB
b WWBB
c WBWB
d BBBB
B player wins.
Here is another sample execution where the human player makes an illegal move and the
computer wins.
Enter the board dimension: 6
Computer plays (B/W) : B
abcdef
a UUUUUU
b UUUUUU
c UUWBUU
d UUBWUU
e UUUUUU
f UUUUUU
Computer places B at bc.
abcdef
a UUUUUU
b UUBUUU
c UUBBUU
d UUBWUU
e UUUUUU
f UUUUUU
Enter move for colour W (RowCol): fa
Invalid move.
B player wins.
Part 2: Implementing Your Own Algorithm
In this part of the lab, your objective is to apply your wits, creativity and resourcefulness
to produce the best computer player possible, using any approach you are aware or can
think of. For example, you may wish to consider using an approach that looks ahead some
number of moves. There is, however, a time limit on how much computer time will be
allowed per move.
Note that the input and output formats of this part are identical to Part 1 above. The only
difference is that your program may use any method to choose the moves made by the
computer.
The instructors are organizing a competition where these programs will be played off
against each other. The best programs will be selected as Finalists, and invited to the
Finals stage. The Finals will be a public event (with pizza for all) on April 6, Thursday, at
the Bahen Atrium. All APS105 students are invited to watch the Finalists’ programs play
against one another on a large screen with graphics. You are encouraged to attend this
event to cheer on your colleagues. Top 3 finalists will be selected.
5
Other requirements:
1. Your program must conform. to the identical output format as in Part 1.
2. For a 26 × 26 board, and indeed all sizes of the board, your program must make a
move (lay a tile) within 1 second on the computer remote.ecf.utoronto.ca. Other-
wise, your program will not be markable or participate in the competition. See below
for information on how to measure the execution time of your moves.
3. In the event that two programs tie in head-to-head competition, the winner will be
the one that uses the least amount of computer time, in total, for making all of its
moves.
4. If your program makes an invalid move, it will immediately lose the game (as in Part
1 above).
Place your program in a file called Lab7Part2.c.
How to Measure the Passage of Time in your Program
If you create an algorithm that searches through a sufficiently large number of choices
for moves, it may use more than the allowed one second time limit (on the computer
remote.ecf.utoronto.ca). There are at least two ways to deal with this:
• Write an algorithm that you are certain will never use more than a second on a 26×26
board, by testing it and measuring it on the slowest test cases.
• Have your program check the elapsed time while it is running, and stop searching
for the next move, when it gets close to the time limit. Here it should use the best
choice found to that point. To do this, you will need to make use of the following
code, which shows how to measure time:
At the top of your C program, add these two lines:
#include
#include
Then, to time part of your program, use the code as below. It consists of two calls to
functions that returns the current time in seconds and microseconds. The code below
produces a value, in the variable total_time in seconds.
struct rusage usage; // a structure to hold “resource usage” (including time)
struct timeval start, end; // will hold the start and end times
getrusage(RUSAGE_SELF, usage);
start = usage.ru_utime;
double timeStart = start.tv_sec +
start.tv_usec / 1000000.0; // in seconds
/ PLACE THE CODE YOU WISH TO TIME HERE */
getrusage(RUSAGE_SELF, usage);
end = usage.ru_utime;
6
double timeEnd = end.tv_sec +
end.tv_usec / 1000000.0; // in seconds
double totalTime = timeEnd - timeStart;
// totalTime now holds the time (in seconds) it takes to run your code
Grading by TA and Submitting Your Program for Auto-Marking
here are a total of 10 marks available in this lab, marked in two different ways:
• By your TA, for 4 marks out of 10. Once you are ready, show your program to your
TA so that it can be marked for style. (1 mark), and to ask you a few questions to test
your understanding of what is happening (3 marks). Programs with good style. have
been described in previous labs, so that will not be repeated here. Be ready to explain
your approach to Part 2 to your TA.
• By an auto-marking program for 6 marks out of 10. You must submit both of your
program files through the ECF computers for marking. We will use a software pro-
gram to compile and run your programs, and test them with different inputs. Part 1
is worth 4 marks; Part 2 is worth 2 marks. The two parts will be marked differently
from one another.
1. Part 1 will be marked using the same procedure applied in prior labs to ensure
your program’s output exactly matches the prescribed output.
2. Part2willbemarkedbyplayingyourgame-playingprogramagainsttwogame-
playing Reversi programs, developed by the APS105 course staff: a first which
is just slightly “smarter” than the Part 1 solution, and a second that is a little
bit smarter than the first. Your program will be played against the two staff-
developed programs twice: in one instance your program will play Black and
in the second instance your program will play White. If your program is able to
win in either instance, you will receive one mark.
• Long before you submit your program for marking, you should run the exercise
program that compiles and runs your program (Part 1) and gives it sample inputs,
and checks that the outputs are correct. Note that for this lab, the exercise program
will only test Part 1. Ensure your Part 2 conforms to the identical output style. as Part
1. Similar to the previous labs, you should run the following command:
/share/copy/aps105s/lab7/exercise
within the directory that contains your solution programs.
This program will look for the file Lab7Part1.c in your directory, compile it, and run
it on some of the test cases that will be used to mark your program automatically later.
If there is anything wrong, the exercise program will report this to you, so read its
output carefully, and fix the errors that it reports.
• Once you have determined that your programs are as correct as you can make them,
then you must submit your program for auto-marking. This must be done by the end
7
of your lab period as that is the due time. To do so, go into the directory containing
your solution files and type the following command:
/share/copy/aps105s/lab7/submit
This command will re-run the exercise program (on Part 1) to check that everything
looks fine. If it finds a problem, it will ask you if you are sure that you want to
submit. Note that you may submit your work as many times as you want prior to
the deadline; only the most recent submission is marked.
For Part 1, the exercise program (and the marker program that you will run after
the final deadline) will be looking for the exact letters as described in the output in
this handout, including the capitalization. When you test your program using the
exercise program, you will see that it is expecting the output to be exactly this, so
you will have to use it to see if you have this output correct.
Important Note: You must submit your lab by the end of your assigned lab period.
Late submissions will not be accepted, and you will receive a grade of zero.
You can also check to see if what you think you have submitted is actually there, for
peace of mind, using the following command:
/share/copy/aps105s/lab7/viewsubmitted
This command will download into the directory you run it in, a copy of the file that
has been submitted. If you already have a file of that same name in your directory,
that file will be renamed with a number added to the end of the filename.
After the Final Deadline — Obtaining Automark
Briefly after all lab sections have finished, you will be able to run the automarker to deter-
mine the automarked fraction of your grade on the code you have submitted. To do so,
run the following command:
/share/copy/aps105s/lab7/marker
This command will compile and run your code, and test it with all of the test cases used to
determine the automark grade. You will be able to see those test cases’ output and what
went right or wrong. You will also be able to see the success of your Part 2 against the
APS105 staff-developed game-playing Reversi programs.
8