Gomoku on a small 9x9 board

Exercise 3: Adversarial Search in Gomoku

Updates


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 an arbitrary rectangular grid. The size of the board will remain constant throughout a single game, but could vary from game to game.
  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.
  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.
  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’, or ‘draw’);
    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);
    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, 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 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; 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:

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.

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.