Cette dernière étape du projet sur le Puissance 4 se consacre à l'optimisation de votre code. Vous trouverez sur cette page des idées de techniques à explorer pour faire en sorte de rendre votre code plus efficace.
Une opération réalisée à de nombreuse reprises par votre code est la détection de lignes, colonnes et diagonales de longueur recherchée (normalement 4). Cette opération est réalisée à chaque fois qu'un coup est joué. Il est donc intéressant d'essayer de réaliser cette tâche de manière efficace.
Pour rappel, cette vérification est faite dans la méthode play de votre classe Board, dans le fichier state.py.
Dans les instructions de la première étape du projet, on vous proposait de vérifier la présence d'un segment gagnant à l'aide de boucles afin de passer en revue les segments de jetons qui incluent le dernier jeton joué.
Une autre façon de procéder consiste à avoir une liste qui maintient un compteur pour chaque segment de la bonne longueur (self.get_connect()) à travers tout le plateau de jeu, et ce peu importe si ces segments sont horizontaux, verticaux ou diagonaux.
Dans la suite, on appelera cette liste self.counts.
En plus de cette liste, une autre structure de données indiquera à quels segments une position appartient. On appelera cette structure self.segments.
L'idée est que lorsqu'une position est jouée, il suffit simplement de regarder à quels segments elle appartient (via self.segments) et d'incrémenter les compteurs appropriés (dans self.counts).
Ces listes seront créées dans le constructeur de la classe Board.
Elles seront donc créées une unique fois, et pas à chaque coup.
Afin de simplifier votre travail, un début d'implémentation vous est proposé ici :
self.counts = []
self.segments = []
# Initialement, chaque position x, y doit avoir une liste vide de segments.
for x in range(0, self.get_width()):
ss = []
for y in range(0, self.get_height()):
ss.append([])
self.segments.append(ss)
next_segment_id = 0 # Le prochain numéro de segment à utiliser.
# Segments horizontaux.
for y in range(0, self.get_height()):
for x in range(0, self.get_width() - self.get_connect() + 1):
for dx in range(self.get_connect()):
self.segments[x + dx][y].append(next_segment_id)
self.counts.append(0)
next_segment_id += 1
# Segments verticaux et en diagonales à implémenter.Restera aussi à utiliser self.counts et self.segments dans vos méthodes play et unplay.
La méthode Alpha-Beta permet d'élaguer un grand nombre de branches lors de l'exploration de l'arbre de jeu. L'idée est d'éviter d'explorer des branches supplémentaires dès le moment qu'elles ne peuvent pas contribuer à changer le résultat.
En plus des paramètres de base utilisé par le Minimax, l'algorithme Alpha-Beta maintient deux paramètres supplémentaires : Alpha et Beta.
Le paramètre Alpha représente le plus petit score que le premier joueur (qui maximise le score) est assuré d'obtenir à ce moment du jeu, et le paramètre Beta représente le plus haut score que le second joueur (qui minimise le score) est assuré d'obtenir.
Initialement, ces deux valeurs sont de -1 pour Alpha et 1 pour Beta.
Lors d'une exploration des enfants d'un noeuds, dès que la valeur d'Alpha dépasse ou égale celle de Beta alors plus rien ne sert d'explorer d'autres enfants. En effet, l'hypothètique valeur des noeuds restant à explorer est forcément soit plus petite qu'Alpha, auquel cas elle ne serait pas prise en compte par le premier joueur, soit plus grande que Beta, auquel cas le second joueur ne la sélectionnerait pas.
Après l'exploration de chaque enfant, les paramètres Alpha et Beta sont mis à jour pour l'exploration des enfants suivants.
Avec Alpha-Beta, l'ordre d'exploration des enfants d'un noeud peut influencer grandement l'efficacité de la recherche. En pratique, il est préférable de tester les meilleurs coups en premier. Pour cette raison, il est avantageux d'explorer les colonnes les plus au centre en premier dans le cadre du Puissance 4.
Lors de votre exploration des différentes parties possibles dans le cadre du Minimax (ou d'Alpha-Beta), il est possible de retomber sur une configuration déjà visitée. Pour éviter de devoir recalculer la valeur du jeu dans une configuration donnée, il est possible de stocker le résultat en mémoire. En Python, on utilisera généralement un dictionnaire pour cela.
cache = {} # Création d'un dictionnaire vide.
cache["key"] = value # Ajout d'une valeur value à la clé "key"
print(cache["key"]) # Récupération d'une valeur à la clé "key"Pour stocker une valeur et la récupérer d'un dictionnaire, il faut passer par une clé. Cette clé peut être un nombre ou une chaîne de caractère, mais pas une liste.
Si vous désirez implémenter cette optimisation, réflechissez à comment concevoir une clé qui correspond à un état de jeu donné.