An Introduction to Artificial Intelligence with AI Game Development

CSC 481

Contents

    Introduction
    Required Texts
    Course Info
    Links

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:
  1. A solid understanding of popular AI techniques that can help solve problems in artificial (and real) worlds.
  2. 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 4, by Steve Rabin, Charles River Media, 2008 .

Course Info

Announcements:

Final project research papers are due on Thursday 5/13 @ 2pm in my office

Teams completing programming projects need to sign up for a 30min demo slot

The following demo slots are available (please sign up by emailing me):
  • Thursday 5/13:
    • 1:00-1:30 -- Jonathan G.
    • 1:30-2:00 -- Xiaochen/Hui
    • 2:00-2:30 -- James M.
    • 2:30-3:00 -- Will D.
    • 3:00-3:30 -- Justin Q.
    • 3:30-4:00
  • Friday 5/14:
    • 1:00-1:30 -- Richard W.
    • 1:30-2:00 -- Jason S.
    • 2:00-2:30 -- Joel B./Ronald D.
    • 2:30-3:00 -- Jason C./Brad B.
    • 3:00-3:30 -- Chris B.
[4/27/10] Please bring a #2 pencil with you on Thursday
[4/2/10] Assignment #7 is NOT due this coming monday 4/5, the new deadline will be announced in class
[3/30/10] Posted programming assignment #7
[3/29/10] More on the presentations:
  • Attendance for non-speakers is mandatory. Each non-speaker has to bring one typewritten question per presentation to class. I will collect these questions. The questions need to be non-trivial, that is, questions like: "what is the title of your paper?" will not count. All the questions submitted together will make up one homework grade.
  • Please take a look at the guidelines. 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.
  • [3/29/10] Readings for Artificial Neural Networks
    • Alex: Chapters 17 and 19
    • AIMA: Chapter 20.5
    • AIG: Chapter 7.7
    [3/17/10] *** NOTE *** the schedule below has changed!!!
    [3/16/10] You can find information with respect to the final project proposal here. *** final project proposals are due on Thursday April 1st in class.***
    [3/16/10] Presentation Schedule:
    Team            Chapter     Date
    --------------------------------------
    Nidal/Chris     2.1         April 8
    Mike/Richard    2.10        April 8
    Xuchen/Hui      2.12        April 13
    Ian/Brad        3.8         April 13
    Ronald/Joel     3.9         April 15
    Jason/Jason     4.1         April 15
    Jonathan/James  4.5         April 20
    Harry/Tyler     4.7         April 20
    Belvie/Richard  5.1         April 22
    Jonathan/Wyatt  5.7         April 22
    JustinQ/Sean    6.3         April 27
    JustinM/Will    7.6         April 27
    Charles/Kyle    7.4         April 29
    Ronald B.       3.6         April 29
    
    Please see the presentation guidelines below.
    [3/11/10] Presentation announcements:
    • Each team of two people needs to pick **3** papers from the "Wisdom" book
    • 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/11/10] More announcements for the tournament: The tournament will be held during class on Thrusday 3/18. 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/11/10] 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 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/11/10] Posted assignments 5 and 6
    [3/9/10] Readings for "Machine Learning: Decision Trees":
    • Alex: chap 26
    • AIMA: chap 18
    • AIG: chap 7.1, 7.4, 7.5
    [3/9/10] Deadline for assignment #4 extended to Thursday 3/11 @ 10pm.
    [3/5/10] Readings for "Searching & Planning":
    • A nice highlevel summary of the topic available on Wikipedia
    • The A* tutorial I used for the class notes
    • AIMA: chaps 3, 4
    • AIG: chaps 4, 8.1, 8.2
    [3/5/10] Given the questions I have been asked there seems to be still some confusion on how we will grade assignment #4. It will be graded as follows:
    • your program will be tested in the "empty room" with the tofu positions given in class.
    • your program will be tested with unknown tofu positions in the "empty room".
    • if your program passes the two previous tests (that is, if it finds all the tofu in both situations) you will get full credit. You don't have to worry about figuring out when you found all the tofu, just keep on searching as long as you can.
    • finally we will test your program in the "obstacle room" with unknown tofu postions. If your program finds all the tofu then you will get 15 points extra credit.
    [3/3/10] Here is an example room for the tournament. In order to test your quagent you should use the following tofu position assignments in your quagent.config file:
    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
    
    [3/2/10] It was pointed out to me that in the assignment I am asking you to develop a program that works in a room with obstactles. Since in class today I asked you to develop a program that only works in the empty room, I will stick to that, but extra credit is available for the teams who get their program to run in the "obstacle room" which is available in your installation.
    [3/1/10] Here is prolog code that uses a finite state machine in its controller.
    [3/1/10] Please bring your laptops to class on Tuesday. The second half of the class will be allotted for teamwork on assignment #4.
    [2/26/10] Here is a list of suggested readings on the topics we are currently discussing:
    • Rule/Logic based systems:
      • Alex: chapters 11 & 12
      • AIMA: chapters 7, 8, & 9
      • AIG: section 5.7
    • Finite state machines:
      • Alex: chapters 38, 40, & 41
      • AIMA: unfortunately does not discuss FSMs but section 2.4 discusses state in agents
      • AIG: section 5.3
      • A nice online FSM tutorial
    [2/24/10] posted assignment #4
    [2/23/10] Some suggestions with respect to Prolog programming:
    • Do not use the or-operator ';'
    • Do not use the implication operator '->'
    Both of these operators will make it extremely difficult to debug your program. Both operators can easily implemented making use of Prolog's backtracking and search semantics.
    [2/23/10] Posted a nice tutorial on finite state machine, see below in the link section.
    [2/23/10] Assignment #3 is due Thursday 2/25 @10pm...is mispoke in class today.
    [2/22/10] Posted assignment #3
    [2/15/10] Quiz is on Thursday 2/18.
    [2/13/10] Alternative readings (see book descriptions below): AIMA chaps 2,5,10,12; AIG chaps 1, 2.4, 3.1, 3.3, 5.1, 5.6, 5.9
    [2/8/10] updated the office hours of the TA.
    [2/8/10] Posted assignment #2.
    [2/4/10] Here is a challenge room that you will be using 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. I posted it so you can play with it if you would like to get a head start on assignment #2. I will post assignment #2 formally next Tuesday.
    [2/4/10] The QII engine was developed on cpu architectures with clock speeds of max 800MHz, consequently on todays architectures with a clock speed in excess of 2GHz it is easy to overwhelm the engine with quagent commands, especially when the main loop in your quagent controller does not do much computation. One way to to slow down your quagent brain is to put a 'sleep' statement into your main loop:
    Thread.currentThread().sleep(1000); // sleep for a second
    
    The argument to the sleep statement is given in milliseconds. PLEASE DO NOT MODIFY THE API TO SLOW DOWN THE QUAGENT BRAIN, THIS MAKES IT IMPOSSIBLE FOR US TO VALIDATE YOUR PROGRAMS.
    [2/1/10] NOTE: It has come to my attention that the University book store has not stocked Alex's book. I am not quite sure what the reason is that the book has not been stocked and I have not been informed when the book will arrive. Therefore, I advise students to purchase the book through alternative channels (e.g. amazon.com).
    [1/26/10] Posted TA info
    [1/26/10] Posted programming assignment #1
    [1/25/10] Note that the gaming engine has only been tested with Windows XP, however, I suspect that it will run in Vista and 7 as well.
    [1/25/10] You should go to the online grade book and sign up for an account, your access code is engrade-csc481spring2010-nnnn where nnnn is your student ID number.
    [1/25/10]  Welcome!

    Homework/Programming Assignments:


    What, When & Where

    CSC481, Spring 2010
    When: T Th 12:30-1:45pm
    Where: Tyler 106

    Instructor:

    Lutz Hamel
    Tyler Hall, Room 251
    Office Hours: Monday 11-noon, Tuesday 2-3pm
    email: hamel@cs.uri.edu
     

    TA:

    Pankaj Ahire
    Office Hours: Thursday -- 9:30am - 11:30am, Room 136
    email: pahire@cs.uri.edu

    Links