CSW 4701
Artificial Intelligence
Project #3
Game Playing Tournament- ISOLATION

Isolation

For this part of the project, you will need to implement a two-player, time-based version of alpha-beta and an appropriate board evaluation function.

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.

Player x starts at position (1,1) while o starts at (8,8).

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. 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:

- is an empty square

* is a filled in square

x is the current position of the x player

o is the current position of the o player

The board will always be 8 by 8.

Your player will be required to run with a set total amount of time. A useful function to consider for this assignment is (get-internal-real-time). 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 column). If you cannot move, return (nil nil). The TA referees will check for this. If you return an illegal move, the other player (and the TA) will detect it and you will lose. Additionally if your time expires you will lose.

What to turn in (60% of your grade is proper functioning code, 20% of your grade is the writeup, 20 points available in the tournament!)

A single code file named player-your-account containing:

your name at the top

a time-based version of alpha-beta

a good evaluation function for your player.

any supporting code

A single writeup file containing:

your name at the top

a paragraph justifying the evaluation function you designed. You may wish to talk about:

1. why it provides an appropriate approximation to the "goodness" of a particular board
2. how it balances quickness of execution (i.e. enables deeper search) vs. accuracy
3. how you determined it was a good evaluation function
4. efficiency of implementation.

a paragraph describing any extensions you implemented

Collaboration Policy

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 explicitly 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.

The Tournament

If you wish, your Isolation game playing agent will be entered into a competition with the other players submitted by the class. Winners of the competition will receive extra credit for the assignment.

1^st round loosers – 5 points, winners 10

2nd round loosers – 2 more points, winners 3

3rd round loosers - 1 more point, winners 2

4^th round loosers – 1 more point, winners 2

Final grand winner gets a final 3 points

(If there are fewer than 4 rounds, points will be adjusted so the grand winner can get 100 points. If there are more rounds, well, enjoy the valuable extra points!)