# AI - lesson 08
#### 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.