In this first exercise you are asked to implement a simple environment simulator that generates instances of a search problem, runs agent programs, and evaluates their performance according to a simple performance measure. The search problem we will use is the game of Hex - See Hexy web page for rules. Note that this is a 2-player game, but at this point we will assume that you need to find a (weighted) shortest path with no opponent. The environment simulator will generate the problem instances in one of three modes (user-selected): randomly, by prompting the user for a problem instance, or using game-playing mode (see below). The simulator receives a step from the agent, and the number of search expansion steps, and computes a performance score. Performance is measured by the number of steps required to reach a solution, times a constant factor F, minus the number of expansion steps used by the search algorithm.
You will also implement three different search agents:
Use whichever non-trivial heuristic you prefer.
After implementing the programs, run them (using the simulator) on the default initial state, and an additional start state of your choice. Compute the score for each agent at the terminal state minus the sum of all search steps executed by the agent. Do that for F=-1, F=-100, and F=-10000 (note that F is negative because a shorter solution is better). Include the results in your report.
This mode is preparation for the next exercise, in which you will be doing game-tree search. The simulator starts from the initial position (usually an empty board), and presents it to your agent. The agent computes one move, returning it to the simulator. The simulator executes the move, and presents the result to another agent (the user, in this exercise, but write the program so this can be any other agent, e.g. a random agent, or even another copy of the same agent). Receiving the move, the simulator executes it, and runs your agent again, until completion.
The weight of a connecting path will be its length, counting an extra 1/k in length for every NEW tile adjacent to an opposing piece, where k is the number of the step at which the tile was added (k=1 for the first step). Additionally, for the A* search, we will assume that only moves that place a piece adjacent to one of the agent's pieces (or the edges) are legal - in order to reduce the branching factor. Note that as far as finding an optimal path, this restriction can be made without loss of generality. Later on, this restriction will be lifted, to allow for real game play.
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.
As a detail, note that the agent keeps a list of actions (initially empty - for and is re-initialized for every problem instance), and returns only one action for each time it is called. An agent that performs a complete search keeps a list of actions in static variables and returns one action each time it is called.
Now, implement A* search in the agent, with a heuristic of your choice, as well as the "real-time" limited A*. Note that this type of agent does not explicitly reason about the number of search steps executed - it simply tries to find the best sequence of steps, with a "hard-programmed" search strategy, limiting the number of search steps. While it is possible to do that, (it is called "meta-control of search"), you must learn to walk before you can run...
Despite the fact that the board uses hexagonal tiles, one can still use cartesian coordinates. For example, the bottom corner can be A1, with numbers increasing when moving diagonally uprwards and to the right, and letters increasing when moving diagonally upwards and to the left. In this numbering scheme, the neighbors of a tile, say B2, are still A2, C2, B1, and B3 (as on a chessboard), but it also has 2 additional neighbours - A1 and C3.
The above scheme is useful in order to name the moves, as well as paths. In addition, some presentation is necessary, in order to allow a user to look at the board. Since this is NOT a graphics course, a simple ASCII output of the result is sufficient, e.g. (with R denoting a red tile, B a blue tile, and an empty tile):
0
R B
0 0 B
0 B
R
The program and code sent to the grader, 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: March 20, 2003