Gomoku on a small 9x9 board

Adaptive Gomoku

In this project, you will, among other things:

For this project, you will write a program that plays Gomoku. However, the point is not to do search (as we might have done in CS116), but rather for the program to learn an evaluation function that will select the best move without search. Chapter 1 of your text describes the design of an adaptive checkers-playing program. You should use that as a guide and implement LMS as your learning method.

In this course I normally allow you to use whatever programming language you would like. However, in this case I want you to use Racket. This works well for students taking CS105 Programming Languages. On Eureka, I am providing a Racket starter package on which you are welcome (but not required) to build.

Your implementation should play games against itself (or another version of itself), improving it's performance based on the games that have been played. Thus, you will have to create training instances from the games played, and then modify your program's model based on these training instances.

Requirements

  1. Game-state representation. Decide on your own internal representation of game states. You will probably lose credit if you stick with the list-based representation found in my starter file. You can use any data structure you want as long as you implement the following GS transformation function. Implement a function that, when given a current game-state, a row and column for a move and the player moving, will create a new game-state corresponding to that move.
  2. Descriptive features. Decide on a set of at least six features that your learning algorithm will use to represent game states. You should implement the needed code to extract those features from a GS.
  3. Play a game. Provide the infrastructure for your program to play a game. It should not use search. Evaluate each possible move from the current state and play the best one.
  4. Learn from game. Based on the moves made in a game, you should create training instances that are then used to update the parameters of your model.
  5. Roadmap. At this stage, you should be able to have your program play against itself, thereby generating training data and learning from it. In the future, you will be given code that retrieves another player's move. You will be integrating that code (and the derived moves) into your program so that your program can play games against other players.

Submission

This is an individual assignment. Appropriate expectations on working together apply. If you search for them, you can find many implementations of Gomoku in many different programming languages. It is not the goal of this exercise to end up with an adaptive Gomoku player; the goal is for you to learn about machine learning through the process of implementing an apdaptive Gomoku player. Do not short-change your own learning experience by grabbing an implementation from the web and then making a few changes.

Submit a README file together with your program file(s) in either .tgz or .zip format. Your README should describe what features you used and what you did to get the program to learn. Describe any significant discoveries or learning experiences you encountered during the process.

In your code, be sure to follow the design recipe!