is2004 | Wiki | グルメマップ | ブックマーク | OWiki

■Michael Buro

Game AI History, Trends, and Challenges

ALBERTA One of the World's strongest AI groups

We are looking for talented graduate students


Traditional Game AI Games are ideal testbeds for AI research

・Simple descriptions create complex worlds

・・Many generalized games are PSPACE or even EXP-time complete

・Can be tailored towards specific research questions

・・1,2 or more players? Teams?

・・Perfect or imperfect information?


・・Zero-sum or arbitrary payoffs?

・Competitions drive research!


chess, go, checkers, Othello, bridge, poker,


・Usually slow paced(except card games)

・AI goal: defeat the best human players


・Minimax search and improvements for perfect information games

・・Look-ahead d moves

・・Evaluate resulting position

・・Propagage values up using the minimax rule

・Selective sampling for card games


1936 turning's chess program

1950s Shannon A+B

1960s Alpha-Beta search

1970s Brute-force takes over

1980s Dedicated chess hardware Belle, Hitech ChipTest

1997 512 chess chips("Deep Blue") defeat Kasparov 3.5-2.5 "IBM can be used for weather-forecasting,too!"

2006 PC program "Deep Fritz" defeats Kramnik 4-2

2007 PC program "Rybka" 80-100 ELO points ahead of competitors, approaching 3000 on a single CPU!


1995 "Chinook" defeats Checkers World-Champion Lafferty (2007 checkers close to being solved)

1996 "TD Gammon" reaches World Champion level

1997 "Logistello" defeats Othello World-Champion 6-0

2006 "Quackle" defeats former scrabble World-Champion 3-2

2007 9*9 Go programs close to 1-dan level


Increased speed gigaherz, parallelization

Large internal/external memory

Search enhancements transposition tables, selectivity

Large opening/endgame databases

Supervised parameter learning

Reinforcement learning

Selective sampling


Amazing recent improvement of Go programs

New game-tree search algorithm UCT

・"Upper Confidence bound for Trees"

Treat move decisions as "multi-armed bandit" problems

・Given k slot machines, find one with highest expected payoff by pulling arms repeatedly

UCB rule: pick move i with highest value

This + clever way of playing games till the end challenges 20 years of computer Go research


Video Games

・Many genres thousands of titles: RPG, FPS, RTS


・Simultaneous actions

・Huge action/state spaces

・Imperfect information

Real-Time Strategy(RTS) games like

・500*500 chess

・hundreds of slow-moving pieces

・all pieces move k times per second

・limited view around own pieces


Humans much better on strategic level

Programs do not




・recognize opponent plans

・cooperate well


Slow progress

・Many companies don't care too much about game AI research

・・"After learning the game, people play on-line, anyway"

・AI still mostly scripted

・・Simple goal-directed behaviors



・・Easy to counter


Black & White

・Reinforcement learning

・Creatures change behavior depending on player feedback


・Applying STRIPS-like planning to FPS

・Designers create basic behaviors ・Planner creates action sequence that satisfies goal(state machine + A*)

Age of Empires ・Terraing analysis by means of pathfinding, zone decomposition, influence maps


Get academics excited and organize competitions


Sound and complete for circular objects

Graph size=#islands

Up to 100 times faster than A* on commercial game maps


Collaborative pathfinding

Adversarial planning(RTSplan, presentation at 9:30 today)

Target selection



Video Game AI


RTS Games

トップ   差分 バックアップ リロード   一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2007-04-11 (水) 22:06:38 (4452d)