·
The min-max algorithm
computes the minimax
decision from the current state.
·
It is used as a searching technique in game problems.
·
It performs a complete DFS of the game tree.
·
Given a game
tree, the optimal
strategy can be determined by examining the minimax
value of each node.
·
The minimax value of a node is the utility of being in
the corresponding state, assuming that both players play optimally from this stage
to the end of the game.
·
The minimax value of a terminal state is just its utility.
·
Given a choice,
MAX will prefer to move to a state of maximum value,
whereas MIN prefers a state of
minimum value.
Algorithm:
1.
The start node is MAX (Player 1) node, with current board
configuration.
2.
Expand nodes down (Play) to some depth of look-ahead in the game.
3.
Apply evaluation function
at each of the leaf nodes.
1.
Back up values
for each non-leaf
nodes until computed
for the root node.
2.
At MIN (Player
2) node, the
backed up value
is the minimum
of the values associated
with its children.
3.
At MAX node, the backed
up value is the maximum
of the values associated with its
children.
Performance
evaluation:
·
Completeness: It is considered to be complete
if the game tree is of finite
size
·
Optimality:
It is considered optimal when it is played against an optimal no. of
opponents.
·
Time and space complexity: The time complexity is O (bm), and space complexity is O (bm).
No comments:
Post a Comment