Game Playing in Artificial Intelligence�

Areas of Interest

• Definitions
• History, Overview
• Concepts
• Applications
• Current trends in this field

NB

One of the most studied and most interesting areas of Artificial Intelligence is game playing. They are Fun, and HARD to create

23-Mar-2009

Artificial Intelligence - CMT310

2

DEFINITION

• Game artificial intelligence refers to techniques used in computer and video games to produce the illusion of intelligence in the behavior of non-player characters (NPCs)
• Hacks and cheats are acceptable and, in many cases, the computer abilities must be toned down to give human players a sense of fairness. E.g racing and shooting
• Emphasis of game AI is on developing rational agents to match or exceed human performance

23-Mar-2009

Artificial Intelligence - CMT310

3

Definition cont …

• AI has continued to improve, with aims set on a player being unable to tell the difference between computer and human players - remember Turin test?

​

• A game must ‘feel’ natural
• Obey laws of the game
• Characters aware of the environment
• Path finding (A* algorithm)
• Decision making
• Planning
• Game ‘bookkeeping’, scoring
• ~50% of game project time is spent on building AI

23-Mar-2009

Artificial Intelligence - CMT310

4

Why are games relevant to AI?

• Games are fun!
• They are limited, well-defined rules
• They provide advanced, existing test-beds for developing several ideas and techniques that are useful elsewhere.
• They are one of the few domains that allow us to build agents.
• Studying games teaches us how to deal with other agents trying to foil our plans
• Huge state spaces – Games are highly complex! Usually, there is not enough time to work out the perfect move. E.g Go & Chess
• Nice, clean environment with clear criteria for success
• Game playing is considered an intelligent human activity.
• AI has always been interested in abstract games.
• Games present an ideal environment where hostile agents may compete.

​

​

23-Mar-2009

Artificial Intelligence - CMT310

5

State Space

• Coarser-grain than Tactical AI (Very Large space search)
• Problem solving consists of: (from Russel and Norvig, Ch. 3)
• Goal formulation
• Problem formulation
• Search
• Solution
• Execution

23-Mar-2009

Artificial Intelligence - CMT310

6

The Illusion of Human Behaviour

• Game AI is about the illusion of human behaviour
• Smart, to a certain extent (Creativity)
• Non-repeating behaviour
• Unpredictable but rational decisions
• Emotional influences (Irrationality, ‘Personality’)
• Body language to communicate emotions
• Being integrated in the environment
• Game AI needs various computer science disciplines
• Knowledge Based Systems
• Machine Learning
• Multi-agent Systems
• Computer Graphics & Animation
• Data Structures

23-Mar-2009

Artificial Intelligence - CMT310

7

Computer Games Types

• Strategy Games
• Real-Time Strategy (RTS)
• Turn-Based Strategy (TBS)
• Helicopter view
• Role-Playing Games (RPG)
• Single-Player
• Multi-Player (MMORPG)
• Action Games
• First-Person Shooters (FPS)
• First-Person Sneakers
• Sports Games
• Simulations
• Adventure Games
• Puzzle Games

23-Mar-2009

Artificial Intelligence - CMT310

8

More complicated games

• Most card games (e.g. Hearts, Bridge, etc.) and Scrabble
• non-deterministic
• lacking in perfect information.
• Cooperative games
• Real-time strategy games (lack alternating moves). e.g. Warcraft

23-Mar-2009

Artificial Intelligence - CMT310

9

​

​

​

The functionalism of game AI

• Turing test ‘1.1’
• Simulated behaviour
• Believability
• Human-like or plausible robot/alien
• Fidelity
• Non-cheating
• Fiction - not (to much) autonomy!

→ Pseudo-autonomy: limited knowledge, ‘personal’ goals etc.

23-Mar-2009

Artificial Intelligence - CMT310

10

History and overview

• Minimax

- Developed by John von Neumann in 1928

- This algorithm is used extensively in game theory

• Samuel’s learning program (1959)

- The program learns through the manipulation of the summation of heuristics.

- If the program wins, it raises high heuristic values and lowers low ones. If it loses, it does the opposite.

• 1960s

- Progress and success in Game AI.

- Creating a successful AI meant coming up with the right rules for it to follow.

1970s-1980s

- Transition to games as entertainment

- Using search based AI to emulate entertaining characters would be unnatural and clumsy

- Game play is based more on skill than on rules

• Early 1990s

- Increased realism becomes the primary focus of the game industry

- A rift develops between the developers of popular games and AI researchers

​

23-Mar-2009

Artificial Intelligence - CMT310

11

Examples:

First Person Shooters (Halflife, Deus Ex, Unreal Tournament): “Suicidal” AI is replaced by more sophisticated AI that appears to care about its own life. It coordinates attacks, calls for backup, and retreats when hurt. Friendly AI can even be given orders by the player.

Real Time Strategy: AI in the broad scheme doesn’t evolve much in RTS games. Individual unit scripts are added in to some games, but in the over all picture, the AI still simply pours units at an enemy until it is defeated. Perhaps this is because of the foreignness of the RTS paradigm, or maybe it really is the best strategy. Most successful human players abide by this “rush” strategy.

23-Mar-2009

Artificial Intelligence - CMT310

12

Late 1990s

- To add intrigue, developers look again to AI

​

CONCEPTS�Technologies / techniques used

• Machine learning
• Waypoint Graph
• Continuous Control
• Cellular Automata
• Case Based Reasoning
• Blend Database
• Dynamic Programming
• Finite State Machines
• Fuzzy Logic
• Influence Mapping
• Hierarchical Task Network
• A* Algorithms
• Ragdoll
• Teleo Reactive Programs
• Scripting

• Motion Graph
• Motion Capture
• Navigation Mesh
• Navigation Graph
• Artificial Neural Networks
• Policy Search
• Path Planning
• Proportional Derivative Controller
• Path Planning
• Path Finding
• Path Following
• Steering
• Semantic Markup
• Reinforcement Learning
• Alpha-Beta pruning
• MiniMax

​

23-Mar-2009

Artificial Intelligence - CMT310

13

Techniques / Technologies used

• Machine Learning - also known as ML, is a field of artificial intelligence which focuses on developing algorithms that can learn to predict, classify, control, or solve problems

​

• Semantic Markup - The process of annotating raw information with meta-data that explains its meaning to the AI.

​

​

• Reinforcement Learning - Taking past data that the AI has recorded and using it to influence behavior and choices made in the future.

​

• Waypoint Graph - is a collection of waypoints linked up to form the information about what areas of a level can be traversed by an actor during path finding.

​

23-Mar-2009

Artificial Intelligence - CMT310

14

Game setup

• Two players: A and B
• A moves first and they take turns until the game is over. Winner gets award, loser gets penalty.
• Games as search:
• Initial state: e.g. board configuration of chess
• Successor function: list of (move, state) pairs specifying legal moves.
• Terminal test: Is the game finished?
• Utility function: Gives numerical value of terminal states. E.g. win (+1), lose (-1) and draw (0) in tic-tac-toe
• A uses search tree to determine next move.

23-Mar-2009

Artificial Intelligence - CMT310

15

How to Play a Game by Searching

• General Scheme
• Consider all legal moves, each of which will lead to some new state of the environment (‘board position’)
• Evaluate each possible resulting board position
• Pick the move which leads to the best board position.
• Wait for your opponent’s move, then repeat.
• Key problems
• Representing the ‘board’
• Representing legal next boards
• Evaluating positions
• Looking ahead

​

23-Mar-2009

Artificial Intelligence - CMT310

16

The Minimax Rule

23-Mar-2009

Artificial Intelligence - CMT310

17

• MiniMax rule: Decision Making in Multi-agent Systems
• Perfect play for deterministic, perfect-information games.
• Idea: make the move for player MAX which has the most benefit assuming that MIN makes the best move for MIN in response

​

• This is computed by a recursive process
• The backed-up value of each node in the tree is determined by the values of its children
• For a MAX node, the backed-up value is the maximum of the �values of its children (i.e. the best for MAX)
• For a MIN node, the backed-up value is the minimum of the �values of its children (i.e. the best for MIN)

Minimax Procedure

​

​

​

​

23-Mar-2009

Artificial Intelligence - CMT310

18

Consider a 2-ply (two step) game:

Max want’s largest outcome --- Min want’s smallest.

1. Start with the current position as a MAX node.
2. Expand the game tree a fixed number of ply (half-moves).
3. Apply the evaluation function to the leaf positions.
4. Calculate back-up up values bottom-up.
5. Pick the move which was chosen to give the MAX value at the root.

MinMax - Overview

• MinMax the heart of almost every computer board game
• Applies to games where:
• Players take turns
• Underlying assumption
• Opponent acts rationally
• Have perfect information
• Chess, Checkers, Tactics
• But can work for games without perfect information or chance e.g Poker, Monopoly, Dice
• Can work in real-time (i.e- not turn based) with timer (iterative deepening, later)

23-Mar-2009

Artificial Intelligence - CMT310

19

Minimax Algorithm

23-Mar-2009

Artificial Intelligence - CMT310

20

function MINIMAX-DECISION(state) returns an action

inputs: state, current state in game

v←MAX-VALUE(state)

return the action in SUCCESSORS(state) with value v

function MIN-VALUE(state) returns a utility value

if TERMINAL-TEST(state) then return UTILITY(state)

v ← ∞

for a,s in SUCCESSORS(state) do

v ← MIN(v, MAX-VALUE(s) )

return v

function MAX-VALUE(state) returns a utility value

if TERMINAL-TEST(state) then return UTILITY(state)

v ← -∞

for a,s in SUCCESSORS(state) do

v ← MAX(v, MIN-VALUE(s) )

return v

Properties of minimax

• Complete? Yes (if tree is finite)�
• Optimal? Yes (against an optimal opponent)�
• Time complexity? O(b^m)�
• Space complexity? O(bm) (depth-first exploration)�

​

• For chess, b ≈ 35, m ≈100 for "reasonable" games�🡪 exact solution completely infeasible
• The avg branching factor for chess is 35. A game may involve 50 moves per player, so the search tree has 35 ¹⁰⁰ nodes. Even eliminating duplicates, there are 10 ⁴⁰ unique legal states! Assuming successors can be generated in .33 nanoseconds, it would take 10 ²² centuries to do an exhaustive search!. The universe is only 10¹⁰ years old

23-Mar-2009

Artificial Intelligence - CMT310

21

Alpha-Beta Pruning

• Eliminating a branch without consideration is called pruning
• Want to visit as many board states as possible (Can be used for entire search or cutoff search)
• Want to avoid whole branches (prune them)
• Because they can’t possibly lead to a good score
• A way to improve the performance of the Minimax Procedure
• Basic idea: “If you have an idea which is surely bad, don’t take the time to see how truly awful it is” ~ Pat Winston

23-Mar-2009

Artificial Intelligence - CMT310

22

• We don’t need to compute the value at this node.
• No matter what it is it can’t effect the value of the root node. (branch cannot produce better score than a node you have already evaluated)

α−β Pruning Example

23-Mar-2009

Artificial Intelligence - CMT310

23

≥ 3

MAX

MIN

=3

3

12

8

Alpha-Beta Pruning

• Traverse the search tree in depth-first order
• For each MAX node n, α(n)=maximum child value found so far
• Starts with – ∞
• Increases if a child returns a value greater than the current α(n)
• Lower-bound on the final value
• For each MIN node n, β(n)=minimum child value found so far
• Starts with + ∞
• Decreases if a child returns a value less than the current β(n)
• Upper-bound on the final value
• MAX cutoff rule: At a MAX node n, cut off search if α(n)>=β(n)
• MIN cutoff rule: At a MIN node n, cut off search if β(n)<=α(n)
• Carry α and β values down in search

23-Mar-2009

Artificial Intelligence - CMT310

24

Alpha-Beta Algorithm 1�MAX Ply

23-Mar-2009

Artificial Intelligence - CMT310

25

function ALPHA-BETA-SEARCH(state) returns an action

inputs: state, current state in game

v←MAX-VALUE(state, - ∞ , +∞)

return the action in SUCCESSORS(state) with value v

function MAX-VALUE(state,α , β) returns a utility value

if TERMINAL-TEST(state) then return UTILITY(state)

v ← - ∞

for a,s in SUCCESSORS(state) do

v ← MAX(v,MIN-VALUE(s, α , β))

if v ≥ β then return v

α ← MAX(α ,v)

return v

Alpha-Beta Algorithm II�MIN Ply

23-Mar-2009

Artificial Intelligence - CMT310

26

function MIN-VALUE(state, α , β) returns a utility value

if TERMINAL-TEST(state) then return UTILITY(state)

v ← + ∞

for a,s in SUCCESSORS(state) do

v ← MIN(v,MAX-VALUE(s, α , β))

if v ≤ α then return v

β ← MIN(β ,v)

return v

α-β

• Properties
• Pruning does not affect final result�

​

• Good move ordering improves effectiveness of pruning�

​

• With "perfect ordering," time complexity = O(b^m/2)

🡪 doubles depth of search

​

• A simple example of the value of reasoning about which computations are relevant (a form of metareasoning)�

• Effectiveness
• Guaranteed to compute same root value as Minimax
• Worst case: no pruning, same as Minimax (O(b^d))
• Best case: when each player’s best move is the first option examined, you examine only O(b^d/2) nodes, allowing you to search twice as deep!
• For Deep Blue, alpha-beta pruning reduced the average branching factor from 35-40 to 6.

23-Mar-2009

Artificial Intelligence - CMT310

27

Minimax for nondeterministic games

1. For min node, compute min of children.
2. For chance node, compute weighted average of children.
3. For max node, compute max of children.

23-Mar-2009

Artificial Intelligence - CMT310

28

3

Deterministic games in practice

Othello: Human champions refuse to compete against computers, who are too good.

​

Go: Human champions refuse to compete against computers, who are too bad. In Go, b > 300, so most programs use pattern knowledge bases to suggest plausible moves.

23-Mar-2009

Artificial Intelligence - CMT310

29

23-Mar-2009

Artificial Intelligence - CMT310

30

APPLICATIONS

• Training Simulators
• Effective training often requires thousands of people
• Computer generated stand-ins can cut costs
• Military simulations
• Management simulations
• Economic simulations
• Education
• Software for pre-school children
• Entertainment
• Virtual Environments
• Simulated worlds allows AI researchers to concentrate on algorithms instead of sensors
• Again, computer generated robots are cheaper than actual robots

23-Mar-2009

Artificial Intelligence - CMT310

31

• Human-level AI

- Every person is an expert on

human-level intelligence

- Testing of AI is easy

• Movies

- Crowd scenes

- Flocking behavior

- Realistic Movement

​

Applications

23-Mar-2009

Artificial Intelligence - CMT310

32

• In his work on CHINOOK, Schaeffer had to develop new parallel algorithms for information storage and retrieval. Those algorithms are now finding use in DNA sequencing and other areas.

​

• The early research on the alpha-beta search algorithm was useful in establishing a foundation for AI theories of heuristic search, and these theories have been useful in many areas of AI

​

• Tesauro used backgammon as a test bed for the development of learning algorithms that have inspired work by other researchers on several other problems. Examples include

- Job-shop scheduling for the NASA space shuttle,

- Elevator dispatch control

- Cellphone channel assignment

- Assembly-line manufacturing

​

Applications

23-Mar-2009

Artificial Intelligence - CMT310

33

To adapt hierarchical task-network planning techniques for use in BRIDGE GAME, ways for the planner to perform complex numeric calculations, plan for multiple agents, consult external information sources, and reason about uncertain information were developed.

These same techniques are now proving useful in generating and evaluating manufacturing process plans

Applications

Game AI Major Challenges

• Resources

- Realism in computer games focused on graphics

- Advanced graphics requires many CPU cycles

- Recent advances in computer hardware have someone alleviated this issue.

• Deadlines

- Game engine must be developed before AI can be tested

- AI programmers often have to compromise to meet deadlines

• Over Intelligence

- Perfect AI would be easier to code

- It would lack believability and not be fun.

- Human-level AI should quit, surrender, or run away- even fight to the end.

• Research and Development

- Lack of cohesion between AI research community and game developers

- AI in modern computer games seems trivial to AI researchers

23-Mar-2009

Artificial Intelligence - CMT310

34

• Human Level Intelligence

- Human level behavior will require AI

- We currently have only limited behavior

- Human level intelligence is really hard to create and

we still do not know how to achieve it

23-Mar-2009

Artificial Intelligence - CMT310

35

TRENDS of Game AI

• Scripting Languages. This are AI Frameworks, Engines, and Integrated Development Environments e.g Lua, WoW, CryENGINE
• Cooperative AI. cooperating groups of enemies.
• Sandbox Games. A sandbox means that the whole game becomes more of a simulation where AI plays an important role.
• Hierarchical Planners. the enemy behaviors is handled using an AI planner.
• Games for All - widening accessibility. games outstripped combined sales of music and video products in 2008
• Open Worlds - use of a free-roaming environment, pursuit of exploration is popular with developers and has proved highly successful.
• Co-op Mode - a second player becomes the main character's sidekick

23-Mar-2009

Artificial Intelligence - CMT310

36

Changes in Games Development

• Content the real issue
• Most games now content led not tech led
• Data driven everything in order to get it all done
• Getting the programmer out of the way
• Team scale impacting process and creativity
• Getting everyone on same page
• Creatively collaboration at a large scale
• Growing gap between top-sellers and the rest
• Growing budgets and team size
• Independent Developers of games are now in market

23-Mar-2009

Artificial Intelligence - CMT310

37

Changes in Gaming

• Games were linear sequences of challenges
• Challenge itself as play-value/entertainment
• “World” abstracted and simplified
• Current trends
• High world fidelity, and growing
• Open-ended worlds, player choice/customization
• New aspects of play

23-Mar-20009

Artificial Intelligence - CMT310

38

Changes in Game Fidelity

• Graphics: huge leaps in 20 years
• Scale and density of environments increasing
• Physics fidelity obviously much better
• No conversation systems
• Inadequate NPC AI

23-Mar-20009

Artificial Intelligence - CMT310

39

Changing Game Players

• providing more multi-human gaming opportunities
• Teaming up with/against other humans
• Large environments
• Changing environments
• Single-player games containing more movie-inspired moments, more watching

​

23-Mar-2009

Artificial Intelligence - CMT310

40

The Industry Now

• Consolidation: Fewer games, bigger budgets
• Harder to get projects approved
• Risk management central to business
• Large public companies revenue driven, need big sales numbers regardless of development costs
• Licensing and sequeling established IP’s

23-Mar-2009

Artificial Intelligence - CMT310

41

• Present

- Broadband and online multiplayer games

- Highly immersive AI to contrast real players

Examples:

Multiplayer Games (Battlefield 1942): The AI in this game is outright pitiful. While it excels at pathfinding, using tanks, planes, ships, and other implements, it is simply not human-like behavior. Among other things, the AI lacks a reasonable strategy. Instead of sending all of its troops to the front lines, it distributes them equally throughout the map. It often has trouble deciding whether it should shoot an enemy or simply lie down and stand up repeatedly.

Immersive AI (Halo): Because of the plotline in this game, the friendly AI acts largely autonomously. While the human player is the “leader,” this only extends to the AI’s protection, not its obedience. This is also reflected in the opponent AI. When attacking a group of AI controlled enemies, if the leader is removed first, the remaining force becomes less effective and less organized.

​

23-Mar-2009

Artificial Intelligence - CMT310

42

THE FUTURE OF GAME AI

• Intelligent Landscape

- Sims weren’t smart at all

- Instead, surrounding objects contained instructions for use

- AI finds the object that makes them happy and follows instructions

• Fuzzy AI

- Rule based AI is not sufficient to model human intelligence

- Uncertain algorithms such as Genetic Algorithms and Neural Networks are the future

• Immersive game space

- Instead of creating a reality, the AI borrows from the real world

- Will a game AI be the first to pass the Turing Test?

​

23-Mar-2009

Artificial Intelligence - CMT310

43

Future of AI games cont …

World Fillers

• Massively multi-player games need to be populated by non-player-character (NPC) agents.
• Key problem: The world is persistent.
• NPCs are needed to;
• Sell things and make things.
• Play key roles in story telling.

Better Opposition

• Opponents that provide a real, dynamic, challenge.
• Not just foot soldiers, but generals, political manipulators etc

​

23-Mar-2009

Artificial Intelligence - CMT310

44

Summary�

• Games are to AI as grand prix racing is to automobile design
• Games are fun to work on (and dangerous)
• They illustrate several important points about AI
• – perfection is unattainable, must approximate
• – it is a good idea to think about what to think about
• – uncertainty constrains the assignment of values to states

23-Mar-2009

Artificial Intelligence - CMT310

45

Philosophical Food for thought

• Drew McDermott:
• "Saying Deep Blue doesn't really think about chess is like saying an airplane doesn't really fly because it doesn't flap its wings”
• Q. If aliens came to Earth and challenged us to chess…
• Would you send Deep Blue or Kasparov into battle?

23-Mar-2009

Artificial Intelligence - CMT310

46

Bibliography

• Peterson, Ivars. “Silicon Champions of the Game.”
• Wookcock, Steve. “Game AI: The State of the Industy”
• “AI in Gaming” Generation5.org. http://www.generation5.org/app_game.shtml.
• McCarthy, John. “Arthur Samuel: Pioneer in Machine Learning.” Stanford Computer Science Computer History
• Laird, John and Michael van Lent. “Human-level AI’s Killer Application: Interactive Computer Games.”
• Laird, John. “Bridging the Gap Between Developers and Researchers.”
• Johnson, Steven. “Wild Things.”
• from http://www.aigamedev.com
• Game Artificial Intelligence. Wikipedia, the free Encyclopedia

23-Mar-2009

Artificial Intelligence - CMT310

47