Reversi Game-Playing Program Solution

$30.00

Description

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.

This lab will be due Friday March 16 / Monday March 19.

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.

!” #” $” %”

!”

#”

$”

%”

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).

  1. 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.

!”

#”

$”

%”

!”

&”

‘”

‘”

#”

$”

%”

AAfewfewimportantnotes:

1. •ItItisislikelythat two or more squares may end up havingthethesamescorescore.In.Inthatthatcasecase

youryourprogrammustchoose the position with thelowerrowrow..IfIftheretherearearetwotwopositions

withwiththethesame score inin the same row, your programmustmustchoosesethethesolutionsolutionwithwith

the lower column. You can ensure this happens easily by the order in which you

the lower . You easily by the order in which you

compute the score and test to see if it is the best.

compute the score and test to if it is the best.

2. •YourYourprogramprogrammustmust bebe ableable toto workwork withwith thethe computercomputerbeingbeingeithereitherthetheBlackBlackororthethe

WhiteWhiteplayer.player.

You do not need to use error check on whether the computer is playing B or W.

3. •Write your program in a file called Lab7Part1.c.

• 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 turnHerereturnsisasampletotheexecutionhumanplayerofthe(playingrogramBlack)(your. program must conform to this output).

Notice that, close to the end, the computer (playing White) has no valid move, and the Enterturn returnstheboardtothedimension:humanplayer4 (playing Black).

Computer plays (B/W) : W

Enterabcd the board dimension: 4

a ComputerUUUU plays (B/W) : W

abcd

b UWBU

a UUUU

c UBWU

b UWBU

d UUUU

c UBWU

Enter move for colour B (RowCol): ba

d UUUU

abcd

Enter move for colour B (RowCol): ba

a UUUU

abcd

b BBBU

a UUUU

c UBWU

b BBBU

d UUUU

c UBWU

Computer places W at aa.

d UUUU

abcd

Computer places W at aa.

  • WUUU abcd

  • BWBU a WUUU

  • UBWU b BWBU

  • cUUUUUBWU

EnterdUUUUmove for colour B (RowCol): ab

abcd

a WBUU

3

BBBU c UBWU d UUUU

Computer places W at ac. abcd

a WWWU

  • BBWU

  • UBWU d UUUU

Enter move for colour B (RowCol): bd abcd

a WWWU b BBBB

  • UBWU

d UUUU

Computer places W at ca.

abcd

  • WWWU b WWBB c WWWU d UUUU

Enter move for colour B (RowCol): da abcd

  • WWWU

  • WWBB c WBWU d BUUU

Computer places W at cd. abcd

a WWWU

  • WWWB

  • WBWW d BUUU

Enter move for colour B (RowCol): dd abcd

a WWWU b WWWB

  • WBWB

d BUUB

Computer places W at db.

abcd

  • WWWU b WWWB c WWWB d BWUB

Enter move for colour B (RowCol): dc abcd

  • WWWU

  • WWWB c WWWB

4

BBBB

W player has no valid move.

Enter move for colour B (RowCol): ad

abcd

  • 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

  • UUUUUU b UUUUUU c UUWBUU d UUBWUU e UUUUUU f UUUUUU

Computer places B at bc. abcdef

  • UUUUUU

  • 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.

Other requirements:

1. Your program must conform to the identical output format as in Part 1.

  1. For a 26 26 board, and indeed all sizes of the board, your program must make a move (lay a tile) within one second on the computer remote.ecf.utoronto.ca. Oth-erwise, your program for Part 2 will not be marked. See below for information on how to measure the execution time of your moves.

  1. 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.

Testing Your Work in Part 2

In Part 2 of this lab, your solution will be marked by playing your game-playing program against two game-playing Reversi programs, developed by the APS105S 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 two marks. Part 2 will be marked out of a total of 4 marks.

If you have implemented a computer AI strategy to play the Reversi game in Part 2, and would like to test the strength of your AI, we provide you with both the “smarter” AI and the “even smarter” AI strategies in a static library file called liblab7part2.a. This tutorial helps you to use this library file to test the strength of your AI before submitting your solution.

Your solution in Lab 7 should have two lines of code that uses printf() and scanf() to prompt a human player to enter his/her move. To set up your code for testing using liblab7part2.a, replace these two lines of code with something similar to the following:

findSmarterMove(board, n, colour, &row, &col);

printf(“Testing AI move (row, col): %c%c\n”, row + ‘a’, col + ‘a’);

findSmarterMove will use the “smarter” AI strategy to find the best move. If you wish to use the “even smarter” AI, call the findSmartestMove function with the same parameters. You will also need to add:

#include “lab7part2lib.h”

to the top of your program.

To compile your code successfully with our provided static library, you will need to first copy the following two files:

lab7part2lib.h

liblab7part2.a

to the directory that contains your Lab 7 Part 2 solution in your CodeLite project. Both files can be found with the other files (such as the handout) in Lab 7 in the course web-site. To link the provided library called liblab7part2.a in your CodeLite project, right click on your project within the workspace, select Settings (at the bottom) and then select Linker from the left hand side in the window that pops up. Then, in Linker Options, enter -llab7part2 (that is “dash” “lower-case L” “lab7part2”).

6

Click Apply and then OK to close this window.

You are now ready to compile your solution with the provided static library, and test your solution to your heart’s content.

Note 1: In the provided archive file liblab7part2.zip, we have provided pre-compiled header and library files for three different operating systems: Linux (32-bit), Linux (64-bit), and MacOS. Use Linux (64-bit) version (9310 bytes in size) for the ECF computers. If you use Windows, please use the Virtual Machine image provided in Lab 1, and then use the Linux (64-bit) version.

Note 2: If you prefer to compile your code using command-line tools, use the following command line:

gcc Lab7Part2.c -L. -llab7part2 -std=c99

where Lab7Part2.c is assumed to be the name of the file containing your Part 2 solution code. Before running this command to compile your solution, you should make sure that both lab7part2lib.h and liblab7part2.a have been copied to the current working direc-tory. These files can be found with the other files in Lab 7 in the course website.

Measuring 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 <sys/time.h>

#include <sys/resource.h>

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;

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 3 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 (2 marks). Programs with good style have been described in previous labs, so that will not be repeated here. Be ready to explain your approach in Part 2 to your TA.

  • By an auto-marking program for 7 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 3 marks; Part 2 is worth 4 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.

    1. Part 2 will be marked by playing your game-playing program against two game-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. Both programs will be identical to the library we pro-vided to you for testing your work. 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 two marks.

  • 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 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

9Briefly 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.

10