Introduction
8，：
1.IllegalMoveException，（）
2.OthelloPosition，，，。
3.Othello.java, main，str，，。
4.OthelloAlgorithmImpl.java，OthelloAlgorithm，Minimax。
5.OthelloEvaluatorImpl.java, OthelloEvaluator。
6.OthelloAction.java，。（1,1）。pass。
Requirement
Assignment : Othello
In this assignment, you will write an Othello engine, i.e., a program that computes moves for the game Othello (a.k.a. Reversi).
Programming language
Ideally, you should write your solutions in Java (1.5 or later). If you absolutely want to write your engine in another language, you will have to do slightly more work yourself (since you cannot use the provided helper code). Talk to the lecturer about specifications and what code should be handed in.
Assignment
Basically, you should write a program that takes an Othello positions and returns a recommended move for the player who has the move.
You will also have to implement a representation for the positions. In the helper code, the Java class OthelloPosition is provided. The code for this class is incomplete, however. You will have to fill in code at the places maked ‘TODO’ in the file.
The actual engine should take a position, use Alpha-Beta search with a sensible heuristic, and return a suggested move. The easiest way is to construct a class that implements the provided Java interface OthelloAlgorithm. This interface has a method evaluate that takes a position and returns an OthelloAction. It also has methods for setting the heuristic evaluation method (an implementation of the interface OthelloEvaluator) and one for setting the search depth.
The provided implementation of the position, and the way it is sent around in the code is not the most efficient way of doing things, but it is fairly easy to understand and work with. If you want to switch to a more efficient representation, feel free to do so.
Requirements: Your solution must use Alpha-Beta search and a sensible heuristic evaluation. It should be good enough to soundly beat a standard Alpha-Beta implementation that uses a naive heuristic (just counting how many black and white markers there are on the board). You must be able to beat it both as black and white.
Note: In this assignment it is assumed that white always start. This means that white player is always max and black always min in the minimax algorithm.
Helper code
The following source files are available:
IllegalMoveExeption.java
OthelloAction.java
OthelloAlgorithm.java (interface)
OthelloEvaluator.java (interface)
OthelloPosition.java (incomplete)
The helper code (and the test code described below) can also be downloaded from git by running the following command in a Linux terminal: git clone
Interface
To run your program, you should provide a shell script. called othello (without .sh) which should be executable and be placed in your home directory at ~/edu/5DV122/lab1/. Please use the provided example script. file and change it so it works with your solution. Important: cd “$(dirname “$0”)/src” is needed to get a relative path to the code. Just change /src to the folder you have the program in, do not use a hard coded path!
The shell script. should take two arguments, a description of the position and a time limit. The first argument should be an ascii string of length 65. The first character is W or B, and indicates which player is to move. The remaining characters should be E (for empty) O (for white markers), or X (for black markers). These 64 charachters describe the board, with the first character referring to the upper left hand corner, the second character referring to the second square from the left on the uppermost row, and so on. For example, the 10th character describes the second square from the left on the second row from the top. Don’t forget to check if the inputs are correct.
The second parameter gives a number of seconds. This should guide the depth of your search. If the second parameter is 5, you should see to it that, when run on itchy or scratchy (using Putty in Windows or ssh in Linux), your program replies and terminates within 5 seconds.
The shell script. should write a move on standard out on the format (4,7), indicating that the move suggested is to place a marker on the fourth row from the top and the seventh column from the left. If the player who has the move has no legal move, the script. should instead write pass on standard out.
Please make sure that you also include the following in your report:
Show that you tested your solution thoroughly (e.g. printouts from different runs)
oBoth as black and white
oUsing different time limits
Describe the heuristics you used
How you translate time into depth
All code necessary to run your solution should be placed in ~/edu/5DV122/lab1/. Make sure that permissions are set correctly.
Before you hand in, read the specification again to make sure you did not miss anything!
Testing your program
Scripts and code for testing your program can be found in test_code.zip. On a linux machine, do the following.
1.Unpack the zipfile in a directory (unzip test_code.zip)
2.Make sure that the scripts ‘othellostart’ and ‘othello’ are executable. If not, write ‘chmod +x othellostart othello’.
3.Run the ‘othellostart’ script. with three parameters, indicating which programs should play against each other and the time limit for them:
o./othellostart white_player black_player time_limit
oFor instance, if your home directory is ‘/home/abc123/‘ and you have placed your ‘othello’ script. in ~/edu/5DV122/lab1/, then you can play the test program against your own (as black) with a 5s time limit by writing ‘./othellostart ./othello /home/abc123/edu/5DV122/lab1/othello 5’.
oYou can also play against a friend by giving the path to her or his script. instead of ./othello.
Additional resources for assignment (）
：，Alpha-Beta，5。。。
，（）