Quarto Plus

Quarto +

1. Introduction :

Dans le cadre du module de l’intelligence artificielle, nous étions invités à implémenter une intelligence artificielle pour le jeu quarto plus.

Le jeu se compose de :

• Un plateau (Grille 4*4)
• Une liste des pièces disponibles
• Un choix d’une pièce à joueur ;

Chaque coup d’un joueur est un couple :

• Mouvement de la pièce choisie précédemment par l’adversaire
• Un choix d’une pièce pour l’adversaire

Le gagnant est celui qui dépose la dernière pièce qui fait une combinaison de Ligne, colonne, diagonale, carré avec un critère en commun.

1. Structures de données

Afin de présenter l’état du jeu, nous avons fait les choix de structures de données ci-dessous :

Plateau (Grille) :

Pour la grille, nous avons utilisé un tableau de deux dimensions.

En effet, les accès à ce composant se font exclusivement par deux indices (Ligne / colonne). Les tableaux à deux dimensions sont les plus adaptés dans ce cas.

Liste des pièces disponibles :

Ce composant est utilisé pour retrouver une pièce avec son nom et pourvoir l’effacer. Les accès se font alors avec le nom de la pièce et non pas l’indice. C’est pour cette raison que nous avons choisi d’utiliser un Hashmap.

Pièce choisie :

La pièce choisie prend la forme d’un seul string qui représente les 4 critères.

1. Alpha / Beta

Quarto plus respecte les règles suivantes :

• Deux joueurs (Ami/Enemi)
• Un jouer gagne = L’autre joueur perd

En effet, avec chaque coup de quarto plus, notre joueur essaye de maximiser ses chances. Alors que l’adversaire essaye de minimiser les chances de notre joueur.

Avec ces règles l’algorithme Min Max est le bon choix pour le problème.

Afin de l’optimiser, en réduisant les branches sans effets, nous implémentons la version Alpha Beta.

Étant donné que nous avons considéré un coup comme un couple mouvement / choix, l’arbre aura :

• Une profondeur maximum : 17 => 1 choix + 15 choix/mouvement + 1 mouvement
• Le nombre total de feuilles à évaluer, si nous développons l’arbre au maximum au premier coup : 16 * (16*15) * (15*14) * (14*13) * …. * 2 * 1

Plus généralement, à un coup donné « C », nous développons l’arbre jusqu’à un profondeur max : nous aurons alors (16 – C + 1)2 ! feuilles.

1. Contrainte de temps

Durant une partie, nous ne devons pas passer les 5 minutes par joueur.

Afin de gérer cette contrainte, nous avons décidé de commencer par deviser le temps disponible entre tous les coups.

Tout en ignorant les coups qui n’ont pas d’impact sur le jeu. Pour ces derniers nous jouons aléatoirement.

Les coups, qui sont considérés sans impact sur le jeu, sont les premiers dont nous sommes certain qu’un choix aléatoire ne peut pas amener à une perte. Une perte peut arriver lorsqu’on a au moins 3 pièces sur le plateau. Nous pouvons donc ignorer les premiers coups qui ne peuvent jamais donner 3 pièces. C’est à dire les 3 premiers coups.

...