ITT63 ARTIFICIAL INTELLIGENCE UNIT V
Academic Year 2015-2016(EVEN SEM)
Advanced Topics: Game Playing: Minimax search procedure - Adding alpha-beta cutoffs.
Expert System: Representation - Expert System shells - Knowledge Acquisition.
Robotics: Hardware - Robotic Perception – Planning - Application domains.
Swarm Intelligent Systems – Ant Colony System, Development, Application and Working of
Ant Colony System.
---------------------------------------------------------------------------------------------------
Advanced Topics: Game Playing
The domain game playing?
The term Game means a sort of conflict in which n individuals or groups (known as
players) participate.
Game theory denotes games of strategy.
John von Neumann is acknowledged as father of game theory. Neumann defined Game
theory in 1928 and 1937 and established the mathematical framework for all subsequent
theoretical developments.
Game theory allows decision-makers (players) to cope with other decision-makers
(players) who have different purposes in mind. In other words, players determine their
own strategies in terms of the strategies and goals of their opponent. Games are integral
attribute of human beings.
Games engage the intellectual faculties of humans.
If computers are to mimic people they should be able to play games.
1.1 Definition of Game
A game has at least two players.
Solitaire is not considered a game by game theory.
The term 'solitaire' is used for single-player games of concentration.
An instance of a game begins with a player choosing from a set of specified (game rules)
alternatives. This choice is called a move.
III YR /VI SEM Page 1
,ITT63 ARTIFICIAL INTELLIGENCE UNIT V
After first move, the new situation determines which player to make next move and
alternatives available to that player.
o In many board games, the next move is by other player.
o In many multi-player card games, the player making next move depends on who
dealt, who took last trick, won last hand, etc.
Minimax - The least good of all good outcomes.
Maximin - The least bad of all bad outcomes.
The primary game theory is the Mini-Max Theorem. This theorem says :
"If a Minimax of one player corresponds to a Maximin of the other player, then that
outcome is the best both players can hope for."
The Mini-Max Search Procedure
Consider two players, zero sum, non-random, perfect knowledge games.
Examples: Tic-Tac-Toe, Checkers, Chess, Go, Nim, and Othello.
2.1 Formalizing Game
A general and a Tic-Tac-Toe game in particular.
Consider 2-Person, Zero-Sum, Perfect Information
Both players have access to complete information about the state of the game.
No information is hidden from either player.
III YR /VI SEM Page 2
, ITT63 ARTIFICIAL INTELLIGENCE UNIT V
Players alternately move.
Apply Iterative methods
Required because search space may be large for the games to search for a solution.
Do search before each move to select the next best move.
Adversary Methods
Required because alternate moves are made by an opponent , who is trying to win, are not
controllable.
Static Evaluation Function f(n)
‡ Used to evaluate the "goodness" of a configuration of the game.
It estimates board quality leading to win for one player.
Example: Let the board associated with node n then
If f(n) = large +ve value means the board is good for me and bad for opponent.
If f(n) = large -ve value means the board is bad for me and good for opponent.
If f(n) near 0 Means the board is a neutral position.
If f(n) = +infinity means a winning position for me.
If f(n) = -infinity means a winning position for opponent.
2. Explain Minimax search procedure - Adding alpha-beta cutoffs in Game Playing
Games hold an inexplicable fascination for many people, and the notion that computers might
play games has existed at least as long as computers.
Charles Babbage the nineteenth century computer architect, thought about programming his
analytical engine to play chess and later of building a machine to play tic tac toe.
Two of the pioneers of the science of information and computing contributed to the fledgling
computer game playing literature.
Claude Shannon [1950] wrote a paper in which he described mechanisms that could be used in a
program to play chess.
A few years later, Alan Turing described a chess playing program, although he never built it.
III YR /VI SEM Page 3
Academic Year 2015-2016(EVEN SEM)
Advanced Topics: Game Playing: Minimax search procedure - Adding alpha-beta cutoffs.
Expert System: Representation - Expert System shells - Knowledge Acquisition.
Robotics: Hardware - Robotic Perception – Planning - Application domains.
Swarm Intelligent Systems – Ant Colony System, Development, Application and Working of
Ant Colony System.
---------------------------------------------------------------------------------------------------
Advanced Topics: Game Playing
The domain game playing?
The term Game means a sort of conflict in which n individuals or groups (known as
players) participate.
Game theory denotes games of strategy.
John von Neumann is acknowledged as father of game theory. Neumann defined Game
theory in 1928 and 1937 and established the mathematical framework for all subsequent
theoretical developments.
Game theory allows decision-makers (players) to cope with other decision-makers
(players) who have different purposes in mind. In other words, players determine their
own strategies in terms of the strategies and goals of their opponent. Games are integral
attribute of human beings.
Games engage the intellectual faculties of humans.
If computers are to mimic people they should be able to play games.
1.1 Definition of Game
A game has at least two players.
Solitaire is not considered a game by game theory.
The term 'solitaire' is used for single-player games of concentration.
An instance of a game begins with a player choosing from a set of specified (game rules)
alternatives. This choice is called a move.
III YR /VI SEM Page 1
,ITT63 ARTIFICIAL INTELLIGENCE UNIT V
After first move, the new situation determines which player to make next move and
alternatives available to that player.
o In many board games, the next move is by other player.
o In many multi-player card games, the player making next move depends on who
dealt, who took last trick, won last hand, etc.
Minimax - The least good of all good outcomes.
Maximin - The least bad of all bad outcomes.
The primary game theory is the Mini-Max Theorem. This theorem says :
"If a Minimax of one player corresponds to a Maximin of the other player, then that
outcome is the best both players can hope for."
The Mini-Max Search Procedure
Consider two players, zero sum, non-random, perfect knowledge games.
Examples: Tic-Tac-Toe, Checkers, Chess, Go, Nim, and Othello.
2.1 Formalizing Game
A general and a Tic-Tac-Toe game in particular.
Consider 2-Person, Zero-Sum, Perfect Information
Both players have access to complete information about the state of the game.
No information is hidden from either player.
III YR /VI SEM Page 2
, ITT63 ARTIFICIAL INTELLIGENCE UNIT V
Players alternately move.
Apply Iterative methods
Required because search space may be large for the games to search for a solution.
Do search before each move to select the next best move.
Adversary Methods
Required because alternate moves are made by an opponent , who is trying to win, are not
controllable.
Static Evaluation Function f(n)
‡ Used to evaluate the "goodness" of a configuration of the game.
It estimates board quality leading to win for one player.
Example: Let the board associated with node n then
If f(n) = large +ve value means the board is good for me and bad for opponent.
If f(n) = large -ve value means the board is bad for me and good for opponent.
If f(n) near 0 Means the board is a neutral position.
If f(n) = +infinity means a winning position for me.
If f(n) = -infinity means a winning position for opponent.
2. Explain Minimax search procedure - Adding alpha-beta cutoffs in Game Playing
Games hold an inexplicable fascination for many people, and the notion that computers might
play games has existed at least as long as computers.
Charles Babbage the nineteenth century computer architect, thought about programming his
analytical engine to play chess and later of building a machine to play tic tac toe.
Two of the pioneers of the science of information and computing contributed to the fledgling
computer game playing literature.
Claude Shannon [1950] wrote a paper in which he described mechanisms that could be used in a
program to play chess.
A few years later, Alan Turing described a chess playing program, although he never built it.
III YR /VI SEM Page 3
