[Ex] L'Algorithme MinMax et le TicTacToe (morpion)
Posté : mar. 09 juin 2015 22:29
par mikell
Les explications sur l'algorithme sont (entre autres) sur le site developpez.com, et les calculs s'affichent dans l'Edit
Les détails sur l'évaluation du jeu sont commentés dans le code
L'algorithme Alpha-Beta
Cette variante de l'algorithme MinMax permet de limiter le nombre d'évaluations et donc d'accélérer le calcul
Les détails sur l'évaluation du jeu sont commentés dans le code
► Afficher le texte
Code : Tout sélectionner
#include <GUIConstantsEx.au3>
Global $jeu[3][3], $case[3][3][1], $cnt
;====================================================
$gui = GUICreate("L'ordi joue en 2ème", 360, 240, -1, 200)
GUISetBkColor(0x000000)
For $i = 0 To 2
For $j = 0 To 2
$case[$i][$j][0] = GUICtrlCreateButton("", $i*68+5, $j*68+5, 64, 64)
GUICtrlSetBkColor(-1, 0xffffff)
GUICtrlSetFont(-1, 32)
Next
Next
$list = GUICtrlCreateEdit("", 230, 5, 120, 200)
$r1 = GUICtrlCreateRadio("facile", 40, 210, 60, 20)
GUICtrlSetColor(-1, 0xffffff)
$r2 = GUICtrlCreateRadio("difficile", 110, 210, 60, 20)
GUICtrlSetColor(-1, 0xffffff)
GUICtrlCreateLabel("évaluations :", 230, 214, 60, 20)
GUICtrlSetColor(-1, 0xffffff)
GUICtrlSetBkColor(-1, 0x000000)
$label = GUICtrlCreateLabel("", 300, 212, 40, 17)
GUICtrlSetBkColor(-1, 0xffffff)
GUISetState()
While 1
If GUIGetMsg() = $GUI_EVENT_CLOSE Then Exit
If GUICtrlRead($r1) = 1 Then
$profondeur = 3
Exitloop
EndIf
If GUICtrlRead($r2) = 1 Then
$profondeur = 5
Exitloop
EndIf
Wend
While 1
$msg = GUIGetMsg()
If $msg = $GUI_EVENT_CLOSE Then Exit
For $i = 0 To 2
For $j = 0 To 2
;joueur
If $msg = $case[$i][$j][0] Then
GUICtrlSetData($case[$i][$j][0], "X")
GUICtrlSetState($case[$i][$j][0], $GUI_DISABLE)
$jeu[$i][$j] = 2
_check()
;ordi
$c = _jeu_IA($jeu, $profondeur)
GUICtrlSetData($label, $cnt)
$jeu[$c[0]][$c[1]] = 1
GUICtrlSetData($case[$c[0]][$c[1]][0], "O")
GUICtrlSetState($case[$c[0]][$c[1]][0], $GUI_DISABLE)
_check()
EndIf
Next
Next
Wend
;=============================================================
Func _jeu_IA($jeu, $profondeur)
Local $max = -10000, $tmp, $maxi, $maxj, $coords[2], $t
If $profondeur <> 0 or _gagnant($jeu) = 0 Then
$cnt = 0
For $i = 0 to 2
For $j = 0 to 2
If $jeu[$i][$j] = 0 Then
$jeu[$i][$j] = 1
$tmp = _Min($jeu, $profondeur-1)
If $tmp > $max Then
$max = $tmp
$maxi = $i
$maxj = $j
EndIf
$jeu[$i][$j] = 0
;debug
$t &= "(" & $i & "," & $j & ") > " & $tmp &" , "& $max &@crlf
GUICtrlSetData($list, $t)
EndIf
Next
Next
EndIf
;debug
$t &= @crlf& "choix (" & $maxi &","& $maxj &")"&@crlf
GUICtrlSetData($list, $t)
$coords[0] = $maxi
$coords[1] = $maxj
Return $coords
EndFunc
Func _Min($jeu, $profondeur)
If $profondeur = 0 or _gagnant($jeu) <> 0 Then Return _eval($jeu)
Local $min = 10000, $tmp
For $i = 0 to 2
For $j = 0 to 2
If $jeu[$i][$j] = 0 Then
$jeu[$i][$j] = 2
$tmp = _Max($jeu, $profondeur-1)
If $tmp < $min Then $min = $tmp
$jeu[$i][$j] = 0
EndIf
Next
Next
Return $min
EndFunc
Func _Max($jeu, $profondeur)
If $profondeur = 0 or _gagnant($jeu) <> 0 Then Return _eval($jeu)
Local $max = -10000, $tmp
For $i = 0 to 2
For $j = 0 to 2
If $jeu[$i][$j] = 0 Then
$jeu[$i][$j] = 1
$tmp = _Min($jeu, $profondeur-1)
If $tmp > $max Then $max = $tmp
$jeu[$i][$j] = 0
EndIf
Next
Next
Return $max
EndFunc
Func _eval($jeu)
$cnt += 1
Local $nb_de_pions = 0, $vainqueur = _gagnant($jeu)
;on compte le nombre de pions présents
For $i = 0 to 2
For $j = 0 to 2
If $jeu[$i][$j] <> 0 Then $nb_de_pions += 1
Next
Next
;s'il y a un gagnant :
If $vainqueur <> 0 Then
If $vainqueur = 1 Then
Return 1000 - $nb_de_pions
ElseIf $vainqueur = 2 Then
Return -1000 + $nb_de_pions
Else
Return 0
EndIf
EndIf
;sinon, on compte le nombre de séries de 2 pions alignés de chacun des joueurs
Local $series = _nb_series($jeu, 2)
Return $series[0] - $series[1]
EndFunc
Func _gagnant($jeu)
Local $series = _nb_series($jeu, 3)
If $series[0] > 0 Then
Return 1
ElseIf $series[1] > 0 Then
Return 2
Else ; si personne n'a gagné
;si le jeu n'est pas fini
For $i = 0 to 2
For $j = 0 to 2
If $jeu[$i][$j] = 0 Then Return 0
Next
Next
;si le jeu est fini
Return 3
EndIf
EndFunc
Func _check()
Local $win = _gagnant($jeu)
Switch $win
Case 1
Exit Msgbox(0,"" , "L'ordi a gagné")
Case 2
Exit Msgbox(0,"" , "Tu as gagné")
Case 3
Exit Msgbox(0,"" , "Match nul")
EndSwitch
EndFunc
Func _nb_series($jeu, $n)
;compte le nombre de séries de $n pions alignés de chacun des joueurs
Local $compteur1 = 0, $compteur2 = 0, $s_j1 = 0, $s_j2 = 0, $series[2]
;diagonale descendante
For $i = 0 to 2
If $jeu[$i][$i] = 1 Then
$compteur1 += 1
$compteur2 = 0
if $compteur1 = $n Then $s_j1 += 1
ElseIf $jeu[$i][$i] = 2 Then
$compteur2 += 1
$compteur1 = 0
if $compteur2 = $n Then $s_j2 += 1
EndIf
Next
;diagonale montante
$compteur1 = 0
$compteur2 = 0
For $i = 0 to 2
If $jeu[$i][2-$i] = 1 Then
$compteur1 += 1
$compteur2 = 0
if $compteur1 = $n Then $s_j1 += 1
ElseIf $jeu[$i][2-$i] = 2 Then
$compteur2 += 1
$compteur1 = 0
if $compteur2 = $n Then $s_j2 += 1
EndIf
Next
;lignes
For $i = 0 to 2
$compteur1 = 0
$compteur2 = 0
;horizontalement
For $j = 0 to 2
If $jeu[$i][$j] = 1 Then
$compteur1 += 1
$compteur2 = 0
if $compteur1 = $n Then $s_j1 += 1
ElseIf $jeu[$i][$j] = 2 Then
$compteur2 += 1
$compteur1 = 0
if $compteur2 = $n Then $s_j2 += 1
EndIf
Next
$compteur1 = 0
$compteur2 = 0
;verticalement
For $j = 0 to 2
If $jeu[$j][$i] = 1 Then
$compteur1 += 1
$compteur2 = 0
if $compteur1 = $n Then $s_j1 += 1
ElseIf $jeu[$j][$i] = 2 Then
$compteur2 += 1
$compteur1 = 0
if $compteur2 = $n Then $s_j2 += 1
EndIf
Next
Next
$series[0] = $s_j1
$series[1] = $s_j2
Return $series
EndFunc
Cette variante de l'algorithme MinMax permet de limiter le nombre d'évaluations et donc d'accélérer le calcul
► Afficher le texte
Code : Tout sélectionner
#include <GUIConstantsEx.au3>
Global $jeu[3][3], $case[3][3][1], $cnt
;====================================================
$gui = GUICreate("L'ordi joue en 2ème", 360, 240, -1, 200)
GUISetBkColor(0x000000)
For $i = 0 To 2
For $j = 0 To 2
$case[$i][$j][0] = GUICtrlCreateButton("", $i*68+5, $j*68+5, 64, 64)
GUICtrlSetBkColor(-1, 0xffffff)
GUICtrlSetFont(-1, 32)
Next
Next
$list = GUICtrlCreateEdit("", 230, 5, 120, 200)
$r1 = GUICtrlCreateRadio("facile", 40, 210, 60, 20)
GUICtrlSetColor(-1, 0xffffff)
$r2 = GUICtrlCreateRadio("difficile", 110, 210, 60, 20)
GUICtrlSetColor(-1, 0xffffff)
GUICtrlCreateLabel("évaluations :", 230, 214, 60, 20)
GUICtrlSetColor(-1, 0xffffff)
GUICtrlSetBkColor(-1, 0x000000)
$label = GUICtrlCreateLabel("", 300, 212, 40, 17)
GUICtrlSetBkColor(-1, 0xffffff)
GUISetState()
While 1
If GUIGetMsg() = $GUI_EVENT_CLOSE Then Exit
If GUICtrlRead($r1) = 1 Then
$profondeur = 3
Exitloop
EndIf
If GUICtrlRead($r2) = 1 Then
$profondeur = 5
Exitloop
EndIf
Wend
While 1
$msg = GUIGetMsg()
If $msg = $GUI_EVENT_CLOSE Then Exit
For $i = 0 To 2
For $j = 0 To 2
;joueur
If $msg = $case[$i][$j][0] Then
GUICtrlSetData($case[$i][$j][0], "X")
GUICtrlSetState($case[$i][$j][0], $GUI_DISABLE)
$jeu[$i][$j] = 2
_check()
;ordi
$c = _jeu_IA($jeu, $profondeur)
GUICtrlSetData($label, $cnt)
$jeu[$c[0]][$c[1]] = 1
GUICtrlSetData($case[$c[0]][$c[1]][0], "O")
GUICtrlSetState($case[$c[0]][$c[1]][0], $GUI_DISABLE)
_check()
EndIf
Next
Next
Wend
;=============================================================
Func _jeu_IA($jeu, $profondeur)
Local $alpha = -10000, $beta = 10000, $tmp, $maxi, $maxj, $coords[2], $t
If $profondeur <> 0 or _gagnant($jeu) = 0 Then
$cnt = 0
For $i = 0 to 2
For $j = 0 to 2
If $jeu[$i][$j] = 0 Then
$jeu[$i][$j] = 1
$tmp = _Min($jeu, $profondeur-1, $alpha, $beta)
If $alpha < $tmp Then
$alpha = $tmp
$maxi = $i
$maxj = $j
EndIf
$jeu[$i][$j] = 0
;debug
$t &= "(" & $i & "," & $j & ") > " & $beta &" , "& $alpha &@crlf
GUICtrlSetData($list, $t)
EndIf
Next
Next
EndIf
;debug
$t &= @crlf& "choix (" & $maxi &","& $maxj &")"&@crlf
GUICtrlSetData($list, $t)
$coords[0] = $maxi
$coords[1] = $maxj
Return $coords
EndFunc
Func _Min($jeu, $profondeur, $alpha, $beta)
If $profondeur = 0 or _gagnant($jeu) <> 0 Then Return _eval($jeu)
Local $tmp
For $i = 0 to 2
For $j = 0 to 2
If $jeu[$i][$j] = 0 Then
$jeu[$i][$j] = 2
$tmp = _Max($jeu, $profondeur-1, $alpha, $beta)
$jeu[$i][$j] = 0
If $beta > $tmp Then $beta = $tmp
If $beta <= $alpha Then Return $beta
EndIf
Next
Next
Return $beta
EndFunc
Func _Max($jeu, $profondeur, $alpha, $beta)
If $profondeur = 0 or _gagnant($jeu) <> 0 Then Return _eval($jeu)
Local $tmp
For $i = 0 to 2
For $j = 0 to 2
If $jeu[$i][$j] = 0 Then
$jeu[$i][$j] = 1
$tmp = _Min($jeu, $profondeur-1, $alpha, $beta)
$jeu[$i][$j] = 0
If $alpha < $tmp Then $alpha = $tmp
If $beta <= $alpha Then Return $alpha
EndIf
Next
Next
Return $alpha
EndFunc
Func _eval($jeu)
$cnt += 1
Local $nb_de_pions = 0, $vainqueur = _gagnant($jeu)
;on compte le nombre de pions présents
For $i = 0 to 2
For $j = 0 to 2
If $jeu[$i][$j] <> 0 Then $nb_de_pions += 1
Next
Next
;s'il y a un gagnant :
If $vainqueur <> 0 Then
If $vainqueur = 1 Then
Return 1000 - $nb_de_pions
ElseIf $vainqueur = 2 Then
Return -1000 + $nb_de_pions
Else
Return 0
EndIf
EndIf
;sinon, on compte le nombre de séries de 2 pions alignés de chacun des joueurs
Local $series = _nb_series($jeu, 2)
Return $series[0] - $series[1]
EndFunc
Func _gagnant($jeu)
Local $series = _nb_series($jeu, 3)
If $series[0] > 0 Then
Return 1
ElseIf $series[1] > 0 Then
Return 2
Else ; si personne n'a gagné
;si le jeu n'est pas fini
For $i = 0 to 2
For $j = 0 to 2
If $jeu[$i][$j] = 0 Then Return 0
Next
Next
;si le jeu est fini
Return 3
EndIf
EndFunc
Func _check()
Local $win = _gagnant($jeu)
Switch $win
Case 1
Exit Msgbox(0,"" , "L'ordi a gagné")
Case 2
Exit Msgbox(0,"" , "Tu as gagné")
Case 3
Exit Msgbox(0,"" , "Match nul")
EndSwitch
EndFunc
Func _nb_series($jeu, $n)
;compte le nombre de séries de $n pions alignés de chacun des joueurs
Local $compteur1 = 0, $compteur2 = 0, $s_j1 = 0, $s_j2 = 0, $series[2]
;diagonale descendante
For $i = 0 to 2
If $jeu[$i][$i] = 1 Then
$compteur1 += 1
$compteur2 = 0
if $compteur1 = $n Then $s_j1 += 1
ElseIf $jeu[$i][$i] = 2 Then
$compteur2 += 1
$compteur1 = 0
if $compteur2 = $n Then $s_j2 += 1
EndIf
Next
;diagonale montante
$compteur1 = 0
$compteur2 = 0
For $i = 0 to 2
If $jeu[$i][2-$i] = 1 Then
$compteur1 += 1
$compteur2 = 0
if $compteur1 = $n Then $s_j1 += 1
ElseIf $jeu[$i][2-$i] = 2 Then
$compteur2 += 1
$compteur1 = 0
if $compteur2 = $n Then $s_j2 += 1
EndIf
Next
;lignes
For $i = 0 to 2
$compteur1 = 0
$compteur2 = 0
;horizontalement
For $j = 0 to 2
If $jeu[$i][$j] = 1 Then
$compteur1 += 1
$compteur2 = 0
if $compteur1 = $n Then $s_j1 += 1
ElseIf $jeu[$i][$j] = 2 Then
$compteur2 += 1
$compteur1 = 0
if $compteur2 = $n Then $s_j2 += 1
EndIf
Next
$compteur1 = 0
$compteur2 = 0
;verticalement
For $j = 0 to 2
If $jeu[$j][$i] = 1 Then
$compteur1 += 1
$compteur2 = 0
if $compteur1 = $n Then $s_j1 += 1
ElseIf $jeu[$j][$i] = 2 Then
$compteur2 += 1
$compteur1 = 0
if $compteur2 = $n Then $s_j2 += 1
EndIf
Next
Next
$series[0] = $s_j1
$series[1] = $s_j2
Return $series
EndFunc