Intro to AI

An Introduction to Artificial Intelligence with AI Game Development

CSC 481

Introduction

Advanced graphics hardware and novel rendering algorithms have revolutionized the look and feel of interactive computer games. With the ever-increasing computational power of desk- and laptop computers, not to mention game consoles, we are about to witness another revolution in games: the very smart NPC (non-player character). The increase in computing power of today’s machines allows game designers to implement sophisticated AI techniques for their synthetic creatures that are beginning to blur the difference in the experience between a multi-player game and a single player game populated with smart synthetic creatures.

In this course we will examine AI techniques which are beginning to be routinely deployed in games including the A* path finding algorithm, rule based reasoning, neural networks, and genetic algorithms. We will also be concerned with knowledge representation and problem formalization.

To make the theory accessible (and fun!) we will be using a mod of the Quake II game engine that allows us to replace the brains of the Q2 monsters with AI routines of our own choosing and design. We will design synthetic creatures that will have special roaming abilities, that will be able learn to pick up loot, and make tactical decisions based on learned behavior.

The goal is that you take two things away from this course:

A solid understanding of popular AI techniques that can help solve problems in artificial (and real) worlds.
A better understanding of how some of the complex behavior in today’s interactive games is generated and managed.

Required Texts

	AI Game Development, by Alex J. Champandard, New Riders Games, 2003.
	AI Game Programming Wisdom 3, by Steve Rabin, Charles River Media, 2006 .

Course Info

Announcements:

>> Final project papers are due on Thursday May 8th @ 4pm in my office.

>> Final project software demonstrations need to be scheduled on Thursday May 8th between 1pm and 4pm, you should count on a 30min meeting, at least one team member needs to be present

[4/7/08] Reminder: you can resubmit programming assignment #5 by Friday 4/11 @ 8am
[4/7/08] Reminder: classes start at 12:50 beginnin 4/8
[3/26/08]Presentation Schedule

Date		Group		Chapter#
============================================
Tues  4/8	Fred		1.5
Tues  4/8	Matt		1.6
Thurs 4/10	Charlotte	1.7
Thurs 4/10	Tyler		3.6
Tues  4/15	David		4.2
Tues  4/15	Ian		4.9
Thurs 4/17	Devon		5.2
Thurs 4/17	Will K		6.1
Tues  4/22	Frank		6.3
Tues  4/22	Chris T		7.1
Thurs 4/24	Adam		7.4
Thurs 4/24	Greg		8.2
Tues  4/29	Tom B		8.3
Tues  4/29	Josh		6.2

Presentation Guide Lines: An excellent set of guidelines can be found here. It is worthwhile to take a close look at. You will be graded on

delivery
format of the presentation slides
completeness of presentation - does it motivate and explain, etc

Your presentation should be about 20min in length. Attendance for non-speakers is mandatory, I will take attendance.

[3/26/08] Posted programming assignment #7
[3/25/08] Test cases for Assignment #3:

game([],X).  -> empty
game([1,2,3,4,5,6,7],X). -> complete
game([1,2,4,5,6,7],X). -> 3, ordered
game([7,6,5,4,2,1],X). -> 3, reverse order
game([56,57,58,59,60,61,63],X). -> 62, not starting at one, smallest first
game([61,56,58,64,60,59,57],X). -> 62,63, not starting at one

[3/11/08] More announcements for the tournament: the program you submit for prog. assign. #4 *does not* have to be the same program as for the tournament. Please bring your tournament program with you on portable media...flash drive, CD, etc. NO floppies, I don't have a floppy drive.
[3/10/08] Posted programming assignment #5/6
[3/6/08] A solution to programming assignment #3
[3/6/08] The presentation proposal is due Tuesday March 25th in class
[3/6/08] The final project proposal is due Tuesday April 1st in class
[3/5/08] Clarification on tournament rules: you will need to use the API unmodified, that also means you are *not* allowed to make copies of the predicates in the API and then modify them. The only legal way to communicate with the quagents is via the API. This includes both the highlevel and the lowlevel predicates.
[3/4/08] New dates: Project 4 is due Wednesday 3/12, Tournament on Thursday 3/13 during class.
[3/3/08] Official Tournament Rules:

There will be 8 tofu pieces in the tournament room.
Each contestant will get an equal, fixed amount of CPU time to execute their deathmatch.
The winner will be the contestant who finds and destroys the most tofu in the shortest amount of time.
You will need to use the Prolog API version 3. You are **not** allowed to modify the API.
You are allowed to modify the quagent.config file, with the exception of the tofu locations which will be added at tournament time if you chose to modify the quagent.config file. In particular, the choice of quagent is yours as well as specific quagent parameters such as wisdom and health.
The instrumented Prolog API throws additional exceptions. In order for your program to behave well you should add the following code to your program:
```
start :-
	q_connect(Q),
 	% turn the camera on, so we can see what's going on during the tournament
	q_cameraon(Q),
	catch(loop(Q),Exception,true),
	writeln(Exception),
	q_cameraoff(Q),
	q_close(Q).
```
Here, the predicate start is the predicate we would use to start your program and the predicate loop is the main loop of your program.

[3/3/08] Here is a practice tournament room. Unzip the file into the C:\ folder keeping the directory structure intact. You should then see the Tournament Room 1 short cut. You will also need to add the following statements to your quagent.config file:

# tofu for tournament1
tofu -128 -448 64
tofu -256 0 64
tofu 0 0 64
tofu 384 448 64
tofu 384 -448 64
tofu 64 -448 64
tofu 256 0 64
tofu -448 448 64

or any other tofu locations. Tofu locations are not fixed and will change for the actual tournament as will the room. Good Luck!
[2/28/08] Here is the challenge room we used for grading programming assignment #2. Unzip the file into the C:\ folder keeping the directory structure intact. You should then see the Challenge Room 1 short cut.
[2/27/08] posted programming assignment #4
[2/25/08] Posted programming assignment #3
[2/19/08] Fixed the link of the new API. You should now be able to download version 3.
[2/15/08] *Important*: I found a bug in the parse functions that use the 'split' function in my lecture notes. I had assumed that the split function munches all white space between tokens, but it doesn't, it only applies the regular expression once per symbol. Therefore, we need to tell the split function to apply the regular expression as many times as appropriate to munch all the whitespace between tokens. The following are corrected versions of some of the parse functions, notice the '+' sign:

public double parseWalkEvent(String eventString) {
    // TELL STOPPED 
    String[] tokens = eventString.split("\\s+");
	
    return Double.parseDouble(tokens[2]);
}

and

public Double rayDistance(String eventString)
{
	// NOTE: only works for single ray commands
	// this is what the event looks like:
	// OK  (ask rays 1) 
	//     1 worldspawn 379.969 54.342 0  
	
	// NOTE: parens are not included in tokens
	String[] tokens = eventString.split("[()\\s]+");

	double x = Double.parseDouble(words[6]);
	double y = Double.parseDouble(words[7]);

	double distance = Math.sqrt(x*x + y*y);
	
	return distance;
}

The general rule is, if you are breaking up a string based on whitespace '\\s', then you should always use the '+' sign which says "apply the whitespace pattern more than once if possible".
[2/14/08] Posted a new version of the Quagent API. See Software section for details.
[2/14/08] Programming Assignment #2 extended until Sunday 6p with a 10% penalty.
[2/13/08] Moved the rooms to the software page: Try out your navigation procedure in some original QuakeII rooms. Unpack this zip file into the root directory of your C drive and you should see three additional rooms.
[2/12/08] Quiz, 2/19/08, up to and *not* including rule based systems, Reading chaps 1-10, excluding 4.
[2/4/08] Here is a challenge room for programming assignment #2. Unzip the file into the C:\ folder keeping the directory structure intact. You should then see the Challenge Room short cut.
[2/6/08] Internships in educational game development available, please read.
[1/30/08] Posted programming assignment #2.
[1/30/08] ** NO CLASS Tuesday 2/5 **
[1/26/08] The readings assigned so far are all from Alex's book.
[1/1/08] Welcome!

Homework/Programming Assignments:

Programming Assignment #1, due Friday, February 1st @8am
Programming Assignment #2, due Wednesday, February 13th @8am
Programming Assignment #3, due Friday, February 29th @8am
Programming Assignment #4, due Monday, March 10th @8am
Programming Assignment #5/6, due Friday, March 28th @8am The learner framework and the ID3 tree builder are available from the software page
Programming Assignment #7, due Friday, April 4th @8am. The learner framework, the neural network adapter and the Tiberius network builder are available from the software page.

What, When & Where

CSC481, Spring 2008
When: T Th 12:30-1:45pm
Where: Wales 226

Instructor:

Dr. Lutz Hamel
Tyler Hall, Room 251
Office Hours: Tuesday 2-3pm, Thursday 11am-12pm
email: lutz at inductive-reasoning dot com

TA:

Remo Stierli
Office Hours: Tyler Hall 134, Friday 09:00 - 12:00,
Phone: 874-5833 email: rstierli@cs.uri.edu