# AI - lesson 07
#### Francesco Arrigoni
###### 4 November 2015
## Adversarial search
Is usually employed in situations called *games*, in which there are multiple agents that interact together in a __strategic way__  
For example in the game of chess we play against another player, and so our moves can be represented by a tree

There are different kind of games:
- __Perfect information__ games: we completely know the status of the game
- __Imperfect information__ games:

Another distinction is:
- __Deterministic__ games: There are no randomness factors
- __Chance__ games: there are elements of chance for example rolling dices or drawing cards.

#### examples
- An example of perfect information and deterministic game is chess,
- An imperfect and deterministic game is battleship
- A perfect information based on chance is backgammon, or gioco dell'oca, or Monopoly
- An imperfect information and chance game is poker or cards games.

For this time will focus of __Perfect information__ and __deterministic__ games like chess.

- We have two players: Max and Min,  
- They are playing in turns,
- Max will play first

An __initial state__ is an initial configuration of the game.

### Tic Tac Toe

Max: X
Min: O

Initial state:

||
---|---|---
||
||

We can define a __function "player(s)" that given a state will return which is the next player
- $\text{PLAYER}(s)\in \{max,min\}$
- $\text{ACTIONS}(s)= \{a_1,a_2,...\}$
- $\text{RESULT}(s,a)=s'$
- $\text{TERMINAL-TEST}(s)=\{yes,no\}$

Next we define a utility function
- $\text{UTLITY}(s,p)\in R$

We consider __zero-based__ games, in which the utility of the two players in a final state are always summing up to zero
$\text{UTILITY}(s,\text{MAX})+\text{UTILITY}(s,\text{MIN})=0$

For example
X|O|O
---|---|---
|X|
||
$\text{RESULT}$Will give __no__ as a result

While
X|O|O
---|---|---
|X|
||X

$\text{RESULT}$Will give __yes__ as a result
While $\text{UTILITY(s,MAX}$Will give -1 as a result
And  $\text{UTILITY(s,MIN}$Will give +1 as a result

### minimax

Is an algorithm for solving __game trees__
- The root is called "MAX" node because t corresponds to MAX's turn  
- All children of MAX are called MIN nodes for the same reason  
- The third row contains the __terminal nodes__, and the number associated to every node is the utility for max to be in that node.

The minimax algorithm is based on the idea of a __minimax value__ for each node, that represents:
> The utility for max of being in (reaching) that node assuming that the other players will play optimally from that node to the end of the game

The general rule for calculating the minimax value is the following:  
- The minimax value of a __terminal node__ is the utility of MAX
- The minimax value of a __MIN node__ is the minimum of the minimax value of the children
- The minimax value of a __MAX node__ is the maximum of the minimax value of the children

#### The minimax algorithm
- Build all the game tree
- Starting from the bottom we have to back-up the minimax value to the upper nodes.
- Knowing the minimax value of all the children of a node, we can calculate the value of a node.

The minimax value can be __minimized__ building a tree in a *depth first* fashion.

The problem of a possible *cutoff strategy* is that not completing the tree, we don't have terminal nodes, and i need an __evaluation function__

#### Cutoff strategy

Usually in chess or checkers i can cut-off the tree at a given level, but i can not do so at a random level

An option is implementing a __quiescence evaluation function__ that tells us if a certain level is stable,
otherwise we continue