Module 3

GAME PLAYING

Properties Games

Deterministic: A game is deterministic if an action of a player leads to

completely predictable outcomes. Example Chess: the rules allow for
no variation of outcome and there are no physical factors involved.
Football is an in deterministic game: players cannot reliably kick the
ball exactly the same way each time, and the small variations of that
action lead to chaotic outcomes.

Turn-taking: A turn-taking game is one where the players play one at

a time in alternating turns.

Two-player Zero-sum: A zero-sum game1 is defined as one where

the total payoff to all players is the same for every instance of the
game.

Perfect information: Perfect information implies knowledge of each

player’s utility functions, payoffs and strategies. Chess is an example
of a game with perfect information as each player can see all the
pieces on the board at all times. Other examples of games with perfect
information include tic-tac-toe, checkers, and Go.

Matching Pennies Game

Matching pennies is the name for a simple game used in game theory.
It is played between two players, Even and Odd. Each player has a
penny and must secretly turn the penny to heads or tails. The players
then reveal their choices simultaneously. If the pennies match (both
heads or both tails), then Even keeps both pennies, so wins one from
Odd (+1 for Even, −1 for Odd). If the pennies do not match (one heads
and one tails) Odd keeps both pennies, so receives one from Even (−1
for Even, +1 for Odd).

Matching Pennies is a zero-sum game because each participant's gain

or loss of utility is exactly balanced by the losses or gains of the utility
of the other participants. If the participants' total gains are added up
and their total losses subtracted, the sum will be zero. The game can
be written in a payoff matrix .Each cell of the matrix shows the two
players' payoffs.

Player 2
H T
Player 1 H 1, -1 -1, 1
T -1, 1 1, -1

Rock paper scissors Game

Rock paper scissors is a hand game usually played between two

people, in which each player simultaneously forms one of three shapes
with an outstretched hand. It is a zero-sum game, it has only two
possible outcomes: a draw, or a win for one player and a loss for the
other. A player who decides to play rock will beat another player who
has chosen scissors ("rock crushes scissors" ), but will lose to one who
has played paper ("paper covers rock"); a play of paper will lose to a
play of scissors ("scissors cuts paper"). If both the players choose the
same shape, the game is tied and is usually immediately replayed to
break tie. The type of game originated in China and spread with
increased contact with East Asia, while developing different variants in
signs over time.
 Player 2
R P S

R (0,0) (-1, 1) (1, -1)

Player 1 P (1, -1) (0,0) (-1, 1)
S (-1, 1) (1, -1) (0,0)

Tic-tac-toe

Tic-tac-toe and crosses is a paper-and-pencil game for two players, X

and O, who take turns marking the spaces in a 3 X 3 grid. The player
who succeeds in placing three of his/her marks in a diagonal,
horizontal, or vertical row is the winner

Game Tree

A game tree is a type of recursive search function that examines all

possible moves of a strategy game, and their results, in an attempt to
ascertain the optimal move. They are very useful in scenarios that do
not require real-time decision making and have a relatively low
number of possible choices per play. The most commonly-cited
example is chess, but they are applicable to many situations.
Example

Consider the game of tic-tac-toe and let the players be named “MAX”
and “MIN”. MAX plays by placing an X and MIN plays by placing an O in
a cell in the grid. In the figure the initial state is represented by a blank
grid at the top. From the initial state, MAX has nine possible moves.
These are indicated in the figure by the nine children of the initial
state. Play alternates between MAX’s placing an X and MIN’s placing an
O. This is continued until we reach leaf nodes corresponding to
terminal states such that one player has three in a row or all the
squares are filled. The number on each leaf node indicates the utility
value of the terminal state from the point of view of MAX; high values
are assumed to be good for MAX and bad for MIN.

Solving a game

By solving a two-player zero sum game we mean determining what

actions are to be taken by the players when they are at particular
states in playing the game. We assume that the players are “rational”
by which we mean that each player would play to secure the optimal
advantage. Since it is a zero-sum game, one player’s gain is
opponent’s loss. As a convention, the player who is trying to maximize
the gain is called the maximizing player and is MAX and the player who
is trying to minimize the loss is called the minimizing player and is MIN.

Question: Solve the following zero-sum two-player game

Solution

The steps in arriving at a solution are described below.

1. The first player is MAX and he is at state A.

2. There are three possible moves for MAX now: a1, a2, a3.

3. Suppose A chooses a1. The resulting state is B.

(a) Then the next move is of MIN. There are three possible moves for
MIN from B, namely, b1, b2, b3. The respective losses are 3, 12, and
8.

(b) Being rational, MIN tries to minimize his loss and co chooses b1
with a possible loss of 3. This results in a gain of 3 for MAX.
4. Suppose A chooses a2. The resulting state is C.

(a) Then the next move is of MIN. There are three possible moves for
MIN from B, namely, c1, c2, c3. The respective losses are 2, 4, 6.

(b) Being rational, MIN tries to minimize his loss and co chooses c1
with a possible loss of 2. This results in a gain of 2 for MAX.

5. Suppose A chooses a3. The resulting state is D.

(a) Then the next move is of MIN. There are three possible moves for
MIN from B, namely, d1, d2, d3. The respective losses are 14, 5, 2.

(b) Being rational, MIN tries to minimize his loss and co chooses d3
with a possible loss of 2. This results in a gain of 2 for MAX.

6. Now, if MAX chooses a1 the minimum gain is 3, if MAX chooses a2

the minimum gain is 2 and a3 is chosen the minimum gain is 2.

7. Hence to maximize the minimum gain, MAX chooses a1.

The solution can be stated as: “Initially, MAX chooses a1 and then MIN
chooses b1. This guarantees a minimum gain of 3 for MAX and a
maximum loss of 3 for MIN.”

Elements

S0: The initial state, which specifies how the game is set up at the
start.

PLAYER(s): Defines which player has the move in a state S.

ACTIONS(s): Returns the set of legal moves in the state S.

RESULT(s, a): The transition model, which defines the result of a

move in state S
 TERMINAL-TEST(s): A Boolean function of the state S. Its value is
true when the game is over and false otherwise. States where the
game has ended are called terminal states.

UTILITY(s; p): A utility function (also called an objective function or

payoff function), defines the final numeric value for a game that
ends in terminal state S for a player P.

S0 A
PLAYER(B) MIN
ACTIONS(B) {b1; b2; b3}
RESULT (C;c2) I
TERMINAL- False
TEST(B)
TERMINAL- True
TEST(K)
UTILITY(E;MIN) 3
The MINIMAX value

The minimax value at a state s, denoted by MINIMAX(s) is defined as

follows

UTILITY(s) if TERMINAL-
TEST(s)
max MINIMAX(RESULT(s; if PLAYER(s) =
MINIMAX(s) aACTIONS( a)) MAX
s)
=
min MINIMAX(RESULT(s; if PLAYER(s) =
aACTIONS( a)) MIN
s)

The MINIMAX algorithm

STEPS

MINIMAX-DECISION (A) = arg a ACTIONS (A) max MIN-VALUE (RESULT

(A, a)):

ACTIONS (A) = {a1, a2, a3}

RESULT (A, a1) =B,

RESULT (A, a2) =C

RESULT (A, a3) =C

MINIMAX-DECISION (A) = arg a ACTIONS (A) max {MIN-VALUE(B), MIN-

VALUE(C), MIN-VALUE(D)}
Next we compute MIN-VALUE (B). Since B is not a terminal state
and since ACTIONS (B) = {b1, b2, b3}, MIN-VALUE (B) is
computed as follows:

v ∞

v  MIN(v, MAX-VALUE(RESULT(B, b1))

v MIN(v, MAX-VALUE(RESULT(B, b2))

v  MIN(v, MAX-VALUE(RESULT(B, b3))

MIN-VALUE (B)  v.

v∞

We have to compute MAX-VALUE(RESULT(B,b1))=MAX-VALUE(E).

Since E is a terminal state it will return the utility value of

MAX-VALUE(RESULT(B, b1)=3

v  MIN(∞,3)

V3

We have to compute MAX-VALUE(RESULT(B,b2))=MAX-VALUE(F).

Since F is a terminal state it will return the utility value of MAX-
VALUE (RESULT(B, b2)=12

v  MIN(3,12)

V3

We have to compute MAX-VALUE(RESULT(B,b3))=MAX-VALUE(G).

Since F is a terminal state it will return the utility value of MAX-
VALUE(RESULT(B, b3)=8

v  MIN(3,8)

V3

Similarly calculate the MIN (MAX VALUES) of C and D, we get the

utility values 2, 2
 MINIMAX-DECISION(A) = max {MIN-VALUE(B), MIN-VALUE(C), MIN-
VALUE(D)}

MINIMAX-DECISION(A)= MAX(3, 2, 2) =3

Advantages

Complete- It will definitely find a solution (if exist), in the finite search
tree

Optimal- Minimax algorithm is optimal if both opponents are playing

optimally

Dis Advantage

It gets slow for games having huge branching factor

Consider the following problem in which the terminal nodes I, J have no

utility values. Then question arises is Do We Need to Compute All
MINIMAX Values?

X Y

Calculate MINIMAX (A)

Max (min(3, 12, 8), min(2,x,y) min(14,5,2))

Max (3, min(2,x,y), 2)

Max (3, min(2,x,y))

Max (3, <2) = 3

Minimax value at root node is not depended which is not known. In that
case, there is no need to check the nodes. This is known as pruning.

Principle for Pruning

Consider a node ‘n’ somewhere in a

tree, such that the player has a choice
of moving to that node If the player has
a better choice ‘m’ either at the parent
node ‘n’ or at any choice point further
up, then ‘n’ will never be reached in
actual play

Minimax with Alpha-Beta Pruning

Alpha ¸beta pruning is a search algorithm that seeks to decrease the

number of nodes that are evaluated by the MINIMAX algorithm in its
search tree. It stops evaluating a move when at least one possibility
has been found that proves the move to be worse than a previously
examined move. Such moves need not be evaluated further.

The algorithm maintains two values, α and β, which respectively

represent the minimum score that the maximizing player is assured of
and the maximum score that the minimizing player is assured of.
Initially we set α =-∞ and β = +∞. Whenever the maximum score that
the minimizing player is assured of becomes less than the minimum
score that the maximizing player is assured of, the maximizing player
need not consider further descendants of this node, as they will never
be reached in the actual play.

Algorithm

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

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

returns the action in ACTIONS (state) with value v

Function MAX-VALUE (state, ∞, β) return a utility value

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

v  -∞

For each a in ACTIONS (state) do

v  MAX (v, MIN-VALUE(RESULTS(s, a), ∞, β))

If v≥β then return v

∞ MAX (∞, v)

Return v

Function MIN-VALUE (state, ∞, β) return a utility value

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

v  +∞

For each a in ACTIONS (state) do

v  MIN (v, MAX-VALUE(RESULTS(s, a), ∞, β))

If v ≤ ∞ then return v

β MIN (∞, v)

Return v

Example: the following figure represents a game tree showing which

nodes can be pruned. Suppose the values of the leaf nodes are given
or are computed given the definition of the game. The numbers at the
bottom show some of these values. The other values are irrelevant

The value of node h is 7, because it is the minimum of 7 and 9.

Just by considering the leftmost child of i with a value of 6, we

know that the value of i is less than or equal to 6.

Therefore, at node d, the maximizing agent will go left. We do not

have to evaluate the other child of i.

Similarly, the value of j is 11, so the value of e is at least 11, and

so the minimizing agent at node b will choose to go left.

The value of l is less than or equal to 5, and the value of m is less

than or equal to 4; thus, the value of f is less than or equal to 5,
so the value of c will be less than or equal to 5.

So, at a, the maximizing agent will choose to go left.

Example: Consider the game tree shown below. We show below why
the leave c2 and c3 can be pruned without affecting the final decision.
The first leaf below B has the value 3. Hence, B, which is a MIN node,
has a value of at most 3.

The second leaf below B has a value of 12; MIN would avoid this move,
so the value of B is still at most 3.

The third leaf below B has a value of 8; we have seen all B’s successor
states, so the value of B is exactly 3. Now, we can infer that the value
of the root is at least 3, because MAX has a choice worth 3 at the root.

The first leaf below C has the value 2. Hence, C, which is a MIN node,
has a value of at most 2. But we know that B is worth 3, so MAX would
never choose C. Therefore, there is no point in looking at the other
successor states of C.

The first leaf below D has the value 14, so D is worth at most 14. This
is still higher than MAX’s best alternative (that is, 3), so we need to
keep exploring D’s successor states. Notice also that we now have
bounds on all of the successors of the root, so the root’s value is also
at most 14.

The second successor of D is worth 5, so again we need to keep

exploring. The third successor is worth 2, so now D is worth exactly 2.
MAX’s decision at the root is to move to B, giving a value of 3.
Additional Problems
 KNOWLEDGE REPRESENTATION

Knowledge is a familiarity, awareness, or understanding of someone or

something, such as facts, skills or objects. Knowledge can be acquired
in many different ways and from many sources including perception,
reason, memory, testimony, scientific inquiry, education, and practice.
The philosophical study of knowledge is called epistemology.

Different types of knowledge

1. Declarative knowledge

Declarative knowledge, also known as descriptive knowledge, is to

know about something such as concepts, facts, and objects. It is
expressed in declarative sentences.

2. Procedural knowledge

Procedural knowledge, also known as imperative knowledge, is a

type of knowledge which is responsible for knowing how to do
something. It can be directly applied to any task and it includes
rules, strategies, procedures, agendas, etc.

3. Meta-knowledge

Knowledge about the other types of knowledge is called meta-

knowledge.

4. Heuristic knowledge

Heuristic knowledge is knowledge of experts in a field or subject.

Heuristic knowledge is a “rule of thumb” knowledge based on
previous experiences, awareness of approaches, and which are good
to work but not guaranteed.

5. Structural knowledge

It describes relationships between various concepts such as kind of,

part of, and grouping of something. It describes the relationship that
exists between concepts or objects.
Knowledge Representation

It is a field of AI that focuses on designing computer representations

that capture information and knowledge about the world that can be
used to solve complex problems. It is not just storing data into some
database, but it also enables an intelligent machine to learn from that
knowledge and experiences so that it can behave intelligently like a
human. A knowledge representation structure is a particular set of
definitions, rules and procedures for setting up a representation that
captures information and knowledge about the world.

Knowledge Representation Systems

1. Semantic networks
2. Frames
3. Conceptual dependencies
4. System based on logic

Semantic networks

A semantic network is a graph constructed from a set of vertices (or

nodes) and a set of directed and labelled edges. The vertices or nodes
represent concepts or objects, and the edges represent relations
between the nodes.

Examples

1. Consider the knowledge contained in the following sentence: S:

“Sparrow is a bird.”

There are two concepts in the sentence, namely, “Sparrow” and “Bird”.
The relation between these concepts is indicated by “is a”. We
represent the two concepts by two nodes in a graph and the relation
between them by a directed edge with the label “is-a”.
 2. Consider the knowledge contained in the following sentences: S:
“Tweety is a bird.”, “Birds are animals.”

The sentences have three objects “Tweety”, “Birds” and”Animals”.

Tweety is the name of a particular bird. So the sentence “Tweety is a
bird” means that the bird Tweety is an instance of the class of things
indicated by the word “Birds”. The sentence “Birds are animals” means
that all members of the class of things indicated by”Birds” are also
members of the class of things indicated by “Animals”.

Or

3. Consider the sentence: S: “A bird has feathers.”

This sentence means that the object “Feather” is part of the object
“Bird”. In a semantic network representation of the sentence, the edge
joining the nodes is labelled “HAS-A” (or “HASA”, or “PART-OF”) such a
relation is referred to as a part-whole relation. The link or edge is from
whole to part.

4. Consider the sentence: S: “Sara has brown eyes.”

This sentence has three concepts “Sara”, “Brown” and “Eyes”.

“Brown” is a property of “Eyes” and, in a semantic representation of
the sentence; the property can be denoted by the label “Property” or
more specifically by the label “Colour”.
5. Consider the knowledge represented by the following sentences:

Tweety and Sweety are

birds.

Tweety has a red beak.

Sweety is Tweety’s child.

A crow is a bird.

Birds can fly.

Different kinds of semantic networks

1. Definitional networks

These emphasize the subtype relation between a concept type and a

newly defined subtype.

2. Assertional networks

Assertional semantic networks, also known as propositional semantic

networks are designed to represent assertions or propositions.

3. Implicational networks

These use implication as

the primary relation for
connecting nodes.

4. Executable networks
These include some mechanism which can perform inferences, pass
messages, or search for patterns and associations.

5. Learning networks

These build or extend their representations by acquiring knowledge

from examples.

6. Hybrid networks

These combine two or more of the previous techniques.

Intersection search
One of the earliest ways that semantic networks were used was to find
relationships between objects by spreading activation from each of two
nodes and seeing where the activations met. This process is called
intersection search.

Advantages

1. They give an adaptable method of representing knowledge

because many different types of object can be included in the
network.
2. The network is graphical and therefore relatively easy to
understand.
3. Can be used as a common communication tool between the
knowledge engineer and the human expert.
4. Efficient in space requirement.
5. Easily clusters related knowledge.

Disadvantages

1. There is no standard definition of link names.

2. Semantic networks are not intelligent, dependent on creator.
3. Links are not all alike in function or form.
4. Links on objects represent only binary options.
5. Undistinguished nodes that represent classes and that represent
individual objects.
6. Processing is inefficient for large networks.
7. Do not represent performances effectively.
8. It is difficult to express some properties using semantic networks,
like negation, disjunction, etc.
Frames

A frame is a collection of attributes and possible values that describe

some entity in the world. A frame system is a collection of frames that
are connected to each other by the fact that the value of an attribute
in one frame may be another frame.

Note:

1. The basic characteristic of a frame is that it represents related

knowledge about a narrow subject.
2. A frame system is a good choice for describing a mechanical
device, for example a car.
3. Just as with semantic nets, there are no standards for defining
frame-based systems.
4. A frame is analogous to a record structure, corresponding to the
fields and values of a record are the slots and slot fillers of a
frame.
5. A frame is basically a group of slots and fillers that defines a
stereotypical object.
6. A frame is also known as slot-filter knowledge representation in
artificial intelligence.

Frame structure

The frame contains information on how to use the frame, what to

expect next, and what to do when these expectations are not met.
Some information in the frame is generally unchanged while other
information, stored in “terminals”, usually change. Terminals can be
considered as variables. Top level frames carry information that is
always true about the problem in hand; however, terminals do not
have to be true. Their value might change with the new information
encountered. Different frames may share the same terminals.

Each piece of information about a particular frame is held in a slot. The

information can contain:
  Facts or data
o Values (called facets)
 Procedures (also called procedural attachments)
o IF-NEEDED: deferred evaluation
o IF-ADDED: updates linked information
 Default values
o For data
o For procedures
 Other frames or subframes

Examples

Frame for a BOOK

Frame for a CAR

Frame with name ALEX

The parent frame BOY of the frame named ALEX

Frame languages

A frame language is a technology used for knowledge representation in

artificial intelligence. The earliest Frame based languages were custom
developed for specific research projects and were not packaged as
tools to be re-used by other researchers. One of the first general
purpose frame languages was KRL (Knowledge Representation
Language). One of the most influential early Frame languages was KL-
ONE. KL-ONE spawned several subsequent Frame languages. One of
the most widely used successors to KL-ONE was the Loom language
developed by Robert MacGregor at the Information Sciences Institute.
Conceptual Dependency (CD)

Conceptual Dependency originally developed to represent knowledge

acquired from natural language input. It is developed by Roger Schank
and his teammates at Yale University in the 1970’s. It is a theory to
represent natural language sentences in such way that:

 It is independent of the language in which the sentences are

stated.
 It facilitates drawing inferences from sentences.

The goals of this theory are:

 To help in the drawing of inference from sentences.

 To be independent of the words used in the original input.
o That is to say: For any 2 (or more) sentences that are
identical in meaning there should be only one
representation of that meaning.

CD provides:

 A structure into which nodes representing information can be

placed
 A specific set of primitives
 At a given level of granularity.
 Sentences are represented as a series of diagrams depicting
actions using both abstract and real physical situations.
 The agent and the objects are represented
 The actions are built up from a set of primitive acts which can be
modified by tense.
Building blocks of conceptual dependency

 Primitives conceptual categories

 The primitive acts
 Conceptual tenses
 Indicators of dependencies (arrows)
 Symbols for conceptual cases
 States

Primitives Conceptual Categories

 PP -- Real world objects.

 ACT -- Real world actions.
 PA -- Attributes of objects.
 AA -- Attributes of actions.
 T -- Times.
 LOC -- Locations.

The Primitive Acts of CD

 ATRANS -- Transfer of an abstract relationship. Give.

 PTRANS -- Transfer of the physical location of an object. Go.
 PROPEL -- Application of a physical force to an object. Push.
 MTRANS -- Transfer of mental information. Tell.
 MBUILD -- Construct new information from old. Decide.
 SPEAK -- Utter a sound.
Say.
 ATTEND -- Focus a sense on a stimulus.
Listen, Watch.
  MOVE -- Movement of a body part by owner. Punch,
Kick.
 GRASP -- Actor grasping an object.
Clutch.
 INGEST -- Actor ingesting an object. Eat.
 EXPEL -- Actor getting rid of an object from body. Cry

Conceptual Tenses

 The use of tense and mood in describing events is extremely

important
 The absence of any modifier implies the present tense.

Indicators of dependencies (arrows)

Symbols for Conceptual Cases

States

States of objects are described by scales which have numerical values.

Examples
Rules