Since this homework has a shorter-than-average due
date, you may work with one partner to implement
this assignment. However, you must turn in your own individual
report, as
described below. For this reason, two people who
worked together on the assignment may not get identical grades.
In this assignment, you will implement techniques for playing
a game of Connect-n. Connect-n is a generalization
of the popular game Connect-Four. In this game, two players alternate
dropping pieces in one of several columns of a vertical board.
This version of the game also includes "drop-outs", which allows
a player to remove one of their own pieces from the bottom of
a column, shifting the whole column down by one. The
first
player
to
align n pieces
in
a row (horizontally, vertically, or diagonally) wins. In the
case
of both players aligning n pieces in a row, which can
happen
due to drop-outs, the player with the most n-length
sequences
will win. I
have
provided
an
implementation of this game in lisp, as well as an implementation
of minimax
to get you started.
In our case, n will always be 4, and the board will
remain the
same size as specified in the implementation.
This homework will have two parts. In the first part, you will implement alpha-beta pruning; in the second part, you will use genetic algorithms to evolve an evaluation function that can be used by your alpha-beta pruning algorithm to play Connect-n.
After the assignment is due, we will hold a mini-competition between these game players in class, mostly for fun. The performance of your agent in this competition will not count for a grade, but your participation will count toward your participation grade.
One of the likely problems in this competition is name-conflicts between global variables and functions. Therefore, be certain to name all of your global variables and functions with unique names. To make this easy, prefix all of your global variables and functions with your name (or your's and your partner's names). For example, in my code you would see such names as Eaton_alpha-beta, Eaton_variable1, etc. If I worked with a partner named Jane Smith, then our functions could be called something like EatonSmith_function1 or (prefixed with our initials) EEJS_function1. I don't actually care about the prefix, so long as it is unique.
The implementation provides the following functions for interacting with the Connect-n game:
Clarification 9/30/2009: This version of connect-n also includes "drop-outs", which allow a player to remove one of their own pieces from the bottom row of a column. All pieces shift down, when this happens. Note that a player cannot remove one of their opponent's pieces. To cause a drop-out, the player would specify a negative column number to add-move. To avoid potential problems with infinite paths, the game terminates in a draw if no one has won after 84 moves. Drop-outs also cause the potential to have more than one connect-n appear immediately. In this case, the player with the most n-length sequences will win. Filling the board with no clear winner results in a draw.
The implementation is provided as two files: connect-n.lisp and game-playing.lisp. You will need to load both of them to play the game. You can run a demo game using the (play-game) function. There is also an interactive player provided so that you may enter moves manually. Further instructions are provided in these two files.
Clarification 9/30/2009: Initially, when you first run the game player, you will probably want to reduce the depth-limit to something reasonable for minimax, say (setf *depth-limit* 3). Later, with alpha-beta pruning, you'll be able to increase the depth limit to its original specification. After you've completed your agent, I encourage you to play against it manually to see if you can beat it.
Minimax search with alpha-beta pruning is the foundational mechanism for most modern adversarial game players. Although I have provided an initial minimax implementation for playing Connect-n, improve this basic player by implementing alpha-beta pruning. This will enable your game player to search to deeper ply of the game tree, thereby improving its performance. You may build your alpha-beta pruning algorithm on top of the provided minimax implementation, or you may start from scratch. Your textbook contains pseudo-code for alpha-beta pruning that may speed your progress.
Use the given constant *depth-limit* to limit the depth of your search. We will use this in the competition to compare the quality of evaluation functions by having everyone use the same depth limit.
Game playing would be nothing without a good evaluation function. Use genetic algorithms to evolve an evaluation function for the game. Note that this will involve repeated self-play to evolve the evaluation function, so be certain to leave yourself time to conduct these evolutions. It is likely you will need a day or so for the GA to evolve a good evaluation function; any mistakes could cause you to need to run it for another day, so be sure to leave yourself enough time.
Implement a basic GA algorithm, with appropriate operators. Define a representation for your evaluation function (which will include both a genotype (e.g., binary string) representation and a phenotype (e.g., the evaluation function code)). Define a fitness function based on how may games the evaluation function won or lost, and use the GA to evolve a population of evaluation functions with high-fitness. Compete these against each other, continuing to evolve them, until you are satisfied with the performance of one of the evaluation functions. This is the evaluation function you will use in the mini-competition.
Keep in mind that you don't have long to do this assignment, so do not make your implementation too fancy. Keep it simple and get it working quickly. Then, if you have time and the desire, you may make it fancier. A simple, working GA will earn more points than a fancy, non-working GA.
After each generation, have your GA output the minimum, maximum and average (mean) fitness of the population. Plot these values versus the generation number to see the population evolve.
You should turn in your code using the handin63 facility. Please create a single file containing all of your code. Do NOT include the code provided by the instructor with this assignment. Name this file <Lastname><Firstname>HW3.lisp. For example, I would turn in a file named EatonEricHW3.lisp. If you worked with a partner, turn in a single file with both people's names (e.g., EatonSmithHW3.lisp). Only one person needs to submit the code.
In the code you submit, set up your game player to be both player 1 and player 2 so that I can play it against itself. Instructions for how to do this are in the provided code.
Your code is due at exactly 7:00pm on the due date (the same time class starts). After that time, your submission is considered late. I highly suggest that you submit your code file often, both to test that the submission procedure works and to keep a backup copy of your progress.
In addition, you should turn in, in hardcopy, both a printout of your code (formatted as neatly as possible). To save paper, I recommend that you print your code with two logical pages per sheet (e.g., using mpage -2ol).
You should also write a brief summary of your findings, describing your implementation choices in detail. The discussion should focus on the genetic algorithms component of the assignment. Be sure to discuss your choice of representation, fitness function, GA operators, and describe the behavior of the evolutionary search. Include the population fitness figure described in the previous section. Describe the final evaluation function that evolved. This summary should be one or two pages, and should be well-written.