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?

・・Stochasticity?

・・Zero-sum or arbitrary payoffs?

・Competitions drive research!

 

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

・Turn-based

・Usually slow paced(except card games)

・AI goal: defeat the best human players

Methods

・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

・Real-time

・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

・plan

・learn

・reason

・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

・・Inflexible

・・Repetitive

・・Easy to counter

 

Black & White

・Reinforcement learning

・Creatures change behavior depending on player feedback

F.E.A.R.

・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 (3896d)