Introduction

As announced, assignment #1 consists of 3 parts: a self-exploratory online task, some paper and pencil work, and some programming. The total credit is 100 points for the whole assignment. Points are given in brackets.

Due date: Tue March 22rd, 2011

Important: Solutions to theoretical assignments have to be sent via email before 2 pm of the due date or be handed in in the lecture hall before the lecture starts. Your submission must include a jar file containing all the classes (except the ones in the provided framework) and source code detailing your approach. It is important that your source code is documented! (documentation will be part of the grading). Test that your jar works prior to submission, failure to provide a complete solution will lead to an invalid solution (will not be graded). Also, your submission you should include a README file that describes any problems that you have encountered and any other details that your TA should know.

Submission format: The Jar file must follow the following naming convention:

{lastname}_{firstname}_pai2011.jar (i.e., fischer_lorenz_pai2011.jar), all characters lowercase.

The jar has to be submitted by e-mail to Lorenz Fischer or Cosmin Basca until due date, 2 PM. The SUBJECT of the email has to be PAI2011_A1.

Part 1: Self Exploration

Please go to

UBC-Search Applet

(page protected with the usual username & password)

alternatively go to:

http://www.cs.ubc.ca/labs/lci/CIspace/Version4/search/index.html

and try out all the search algorithms. Ask yourself whether you can find all the differences between the algorithms addressed in class.

Part 2: Paper and Pencil: (30)

Part 2a: Formulate the "Sussman anomaly" with STRIPS language (10)

The following figure shows a blocks-world problem known as the Sussman anomaly. Formulate it in STRIPS language.

Part 2b: Solving a problem with CSP (10)

Consider the sudoku puzzle below. If you don't know sudoku read this.

Formulate the problem in terms of variables, domains, and constraints. You may want to enter the problem into the applet that can be found and downloaded here.

Using the applet is not mandatory because it's quite time-consuming.

Please note: If you choose the applet, you might NOT want to use any string-set domains (but integers), as the number of constraint types is too limited with strings!

What to hand in:

A textual definition of the problem (domains, variables, etc.) Handing in the textual definition of the problem (without solution) is mandatory and worth the 10 points.

Part 2c: Minimax applied to the TicTacToe Game (10)

On the image below, you can see a state of the popular TicTacToe Game.

Your task is now to draw the full minimax search tree starting from this state, and ending in terminal nodes.

Show the utility value for each terminal and non-terminal node.

Utility values are +1 if X wins, 0 for a tie, and -1 if O wins. Assume that X makes the next move.

Part 3: Programming an intelligent Mario agent (70)

Introduction

We use a modified version of the popular "Super Mario" game. The version used is the same version as used by the Mario AI Competition 2009. Please do not use any subsequent versions, as the API changes are substantial and not supported in this course.

Your task is to create an "intelligent" Mario agent, that si capable of navigating the world in a smart manner, avoid enemies, pits, potentially collect points (it increases your score), and possibly reach the end of the level.

: The game board

Above you can see a snapshot of one of the Mario worlds. Your primary task is to implement the ch.idsia.ai.agents.Agent interface (extract from this paper):

public enum AGENT_TYPE {AI, HUMAN, TCP_SERVER}
public void reset();
public boolean[] getAction(Environment observation);
public AGENT_TYPE getType();
public String getName();
public void setName(String name);

The observations about the "world" come from the ch.idsia.mario.environments.Environment interface as follows, always the same dimensionality 22x22 and always centered on the agent:

public byte[][] getCompleteObservation();
public byte[][] getEnemiesObservation();
public byte[][] getLevelSceneObservation();
public float[] getMarioFloatPos();
public float[] getEnemiesFloatPos();
public boolean isMarioOnGround();
public boolean mayMarioJump();

The getEnemiesObservation() and getLevelSceneObservation() are convenience methods used to get a quick idea if there are enemies (0 or 1) in view, similar for the level scene observation. The getMarioFloatPos() and getEnemiesFloatPos() methods offer more accurate information wrt mario and the enemies (their actual x,y coordinates in the game coordinate system). Following is a detailed description of the integer types returned by the complete observation:

public static final int KIND_NONE = 0;
public static final int KIND_MARIO = -31;
public static final int KIND_GOOMBA = 2;
public static final int KIND_GOOMBA_WINGED = 3;
public static final int KIND_RED_KOOPA = 4;
public static final int KIND_RED_KOOPA_WINGED = 5;
public static final int KIND_GREEN_KOOPA = 6;
public static final int KIND_GREEN_KOOPA_WINGED = 7;
public static final int KIND_BULLET_BILL = 8;
public static final int KIND_SPIKY = 9;
public static final int KIND_SPIKY_WINGED = 10;
public static final int KIND_ENEMY_FLOWER = 12;
public static final int KIND_SHELL = 13;
public static final int KIND_MUSHROOM = 14;
public static final int KIND_FIRE_FLOWER = 15;
public static final int KIND_PARTICLE = 21;
public static final int KIND_SPARCLE = 22;
public static final int KIND_COIN_ANIM = 20;
public static final int KIND_FIREBALL = 25;
public static final int KIND_UNDEF = -42;

Zoom levels (depth of observation detail) are explained in more detail in this page.

To get more details about the API and the game please read "The 2009 Mario Ai Competition" and "Super Mario Evolution", and have a thorough look at the included examples:

ch.idsia.ai.agents.ai.BasicAgent
ch.idsia.ai.agents.ai.ForwardAgent
ch.idsia.ai.agents.ai.ForwardJumpingAgent
ch.idsia.ai.agents.ai.RandomAgent
ch.idsia.ai.agents.ai.ScaredAgent

a more advanced A* based agent (winner of the 2009 Mario AI Competition) can be found in this package:

competition.cig.robinbaumgarten.AStarAgent

Note: all agents are provided with the framework.

Download and setup the framework here.

How does Mario move? There are 6 keys defined that Mario can use to express it's intent to advance in the next state (any combination is possible - although some don't make sense: like left and right at the same time) as can be seen in the previous picture.

public static final int KEY_LEFT = 0;
public static final int KEY_RIGHT = 1;
public static final int KEY_DOWN = 2;
public static final int KEY_JUMP = 3;
public static final int KEY_SPEED = 4;
public static final int KEY_UP = 5;

the public boolean[] getAction(Environment observation) takes an observation as input and outputs the next state Mario will be in (based on your intelligent search algorithm), the output is a boolean array where the index is given by the constants enumerated before while the True or False values signify wether the respective key is pressed or not.

Do not hesitate to contact Lorenz Fischer or Cosmin Basca if you have questions or remarks related to the assignment.

How is your Mario agent evaluated? To get full points for this part, one must provide an agent performing the search to goal (end of level) using one of the methods described in the course. You can use the example agents as sources of inspiration (copied solutions are not accepted). It is not required that Mario reaches the end of the level, however if it does so you are awarded a bonus 10 credits.