In the second exercise you will be using the environment simulator from the first assignment, the Canadian traveller problem variant, as a platform for implementing intelligent adversarial agents. The environment is the same as before, except that now the opposing agent is an intelligent agent, rather than the dumb automaton such as the ice removing agent.
As before, the environment consists of a weighted graph. Each edge can be either blocked by a given amount of ice, or clear. Some vertices are known to contain a supply of salt. The environment can contain one or more agents, each with a known starting location, and a required goal location. For each agent, there are state variables designating it current location, and the amount of salt it is carrying, initially zero.
An agent can apply 2 types of action: move (as in the standard CTP), and load salt. The latter is a parametrized action, one must specify S, how much salt to load. The result of this action is that the amount of salt that the agent is carrying is increased by S, or by the amount of salt in the current vertex, whichever is less, up to a maximum capacity of salt that an agent can carry (an optional parameter). The results of a move (from a current vertex V to a specific adjacent vertex U) action is as follows. If the edge E to be traversed is clear, the agent reaches U. If E is blocked, and the agent carries a sufficient amount of salt S (at least equal to the amount of ice on E), the required amount of salt is deposited on the ice as the agent traverses E, and again the agent reaches U. Side effects of this action are that E is now clear, and the amount of salt the agent carries is reduced by S. However, if E is blocked but the agent does not have sufficient salt, the action fails, and the agent remains at V.
Note that in this assignment the agents can be completely adversarial, or semi-cooperating, as discussed below.
The simulator should query the user about the parameters, the type of game (see below) as well as other initialization parameters for each agent (type of agent, position, and goal).
After the above initialization, the simulator should run each agent in turn, performing the actions retured by the agents, and update the world accordingly. Additionally, the simulator should be capable of displaying the world status after each step, with the appropriate state of the agents and their score. Here there are two types of agent programs: human (i.e. read input from keyboard) and game tree search agent.
Each agent program (a function) works as follows. The agent is called by the simulator, together with a set of observations. The agent returns a move to be carried out in the current world state. The agent is allowed to keep an internal state if needed. In this assignment, the agents can observe the entire state of the world. You should support the following types of games:
Since the game tree will usually be too big to reach terminal position in the search, you should also implement a cutoff, and a heuristic static evaluation function for each game. You may use the same heuristic for all games, if you think this is justified.
The program and code sent to the grader, by e-mail or otherwise as specified by the grader, a printout of the code and results. You need to show example scenarios where the optimal behavior differs for the 2 kinds of games (you will need to make the example scenarios very small in order to be able to reach terminal states in the search). A description of your heuristic evaluation functions and their rationale. 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.
Due date: December 11, 2009.