19-11-2012, 11:25 AM
Artificial Intelligence for Games
AI.ppt (Size: 419 KB / Downloads: 168)
Introduction to Artificial Intelligence (AI)
Many applications for AI
Computer vision, natural language processing, speech recognition, search …
But games are some of the more interesting
Opponents that are challenging, or allies that are helpful
Unit that is credited with acting on own
Human-level intelligence too hard
But under narrow circumstances can do pretty well (ex: chess and Deep Blue)
For many games, often constrained (by game rules)
Artificial Intelligence (around in CS for some time)
AI for CS different than AI for Games
Must be smart, but purposely flawed
Loose in a fun, challenging way
No unintended weaknesses
No “golden path” to defeat
Must not look dumb
Must perform in real time (CPU)
Configurable by designers
Not hard coded by programmer
“Amount” and type of AI for game can vary
RTS needs global strategy, FPS needs modeling of individual units at “footstep” level
RTS most demanding: 3 full-time AI programmers
Puzzle, street fighting: 1 part-time AI programmer
All of project 2.
MinMax - Overview
MinMax the heart of almost every computer board game
Applies to games where:
Players take turns
Have perfect information
Chess, Checkers, Tactics
But can work for games without perfect information or chance
Poker, Monopoly, Dice
Can work in real-time (ie- not turn based) with timer (iterative deepening, later)
MaxMin - Algorithm
Named MinMax because of algorithm behind data structure
Assign points to the outcome of a game
Ex: Tic-Tac-Toe: X wins, value of 1. O wins, value -1.
Max (X) tries to maximize point value, while Min (O) tries to minimize point value
Assume both players play to best of their ability
Always make a move to minimize or maximize points
So, in choosing, Max will choose best move to get highest points, assuming Min will choose best move to get lowest points
MinMax and Chess
With full tree, can determine best possible move
However, full tree impossible for some games! Ex: Chess
At a given time, chess has ~ 35 legal moves. Exponential growth:
35 at one ply, 352 = 1225 at two plies … 356 = 2 billion and 3510 = 2 quadrillion
Games can last 40 moves (or more), so 3540 … Stars in universe: ~ 228
For large games (Chess) can’t see end of the game. Must estimate winning or losing from top portion
Evaluate() function to guess end given board
A numeric value, much smaller than victory (ie- Checkmate for Max will be one million, for Min minus one million)
So, computer’s strength at chess comes from:
How deep can search
How well can evaluate a board position
(In some sense, like a human – a chess grand master can evaluate board better and can look further ahead)