# TD 5 -- Introduction a l'Intelligence Artificielle et à la Theorie des Jeux

###### tags `TD` `M1 S1` `IA`
[Sommaire](/8Sa-Z4QBS1ep0xPwtzigJA)
> [time= 23 oct 2020]

[TOC]

## Exercice 1 -- Découverte des algorithmes
### Enoncer

### réponse
#### 1) MinMax

Digraph MinMax {
    a [label="a - 8"]
    b [label="b - 8"]
    c [label="c - 4"]
    d [label="d - 5"]
    e [label="e - 8"]
    f [label="f - 8"]
    g [label="g - 7"]
    h [label="h - 4"]
    i [label="i - 5"]
    j [label="j - 8"]
    k [label="k - 5"]
    l [label="l - 4"]
    m [label="m - 8"]
    n [label="n - 8"]
    o [label="o - 3"]
    p [label="p - 7"]
    q [label="q - 9"]
    r [label="r - 4"]
    s [label="s - 1"]
    t [label="t - 0"]
    u [label="u - 5"]
    v [label="v - 7"]
    w [label="w - 8"]
    x [label="x - 1"]
    y [label="y - 5"]
    
    a -> {b; c; d}
    
    b -> {e, f}
    c -> {g, h, i}
    d -> {j, k}
    
    e -> {l, m}
    f -> {n, o}
    g -> {p, q}
    h -> {r, s}
    i -> {t, u}
    j -> {v, w}
    k -> {x, y}
}

### 2) alpha-beta

digraph alpha_beta {
    a [label="a - 8 
    (-inf, +inf)
    (8, +inf)"]
    b [label="b - 8
    (-inf, +inf)
    (-inf, 8)"]
    c [label="c - 4
    (8, +inf)
    (8, 9)"]
    d [label="d - 8
    (8, +inf)"]
    e [label="e - 8
    (-inf, +inf) 
    (4, +inf)"]
    f [label="f - 8
    (-inf, 8)"]
    g [label="g - 9  
    (8, +inf)"]
    h [label="h - 4  
    (8, 9)"]
    i [label="i -  "]
    j [label="j - 8
    (8, +inf)"]
    k [label="k -  "]
    l [label="l - 4 
    (-inf, +inf)"]
    m [label="m - 8
    (4, +inf)"]
    n [label="n - 8
    (-inf, 8)"]
    o [label="o - 3"]
    p [label="p - 7
    (8, +inf)"]
    q [label="q - 9
    (8, +inf)"]
    r [label="r - 4
    (8, 9)"]
    s [label="s - 1
    (8, 9)"]
    t [label="t - 0"]
    u [label="u - 5"]
    v [label="v - 7
    (8, +inf)"]
    w [label="w - 8
    (8, +inf)"]
    x [label="x - 1"]
    y [label="y - 5"]
    
    a -> {b; c; d}
    
    b -> {e, f}
    c -> {g, h}
    c -> i [style=dotted]
    d -> j
    d -> k [style=dotted]
    
    e -> {l, m}
    f -> {n}
    f -> o [style=dotted]
    g -> {p, q}
    h -> {r, s}
    i -> {t, u} [style=dotted]
    j -> {v, w}
    k -> {x, y} [style=dotted]
}

## Exercice 2 -- Variation autour du solitaire

### énoncé

### Réponse


## Exercice 3 alpha beta
### énoncé

### réponse

A = -inf (-inf, +inf)
B = +inf (-inf, +inf)
C = -inf (-inf, +inf)
a = 1 (-inf, +inf)
C = 1 (1, +inf)
b = 2 (-inf, +inf)
C = 2 (2, +inf)
B = 2 (-inf, 2)
D = -inf (-inf, 2)
c = 3 (-inf, 2)
# 'c' doit faire une coupe Beta dans 'D' donc v(c) > beta=2
D = 3 (-inf, 2)
B = 2 (-inf, 2)
A = 2 (2, +inf)
E = +inf (2, +inf)
F = -inf (2, +inf)
# e, f, g peut etre quelconque
e = 3 (2, +inf)
F = 3 (2, +inf)
f = 3 (2, +inf)
F = 3 (2, +inf)
g = 4 (2, +inf)
F = 4 (2, +inf)
E = 4 (2, 4)
G = -inf (2, 4)
h = 5 (2, 4)
# h doit etre superieur a 4 pour faire un élagage beta
G = 5 (2, 5)
E = 4 (2, 4)
A = 4 (4, +inf)
H = +inf (4, +inf)
I = -inf (4, +inf)
j = 2 (4, +inf)
# j, k, l <= 4 pour coupe alpha en H
I = 2 (4, +inf)
k = 3 (4, +inf)
I = 4 (4, +inf)
l = 4 (4, +inf)
I = 4 (3, +inf)
H = 4 (4, 6)
A = 4 (4, +inf)

donc:
- a = 1 (quelconque)
- b = 2 >= b
- c = 3 >= b
- d = >=c :cry:
- e = 3 (quelconque)
- f = 3 >= e
- g = 4 >= g
- h = 5 >= g >= b
- i = >=h :cry:
- j = 2 <= b
- k = 3 <= b
- l = 4 <= b
- m = :cry:
- n = :cry:
- o = :cry:
- p = :cry:
- q = :cry: