Gomoku on a small 9x9 board

Exercise 3: Adversarial Search in Gomoku

In this exercise, you will, among other things:

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.

Requirements

As in other exercises, you may use the language of your choice with the provision that it run on my laptop, etc.

  1. 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 somewhat smaller square boards. The size of the board will remain constant throughout a single game, but could vary from game to game. Thus, your program must determine the size of the board from the first game-state received from the server.
  2. 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.
  3. 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.
  4. 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. You must also print a message to the standard output whenever your algorithm prunes a branch based on an alpha-beta cut-off; the message should include the depth at which the cut-off occurred. Alpha-Beta Search is the heart of the assignment, so you should budget your time accordingly and carefully explain your implementation in your written report.
  5. 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. Based on my informal experiments, I recommend leaving a margin of 10msec to allow for your player's move to reach the server.
  6. 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:
    1. the first line reports the game status (one of ‘continuing’, ‘win’, ‘lose’, ‘draw’ ‘forfeit-move’, or ‘forfeit-time’, the last two reflecting an illegal move or exceeding the 2 second limit, respectively);
    2. 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); note: since we are playing on square boards, the total number of lines will be the same as the number of characters in the first line.
    3. the third datam is a single character specifying which player (‘x’ or ‘o’) is to play next;
    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, your program must display on standard output the maximum depth to which your code was able to search on that turn. Report this as the move-depth, where one move consists of two ply, i.e., both players moving once. For your submission, do not output other information that you may be reporting for your development/debugging purposes.

The Report

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 so you should focus your explanation of the search on your specific implementation. You should also carefully describe the creative elements that you implemented, such as 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.

I am providing a modified template file that you should use to format your one-page report; this template works with Libreoffice. If you would rather use LaTeX, you may use the style file from the ACM.) Your affiliation should be just “Westmont”; If using a template from the ACM site (instead of the one I provide), you should make the following modifications:

When you have completed your report and its formatting, generate a pdf document to be included in your final submission.

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, as well as appropriate acknowledgments.

You should bundle your files (code, README, and report pdf) in a zip or 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 extract submission, your files should be contained within a sub-directory with your email handle.