lesson_07.md 2.3 KB
AI - lesson 07
Francesco Arrigoni
6 November 2015
Adversarial games
$\alpha - \beta pruning$
Iteration
- We start from the root, that will be labeled after the starting player.
- From the root the first set of arcs representing actions is called a1,a2,a3...
- The arcs starting from a 2nd level node are named b1,b2,b3...
- For a MIN node (e.g 2nd level) we not necessarily know the minimax value, but we can tell it is lower than the values of the known children (minimum value)
- We can have an hint about the minimax value of the root only when we have at least one branch completely built
- After we have found the minimax value of a node, we can remove from memory his children. I do not need to generate the complete tree of a node if MAX has already found a node of higher value
The order of the nodes determines which nodes are discovered or not
Complexity
Using the most efficient $\alpha - \beta pruning$ We have a time complexity of $O(b^{m/2})$ With respect of classic minimax $O(b^n)$
This means that with $\alpha - \beta pruning$ we can obtain a tree with double the depth comparing to minimax
Meaning of the name
In the first public version of this algorithm, the current best option for MAX was called $\alpha$
In a dual way $\beta$ was the value of the current best option for MIN.
General case
In a general case, known a MAX node value $\alpha$, while discovering MAX nodes of lower levels, all children with value higher than $\alpha$ are pruned.
We can repeat the same reasoning for MIN and $\beta$
$\alpha$ and $\beta$ are not the extremens of a node interval.
Games with chance
For this games certain authors say that there are three players: MAX,MIN and Nature, but this is misleading.
Expectiminimax algorithm
We have a similar tree to the minimax one, With chance nodes with probability on the descending arcs.
The procedure of calculating and backing up the minimax values for the normal nodes is the same as minimax.
Alternative strategy
We know that our utility function from design will return values in a given interval e.g $[-2,2]$
From this we know that for every node, the minimax value will be between $[-2,2]$
Expectiminimax is dependent on the actual values of the utility function, while in standard minimax it does not mattes.