Sur les opérations sur les bits, l’élagage alpha-bêta et le codage en dur des états de jeu initiaux pour créer un agent d’IA très fort pour connect-four.
Dans le cadre du cours » Informatique « , où les ingénieurs de première année de l’Université de Gand apprennent à coder en Python, nous avons mis en place une plateforme de compétition de bot d’IA. Le but était de créer un bot qui joue au jeu connect-four en implémentant la fonction suivante:
def generate_move(board, player, saved_state):
"""Contains all code required to generate a move,
given a current game state (board & player) Args: board (2D np.array): game board (element is 0, 1 or 2)
player (int): your plabyer number (float)
saved_state (object): returned value from previous call Returns: action (int): number in
saved_state (optional, object): will be returned next time
the function is called """
return 0
Après avoir soumis du code à la plateforme, vous défiez automatiquement tous les joueurs classés plus haut que vous sur le classement. Les parties sont simulées entre votre bot et vos adversaires. Chaque partie se compose de cinq rounds au cours desquels 5 points sont attribués au joueur qui parvient le premier à connecter quatre jetons ou 1 point au joueur qui a connecté la plus longue chaîne (le plus souvent 3 jetons) en premier, en cas d’égalité. Ceci afin de s’assurer qu’il y a toujours un gagnant. Le joueur qui commence le premier tour est choisi au hasard, après quoi les joueurs alternent dans les départs. Votre rang continue d’augmenter jusqu’à ce que vous perdiez (jeu de l’échelle).
Un collègue, Jeroen van der Hooft, et moi avons décidé que ce serait un exercice amusant d’essayer d’imiter autant que possible un solveur parfait (qui gagne le jeu s’il peut commencer), basé sur l’article de blog suivant. Quelques exigences importantes auxquelles notre code devait se conformer (ce qui a conduit au fait que notre solveur n’était pas complètement optimal) étaient :
* taille maximale du fichier de 1 Mo
* generate_move ne pouvait pas s’exécuter plus de 1s
* faire uniquement appel à la bibliothèque standard et à NumPy
Présentons d’abord une structure de données efficace pour stocker le plateau de jeu : les bitstrings. Je vais résumer les opérations les plus importantes (comme vérifier si quatre jetons sont connectés, et mettre à jour le plateau après un déplacement). Pour une explication très complète sur les bitstrings (ou bitboards), et toutes les opérations possibles, veuillez consulter ce readme (quoique fait un peu différemment).
Nous pouvons représenter chaque état de jeu possible (ou configuration du plateau de jeu) de manière unique sous la forme de deux bittrings, qui peuvent facilement être convertis en un entier :
* une bittring représentant les positions des jetons d’un joueur (position)
* une bittring représentant les positions de des deux joueurs (masque)
La bittring de position de l’adversaire peut être calculée en appliquant un opérateur XOR entre masque et position. Bien sûr, stocker deux bittrings pour les jetons des deux joueurs est également une approche viable (nous pouvons alors calculer le masque en appliquant l’opérateur OU sur les deux bittrings).
La bittring est composée de 49 bits qui inclut une rangée sentinelle (tous les 0) de 7 bits (l’utilisation de celle-ci sera expliquée prochainement). Les bits sont ordonnés comme suit :
À titre d’exemple, vérifiez la configuration suivante du plateau de jeu :
.
Maintenant, formons les bitstrings, avec la bittring de position pour le joueur jaune :
position
0000000
0000000
0000000
0011000 = b'0000000000000000000110001101000100000000000000000'
0001000
0000100
0001100 = 832700416mask
0000000
0000000
0001000
0011000 = b'0000000000000100000110011111000111100000000000000'
0011000
0011100
0011110 = 35230302208(opponent position)
0000000 0000000 0000000
0000000 0000000 0000000
0000000 0001000 0001000
0011000 XOR 0011000 = 0000000
0001000 0011000 0010000
0000100 0011100 0011000
0001100 0011110 0010010
Puisque le paramètre d’entrée du tableau est un tableau numpy de tableaux numpy, nous devons d’abord convertir ce tableau en bitmaps correspondants. Voici le code (plutôt simple) pour le faire :
def get_position_mask_bitmap(board, player):
position, mask = '', ''
# Start with right-most column
for j in range(6, -1, -1):
# Add 0-bits to sentinel
mask += '0'
position += '0'
# Start with bottom row
for i in range(0, 6):
mask += != 0]
position += == player]
return int(position, 2), int(mask, 2)
Nous pouvons maintenant utiliser la chaîne binaire de position pour vérifier si quatre jetons sont connectés, avec les opérations binaires suivantes :
def connected_four(position):
# Horizontal check
m = position & (position >> 7)
if m & (m >> 14):
return True # Diagonal \
m = position & (position >> 6)
if m & (m >> 12):
return True # Diagonal /
m = position & (position >> 8)
if m & (m >> 16):
return True # Vertical
m = position & (position >> 1)
if m & (m >> 2):
return True # Nothing found
return False
Maintenant, décomposons la partie où nous vérifions si quatre jetons sont connectés horizontalement:
1. m = position & (position >> 7)
2. if m & (m >> 14):
return True
La première étape (1.) consiste à décaler notre chaîne de bits de 7 positions vers la droite et à prendre un masque ET, cela revient à déplacer chaque bit vers la gauche dans notre tableau de bits (on diminue l’indice dans la chaîne de bits, l’indice 0 correspondant au bit le plus à droite ou le moins significatif). Prenons le bitboard suivant comme exemple (version simplifiée qui ne peut pas se produire dans un jeu réel):
0000000
0000000
0011110
0000000
0000000
0000000
0000000= b'0000000001000000100000010000001000000000000000000'
>> 7: b'0000000000000000100000010000001000000100000000000'0000000
0000000
0111100
0000000
0000000
0000000
0000000&: b'0000000000000000000000010000001000000100000000000'0000000
0000000
0011100
0000000
0000000
0000000
0000000
Nous pouvons voir le nouveau bitboard comme suit : un bit est égal à 1 s’il y a un jeton à sa gauche et s’il est identique (ou en d’autres termes : les bits égaux à 1 indiquent que nous pouvons connecter deux jetons horizontalement à gauche à partir de cette position). Maintenant, pour l’opération suivante (2.), nous déplaçons notre résultat de 14 positions vers la droite et appliquons à nouveau un masque ET.
0000000
0000000
0011100
0000000
0000000
0000000
0000000= b'0000000000000000100000010000001000000000000000000'
>> 14: b'0000000000000000000000000000001000000100000000000'
-------------------------------------------------
& : b'0000000000000000000000000000001000000000000000000'> 0? : True # four connected tokens found
En déplaçant notre chaîne de bits résultante de 14 positions vers la droite, nous vérifions si nous pouvons faire correspondre deux jetons horizontalement consécutifs avec deux autres jetons horizontalement consécutifs à 2 positions à sa gauche sur le tableau. Ces étapes combinées équivalent à vérifier si quatre jetons sont connectés horizontalement. Les opérations pour les autres directions (diagonale et verticale) sont les mêmes, nous décalons simplement notre bitmap pour plus ou moins de positions (1 pour la verticale, 8 pour la diagonale vers le sud-ouest (/) et 6 pour la diagonale vers le sud-est (\)).
La raison de la rangée sentinelle (les sept bits supplémentaires) est de faire une distinction entre la rangée supérieure et inférieure de la grille. Sans elle, cette approche produirait des faux positifs, ci-dessous deux chaînes de bits de position, l’une sur une grille 6×7, l’autre sur une grille 7×7. Nous vérifions si nous pouvons trouver quatre jetons verticalement consécutifs (ce qui est, dans ce cas, faux)
vertical check on 6x7 grid
--------------------------
0010000
0010000
0010000
0000000
0000000
0001000= b'000000000000000000000001111000000000000000'
>> 1: b'000000000000000000000000111100000000000000'
& : b'000000000000000000000000111000000000000000'
>> 2: b'000000000000000000000000001110000000000000'
& : b'000000000000000000000000001000000000000000'
> 0?: True (WRONG)vertical check on 7x7 grid
--------------------------
0000000
0010000
0010000
0010000
0000000
0000000
0001000= b'0000000000000000000000000001011100000000000000000'
>> 1: b'0000000000000000000000000000101110000000000000000'
& : b'0000000000000000000000000000001100000000000000000'
>> 2: b'0000000000000000000000000000000011000000000000000'
& : b'0000000000000000000000000000000000000000000000000'
> 0?: False (CORRECT)
Maintenant, regardons de plus près l’opération de déplacement, où nous changeons les bitmaps en fonction d’un déplacement effectué par un joueur :
def make_move(position, mask, col):
new_position = position ^ mask
new_mask = mask | (mask + (1 << (col*7)))
return new_position, new_mask
La première chose que nous faisons est d’appliquer un masque XOR entre la position et la bittring de masque pour obtenir la bittring de position de l’adversaire (puisque ce sera son tour après avoir effectué ce mouvement). Ensuite, nous mettons à jour notre bittring de masque en appliquant un masque OU entre le masque actuel et une addition du masque avec un bit dans la colonne correspondante (où nous voulons déposer notre jeton). Voyons un exemple :
position
0000000
0000000
0000000
0011000
0001000
0000100
0001100mask
0000000
0000000
0001000
0011000
0011000
0011100
0011110# Drop a token in the fourth column
--> make_move(position, mask, 4)new_position = position ^ mask
new_position
0000000 0000000 0000000
0000000 0000000 0000000
0000000 0001000 0001000
0011000 XOR 0011000 = 0000000
0001000 0011000 0010000
0000100 0011100 0011000
0001100 0011110 00100101 << (col*7)
0000000
0000000
0000000
0000000 = 268435456
0000000
0000000
0000100mask + (1 << (col*7)) = 35230302208 + 268435456 = 35498737664
0000000
0000000
0001000
0011000
0011100
0011000
0011010mask | (mask + (1 << (col*7)))
0000000
0000000
0001000
0011000
0011100
0011100
0011110
Arbres de jeu, minimax et élagage alpha-beta
Pendant la lecture de la section précédente, vous vous êtes peut-être dit : » pourquoi ajouter autant de complexité à votre code ? « . La raison pour laquelle nous sur-optimisons les opérations de base du jeu connect-four est due au concept que je vais maintenant introduire : les arbres de jeu.
Pour chaque jeu qui a un espace d’action discret (ou un nombre fini d’actions possibles à chaque coup), nous pouvons construire un arbre de jeu dans lequel chaque nœud représente un état de jeu possible. Les nœuds internes d’une profondeur paire représentent soit l’état initial du jeu (la racine), soit un état du jeu résultant d’un mouvement effectué par l’adversaire. Les nœuds internes d’une profondeur impaire représentent les états de jeu résultant des mouvements que nous avons effectués. Si un état met fin au jeu (quatre jetons connectés ou le plateau est plein), il s’agit d’un nœud feuille. Chaque nœud feuille se voit attribuer un certain score et n’est pas développé davantage. Voici un exemple de sous-arbre de jeu pour le jeu connect-four.
Au total, il y a 4531985219092 nœuds de feuilles possibles et donc un nombre beaucoup plus important de nœuds totaux dans l’arbre. Même avec les opérations optimisées du tableau de bord, il est infaisable sur le plan informatique de parcourir l’ensemble de l’arbre de jeu. Nous aurons besoin de techniques pour trouver efficacement un chemin gagnant dans cet arbre.
Maintenant, bien que le chemin 1-1-2 dans l’arbre de jeu de la figure ci-dessus mène à un état de fin de partie où le joueur jaune gagne (c’est un chemin gagnant), il repose sur l’hypothèse que rouge est un bot stupide et qu’il foire son coup (il ne vous bloque pas).
Puisque nous ne savons pas à quel point le bot contre lequel nous allons jouer est » bon « , nous devons supposer le pire des cas : que se passe-t-il si notre adversaire est le meilleur bot possible et fait donc le meilleur coup possible à chaque fois ? Si nous parvenons à trouver un chemin gagnant contre un tel robot, nous pouvons définitivement emprunter ce chemin et être sûrs de gagner la partie (le vrai robot ne peut que faire pire, ce qui fait que la partie se termine plus tôt). Pour le jeu de connexion à quatre, un tel chemin existe si vous êtes le joueur de départ. C’est ici que l’algorithme minimax entre en jeu.
Avant de pouvoir appliquer cet algorithme aux arbres de jeu, nous devons définir une fonction de notation pour chaque nœud de l’arbre. Nous allons simplement prendre la même fonction de notation que celle de l’article de blog sur lequel cet écrit est basé. Le score d’une configuration de plateau de jeu est égal à :
* 0 si la partie va se terminer par un match nul
* 22 – le nombre de pierres utilisées si nous pouvons gagner la partie
* -(22 – le nombre de pierres) si nous allons perdre.
Dans l’image ci-dessous, si nous supposons que nous sommes le joueur jaune, nous pouvons attribuer un score de -18 au plateau de jeu, puisque le joueur rouge peut gagner avec sa quatrième pierre.
En pratique, il est difficile d’attribuer un score lorsque la partie n’est pas encore terminée. C’est pourquoi nous explorons notre arbre jusqu’à ce que nous atteignions un nœud feuille, calculons le score et propageons ce score vers le haut jusqu’à la racine. Maintenant, lorsque nous propageons ces valeurs vers le haut, les nœuds internes de notre arbre de jeu recevront plusieurs valeurs (une valeur pour chacun de ses enfants). La question est de savoir quelle valeur nous devons attribuer aux noeuds internes. Maintenant, nous pouvons donner la définition de la valeur d’un nœud interne :
* Si le nœud interne est sur une profondeur impaire, nous prenons la valeur minimale des enfants leurs valeurs (en tant qu’adversaire, nous voulons rendre le score final aussi négatif que possible, puisque nous voulons gagner)
* Si le nœud interne est sur une profondeur paire, nous prenons la valeur maximale des enfants leurs valeurs (nous voulons que notre score soit aussi positif que possible)
Voici un exemple, tiré directement de wikipedia :
Donc, nous avons maintenant un moyen de trouver le chemin optimal dans un arbre de jeu. Le problème avec cette approche est que, surtout au début du jeu, il faut un temps très long pour parcourir l’arbre entier. Nous n’avons qu’une seconde pour faire un coup ! Par conséquent, nous introduisons une technique qui nous permet d’élaguer de (grandes) parties de l’arbre de jeu, de sorte que nous n’ayons pas besoin de le parcourir entièrement. L’algorithme est appelé élagage alpha-beta.
Je vais résumer les concepts les plus importants. Une belle vidéo étape par étape, par le prof. Pieter Abbeel, peut être trouvée ici. Nous définissons les variables suivantes :
* alpha : le meilleur score actuel sur le chemin vers la racine par le maximiseur (nous)
* beta : le meilleur score actuel sur le chemin vers la racine par le minimiseur (adversaire)
Ce que nous faisons, c’est mettre à jour nos valeurs alpha et beta chaque fois que nous voyons une nouvelle valeur de nos enfants (selon que nous sommes sur une profondeur paire ou impaire). Nous transmettons ces alpha et bêta à nos autres enfants, maintenant lorsque nous trouvons une valeur qui est soit supérieure à notre bêta actuel, soit inférieure à notre alpha actuel, nous pouvons écarter le sous-arbre entier (puisque nous sommes sûrs que le chemin optimal ne passera pas par là). Examinons un autre exemple, toujours tiré de wikipedia :
.
- Nous parcourons l’arbre de jeu en profondeur d’abord, de gauche à droite. Le premier leaf que nous rencontrons est le leaf le plus à gauche (avec la valeur 5). La feuille propage cette valeur à son parent, où la valeur bêta est mise à jour et changée en 5. Elle vérifie également la deuxième feuille la plus à gauche (qui a une valeur de 6) mais cela ne met à jour aucune des valeurs (puisque 6 n’est pas meilleur que 5 si nous sommes dans la perspective du minimiseur).
- La meilleure valeur trouvée dans ce nœud (encore une fois, 5) est propagée à son parent, où la valeur alpha est mise à jour. Maintenant, nous sommes à l’enfant droit de ce parent, et vérifie d’abord son enfant gauche avec la valeur 7, et met à jour la valeur bêta (nous avons maintenant alpha=5 et bêta=7). Nous vérifions l’enfant suivant : avec la valeur 4, c’est une meilleure valeur pour le minimiseur donc nous avons maintenant beta=4 et alpha=5.
- Puisque maintenant beta ≤ alpha, nous pouvons élaguer tous les enfants restants. C’est parce que nous aurons TOUJOURS une valeur ≤ 4 maintenant dans ce nœud interne (nous sommes un minimiseur et ne mettons à jour notre valeur que lorsque nous rencontrons une valeur plus petite que la valeur actuelle), MAIS le nœud parent ne mettra à jour les valeurs que lorsqu’elles seront ≥ 5 (puisque nous sommes un maximiseur dans ce nœud). Ainsi, quelle que soit la valeur que nous aurons après avoir traversé tous les nœuds, elle ne sera jamais choisie par le nœud maximisateur, puisqu’elle devra être supérieure à 5 pour que cela se produise.
- Ce processus continue pour tous les nœuds restants…
Une bonne implémentation python de cet algorithme, par les auteurs d’un des livres de référence les plus éminents de l’IA, peut être trouvée ici.
Dans la section suivante, d’autres optimisations de cet algorithme alpha-bêta, dont la plupart sont adaptées spécifiquement au jeu connect-four seront discutées. Pour évaluer le gain de performance de chacune des optimisations, nous établirons une base de référence. Nous exprimerons le taux de réussite en fonction du nombre de coups déjà effectués. Une exécution est réussie si la solution a été trouvée en moins d’une seconde. Voici notre tracé de la ligne de base.