Règles du jeu (Breakthrough)

Breakthrough est un jeu de stratégie de plateau créé par Dan Troyka en 2000. Il gagna le concours du meilleur design de jeu de plateau 8x8, et il a quelques similitudes avec les Dames, mais la stratégie est différente.

Le but du jeu est d'atteindre la rangée de départ de l'adversaire, la plus éloignée du joueur. Cela signifie que le joueur blanc doit atteindre la 8e rangée et que le joueur noir doit atteindre la 1ère rangée pour gagner la partie.

Introduction

Je vous présente en détail la conception, l'implémentation et les résultats de mon programme d'intelligence artificielle pour les jeux de plateau. Notre objectif était de créer une IA capable de prendre des décisions informées et efficaces dans un environnement de jeu complexe.

Élagage de Alpha-Beta

L'élagage alpha-beta est une technique utilisée dans les algorithmes de recherche arborescente, tels que Minimax, pour réduire le nombre de nœuds évalués. Il fonctionne en éliminant les branches de l'arbre de recherche qui ne contribuent pas à la décision finale. Cela se fait en utilisant deux valeurs, alpha et bêta, pour suivre les valeurs minimale et maximale respectivement, ce qui permet d'éliminer les branches qui ne peuvent pas améliorer le résultat actuel. Cela permet de réduire considérablement le temps de calcul nécessaire pour trouver la meilleure action à prendre.

Fonction d'Évaluation

Notre fonction d'évaluation est divisée en trois points principaux :

1. Calcul du nombre de pièces sur le terrain et attribution de points en fonction du surplus ou du déficit par rapport à l'adversaire.
2. Attribution de points à chaque case du plateau, avec un bonus de 50% aux cases contenant des pions en sécurité.
3. Évaluation des positions en tenant compte de critères tels que l'importance stratégique des pièces, leur mobilité, les positions avancées et les menaces directes sur les pièces adverses.

Nous utilisons également une matrice de score de position pour attribuer des points à chaque case du plateau, favorisant une défense solide sur les positions importantes tout en encourageant la progression vers l'avant et le centre. Enfin, nous avons ajouté un bonus de 50% aux pions en sécurité, renforçant ainsi notre stratégie de défense et améliorant le contrôle du terrain de notre programme.

Profondeur de l'arbre MinMax et temps de calcul moyen

Notre algorithme MinMax atteint une profondeur de 7 dans l'arbre de recherche, ce qui entraîne souvent des dépassements de temps. À la profondeur 6, quelques dépassements de temps sont rencontrés, mais à la profondeur 5, ils sont rares, indiquant que cette profondeur est plus raisonnable pour obtenir des résultats satisfaisants.

La profondeur de l'arbre est statique et ne dépend d'aucun paramètre autre que la valeur de profondeur préalablement attribuée. Cependant, la limite de temps définie a un impact direct sur la profondeur atteinte dans l'arbre de recherche.

Le temps moyen requis pour évaluer nos coups est de 4,2 secondes à une profondeur de 5. Nous continuons à rechercher des moyens d'optimiser notre algorithme pour améliorer encore davantage ces performances.

Nous avions initialement choisi une profondeur finale de 7, mais après le tournoi, nous envisagerions probablement de l'abaisser à 5 pour garantir une exploration plus complète de l'arbre.

Nous avons exploré un choix de profondeur adaptatif en estimant une profondeur différente en fonction du nombre de pions restants en jeu, mais cette approche n'a pas donné les résultats escomptés.