IA de jeux, Conclusion
Voir aussi : video youtube - video peertube - code source
Cet article conclut la série consacrée à l’implémentation d’un jeu de Puissance 4 et de quelques Intelligences Artificielles, en C++ et en Haskell. Il résume les points abordés et compare les implémentations réalisés dans ces deux langages.
Articles de la séries IA de jeux :
- Introduction
- Implémenter un Puissance 4, en C++
- Implémenter une IA basique, en C++
- Implémenter une IA arborescente, en C++
- Performances de code, en C++
- Implémenter un Puissance 4, en Haskell
- Implémenter une IA basique, en Haskell
- Implémenter une IA arborescente, en Haskell
- Performances de code, en Haskell
- Conclusion
Résumé du projet
Dans ce projet, on a implémenté un jeu de Puissance 4 (en C++ et en Haskell). Il s’agit d’un jeu simple, à deux joueurs en tour-à-tour. Ici, on l’a implémenté avec un simple tableau 2D et une dectection de victoire à partir du coup joué.
Concernant les IA, on a implémenté notamment un Monte-Carlo (estimation de chaque coup possible via des parties aléatoires) et un Monte-Carlo Tree Search (estimations de l’arbre de jeu par sélection UCB et parties aléatoires).
On a également développé une interface utilisateur, permettant à un humain de jouer contre une IA, et un programme de comparaison d’IA, permettant d’estimer et de visualiser l’efficacité des différentes IA.
$ ./cli.out
...
0123456
YYY....
RRR....
YYY....
RRR....
YYY....
RRRR...
moves:
status: WinR
new game (y/n) ? 
Enfin, on a également écrit des tests unitaires pour vérifier que les codes sont à peu près fonctionnels et on a abordé l’optimisation des performances d’exécution, les IA étant assez calculatoires.
Code source
L’implémentation C++ est assez classique pour ce genre de projet : tableau 2D pour le plateau de jeu, interface de Bot + classes dérivées, structure arborescente pour l’algo MCTS…
===================================================================================
Language Files Lines Code Comments Blanks
===================================================================================
C++ 4 397 310 28 59
-----------------------------------------------------------------------------------
cpp/Game.cpp 106 85 3 18
cpp/cmp0.cpp 19 16 0 3
cpp/Bot.cpp 179 140 15 24
cpp/cli.cpp 93 69 10 14
-----------------------------------------------------------------------------------
C++ Header 3 164 119 9 36
-----------------------------------------------------------------------------------
cpp/Bot.hpp 87 60 9 18
cpp/cmp.hpp 35 26 0 9
cpp/Game.hpp 42 33 0 9
===================================================================================
Total 7 561 429 37 95
===================================================================================Concernant l’implémentation Haskell, comme on voulait avoir du code relativement performant, on a utilisé la monade ST, notamment pour gérer la mémoire efficacement : tableaux mutables, structure d’arbre avec noeuds “en-place”… Au final le code ressemble assez à du code impératif classique, à ceci près que les sections de code pouvant faire des mutations sont déclarées et vérifiées au niveau du typage.
===================================================================================
Language Files Lines Code Comments Blanks
===================================================================================
Haskell 5 425 306 33 86
-----------------------------------------------------------------------------------
hs/cmp0.hs 20 16 0 4
hs/cli.hs 85 57 11 17
hs/Game.hs 107 77 6 24
hs/Bot.hs 184 134 14 36
hs/Cmp.hs 29 22 2 5
===================================================================================
Total 5 425 306 33 86
===================================================================================Performances
Pour comparer les performances, entre l’implémentation C++ et l’implémentation Haskell, il faudrait tester différents jeux de paramètres, mais ici on se contendra d’un paraétrage type de 100 parties de Monte-Carlo 500 contre MCTS 1000.
Conclusion
Programmer des IA de jeux est typiquement un cas où on utiliserait plutôt des langages comme C++. L’implémentation en Haskell proposée ici n’est cependant pas ridicule, avec un temps de calculs de 1.86x l’implémentation C++, pour 0.71x son nombre de lignes de code.
En perspective, il serait intéressant de considérer des implémentations multi-thread, d’autres algorithme d’IA, des interfaces graphiques, etc. Certains de ces points feront certainement l’objet de prochains articles de blog.