In this first exercise you are asked to implement a simple environment simulator that runs agent programs, and evaluates their performance according to a simple performance measure. In addition, you will write several (not very intelligent, at this stage) agents for the environment.
The environment simulator will run the game of backgammon, which is a well-known two-player game with a random element. The version of the game to be implemented is the standard game (see rules), but without doubling (i.e., without the doubling cube, but with double dice - double 6 still means you play 4 times 6). The simulator should allow the user to choose both agent types, from a list of simple agnets listed below, which are also to be implemented in this assignment (more intelligent agents will be added later on). Then, the game is run multiple times, with the score updated and reported after each game. Note that it should be possible to turn on or off the display of the state after each move - later on we will wish to run many thousands of games between learning agents!
Performance is measured for each agent by measuring the average number of points gained per game. Provisions must be made to later on take into account computational resources used by the agent.
Example game display (initial position): | v v v v v v | v v v v v v | | w b | b w | | w b | b w | | w b | b | | w | b | | w | b | | | | | | | | b | w | | b | w | | b w | w | | b w | w b | | b w | w b | ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ White to move, dice: 6 5
You will also implement four different search agents:
After implementing the programs, run them (using the simulator) for multiple games, and report the scores.
As at the beginning of the semester we will not have covered search as yet, start by programming the environment simulator, and the first "non-search" search agent. You will need to program at this stage the functions that compute and check legality of states and moves, for use in the simulator and agent. Also, your simulator at this stage should be able to compute agent score.
Before you start writing code, it is important to decide on a representation for moves that facillitates enumerating and storing all legal moves starting at a certain board state and die roll, as well as a representation for a board state!
The program and code sent to the grader, with documentation on the above design choices (representation, heuristic) to Mr. Ami Berler by e-mail or otherwise as specified by the grader, a printout of the code and results. Set up a time for frontal grading checking of the delivered assignment, in which both members of each team must demonstrate at least some familiarity with their program...
Deadline: November 20, 2002