A boolean decision tree is a binary tree structure used to model decision processes and their possible consequences. In this project we will implement an architecture for creating boolean decision trees to control the behavior of characters in a simple, gridbased Wumpus World. This projects objectives are:
Wumpus World is a game world where a player navigates connected rooms hunting a mythical monster called a Wumpus. Wumpus World was first created by Gregory Yob in the 1972 text adventure Hunt the Wumpus.
Unlike the original Wumpus World, our world is represented by an NxN grid, it contains only some number of Wumpuses and Wumpus hunters, and the Wumpuses can move. In this assigment we will create a decision tree to guide a Wumpus to sense its environment, make decisions, and execute actions in order to catch players.
If the Wumpus cannot see the player, it will randomly search the game world. If it can see the player, it will check if they are at the same grid location. If they are at the same location, the Wumpus will grab the player. If not, the Wumpus will move towards the players position. Here is the Wumpus decision tree: See image.
Boolean decision trees have two types of nodes: decision nodes and action nodes. Both decision nodes and action nodes implement a more general decision tree node interface. Here is the DecisionTreeNode Java code:
public interface DecisionTreeNode {
public DecisionTreeNode makeDecision();
}
Decision nodes are internal boolean decision tree nodes with exactly two children that implements DecisionTreeNode. Decision nodes contain a method for evaluating the current world state, called isTrue(), that returns true or false based on some information about the world. The methods, setTrue() and setFalse(), take as input other DecisionTreeNodes and set them as the two children of the current decision node. The method getBranch() returns the nodes true child if isTrue() returns true and the nodes false child otherwise. Finally, makeDecision() recursively calls getBranch()s makeDecision() method until a leaf node is returned. Here is the decision nodes API:
public abstract class DecisionNode implements DecisionTreeNode {
boolean isTrue()
void setTrue (DecisionTreeNode trueNode)
void setFalse (DecisionTreeNode falseNode)
DecisionTreeNode getBranch()
DecisionTreeNode makeDecision()
}
Action nodes are leaf decision tree nodes that expose two methods. Since they are a leaf node and represent an action to take, their makeDecision() method returns themselves. Their other method, getAction(), returns a String that describes the action. Here is the action nodes API:
public abstract class ActionNode implements DecisionTreeNode {
String getAction()
DecisionTreeNode makeDecision()
}
Before we can build a Wumpus decision tree, we need some representation of the Wumpus World to reason about. We will use two object types to represent the Wumpus World and some number of world characters: WorldState and Character.
WorldState contains a collection of characaters. It exposes two methods. Its first method, getCharacter(), takes a String as input and searches the collection for a character with a matching name. The second method, addCharacter(), takes a character as input and adds it to the collection. Here is WorldStates API:
public class WorldState {
WorldState()
Character getCharacter(String name)
void addCharacter(Character character)
}
Character contains information about a character that exists in the Wumpus World. Each character maintains a non-negative (x, y) coordinate position and a name. It exposes methods that allow these values to be accessed and modified. Here is Characters API:
public class Character {
Character(String name, int x, int y)
int getX()
void setX(int x)
int getY()
void setY(int y)
String getName()
void setName(String name)
}
To implement the Wumpus decision tree we need implementations of each of the types of nodes pictured in the diagram in Section 2: IsVisible, IsColocated, Search, MoveToward, and Grab.
IsVisible takes two characters as input in its constructor. It implements isTrue() to return true if the two characters are on the same row or column. Here is IsVisibles API:
final class IsVisible extends DecisionNode {
public IsVisible (Character me, Character target)
protected boolean isTrue()
}
IsColocated takes two characters as input in its constructor. It implements isTrue() to return true if the two characters are on the same row and column. Here is the IsColocated API:
final class IsColocated extends DecisionNode {
public IsColocated (Character me, Character target)
protected boolean isTrue()
}
Search, MoveToward, and Grab take as input characters in the constructor and return a String describing the action when getAction() is called. Here are the APIs:
final class Search extends ActionNode {
public Search (Character me)
protected String getAction()
}
final class MoveToward extends ActionNode {
public MoveToward (Character me, Character target)
protected String getAction()
}
final class Grab extends ActionNode {
public Grab (Character me, Character target)
protected String getAction()
}
Once we have implementations of the node types, we need to build and use the Wumpus decision tree. We build the Wumpus tree with a class called WumpusDecisionTree. WumpusDecisionTree takes a WorldState as input to its constructor and builds the decision tree based on the WorldState. It also exposes a method called getAction() that traverses the decision tree and returns the String description of the ActionNode at the leaf it finds. Here is WumpusDecisionTrees API:
public class WumpusDT {
public WumpusDT (WorldState state)
public String getAction()
}
Finally, a Game class should be created to instantiate the objects and run the Wumpus decision tree. Here is the Game main method:
public class Game {
public static void main(String[] args) {
WorldState state = new WorldState();
state.addCharacter(new Character(“Wumpus”, 0, 0));
state.addCharacter(new Character(“Player”, 10, 0));
WumpusDT wumpusTree = new WumpusDT (state);
System.out.println(wumpusTree.getAction());
}
}
It should print Wumpus moves toward Player.