In this first exercise you are asked to implement an environment simulator that runs a simplified discrete version of the Unreal Tournament game. Then, you will implement some agents that live in the environment and evaluate their performance.
The game is played on a 2 dimensional finite grid, where each location may contain objects, and agents move among grid locations, much like the version of the wumpus world in chaper 6 of the Russel and Norvig Intro to AI book (first edition). However, the rules of the game and the objects, as well as the goals, are different and are explained below.
Each grid location (square) can be either an obstacle or a free square. Assume that all the perimeter consists of obstacles. Free squares are available for agent motions, but may contain objects. The type of objects in the game are flags and special objects (such as weapons, ammunition, etc.). We will ignore the special objects in this assignment. Each flag has an associated reward value: an agent stepping on a flag earns the reward (essentially "picking up" the flag, which then cannot be picked up again).
An agent can perform the following actions: move forward, turn right, and turn left. The agent score decreases by 1 for each action it performs. The agent state is its grid position, and the direction it is facing (NEWS). A turn is 90 degrees. An action always succeeds, unless the agent attempts to move into a wall or to a location occupied by another agent. We will assume that the game is turn based.
Initially you will implement the environment simulator, and several simple (non-AI) agents. The environment simulator should start up by reading a map of the world from a file, in a format of your choice. We suggest the following simple format: an ASCII file containing the world map, each row on a separate line, with blank representing free space, and characters representing obstructions and flags. See an example map below, with # representing obstructions, and F representing a flag.
################## # F #### ### #### # # ### ## ###### # F # # # F # # # # ##################
The simulator should query the user about the number of agents and what agent program to use for each of them, from a list defined below. Initialization parameters for each agent (position and direction) are also to be queried from the user.
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 map after each step, with the appropriate state of the agents and their score. (In this case, total value of flags collected, minus total number of actions). A simple screen display in ASCII is sufficient (no bonuses for fancy graphics - this is not the point in this course! But you may wish to use the graphics interface provided.) To simplify this task, you may assume that the width of the map is at most 70, and its height is at most 30.
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 (for example, a computed optimal path, or anything else desired) if needed. In this assignment, the agents can observe the entire state of the world.
You should implement the following agents:
At this stage, you should run the environment with two agents participating in each run: one dumb automaton, and one other agent that can be chosen by the user. Your program should display and record the scores. In particular, you should run the greedy search agent with various initial configurations and flag locations, and various initial locations of the opposing dumb automaton agent. Also, test your environment with several agents in the same run, to see that it works correctly.
Later on, after chapter 4, you will be implementing intelligent agents (this is part 2 of the assignment). All the algorithms will use a heuristic evaluation function of your choice. Note that although your agent supposedly competes against an opposing agent, the fact that the opposing agent is a dumb automaton allows your agent to model the opposition simply as part of a static and deterministic environment!
The performance measure will be composed of two parts: S, the agent's score, and T, the number of search expansion steps performed by the search algorithm. The performance of an agent will be:
P = f * S - T
Clearly, a better agent will have P as large as possible. The parameter f is a weight constant. You should compare the performance of the three agents against the completely passive opponent for the following values of f: 1, 100, 10000. Note that the higher the f parameter, the more important it is to expend computational resources in order to get a better score!
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. 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: for 1st part - March 26 (this deadline not enforced). For the complete assignment - April 7 (enforced).