Due: Feb 10, 2004 23:59:59 EST
Please submit your code and explanations via WebWork (click
here for directions). For questions about the assignment contact
Steve Marlowe.
The assignment is worth 7% of your final grade; however, there is an opportunity to earn additional points in a class competition.
The purpose of this project is to explore some of the game-playing algorithms that we have discussed in class, and that are detailed in Chapter 6 of your textbook. Essentially, you will be asked to write a time-based version of minimax and to exercise your creativity in coming up with and justifying an evaluation function for an interesting game called "mixed-up" isolation. Once all of the code is submitted it will be graded, and a class competition will be held to determine who's player is the best. The competition will be held on Feb 17 in order to give you another few days to tweak your player.
Naturally, all of this will be done in LISP. Those of you who didn't do project 1 will probably wish you had.
Read everything below carefully!
We will make these three files available to you:
Compiling code
You may (and should) compile your functions for the competition. This will make your code run faster, which may be important since players will have a limited amount of time to search the game tree. Implementing alpha-beta pruning will also help to speed up your code. To compile a function simply execute:
(compile 'function-name)
All of your functions should be compiled when your file is loaded. To do this, add the (compile 'function-name) lines at the end of your lisp file for each function you will be using. These will then be executed when the file is loaded into the interpreter.
Vitally Important Details of Naming Conventions
Name your player functions:
iso-player-yourgtaccount
For example, if Steve Marlowe were taking this class and had this assignment, his player would be named: iso-player-gtg654j. The signature of your isolation player function is described below.
Put those functions as well as any other functions you need (that you do not find in utils.lisp or isolation.lisp) in a file called:
player-yourgtaccount.lisp
Append -yourgtaccount to any code that you write. This will prevent conflicts while loading multiple students' players. Bascially, any function or macro or global variable defined in your player-xxx.lisp file should end in -xxx.
During testing, utils.lisp and isolation.lisp will be loaded before your file is loaded, so there is no reason to include any code from these files in your player-xxx.lisp file or to write code which automatically loads these files.
To test your code against other players:
(load "utils.lisp") (load "isolation.lisp") (load "player-xxx.lisp") (isogame 5000 #'iso-player-xxx #'iso-random-player iso-board)
This will test your player against a random player in a single game with a time limit of 5 seconds per player. You can also test several players against each other in a tournament. To test, say, six players against each other using a default time setting (as specified in the compete-isolation function) simply execute:
(compete-isolation (list #'p1 #'p2 #'p3 #'p4 #'p5 #'p6))
For this part of the project, you will need to implement a two-player, time-based version of minimax and an appropriate board evaluation function. For better performance (and likely better play), we suggest you also implement time-based alpha-beta pruning.
The Game
The game has two players: x and o. The players alternate turns,
with player x moving first at the beginning of each game. If after
10 rounds the game has not been won, it pauses to enter phase 2.
During the intermission, the players switch
positions and markers--x becomes o and o becomes x. The players
then resume play with the new x (old o) making the first
move in phase 2.
Specifically this means if at round 10 your player is called by:
(player-xxx 'x ... 10 nil)It will be called in round 11 by:
(player-xxx 'o ... 11 t)See the isogame function contained in isolation.lisp for implementation details.
Each turn, a player can move like a queen in chess (in any of the eight directions) as long as her path does not cross a square already filled in or occupied by the other player. After moving, the space vacated by the player is designated as filled and cannot be moved to again. Notice that only the space that was occupied is filled, not the entire path.
The game ends when one player can no longer move, leaving the other player as the winner.
The coordinate (1 1) indicates the top left hand side of the board.
The board is specified as a list of rows. Each row is a list of entries:
The board will always be 8x8 and will be specified with a border around its outer limits. Note that while the board is specified as a rectangle, any geometry can be defined simply by filling in the appropriate squares with *'s.
You have been provided with:
Your player will be required to run with a set total amount of time. The player should be called by:
(iso-player-yourgtaccount marker xpos opos time-left current-board current-round switched)
where time-left is remaining time allocated to the player for the remainder of the game in milliseconds, marker is which player you are (X or O), xpos and opos are the positions of the players, current-board is the current state of the board and round is a number specifying what the current round is. The switched parameter is a boolean indicating if the players have switched sides yet. A useful function to consider for this assignment is (get-internal-real-time). Check out utils.lisp for how it is used. It is also useful to think of dividing the time you have left equally among the subtrees you want to search, stopping along any path when you're coming close to running out of the allocated time.
Your player function should take in the parameters as described above and return a move as a list in the format (row colum). If you cannot move, return (nil nil). The game control code will check for this. If you return an illegal move, the competition code will detect it and you will lose. Additionally if your time expires you will lose.
What to turn in (50% of your grade is code, 50% of your grade is the writeup!)
Before turning in your assignment, you are allowed to try your player out against the players written by your fellow students; however, you are quite explictly not allowed to look at any code (except what we provide) or descriptions of code for these games (or any games that are similar).
You are, of course, allowed to play the games yourself or to play against humans. Again, do not let your discussions turn into any descriptions of an algorithm.