��

​

Eng. Suleiman Sead Ibrahim

Artificial Intelligence

Chapter 6�Game playing in AI

• Chapter outline
• An introduction
• Environment type discussed in this chapter
• Zero-Sum Game
• Game trees
• Evaluation Functions
• The Minimax algorithm

​

​

​

An introduction

• Game-playing systems tend to rely heavily on the search techniques described in Chapters 4 and 5, in combination with a number of heuristics and often a detailed database of knowledge about the game.
• This chapter explains the relationship between search and games such as tic-tac toe, and It explains the concepts of minimax algorithms

Environment type discussed in this chapter

Fully-Observalbe

Multi-agent environment

Deterministic

Zero-Sum Game

• In Zero-sum game each agent's gain or loss of utility is exactly balanced by the losses or gains of utility of another agent.
• One player of the game try to maximize one single value, while other player tries to minimize it.
• Each move by one player in the game is called as ply.
• Chess and tic-tac-toe are examples of a Zero-sum game.
• Most of the games we will consider in this chapter are zero-sum games.

​

Game trees

• A game tree is an instance of a tree in which the root node initial state and the nodes in the tree represent possible states of the game (or positions), and arcs in the tree represent moves.
• Leaf nodes in the tree represent final states, where the game has been won, lost, or drawn

​

​

A partial game tree for the game tic-tac-toe

A game can be formally defined with the following elements:

• S0: the initial state, which specifies how the game is set up at the start.
• Moves(s): the player whose turn it is to move in state s.
• Actions(s): the set of legal moves in state s.
• Result(s, a): the transition model, which defines the state resulting from taking action a in state s.
• Is-terminal(s): a terminal test, which is true when the game is over and false terminal test otherwise.
• Utility(s, p) which defines the final numeric value to player p when the game ends in terminal state s.

A (partial) game tree for the game of tic-tac-toe.

Evaluation Functions

• A static evaluation function (that measure the goodness of a move) is used to determine the value of a given move from a given game state.
• The static evaluation function is defined as the number of possible win positions not blocked by the opponent minus the number of possible win positions for the opponent not blocked by the current player.

​

​

​

Consider this partial game tree

Cont.…

• Using this evaluation function, we identify the goodness of the board configuration given a move for X in Figure 4.2.
• The higher the result of the static evaluation function, the closer the move brings the player toward a win.
• Three moves result in the evaluation function equaling three, but only one move can lead to a win for X as the other two lead to a subsequent win for O

The Minimax algorithm

• The Minimax algorithm can search the game trees to determine the best move to make from the current state.
• The minimax algorithm is a useful method for simple two-player games
• It’s used In decision-making and game theory, the mini-max algorithm is a recursive or backtracking method.

Working of Minimax Algorithm

• There are two players in this scenario, one named Maximizer and the other named Minimizer.
• Maximizer will strive for the highest possible score, while Minimizer will strive for the lowest possible score.
• Because this algorithm uses DFS, we must go all the way through the leaves to reach the terminal nodes in this game-tree.
• The terminal values are given at the terminal node, so we'll compare them and retrace the tree till we reach the original state

​

Step 1

Step 2

Step 3

Step 4

An implementation of Minimax algorithm

Properties of Mini-Max algorithm

• Complete
• The Min-Max algorithm is finished. In the finite search tree, it will undoubtedly locate a solution (if one exists).
• Optimal
• If both opponents are playing optimally, the Min-Max algorithm is optimal.
• Time complexity
• Because it executes DFS for the game-tree, the time complexity of the Min-Max algorithm is O(b^m), where b is the game-branching tree's factor and m is the tree's maximum depth.

​

Limitation of the minimax Algorithm

• The biggest disadvantage of the minimax algorithm is that it becomes extremely slow while playing complex games like chess or go.
• This style of game contains a lot of branching, and the player has a lot of options to choose from.
• The minimax algorithm's drawback can be alleviated by using alpha-beta pruning , which we will explore in the next section. the depth to which the tree can grow.

​

Thank you