Next
2.6
Minimax (cont.)
Prev
Minimax (cont.)
Minimax algorithm:
is
complete
if tree is complete (chess has specific rules for this, but finite strategy can exist even in an infinitive tree)
is
optimal
against optimal opponent (again, if tree is complete)
depth-first exploration takes O(
b
m
)
time
, or O(
b
m
/2
) with alpha-beta pruning
depth-first exploration takes O(
b
m
)
space
Next
Artificial Intelligence and Perl
Prev