Catégorie : Informatique

L’objectif était de mettre au point une intelligence artificielle (IA) la meilleure possible pour jouer à Puissance 4, sans descendre en profondeur dans un arbre comme avec l’algorithme minimax ou alpha-bêta. Je pense être très près du but avec IA15 bien que l’IA en question soit encore facile à battre pour un humain. Va désormais venir 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 sont 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 sont pris en compte)

Le codage des IA en compétition est :

IA0 : Priorité H
IA1 : Priorité PH
IA12 : Priorités A4PH / A3PH / A2PH / PH
IA13 : Priorités B4PH / B3PH / B2PH / PH
IA14 : Priorités A4PH / B4PH / A3PH / B3PH / A2PH / B2PH / PH
IA15 : Priorités A4PH / B4PH / A3PH / B3PH / B2PH / A2PH / PH
IA16 : Priorités A4PH / B4PH / B3PH / A3PH / A2PH / B2PH / PH
IA17 : Priorités A4PH / B4PH / B3PH / A3PH / B2PH / A2PH / PH
IA18 : Priorités A4PH / B4PH / A2PH / B2PH / PH
IA19 : Priorités A4PH / B4PH / B2PH / A2PH / PH
IA20 : Priorités A4PH / B4PH / B3PH / B2PH / A3PH / A2PH / PH

Présentation des résultats :

Sur 1 million de parties, les résultats bruts sont :

IA0 / IA0 / Nulles : 499 231 / 498 300 / 2 469
IA1 / IA0 / Nulles : 878 716 / 121 257 / 27
IA12 / IA0 / Nulles : 970 480 / 29 520 / 0
IA13 / IA0 / Nulles : 967 884 / 18 236 / 13 880
IA14 / IA0 / Nulles : 996 952 / 3 034 / 14
IA15 / IA0 / Nulles : 995 524 / 4 369 / 107
IA16 / IA0 / Nulles : 993 656 / 6 191 / 153
IA17 / IA0 / Nulles : 993 568 / 5 938 / 494
IA18 / IA0 / Nulles : 992 092 / 7 886 / 22
IA19 / IA0 / Nulles : 988 123 / 11 735 / 142
IA20 / IA0 / Nulles : 991 937 / 7 195 / 868

IA15 / IA0 / Nulles : 995 524 / 4 369 / 107
IA15 / IA1 / Nulles : 979 122 / 0 / 20 878
IA15 / IA12 / Nulles : 1 000 000 / 0 / 0
IA15 / IA13 / Nulles : 724 198 / 266 561 / 9 241
IA15 / IA14 / Nulles : 1 000 000 / 0 / 0
IA15 / IA15 / Nulles : 500 000 / 500 000 / 0
IA15 / IA16 / Nulles : 1 000 000 / 0 / 0
IA15 / IA17 / Nulles : 1 000 000 / 0 / 0
IA15 / IA18 / Nulles : 771 989 / 228 011 / 0
IA15 / IA19 / Nulles : 746 678 / 0 / 253 322
IA15 / IA20 / Nulles : 723 979 / 266 779 / 9 242

Commentaires :

Si on compare IA14 et IA15, il n’y a qu’une seule inversion dans le codage de la stratégie : on passe de A2PH / B2PH pour IA14 à B2PH / A2PH pour IA15 et l’effet est radical : IA15 écrase IA14. De même, si on compare IA15 et IA17, on passe de A3PH / B3PH pour IA15 à B3PH / A3PH pour IA17 et l’effet est radical : IA17 est écrasée par IA15.

Code source sur GitHub.

Je viens de reprendre mon travail sur Puissance 4 après 9 mois d’interruption. La mise à jour qui intègre cette fois les alignements « troués » est sur GitHub. Une nouvelle compétition entre IA sera lancée très bientôt.

J’ai rajouté 9 nouvelles IA avec les correspondances suivantes :
IA12 (alignements troués) / IA2 (alignements pleins)
IA13 (alignements troués) / IA3 (alignements pleins)
IA14 (alignements troués) / IA4 (alignements pleins)
IA15 (alignements troués) / IA5 (alignements pleins)
IA16 (alignements troués) / IA6 (alignements pleins)
IA17 (alignements troués) / IA7 (alignements pleins)
IA18 (alignements troués) / IA8 (alignements pleins)
IA19 (alignements troués) / IA9 (alignements pleins)
IA20 (alignements troués) / IA10 (alignements pleins)

Sur 1 000 parties, IA20 contre IA10 (la meilleure jusqu’ici) donne 957 victoires à IA20, 0 victoires à IA10 et 43 parties nulles. Dans la suite, je laisserai donc tomber les stratégies basées sur les alignements pleins.

Etant donné les résultats de la compétition précédente concernant IA3 et IA7 (7 victoires chacune) et le faible score d’IA6 alors qu’entre IA6 et IA7 il n’y a qu’une inversion (B2PH et A2PH), je vais introduire une nouvelle IA (IA10) avec comme priorités : A4PH / B4PH / B3PH / B2PH / A3PH / A2PH / PH. Il s’agit donc d’une IA offensive. Elle reste cependant facile à battre pour un humain (Les alignements « troués » ne sont toujours pas pris en compte).

Présentation des résultats :

Sur 1 million de parties, les résultats bruts sont :

IA10 / IA0 / Nulles : 984 590 / 14 607 / 803
IA10 / IA1 / Nulles : 670 273 / 0 / 329 727
IA10 / IA2 / Nulles : 883 310 / 116 690 / 0
IA10 / IA3 / Nulles : 201 453 / 157 344 / 641 203
IA10 / IA4 / Nulles : 710 937 / 210 235 / 78 828
IA10 / IA5 / Nulles : 400 016 / 390 242 / 209 742
IA10 / IA6 / Nulles : 1 000 000 / 0 / 0
IA10 / IA7 / Nulles : 166 433 / 112 602 / 720 965
IA10 / IA8 / Nulles : 555 897 / 314 420 / 129 683
IA10 / IA9 / Nulles : 507 615 / 4 644 / 487 741
IA10 / IA10 / Nulles : 178 886 / 179 550 / 641 564

Suite à l’introduction d’une faible part d’aléatoire dans le codage des IA (voir article précédent), une mise à jour s’impose.

Présentation des résultats :

Sur 1 million de parties, les résultats bruts sont :

IA0 / IA0 / Nulles : 498 749 / 498 630 / 2 621
IA1 / IA0 / Nulles : 877 813 / 122 165 / 22
IA2 / IA0 / Nulles : 970 751 / 29 249 / 0
IA3 / IA0 / Nulles : 963 172 / 26 350 / 10 478
IA4 / IA0 / Nulles : 986 385 / 13 601 / 14
IA5 / IA0 / Nulles : 984 896 / 15 012 / 92
IA6 / IA0 / Nulles : 988 261 / 11 645 / 94
IA7 / IA0 / Nulles : 986 483 / 13 095 / 422
IA8 / IA0 / Nulles : 969 613 / 30 376 / 11
IA9 / IA0 / Nulles : 944 008 / 55 872 / 120

IA1 / IA1 / Nulles : 469 129 / 468 488 / 62 383
IA2 / IA1 / Nulles : 1 000 000 / 0 / 0
IA3 / IA1 / Nulles : 533 878 / 0 / 466 122
IA4 / IA1 / Nulles : 583 322 / 416 678 / 0 **
IA5 / IA1 / Nulles : 979 151 / 0 / 20 849
IA6 / IA1 / Nulles : 500 000 / 500 000 / 0
IA7 / IA1 / Nulles : 752 809 / 0 / 247 191
IA8 / IA1 / Nulles : 749 970 / 250 030 / 0
IA9 / IA1 / Nulles : 513 791 / 402 861 / 83 348 **

IA2 / IA2 / Nulles : 500 000 / 500 000 / 0
IA3 / IA2 / Nulles : 738 376 / 190 170 / 71 454 **
IA4 / IA2 / Nulles : 1 000 000 / 0 / 0
IA5 / IA2 / Nulles : 1 000 000 / 0 / 0
IA6 / IA2 / Nulles : 958 403 / 41 597 / 0
IA7 / IA2 / Nulles : 708 737 / 291 263 / 0
IA8 / IA2 / Nulles : 407 473 / 592 527 / 0 **
IA9 / IA2 / Nulles : 333 884 / 666 116 / 0

IA3 / IA3 / Nulles : 180 253 / 179 288 / 640 459
IA4 / IA3 / Nulles : 210 562 / 711 181 / 78 257
IA5 / IA3 / Nulles : 390 837 / 399 848 / 209 315 **
IA6 / IA3 / Nulles : 0 / 749 868 / 250 132
IA7 / IA3 / Nulles : 113 404 / 166 407 / 720 189
IA8 / IA3 / Nulles : 314 354 / 555 529 / 130 117 **
IA9 / IA3 / Nulles : 143 539 / 106 110 / 750 351

IA4 / IA4 / Nulles : 499 900 / 500 100 / 0
IA5 / IA4 / Nulles : 1 000 000 / 0 / 0
IA6 / IA4 / Nulles : 125 486 / 125 397 / 749 117
IA7 / IA4 / Nulles : 624 828 / 0 / 375 172 **
IA8 / IA4 / Nulles : 116 529 / 883 471 / 0
IA9 / IA4 / Nulles : 53 125 / 874 902 / 71 973

IA5 / IA5 / Nulles : 500 107 / 499 893 / 0
IA6 / IA5 / Nulles : 0 / 1 000 000 / 0
IA7 / IA5 / Nulles : 523 509 / 434 870 / 41 621 **
IA8 / IA5 / Nulles : 727 853 / 272 147 / 0 **
IA9 / IA5 / Nulles : 0 / 746 805 / 253 195

IA6 / IA6 / Nulles : 0 / 0 / 1 000 000
IA7 / IA6 / Nulles : 1 000 000 / 0 / 0
IA8 / IA6 / Nulles : 244 349 / 744 638 / 11 013 **
IA9 / IA6 / Nulles : 500 000 / 500 000 / 0

IA7 / IA7 / Nulles : 166 210 / 166 396 / 667 394 **
IA8 / IA7 / Nulles : 858 227 / 133 496 / 8 277
IA9 / IA7 / Nulles : 0 / 635 147 / 364 853 **

IA8 / IA8 / Nulles : 499 861 / 500 139 / 0
IA9 / IA8 / Nulles : 250 253 / 749 747 / 0 **

IA9 / IA9 / Nulles : 381 972 / 381 387 / 236 641

Bilan (Nombre de victoires) :

IA0 : 0
IA1 : 1
IA2 : 4
IA3 : 7
IA4 : 5
IA5 : 6
IA6 : 3
IA7 : 7
IA8 : 5
IA9 : 2

Quelques paradoxes :

IA6 bat très largement IA2 ; IA2 écrase IA1 et pourtant on n’arrive pas à départager IA6 et IA1. IA5 écrase IA4 ; IA4 bat largement IA8 et paradoxalement IA8 bat IA5. IA7 écrase IA6 ; IA6 bat largement IA8 et paradoxalement IA8 bat largement IA7.

Code source sur GitHub.

Introduction d’un peu d’aléatoire au niveau des IA : Si plusieurs positions sont possibles (égalité de poids), l’IA tire au hasard parmi ces meilleures positions plutôt que de s’arrêter à la première dans la liste. Reste à voir ce que cela va changer au niveau de la compétition précédente.

Le codage des IA devient donc :

IA0 : Priorité H
IA1 : Priorité PH
IA2 : Priorités A4PH / A3PH / A2PH / PH
IA3 : Priorités B4PH / B3PH / B2PH / PH
IA4 : Priorités A4PH / B4PH / A3PH / B3PH / A2PH / B2PH / PH
IA5 : Priorités A4PH / B4PH / A3PH / B3PH / B2PH / A2PH / PH
IA6 : Priorités A4PH / B4PH / B3PH / A3PH / A2PH / B2PH / PH
IA7 : Priorités A4PH / B4PH / B3PH / A3PH / B2PH / A2PH / PH
IA8 : Priorités A4PH / B4PH / A2PH / B2PH / PH
IA9 : Priorités A4PH / B4PH / B2PH / A2PH / PH

Code source sur GitHub.

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?

Bien que le travail sur l’IA ne soit pas encore fini (il reste quelques manques comme les alignements « troués » de 2 ou 3 pions), on a déjà des résultats intéressants (98 % de victoires pour l’IA / 2 % pour un jeu aléatoire). Notez que je n’ai pas encore implémenté les algorithmes minimax et alpha-bêta qui amèneront eux de la profondeur. Pour jouer contre l’ordinateur, le code source est sur GitHub.

Pour l’IA à base de minimax et d’alpha-bêta, voir le code de Christian Schmidt qui a fait ce travail en JavaScript.