Game Playing

Game as Search Problem

• Initial State: board position and player to
move
• Successor Function: returns a list of legal
(move, state) pairs
• Terminal Test: determines when the game
is over
• Utility function: Gives a numeric value for
the terminal state
CS 484 – Artificial Intelligence 2
 Game Trees
• Game trees are used to represent two-player
games.
• Alternate moves in the game are represented by
alternate levels in the tree (plies).
• Nodes in the tree represent positions.
• Edges between nodes represent moves.
• Leaf nodes represent won, lost or drawn positions.

CS 484 – Artificial Intelligence 3

Game Trees

This is an example of a
partial game tree for the
game tic-tac-toe.
Even for this simple game,
the game tree is very large.

CS 484 – Artificial Intelligence 4

 Assumptions
• In talking about game playing systems, we
make a number of assumptions:
• The opponent is rational – will play to win.
• The game is zero-sum – if one player wins, the
other loses.
• Usually, the two players have complete
knowledge of the game. For games such as
poker, this is clearly not true.

CS 484 – Artificial Intelligence 5

Game Tree Representation
Computer
S
Moves

Opponent
Moves

Computer
Moves

G Possible Goal State

lower in Tree (winning situation for computer)

• New aspect to search problem

• there’s an opponent we cannot control
• how can we handle this?
 Complexity of Game Playing
• Imagine we could predict the opponent’s moves given each computer move

• How complex would search be in this case?

• worst case, it will be O(bd)
• Chess:
• b ~ 35 (average branching factor)
• d ~ 100 (depth of game tree for typical game)
• bd ~ 35100 ~10154 nodes!! (“only” about 1040 legal states)
• Tic-Tac-Toe
• ~5 legal moves,
• 59 = 1,953,125
• 9! = 362,880 (Computer goes first)
• 8! = 40,320 (Computer goes second)

• well-known games can produce enormous search trees

 Utility Functions
• Utility Function:
• defined for each terminal state in a game

• assigns a numeric value for each terminal state

• these numbers represent how “valuable” the state is for the computer
• positive for winning
• negative for losing
• zero for a draw

• Typical values from -infinity (lost) to +infinity (won) or [-1, +1].

 Minimax
• Minimax is a method used to evaluate game
trees.
• A static evaluator is applied to leaf nodes,
and values are passed back up the tree to
determine the best score the computer can
obtain against a rational opponent.

CS 484 – Artificial Intelligence 9

 Minimax – Animated Example
Max 3 6 The computer can
obtain 6 by
choosing the right
Min 6 hand edge from the
5 3 first node.

Max 1 3 6 0 7
5

5 2 1 3 6 2 0 7

CS 484 – Artificial Intelligence 10

General Minimax Algorithm on
a Game
For each move by the computer
Tree
1. perform depth-first search with depth-limit m
2. assign evaluation functions at each state at depth m
3. propagate upwards the minimax choices
if the parent is a minimizer (opponent)
propagate up the minimum value of the children
if the parent is a maximizer (computer)
propagate up the maximum value of the children
4. choose the move (the child of the current node) corresponding
to the maximum of the minimax values if the children

Note:
- minimax values are gradually propagated upwards as depth-first
search proceeds, i.e., minimax values propagate up the tree in
a “left-to-right” fashion
- minimax values for sub-tree are propagated upwards “as we go”,
so only O(bd) nodes need to be kept in memory at any time
 Searching Game Trees
• Exhaustively searching a game tree is not usually
a good idea.
• Even for a game as simple as tic-tac-toe there are
over 350,000 nodes in the complete game tree.

CS 484 – Artificial Intelligence 12

 Alpha-beta Pruning
• A method that can often cut off a half the
game tree.
• Based on the idea that if a move is clearly
bad, there is no need to follow the
consequences of it.
• alpha – highest value we have found so far
• beta – lowest value we have found so far

CS 484 – Artificial Intelligence 13

 Alpha-beta Pruning –
Example.
max 3 • In this tree,
having
min examined the
nodes with
values 7 and 1
there is no need
to examine the
final node.

CS 484 – Artificial Intelligence 14

 The Alpha Beta Principle:
Marry Search Tree Generation
with Position Evaluations
1

Computer's

0 -8
1
Opponent’s Moves
(min of evaluations)

3 4 1 2 0 -8

X X X (X indicates ‘not evaluated’)

 Effectiveness of Alpha-Beta
Search
• In practice often get O(b(d/2)) rather than O(bd)
• this is the same as having a branching factor of sqrt(b),
• since (sqrt(b))d = b(d/2)
• i.e., we have effectively gone from b to square root of b
• e.g., in chess go from b ~ 35 to b ~ 6
• this permits much deeper search in the same amount of time
• makes computer chess competitive with humans!
 Alpha Beta Procedure
• Depth first search of game tree, keeping track of:
• Alpha: Highest value seen so far on maximizing level
• Beta: Lowest value seen so far on minimizing level

• Pruning
• When Maximizing,
• do not expand any more sibling nodes once a node has been seen
whose evaluation is smaller than Alpha
• When Minimizing,
• do not expand any sibling nodes once a node has been seen whose
evaluation is greater than Beta
 Bounded Lookahead
• For trees with high depth or very high branching
factor, minimax cannot be applied to the entire
tree.
• In such cases, bounded lookahead is applied:
• search is cut off at specified depth
• static evaluator applied.

18
 Static Evaluation Functions
• A static evaluator assigns a score to a position:
• High positive = computer is winning
• Zero = even game
• High negative = opponent is winning
• It is most important that a static evaluator will give
a better score to a better position – the actual
values are not so important.

19
Natural Language Processing
Natural Language Processing (NLP) refers to AI
method of communicating with an intelligent
systems using a natural language such as English.

Processing of Natural Language is required when

you want an intelligent system like robot to
perform as per your instructions, when you want
to hear decision from a dialogue based clinical
expert system, etc.
The field of NLP involves making computers to perform useful
tasks with the natural languages humans use.

The input and output of an NLP system can be −

1.Speech

2.Written Text

Components of NLP

There are two components of NLP as given −

• Natural Language Understanding (NLU)
• Natural Language Generation (NLG)
Natural Language Understanding (NLU)

Understanding involves the following tasks −

• Mapping the given input in natural language into useful

representations.

• Analyzing different aspects of the language.

Natural Language Generation (NLG)
It is the process of producing meaningful phrases and
sentences in the form of natural language from some internal
representation.
It involves −
• Text planning − It includes retrieving the relevant content
from knowledge base.
• Sentence planning − It includes choosing required words,
forming meaningful phrases, setting tone of the sentence.
• Text Realization − It is mapping sentence plan into
sentence structure.

The NLU is harder than NLG.

NLP Terminology

• Phonology − It is study of organizing sound

systematically.

• Morphology − It is a study of construction of words

from primitive meaningful units.

• Morpheme − It is primitive unit of meaning in a

language.

• Syntax − It refers to arranging words to make a

sentence. It also involves determining the structural
role of words in the sentence and in phrases.
.
• Semantics − It is concerned with the meaning of
words and how to combine words into meaningful
phrases and sentences.

• Pragmatics − It deals with using and understanding

sentences in different situations and how the
interpretation of the sentence is affected.

• Discourse − It deals with how the immediately

preceding sentence can affect the interpretation of the
next sentence.

• World Knowledge − It includes the general

knowledge about the world
Steps in NLP
There are general five steps −

• Lexical Analysis − It involves identifying and analyzing

the structure of words. Lexicon of a language means the
collection of words and phrases in a language. Lexical
analysis is dividing the whole chunk of txt into
paragraphs, sentences, and words.

• Syntactic Analysis (Parsing) − It involves analysis of

words in the sentence for grammar and arranging words
in a manner that shows the relationship among the words.
The sentence such as “The school goes to boy” is rejected
by English syntactic analyzer.
• Semantic Analysis − It draws the exact meaning or the
dictionary meaning from the text. The text is checked for
meaningfulness. It is done by mapping syntactic
structures and objects in the task domain. The semantic
analyzer disregards sentence such as “hot ice-cream”.

• Discourse Integration − The meaning of any sentence

depends upon the meaning of the sentence just before it.
In addition, it also brings about the meaning of
immediately succeeding sentence.

• Pragmatic Analysis − During this, what was said is re-

interpreted on what it actually meant. It involves deriving
those aspects of language which require real world
knowledge.