Tournoi d'un algorithme d'Ultimate Tic Tac Toe

Un algorithme du jeu Ultimate tic tac toe qui m'a valu la première place dans mon cours de Structure de données et algorithme.

Projet personel!

J'ai effectué ce projet dans le cadre du cours de Structure de données et algorithme. Notre tâche était d'implémenter un algorithme MiniMax avec élaguage alpha-béta capable de jouer une partie d'Ultimate tic tac toe.

À la fin de la session, un tournoi a été réalisé entre tous les étudiants du cours. Les performances du tournoi impactait directement La note reçue au projet. Mon algorithme a obtenu la première place, en égalité avec l'autre finaliste.

Un arbre de jeu qui représente le fonctionnement de l'algorithme MiniMax. Un arbre de jeu qui représente le fonctionnement de l'algorithme MiniMax.

Algorithme et structure de donnée

La base de l'algorithme est un algorithme Minimax avec élaguage alpha/bêta. Comme on avait un temps de réflexion limite par tour, j'ai utilisé une recherche itérative, ce qui me permettait d'atteindre la profondeur maximale de l'arbre de recherche avant le temps limite. Afin de minimiser le nombre de branches évaluées durant une recherche, je m'assurais d'ordonner les branches en fonction du coup le plus prometteur. Pour déterminer le coup le plus prometteur, j'utilisais l'information de l'itération précédente et j'utilisais des hypothèses en fonction de l'état de la partie.

En plus d'un algorithme solide, j'ai aussi utilisé des techniques d'optimisation. J'ai accordé une attention particulière aux structures de données utilisées et je me suis assuré que les opérations effectuées fréquemment étaient les plus rapides possible. Parmi ces optimisations, de loin celle qui a eu le plus grand impact est la représentation du plateau de jeu avec une série de bits (bitboard) et utiliser les opérations sur les bits pour vérifier l'état du jeu.

Stratégie de test

L'une des premières choses que j'ai remarquées, c'est la difficulté d'évaluer rigoureusement les performances de l'algorithme. En particulier, pour déterminer si les modifications apportées entraînent une réelle amélioration. C'est juste difficile d'évaluer l'effet d'un changement donné avec seulement une poignée de parties.

Pour pallier ce problème, j'ai pris du temps pour écrire une batterie de tests empiriques. Le fonctionnement de ces tests étaient relativement simple et consistait à faire s’affronter différentes versions de l’algorithme. Ainsi, quand j'ajoutais une fonctionnalité à l'algorithme, je le testais contre la version inchangée de l'algorithme par le biais d'environ 350 parties.

Avec du recul, je pense que la décision d'accorder du temps pour effectuer des tests automatique est la décision qui a eu le plus grand impact positif dans le tournoi. Ces tests m'ont permis de quantifier chaque changement et de réaliser quand une optimisation heurtait davantage l'algorithme qu'elle ne l'aidait.