Overview

Designing computer games requires integration of a variety of core computer science skills. Techniques from Artificial Intelligence (AI) can play a key role in helping to generate the behavior of non-player characters. In classic board games such as checkers or chess, adversarial search often forms the backbone of a competitive system. For real-time computer games, there are a variety of problems that must be addressed, from low level route finding, to higher level strategic planning.

This project investigates the use of heuristic search, knowledge representation and machine learning within the space of an interesting, open-ended, computer game. Students are provided with Robot Defense, a real time strategy game similar to the highly popular Flash game, Desktop Tower Defense. The game contains a variety of non-player characters. Throughout the course of this project, students improve the initial implementation by applying AI techniques to this particular problem domain.

The project is split into three modules each covering a core area of Artificial Intelligence including: search, knowledge representation and reinforcement learning. Assignments are designed to be used sequentially so that the game increases in sophistication over time. By the end of semester, students will have added low level functionality into the initial version of the game and created two agents capable of playing the game autonomously.
The aim of this project is to explore the use of AI within an interactive real-time game. The project is split into three modules that are designed to be used sequentially, but may also be used individually if the need arises. Each module covers one core area of Artificial Intelligence including: search, knowledge representation and machine learning. Objectives of the sequence are to:
  • Evaluate how changes to a problemís state space impact computational complexity of standard AI algorithms such as search.
  • Implement search within a resource-limited, real-time, environment.
  • Use a rule-based agent architecture to create an agent capable of playing the game autonomously and explore explanation-based learning within this context.
  • Implement an agent capable of playing the game based on policies acquired through reinforcement learning.
  • Compare and contrast the benefits of hand-coded knowledge and knowledge acquired through reinforcement learning.
Students should have a basic knowledge of algebra, discrete mathematics and statistics. Programming competence in at least one language is assumed and some background in Java would be helpful as all assignments are designed for this language. The Robot Defense Game itself is built using the Java Instructional Game Engine, but neither students nor the instructor is expected to be familiar with this framework.

The game should run on Windows, Macintosh and Linux platforms, although testing has been most thorough on the Windows XP platform. All machines should be verified to ensure that they have correct and up-to-date video card drivers for the best possible experience. The software is compatible with Java 1.5 and above, but Java 1.6r3 and above will provide a better game-play experience. The recommended minimal system requirements are a P4 3.0GHz CPU and a graphics card with 64MB of VRAM.
An introduction to search, machine learning and reinforcement learning can be found in any good AI book. Chapters 4, 18 and 21 respectively from Russell and Norvigís book are good examples. Soar, a rule-based agent architecture, is used in the second module of this project. The Soar website can be found at http://sitemaker.umich.edu/soar/home. An introduction to Soar Programming can be found in the tutorial while theoretical underpinnings are discussed in the Gentle Introduction to Soar.
The detailed project description is available in the PDF file RobotDefense.pdf. You will need the free Adobe Acrobat Reader to view this file.
This project is customizable to accommodate different teaching approaches and different course objectives. The description provides suggestions for individual use of the project modules and also provides suggestions for students seeking additional challenges.
A sample syllabus used at Washington State University Vancouver when this project was assigned is available at:
Syllabus for AI Course at Washington State University Vancouver

Other course materials are available at the course website.

Additional readings are included in the Background section above.