# Cour 6 -- Introduction a l'Intelligence Artificielle et à la Theorie des Jeux

###### tags `cour` `M1 S1` `IA`
[Somaire](/8Sa-Z4QBS1ep0xPwtzigJA)\
[Precedent](/Lj3NskXUTea7kl21sp3EmQ)
> [time= 16 oct 2020] et [time= 23 oct 2020]

[TOC]

## Environnement non déterministe / adversarial
- Une action n'a pas un effet unique
- Dû à l'environnement qui peut agir de manère imprévisible
- on peut voir ca comme un jeu entre l'agent et l'environnement
- l'agent choisit une action, l'environnement choisit l'état successeur
- l'agent veux atteindre le but quelque soit le comportement de l'environnement

La solution n'est donc pas une séquence d'action.\
C'est un "plan", une "stratégie"


- () : agent joue
- noir: etat but (on a gagné)
- blanc: etat ou on continue (on a pas gagné)
- \[] : environnement joue


## recherche or and


- Similaire au parcours en profondeur, version récursive
- On distingue les sommets AND (adversaire) et les sommets OR (l’agent)
- On doit marquer les états traités, mais pour des raisons d’efficacité, on ne prend en compte que les états sur le chemin de l’état initial à l’état courant
- Si on retombe sur un état déjà vu au dessus, on considère que c’est une feuille 0 (car si une possibilité de succès existe, on le trouvera sur une branche alternative à partir de l’occurrence précédente)
- Le plan est construit récursivement à partir des plans pour les descendants

def and_or_graph_search(problem):
    """
    return:
        a conditional plan or failure
    """
    return or_search(problem.initial_state, problem, [])
    
def or_search(state, problem, path):
    """
    state: 
        etat a explorer
    problem:
        graph du probleme
    path:
        list des etat empreinté pour arrivé a cette état
        
    return:
        a conditional plan or failure
    """
    if problem.goal_test(state):
        return EMPTY_PLAN
        
    elif state in path:
        return FAILURE
        
    for action in problem.actions(state):
        plan = and_search(results(state, action), problem, [state] + path )
        if plan != FAILURE:
            return {action: plan}
    return FAILURE
    
def and_search(states, problem, path):
    """
    state: 
        etat a explorer
    problem:
        graph du probleme
    path:
        list des etat empreinté pour arrivé a cette état
        
    return:
        a conditional plan or failure
    """
    plan = {}
    for s in states:
        p = or_search(s, problem, path)
        if p != failure:
            return FAILURE
        plan[s] = p
    return plan
        

Ces probleme sont des **jeux a somme 0 et information parfaite**
- 2 joueur
- MIN
- MAX
- ce qu'un joueur gagne l'autre perd:
- on a $u_{max} + u_{min} = 0$

si *o* le résultat de jeu et $u_{MAX}$ et $u_{MIN}$ les fonctions de paiement (les fonction d'utilité) de deux joueur alors:
$$
u_{MIN}(o) + u_{MAX}(o) = 0
$$
pour chaque o.


### Description d'un jeu
- **s~0~** l'état initial
- **PLAYER(s)** le joueur
- **ACTIONS(s)** l'ensemble d'actions disponibles dans l'état *s*
- **RESULTAT(s,a)** transition, l'état obtenu si on exécute l'action dans *s*
- **TERMINAL(s)** test booléen pour déterminer si s est un état final
- **UTILITE(s)** la fonction d'utilité définie pour chaque état final *s*.

On suppose que *UTILITE* est la fonction d'utilité pour le joueur *MAX*, changeant le signe on obtient l'utilité pour le joueur *MIN*.

### Dificulté de jeux
Grand nombre d'états : jeu d'échec :
* facteur de branchement (en moyenne) *35*
* nombre de coup par joueur *50*
* l'arbre de jeu *35^100^* de noeuds

## MinMax

def MinMaxDecision(s: Etat):
"""
    return:
        action a effectué
"""
   if Player(s) == MAX: 
        return max(MinMax(Resultat(s,a) for a in Actions(s))
   else
        return min(MinMax(Resultat(s,a) for a in Actions(s))
        
def MinMax(s: Etat):
"""
    return:
        valeur
"""
    if Terminal(s):
       return Utilite(s)
       
    elif Player(s) == MAX:
        v = -INFINITY
        for a in Actions(s):
            v = max(v, MinMax(Resultat(s,a)))
    else:
        v = +INFINITY
        for a in Actions(s):
            v = min(v, MinMax(Resultat(s,a)))
    return v

### Propriété
- complet
- oui (si arbre fini)
- optimal
- oui (si arbre fini et adversaire optimal)
- compléxité en temps
- $O(b^{m})$
- compléxité en espace
- $O(b \times m)$

## Elagage alpha beta

- Elagage n'affecte pas le résultat
- L'**ordre de visite de enfants est important** et influence la complexité (qui dépend de la taille de parties élaguées).
- Avec l'ordre de visite optimal la complexité en temps passe de $O(b^m)$ à O(b^{m / 2}), donc on peut doubler la hauteur de l'arbre visité.

### Le rôle de paramètres alpha-beta
- $\alpha$ Max possède une stratégie qui lui garantie au moins $\alpha$
- $\beta$ Min possède une stratégie qui lui garantie de ne perdre au plus $\beta$


### Joueur Min

### Algorithme

def alpha_beta_search(state):
"""
    return action
"""
    v = max_value(state, -INFINITY, +INFINITY)
    return action.with(v)

def max_value(state, alpha, beta):
"""
    return:
    utility value
"""
    if terminal_test(state):
        return utility(state)
    v = -INFINITY
    for a in actions(state):
        v = max(v, min_value(result(s, a), alfa, beta))
        if v >= beta:
            return v
        alpha = max(alpha, v)
    return v

def min_value(state, alpha, beta):
"""
    return:
    utility value
"""
    if terminal_test(state):
        return utility(state)
    v = +INFINITY
    for a in actions(state):
        v = min(v, max_value(result(s, a), alfa, beta))
        if v <= alpha:
            return v
        alpha = min(beta, v)
    return v


### fonction d'évaluation
Si la profondeur de l'arbre trop grande on coupe à un niveau d et on applique une heuristique pour évaluer les positions à ce niveau (une estimation de valeur de sommets).

La plupart de fonctions d'évaluation utilisent un certain nombre de propriétés (features) et ensuite on applique une somme pondérée pour évaluer la position:
$$
Eval(s) = w_1 f_1(s) + \cdots + w_n f_n(s)
$$

par exemple:
- w1=9
- f1(s)=le nombre de reines blanches-le nombre de reines noires

[suivant](/SsELiBJQSIuFPBUHO90pYw)