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 :

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.

Temps de calculs moyen (C++ = 5.0s, Haskell = 9.3s).

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.