Expectiminimax

Game of Chances

Computer over the years have become truly smart. Thought this smartness is not of their own but the ine we have programmed in them. Feeding them millions of combinations, Gigabytes of Data, they have developed to the point where they are now able to beat humans in many games. Beating humans in game s like chess or tic-tac-toe can be seen as type of search problem in which the machine searches for the best possible move from the finite set of many possible moves. But what about games where there is a factor of chance e.g. backgammon. How can a machine take into the factor of chance when we humans donnot how to take that into account. Well here we teach the machine expected value, the machine guess the expected value from the present state and decides it moves accordingly. This algorithm is called Minimax. and is illustrated below as follows.

Minimax algorithm applied in situations with an unpredictability by including a random chance element. The minimax search tree now contains chance nodes at each decision level which stores the expected value of the children nodes.

Provide the leafs nodes for the tree to see how the algorithm will solve different problems.
Provide the probabilities for the tree branches to see how the algorithm will solve different problems.

Provide the probabilities for the tree branches to see how the algorithm will solve different problems. The darker branches are where chances are evaluated. The value of the chance is the expected value of its child nodes calculated on the bases of the input probabilities.
Start Simulation