Friday, September 28, 2018

Mini Max Search Procedure.

  • The Min-Max algorithm evaluates decision-based on the current situation of the game.
  • This algorithm needs a deterministic environment with exact information.
  • Min-Max algorithm directly implements the defining equation.
  • Every time based on the successor state min-max value is calculated using simple recursive computation.
  • Algorithm:
1)Create the entire game tree including all the terminal states.
2)For every terminal state, find out utility. This means that 1 means win and 0 means draw.
3)Apply min and max operators on the nodes of the current stage and propagate the utility value upward in the tree.
4)With the max utility value, select the action at root node using min-max decision.
  • Example,
First iteration Procedure:
Min= inf
Min(inf,10)=10
Min(10,11)=10
Min=inf
Min(inf,9)=9
Min(9,11)=9
.
.

Second iteration Procedure:
Max=-inf
Max(-inf,10)=10
Max(10,9)=10
Max=-inf
Max(-inf,14)=14
Max(14,13)=14
.
.

Again Min Procedure:
Min=inf
Min(inf,10)=10
Min(10,14)=10
.
.

.
If we keep going, the final answer will be 10.

No comments:

Post a Comment