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 usually allow students to use whatever programming language they prefer. On Eureka, I will be providing a Racket starter package that includes a game server and a sample client that plays random moves. You are welcome to build on that if you want to use Racket. However, if you choose to use another language for your learner, it must connect and coordinate with the Racket-based game server. In any event, the protocol is operationally defined by the Racket server.

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. For this assignment, I want you to implement the LMS learning method that we discussed in class.

Requirements

  1. Game-state representation. Decide on your own internal representation of game-states. You can use any data structure you want as long as you implement the following game-state transformation function. Implement a function that, when given (i) a current game-state, (ii) a row and column for a move, (iii) and the player moving, will create a new game-state corresponding to that move. Document your data-definition(s) thoroughly.
  2. Generate possible next game-states. If you are using a language other than Racket, you will need to implement a function that generates the set of legal moves. This will be necessary to get the set of valid game-states that follow from the one for which you need to play.
  3. 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 game-state.
  4. Play a game. Provide the infrastructure for your program to play a game via the Racket game-server that is provided. Your player should not use search. Evaluate each possible move from the current game-state and choose the best one.
  5. 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. You may find this to be one of the more challenging aspects of the project.
  6. Make your program runnable. After training your player, fix the weights and package your program so that it can be run from the command-line. That is, when executed it should (a) connect to the game-server (b) play a game, and (c) exit. (This last is important.)

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. Be sure to document your code and to include everything I will need to compile and run your program.