Exercise 3: Adversarial Search in Gomoku
- [9/17: 4:36pm] Your Gomoku player will only be required to play on square boards.
- [9/18: 3:57pm] I have updated the server and client files on Eureka.
Now you can simply run the server from the shell with racket.
Note that the two-second time limit for moving is now enforced.
Based on my informal experiments, I recommend leaving a margin of 10msec
to allow for your player's move to reach the server.
- [9/18: 4:41pm] After your program sends its move to the server,
display the maximum depth that was searched.
Report this value as a number of ‘ply’,
which counts a complete turn (both players move) as one ply.
In this exercise, you will, among other things:
- acquire experience implementing game search techniques
- improve your programming skills
- have fun
Each of you will write a program that plays Gomoku.
This is an individual assignment. Appropriate expectations on working together apply.
If you search for them, you can find many implementations of Alpha-Beta search
in many different programming languages.
It is not the goal of this exercise
to end up with a Gomoku playing program;
the goal is for you to learn about adversarial search
through the process of implementing Alpha-Beta pruning on your own.
Do not short-change your own learning experience by grabbing an implementation from the web and then making a few changes.
During development, your implementation should play games against itself (or another version of itself).
Our goal is to have your respective implementations play against each other.
Thus, implementing efficient code, effective pruning, and informative heuristics
will make the difference for whose program wins the tournament.
As in other exercises, you may use the language of your choice
with the provision that it run on my laptop, etc.
- Game-state representation. Decide on your own internal representation of game states.
You can use any data structure you want
provided you implement the appropriate game-state transformation functions
for communicating with the game server.
Although Gomoku is traditionally played on a Go board (19x19),
we will be playing on an arbitrary rectangular grid.
The size of the board will remain constant throughout a single game,
but could vary from game to game.
- Generating moves.
Implement functionality that, when given a current game-state,
and the identity of the player currently moving (given as 'x' for black and 'o' for white),
generates all (or a subset of) legal moves for that player in that position.
- Game-state evaluation.
Because you will not be able to search to leaf nodes in the game tree,
you need to implement a heuristic evaluation function
that estimates the utility of a given board state.
You may want to base your evaluation function on a set of features of the game-state;
you will need to implement the code to extract these features.
- Alpha-Beta pruning.
Implement Alpha-Beta Search.
Your code should maintain a counter for how deep you searched;
this will be reported after each move.
- Manage your time.
It is always good advice to manage your time when working on projects.
However, for this assignment your program must manage its own time.
During tournament play, your program will have 2.0 seconds in which to make a move.
If your program exceeds the 2 second limit before making its move it will forfeit the game.
Your program may take advantage of the nominal 2 seconds
during which the opponent is deliberating and moving;
however, your program's 2 second clock starts as soon as new game-state is sent
so it should pay attention.
- Play a game.
You will probably want to write your code so that you can play your algorithm against itself
(and/or a human player).
For the tournament play,
the protocol involves connecting and playing moves.
Connecting is simply establishing a socket connection
with the port at the given host.
Nothing should be sent by the player at this time.
For each move (starting with the first), the server sends three datums:
Before the 2 seconds are passed,
your program must send a move as a single line with two numbers representing the row and column
of its selected move.
The two numbers must be separated by a single space.
After each move has been sent to the server,
display for the user the maximum depth to which your code was able to search on that move.
Report this as the number of plys, where one ply consists of both players moving once.
- the first line reports the game status
(one of ‘continuing’, ‘win’, ‘lose’, or ‘draw’);
- the second line begins a series of lines for as many rows as there are in the game board;
each line consists of as many characters as the width of the board;
the characters are one of ‘x’, ‘o’, or ‘ ’ (space);
- the third datam is a single character
specifying which player (‘x’ or ‘o’) is to play next;
You should write a one-page report of your activities and findings associated with this assignment.
Your report should serve as a stand-alone document;
thus, it should describe the problem or focus,
the approach that you employed,
and an indication of how well it performed.
The Alpha-Beta Search technique is widely known and reported;
it would be good to have a brief description of the algorithm in your own words,
but you can focus your writing on the creative elements that you implemented.
These probably include the hueristic evaluation function
and algorithm optimizations that allow your implementation to search deeper.
You certainly should describe how you tested your implementation
and report on what you learned from that testing.
You are welcome to include figures if you think they contribute to the report;
however, make sure your picture really is worth a thousand words.
You should format your one-page report
using a template (either LaTeX or Word) found at the
ACM SIG Proceedings Templates page.
Your affiliation should be “Westmont”;
Whether you use LaTeX or Word,
you should use the template with only the following modifications:
- Remove the first four sections
(Abstract, Categories and Subject Descriptors, General Terms, and Keywords).
- Remove the blank text box at the bottom of the left column
that is reserved for a copyright notice.
- Do not include your phone number in the author section.
When you have completed your report and its formatting,
generate a pdf document to be included in your final submission.
Include a README file with your final submission.
It should serve as an index to the files that you are submitting,
and include instructions for running your program.
You should bundle your files (code, README, and report pdf)
in a gzipped tar file.
Name your gzipped tar file with your Westmont emailname and "P3" (no spaces);
for example, someone named Eva Bailey might create a folder called
"evabaileyP3" or "ebaileyP3".
When I open your submission,
your files should be contained within an easily identifiable sub-directory.