Wumpus World

Recall from last time we discussed:

The Wumpus world as an environment for agent design.
Using the Wumpus simulation program

This time we will discuss how the simulation program works

An overview of the object hierarchy
The interaction among objects
A closer look at the player class
Requirements for your player

The class hierarchy in the lib directory

Top level classes:

Object.hh(and .cc)
Point.hh(and .cc)

Used to specify locations in terms of x,y coordinates

Environment.hh(and .cc)
Percept.hh(and .cc)

Sets and returns percept values

List classes:

ObjectPtr.SLList.hh(and .cc)
Percept.DLList(and .cc)
Action.DLList(and .cc)

Enumerated Definitions (.hh files only)

ObjectTypes.hh
Orientations.hh
ActorStates.hh
Actions.hh

Object Class hierarchy:

(Object) -IsA- (GridObject) -IsA- (Gold, MovingObject, Pit)

(MovingObject) -IsA- (Actor, Arrow)

(Actor) -IsA- (Wumpus, Agent)

(Agent) -friend- (Player)

All objects share a core set of methods defined in the base class, Object.hh:

class Object
{
public:
Object ( ObjectType objectType=NULL_OBJECT );
virtual ~Object() {};
virtual void reset();
virtual void update() = 0;
virtual void done();
virtual void display() const = 0;
virtual int getScore() const { return score; };
virtual void printScore() const = 0;
virtual void updateStats() = 0;
virtual void printStats() = 0;
virtual void write(ofstream &) const {};
virtual void linkToEnv ( Environment *envPtr );
int isA ( ObjectType objectType ) const;
ObjectType isA() const;
protected:
ObjectType type;
int score;
Environment *env;
SampleStatistic stats;
};

Environment Class hierarchy:

(Environment) -IsA- (GridEnvir.) -IsA- (WumpusEnvir.)

Environments share a core set of methods defined in the base class, Environment.hh:

class Environment
{
public:
Environment();
virtual ~Environment();
virtual void addObject ( Object* );
virtual int stillRunning() = 0;
virtual void reset();
virtual void done();
virtual void trials ( int numTrials, int maxSteps );
virtual void run ( int maxSteps );
virtual void preUpdate() {};
virtual void postUpdate() {};
virtual void updateStats();
virtual void step();
virtual void display() = 0;
virtual void displayScores();
virtual void displayStats();
protected:
ObjectPtrSLList objectList;
int numSteps;
};

List classes (taken from the GNU C++ Class Library):

Objects, Percepts and Actions are stored as linked-lists. These linked-lists are accessed via index variables of the class Pix (also part of the GNU C++ Class Library). Below are some of the methods you can use to access these lists, where the percept list is used in the examples:

perceptList.clear();

Deletes all items from the list.

perceptList.append(x);

Places percept x at the end of the list.

perceptList.empty();

Returns true if list is empty.

perceptList.length();

Returns the length of the List.

perceptList.front();

Returns a reference to the first element in the list. If the list is empty, this will cause a fatal error.

perceptList.rear();

Returns a reference to the last element in the list. If the list is empty, this will cause a fatal error.

Pix p = perceptList.first();

Assigns the index variable "p" to the index of the first element of the list. If the list is empty, p is zero.

Pix p = perceptList.last();

Assigns the index variable "p" to the index of the last element of the list. If the list is empty, p is zero.

perceptList.next( p );

Updates the index variable "p" to the next index of the list. If there is no next item in the list, p is zero.

perceptList.prev( p );

Updates the index variable "p" to the previous index of the list. If there is no previous item in the list, p is zero.

perceptList( p );

Return a reference to the item in the list indexed by the index variable "p".

For more information see: http://sunland.gsfc.nasa.gov/info/g++/LinkList.html or http://www.cs.ucsb.edu/Facilities/Software/ligb++-info/LinkedList.html

The interaction among objects:

main.cc creates a Wumpus environment:

main ( int argc, char **argv )
{
...
WumpusEnvironment *env;

...
env = new WumpusEnvironment ( size );
...
env->trials ( trials, MaxSteps );
...
}

WumpusEnvironment creates an object list in the constructor. The method trails() runs the simulation:

void Environment::trials ( int numTrials, int maxSteps )
{
int i;
for ( i=0; i<numTrials; i++ ) {
cout << endl << endl
cout << "Trial " << i << ":" << endl << endl;
run ( maxSteps );
updateStats();
}
displayStats();
}

void Environment::run ( int maxSteps )
{
numSteps = 0;
reset();
cout << "Initial:" << endl;
display();

for ( numSteps=0;
stillRunning() && numSteps<maxSteps;
numSteps++ ) {
step();
}
done();
cout << "Final:" << endl;
display();
displayScores();
}

void Environment::reset()
{
Pix o;
for ( o=objectList.first(); o; objectList.next(o) )
objectList(o)->reset();
}

void Environment::done()
{
Pix o;
for ( o=objectList.first(); o; objectList.next(o) )
objectList(o)->done();
}

void Environment::step()
{
cout << "Step " << numSteps << ":" << endl;
preUpdate();
Pix o;
for ( o = objectList.first(); o; objectList.next(o) )
objectList(o)->update();
postUpdate();
}

As can be seen the real work is done by the methods written for each object.

A closer look at the Player class:

class Player
{
friend Agent;
public:
Player();
virtual ~Player();
// For use by subclasses
virtual void reset();
virtual const Action process ( const Percept &percept ) = 0;
virtual void done();

virtual ActorState getState() const;
virtual int numGold() const;
virtual int numArrows() const;
virtual int getScore() const;
// Interfacing with Simulation
virtual void linkToAgent ( Agent *agentPtr );
virtual const Action think ( const Percept &percept );
virtual void preProcess ( const Percept &percept );
virtual void postProcess ( const Action action );
protected:
PerceptDLList perceptList;
ActionDLList actionList;
private:
Agent *agent;
static Player *player;
};

The pure virtual method process (const Percept &percept) must be provided by the derived class that you write. This is the method that actually determines the agents actions:

In WumpusEnvironment() an agent is put on the Object list:

addObject ( new Agent ( "The Agent", 0, 0, RIGHT, 1 ) );

As shown above, Environment::step() calls the update function for the agent:

for ( o = objectList.first(); o; objectList.next(o) )
objectList(o)->update();

The agent update function calls think():

void Agent::update()
{
if ( state == ALIVE )
{
Percept percept = look();
Action action = think( percept );
act( action );
}
}

Agent::think() calls Player::think() which finally calls the pure virtual function Player::process():

Action Agent::think ( const Percept &percept )
{
return Player::player->think ( percept );
}

const Action Player::think ( const Percept &percept )
{
preProcess ( percept );
const Action action = process ( percept );
postProcess ( action );
return action;
}

Requirements for your player: The code you write will be a derived class from the class "Player". The Player class performs all the interfacing to the simulation for you, as well as providing you with a history of seen percepts and actions taken.

There are 5 methods your subclass of Player will need to implement:

A Constructor

A Destructor

void reset();

This method is called at the beginning of each trial. You should perform whatever initialization is necessary to get your Player ready for a new game. You must call Player::reset(); within this function.

const Action process (const Percept &percept);

This method is called at each step. The percept argument is the current percept for the Player at this stage in the game. The percept parameter will have already been added to the Percept List.

void done();

This method is called when a game is over, either by the player leaving the cave, dying, or the maximum number of steps has been reached (currently set to 1000).

There are several methods implemented by the Player class that you can use to get information about your state:

ActorState getState();

Returns a value of type ActorState with one of these values: ALIVE, DEAD, or VICTORIOUS (meaning you have left the cave)

int numGold();

Returns the number of Gold pieces you are holding.

int numArrows();

Returns the number of Arrows you still have.

int getScore();

Returns your current score.

Global Player Variable: You should create a global static variable of the type of your derived Player subclass. This is all that is needed to add your player to the simulation.

Example: class MyPlayer : public Player

{ ...
};

static MyPlayer myPlayer;