Introduction To Artificial Intelligence in Games

Introduction to
Artificial Intelligence in Games

Lecture 6
1
Game Playing Algorithms
• Game playing algorithms help us to find an optimum move to win the
game.
• In particular, the games that we will consider have the following
characteristics:
- Two players
- Zero-sum: one player wins and the other player loses
- Alternate move (turn): the players play in turns
- Deterministic: when the player wins and when he loses?
- Complete information about the game environment, game rules, and what
moves available to the other player
2
Minimax Algorithm
• Minimax is a recursive algorithm (search through the game-tree) that is
used in decision making and game theory to find the optimal move for a
player, assuming that your opponent also plays optimally. It is widely used
in two player turn-based games such as Tic-Tac-Toe, Chess, etc.
• In Minimax the two players are called maximizer (us) and minimizer (the
opponent).
• On our moves we are trying to maximize our score.
• When our opponent moves, however, we assume they will choose the
move that leaves us in the worst available position. Our opponent is trying
to minimize our score.
3
Minimax Algorithm
• The minimax algorithm performs a
depth-first search algorithm for the
exploration of the complete game
tree.
• The minimax algorithm proceeds
all the way down to the terminal
node of the tree, then backtrack
the tree as the recursion.
4
Minimax Algorithm
Example
• In this example, there are two players
one is called Maximizer and other is
called Minimizer.
• Maximizer will try to get the Maximum
possible score, and Minimizer will try
to give the minimum possible score.
• This algorithm applies DFS, so in this
game-tree, we have to go all the way
through the leaves to reach the
terminal nodes.
• At the terminal node, the terminal
values are given so we will compare
those values and backtrack the tree
until the initial state occurs. 5
Minimax Algorithm
Step 1:
• Starting from the bottom, the
maximizer selects the maximum
value from available options.
• For node D max(-1,4)= 4
• For Node E max(2, 6)= 6
• For Node F max(-3,-5) = -3
• For node G max(0, 7) = 7
6
Minimax Algorithm
Step 2:
• Now, it is a turn for minimizer, the
minimizer selects the minimum
value from available options.
• For node B min(4,6) = 4
• For node C min (-3, 7) = -3
7
Minimax Algorithm
Step 3:
• Now it's a turn for maximizer, and
it will again choose the maximum
of all nodes value and find the
maximum value for the root node.
• For node A max(4, -3)= 4
• Therefore, the best choice for the
first move for maximizer is to the
left, and the optimal value he get
is 4.
8
Minimax Algorithm
Another example
9
Minimax Algorithm
won
Example: Tic-Tac-Toe AI game
• For this scenario, let us consider X as
the maximizer and O as the minimizer.
• Let us assume the evaluation function
(score) as : Lose
- If X wins on the board, we give it a
positive value of +10.
- If O wins on the board, we give it a
negative value of -10. Draw
- If no one has won or the game results

in a draw, then we give a value of +0.
10
Minimax Algorithm
Example: Tic-Tac-Toe AI game
• The 3 possible scenarios in the above
example are :
• Left Move : If X plays [2,0]. Then O will play
[2,1] and win the game. The value of this
move is -10
• Middle Move : If X plays [2,1]. Then O will
play [2,2] which draws the game. The value
of this move is 0
• Right Move : If X plays [2,2]. Then he will
win the game. The value of this move is
+10;
• Remember, even though X has a possibility
of winning if he plays the middle move, O
will never let that happen and will choose to
draw instead.
• Therefore, the best choice for X, is to play
[2,2], which will guarantee a winning for him.
11
Minimax Algorithm
Example:
• What will the first move for Max to get
the optimal value?
• What is the optimal value he gets?
12
Minimax Algorithm
Example:
• What will the first move for Max to get the optimal value?
• What is the optimal value he gets?
13
14

Introduction To Artificial Intelligence in Games

Uploaded by

Copyright:

Available Formats

Introduction To Artificial Intelligence in Games

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Introduction To Artificial Intelligence in Games

Uploaded by

Copyright:

Available Formats

Introduction to

Artificial Intelligence in Games

- If no one has won or the game results

You might also like