Dans un premier temps, l’objectif est de mettre au point une intelligence artificielle (IA) la meilleure possible pour jouer à Puissance 4, sans avoir à descendre en profondeur dans un arbre comme avec l’algorithme minimax ou alpha-bêta. Viendra ensuite le temps des arbres, puis de l’apprentissage…
Présentation des IA :
Codage de la stratégie :
H veut dire Hasard
P veut dire Poids des cases (il y a plus de possibilités d’alignements pour certaines cases)
AX veut dire Alignement de X pions (l’IA essaye d’aligner X pions ; les alignements « troués » de 2 ou 3 pions ne sont pas encore pris en compte)
BX veut dire Blocage de X pions (l’IA essaye d’empêcher l’adversaire d’aligner X pions ; les alignements « troués » de 2 ou 3 pions ne sont pas encore pris en compte)
IA0 : Priorité H
IA1 : Priorité P
IA2 : Priorités A4P / A3P / A2P / P
IA3 : Priorités B4P / B3P / B2P / P
IA4 : Priorités A4P / B4P / A3P / B3P / A2P / B2P / P
IA5 : Priorités A4P / B4P / A3P / B3P / B2P / A2P / P
IA6 : Priorités A4P / B4P / B3P / A3P / A2P / B2P / P
IA7 : Priorités A4P / B4P / B3P / A3P / B2P / A2P / P
IA8 : Priorités A4P / B4P / A2P / B2P / P
IA9 : Priorités A4P / B4P / B2P / A2P / P
Présentation des résultats :
Sur 1 million de parties (ou 10 000 pour des mécaniques répétitives bien que 2 suffiraient), les résultats bruts sont :
IA0 / IA0 / Nulles : 498 180 / 499 269 / 2 551
IA1 / IA0 / Nulles : 878 082 / 121 899 / 19
IA2 / IA0 / Nulles : 971 125 / 28 874 / 1
IA3 / IA0 / Nulles : 962 081 / 26 922 / 10 997
IA4 / IA0 / Nulles : 987 349 / 12 637 / 14
IA5 / IA0 / Nulles : 984 923 / 14 995 / 82
IA6 / IA0 / Nulles : 989 355 / 10 538 / 107
IA7 / IA0 / Nulles : 986 549 / 13 043 / 408
IA8 / IA0 / Nulles : 971 554 / 28 431 / 15
IA9 / IA0 / Nulles : 948 080 / 51 821 / 99
IA1 / IA1 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne en 10 coups)
IA2 / IA1 / Nulles : 10 000 / 0 / 0
IA3 / IA1 / Nulles : 10 000 / 0 / 0
IA4 / IA1 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne)
IA5 / IA1 / Nulles : 10 000 / 0 / 0
IA6 / IA1 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne)
IA7 / IA1 / Nulles : 10 000 / 0 / 0
IA8 / IA1 / Nulles : 10 000 / 0 / 0
IA9 / IA1 / Nulles : 5 000 / 0 / 5 000 (quand IA9 commence, IA9 gagne)
IA2 / IA2 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne en 4 coups)
IA3 / IA2 / Nulles : 0 / 5 000 / 5 000 (quand IA2 commence, IA2 gagne)
IA4 / IA2 / Nulles : 10 000 / 0 / 0
IA5 / IA2 / Nulles : 10 000 / 0 / 0
IA6 / IA2 / Nulles : 10 000 / 0 / 0
IA7 / IA2 / Nulles : 10 000 / 0 / 0
IA8 / IA2 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne)
IA9 / IA2 / Nulles : 0 / 10 000 / 0
IA3 / IA3 / Nulles : 0 / 0 / 10 000 *
IA4 / IA3 / Nulles : 0 / 5 000 / 5 000 (quand IA4 commence, IA3 gagne)
IA5 / IA3 / Nulles : 10 000 / 0 / 0
IA6 / IA3 / Nulles : 0 / 10 000 / 0
IA7 / IA3 / Nulles : 0 / 5 000 / 5 000 (quand IA7 commence, IA3 gagne)
IA8 / IA3 / Nulles : 5 000 / 0 / 5 000 (quand IA8 commence, IA8 gagne)
IA9 / IA3 / Nulles : 0 / 0 / 10 000 *
IA4 / IA4 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence perd en 17 coups)
IA5 / IA4 / Nulles : 10 000 / 0 / 0
IA6 / IA4 / Nulles : 0 / 0 / 10 000 *
IA7 / IA4 / Nulles : 5 000 / 0 / 5 000 (quand IA7 commence, IA7 gagne)
IA8 / IA4 / Nulles : 0 / 10 000 / 0
IA9 / IA4 / Nulles : 0 / 10 000 / 0
IA5 / IA5 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne en 13 coups)
IA6 / IA5 / Nulles : 0 / 10 000 / 0
IA7 / IA5 / Nulles : 0 / 10 000 / 0
IA8 / IA5 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence perd)
IA9 / IA5 / Nulles : 0 / 10 000 / 0
IA6 / IA6 / Nulles : 0 / 0 / 10 000 *
IA7 / IA6 / Nulles : 10 000 / 0 / 0
IA8 / IA6 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne)
IA9 / IA6 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne)
IA7 / IA7 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence perd en 19 coups)
IA8 / IA7 / Nulles : 10 000 / 0 / 0
IA9 / IA7 / Nulles : 0 / 5 000 / 5 000 (quand IA7 commence, IA7 gagne)
IA8 / IA8 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne en 8 coups)
IA9 / IA8 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne)
IA9 / IA9 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne en 11 coups)
Bilan (Nombre de victoires franches) :
IA0 : 0
IA1 : 1
IA2 : 3
IA3 : 3
IA4 : 4
IA5 : 8
IA6 : 2
IA7 : 4
IA8 : 3
IA9 : 1
Sur les parties entre IA4, IA5, IA6 et IA7 : IA5 écrase les autres IA.
Si on compare les stratégies IA4 et IA5 (une seule inversion), B2P doit être avant A2P pour gagner. Si on compare les stratégies IA6 et IA7 (une seule inversion), B2P doit être avant A2P pour gagner. Si on compare les stratégies IA5 et IA7 (une seule inversion), A3P doit être avant B3P pour gagner. Si on compare les stratégies IA4 et IA6 (une seule inversion), A3P avant B3P n’apporte aucun gain (match nul).
Dans tous les cas, B2P doit être avant A2P pour gagner. A3P avant B3P ne prend tout son potentiel que si B2P est avant A2P. Supprimons A3P et B3P pour voir… (IA8 et IA9)
Petite réflexion pour le futur : Si on décompose une stratégie en micro-stratégies, cela nous amène comme ici à un codage (une sorte d’ADN de la stratégie). Je verrais bien comme développement futur quelque chose avec les algorithmes génétiques…
Quel est ce paradoxe ? IA5 écrase IA4, IA4 écrase IA8 et pourtant on n’arrive pas à départager IA5 et IA8. C’est un peu comme si des micro-logiques internes s’interpénétraient jusqu’à s’anéantir… un peu comme le mangeur de planeurs dans le jeu de la vie.
Code source sur GitHub.
* Extrait de WarGames (1983) :
GREETINGS PROFESSOR FALKEN
HELLO
A STRANGE GAME.
THE ONLY WINNING MOVE IS
NOT TO PLAY.
HOW ABOUT A NICE GAME OF CHESS?