Transcript PPT - CCSC - Consortium for Computing Sciences in Colleges

Applications for
Gaming in AI
Sample Projects
from Computational Intelligence
Course
at Washburn University
Outline


Sample projects from this course
Challenges
Applications of Informed Search

Build Game Board where Predator is Searching
a matrix looking for least cost path to Prey
Task Environment is fully observable
 Both Single and Multi-Agent Implementations [i.e.
both predator and prey are moving]
 A*

Idea: avoid expanding paths that are already expensive
 Evaluation function f(n) = g(n) + h(n)

Applications of Informed Search

Build a Corn Maze where agent finds its way
through the maze

LRTA*


Used to solve problems where planning and action are
interleaved and environment is safely-explorable
Search to find the optimal solution to a
randomly selected scrambled Rubik's Cube

Iterative Deepening A* (IDA*)
Applications of Optimization
Algorithms

N-Queens
Place n=8 queens on board with no attacking queens
 Hill Climbing

Successor function generates 64 new boards
 Pick the best new board
 Beam Search - Pick best k moves


Genetic Algorithms

Successor function applies Fitness Function, Cross-Over,
and Mutation to generate new population of moves
Applications of Adversarial Search

Tic-Tac-Toe
MiniMax [with Alpha-Beta Pruning]
 Setting a cutoff where levels can be novice through
Master Level


Mastermind

Please don’t ask me questions about this game…
student is currently researching
Applications of Machine Learning

You enter how you would vote on a set of
legislative bills and I [the computer] will predict
your political party


Naïve Bayes
Guess your Cartoon Character based on the
answer to twenty questions

Nearest Neighbor
Challenges


Understanding is not necessarily trivial
Significant career opportunities in emerging
fields that are not just related to gaming


[e.g. Learning Science and Web Science].
The challenge
Develop the proper pedagogy and scaffolding that
will support student learning of these concepts.
 Course needs to be adaptable to meet the needs of
many types of students

References



[1] American Association for Artificial
Intelligence, 2006, Games and Puzzles,
http://www.aaai.org/AITopics/html/games.ht
ml, retrieved December 6, 2006
[2] Russell S. and Norvig R., Artificial
Intelligence a Modern Approach, 2ed., 2003,
Pearson Education, Inc.
[3] Bourg D. M. and Seemann G., AI For Game
Developers, 2004, O’Reilly Media, Inc