COSC 4117
Course Project
An intelligent Amazons player
The goal of this project is to write an intelligent player agent for the
game of Amazons. You will have to produce a program that implements
the rules of Amazons and allows any of three agent objects to play a game.
The three game playing agents are
(i) an interface agent that allows a human at the keyboard to make
the moves,
(ii) a communication agent that communicates with a remote player to
receive moves, and
(iii) an intelligent agent that generates its own moves.
The communication agent allows a game of Amazons to be played across
the network. Two humans could play this way but, for our purposes,
the important play will be between two intelligent agents.
You can do this project individually or as a team. Teams may consist
of two or three members. Near the end of the course, we'll hold a
tournament among the intelligent agents to see which team's agent rules
the board.
The game: Amazons
Amazons is played on a 10 by 10 board of 100 squares. Each player
has four pieces, called queens, that are placed on the board in the configuration
in Figure 1 to start a game.
The players are called queens because they have the same mobility on
the board as a chess queen. That is, a piece can move in a straight line
in any direction (vertical, horizontal or either diagonal) any distance
along an unobstructed path. If the path is obstructed by another
piece (belonging to either the same or the opposing player), the queen
cannot move onto or beyond that square. A piece cannot occupy a square
already occupied.
The path is also obstructed by the edge of the board of course.
It can also be obstructed by a missing square. At the beginning of
the game, the board consists of 100 squares, but at each turn a square
is removed.
A player's turn consists of a move and a shot. First the player
moves one of his or her queens, according to the description above, to
a new position. From the new position, the queen 'shoots an arrow.'
Shooting an arrow means specifying another square, reachable from the new
position by the same rules of movement. This square is removed from
the board. In Figure 1, the queen at D0 moves to D4 and shoots at
J4 resulting in the board of Figure 2.
Figure
1
Figure
2
J4 can no longer be occupied, moved through, shot through or shot at.
The player who takes the last turn is the winner of the game.
Although Amazons is a fairly new game, it has been subject to considerable
analysis. There are several web sites that contain information
that might help you in analyzing the game. However, I expect you
to write every line of code yourself.
The program of the game
Your program should be organized with an environment class called Amazons
and three player agent classes called AgentHCI to handle keyboard
entry of moves, AgentComm to handle communication with another program
and AgentIntelligent to be the artificially intelligent player.
It's probably best to make the three classes extend an abstract Agent
class.
-
The game should be able to run with any of the nine combinations of pairs
of players.
-
The game environment class must verify moves: if a player proposes an illegal
move, the game is terminated and the opponent is declared the winner.
-
The game environment must also recognize a final state and output the results,
declaring a winner.
-
The game should be able to execute in 'stepper' mode if specified; that
is, wait for keyboard input to call for the next move from a player.
-
The game should also be able to disqualify a player that takes too long
to make a move. Have a parameter that can hold a time limit
in seconds.
The game board will be labelled as in the figures (A-J by 0-9). A
board position is specified by a letter then a number, e.g. D0. A
turn is specified as a six character String indicating the starting position,
move position and arrow position. For example, 'D0D4J4' specifies
that the queen at D0 moves to D4 and shoots an arrow at J4.
The project
The project will proceed in stages as indicated below in the marking scheme.
At each stage I will make suggestions to keep your work on track.
Note that the game environment class must show a display of the current
state of the game but there are NO marks for fancy graphics. Arrays
of text characters scrolling by in a console window are just as good as
a fancy frame based animated board.
The tournament, schedule and results
In the tournament, each team will play every other team twice, playing
first (RED) once and playing second (BLUE) once. A win is worth 1
point; a loss gets 0. If a team defaults a game, it receives a score of
0 and the opponent gets 1. A team defaults if (i) it is not at the agreed
location at the agreed time ready with a working program, (ii) the team's
program crashes during the game, (iii) the team's program makes an illegal
move, (iv) the program exceeds the time allowed to complete its moves (to
be arranged), or (v) the tournament judge (me) declares a default for some
other reason.
The marking scheme
| Tuesday, Sept. 25 (5% of project mark) |
Submit on one sheet of paper:
-
Name of team member(s)
-
Description of the data structure you propose to track the state of the
game - essentially, the instance variables of the Amazons game class.
|
| Tuesday, Oct. 16 (10% of project mark) |
At this point the program should be working with 'interface'
and 'communication' players complete and a stub of an AI player. For this
stage, collaboration is the way to go. Work with other class members
to get Environments working, and working cooperatively. In the course
directory, there are some sample classes for communication by UDP or TCPIP
in Java. We'll reach a consensus early on about which way to do the
communication. Submit
-
a printed listing of the code of your program
-
a list of trial games you have played with other class members to assure
your program communicates properly and correctly maintains the state of
the game, including determining when a game is complete and which player
has won.
|
| Tuesday, Oct. 30 (10% of project mark) |
At this point, your AI player should have, at least, a
basic search algorithm implemented. Submit
-
a listing of your AI player class
|
| November 19-23 (25% of project mark) |
Your program should be ready to compete in the course Amazons
tournament. During the week of November 19-23, games will be scheduled
and played to determine the agents who make the playoffs. The tournament
format will be decided well in advance, once I have an idea of how many
teams will be competing, how long games take to play and so on. Tournament
format. Marks out of 25 will be based on tournament standings.
A team that completes all matches gets a minimum
of 16.
Early in the week of November 26, a tournament among playoff agents
will determine the grand champion; the champion gets
25. |
| Tuesday, Dec. 4 (50% of project mark) |
Submit your final report consisting of the following.
-
printout of source code for your complete program - environment plus players
-
source and compiled code on a floppy disk. If the program's too big,
talk to me and we'll arrange for emailing it.
-
description (approximately 1000-2000 words plus diagrams if required) of
your AI player's intelligence. I will be evaluating your player based
on how you have incorporated a variety of techniques including any or all
of: (i) appropriate data structures, (ii) classical AI techniques such
as search, (iii) creative heuristic techniques, (iv) 'tuning' based on
testing of the intelligent agent against AI and human opposition.
I will also be looking for a critique of your agent: what did it do well;
what did it do badly? The best way to organize the description would
be to start with data structures and classic techniques then describe your
own creative ideas, then the refinements you did during testing and competition
and finish off with the critique of the strengths and weaknesses.
|