IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

pyReversi


précédentsommairesuivant

VI. Plate.py

Vous pouvez visualiser le contenu du fichier en cliquant sur le lien Plate.py

Le fichier Plate.py gère le plateau de jeu à travers des fonctions prenant toujours en premier paramètre une liste représentant un plateau de jeu. Initialement, j'avais construit ce module à travers une classe Plate, mais je me suis aperçu finalement que l'IA, qui devait effectuer de nombreuses copies en particulier d'objets de cette classe, était grandement accélérée en utilisant plutôt directement des fonctions et juste une liste pour le plateau de jeu. J'ai finalement opté pour la suppression de la classe pour ne conserver que des fonctions qui s'appliquent sur un objet list que l'on doit fournir en paramètre à chaque appel. Finalement, on y gagne tout de même un facteur 2 au niveau de la réflexion de l'ordinateur. Le plateau de jeu de 8x8 cases est géré à travers une liste de 100 éléments en ayant ajouté au préalable une bordure pour éviter que certains tests se fassent en dehors du plateau de jeu.
Ainsi, la case du plateau en haut à gauche est la 12e case de la liste (numéro 11), quand on se déplace sur le plateau d'une case à droite, on avance d'une case dans la liste et quand on se déplace sur le plateau d'une case vers le bas, on avance de 10 cases dans la liste.

Méthodes principales applicables sur une liste représentant le plateau de jeu :

  • TestLeClic(Plate, r, joueur) : teste si le coup r par le joueur joueur est acceptable (en vérifiant que la case r est vide) ;
  • TestLeClic2(Plate, r, joueur) : teste si le coup r par le joueur joueur est acceptable (sans vérifier que la case r est vide) ;
  • DoitPasser(Plate, joueur) : indique si le joueur ne peut pas joueur à son tour de jeu ;
  • MovePossible(Plate, joueur) : donne la liste des coups jouables ;
  • Reverse(Plate, r, joueur) : effectue le coup r par le joueur joueur ;
  • Score(Plate) : retourne le score (au niveau nombre de pions) de la partie en cours ;
  • ScoreMove(Plate) : retourne le score d'une position de jeu à partir du calcul de différents paramètres.

Pour construire le plateau de jeu, on l'initialise avec la constante PLATEINIT ou bien on fait une copie du plateau précédent plate[:]. La liste est représentée avec les chiffres 0, 1, 2 et 3 :

  • 0 si la case est vide ;
  • 1 si la case est prise par un pion noir ;
  • 2 si la case est prise par un pion blanc ;
  • 3 si la case est en dehors du plateau de jeu.

Initialement, seules les quatre cases du centre ont un pion dessus.

VI-1. TestLeClic(Plate, r, joueur) et TestLeClic2(Plate, r, joueur)

Cette fonction indique si le coup r (r étant compris entre 11 et 88) joué par le joueur joueur est acceptable. Pour cela, il suffit de vérifier que le coup permet au joueur joueur de retourner au moins un pion adverse en testant donc toutes les directions.
Dans le cas de TestLeClic, on vérifie avant tout que la case est vide, ce qu'on ne fait pas dans TestLeClic2 (ce qui peut nous permettre de gagner un peu de temps lors de la réflexion de l'ordinateur).

 
Sélectionnez
def TestLeClic(Plate, r, joueur):
    if Plate[r] == 0: 
        jou = 3 - joueur
        k = r-1
        if Plate[k] == jou:
            k -= 1
            while Plate[k] == jou: k -= 1
            if Plate[k] == joueur: return True

        k = r+1
        if Plate[k] == jou:
            k += 1
            while Plate[k] == jou: k += 1
            if Plate[k] == joueur: return True

        k = r-10
        if Plate[k] == jou:
            k -= 10
            while Plate[k] == jou: k -= 10
            if Plate[k] == joueur: return True

        k = r+10
        if Plate[k] == jou:
            k += 10
            while Plate[k] == jou: k += 10
            if Plate[k] == joueur: return True

        k = r-11
        if Plate[k] == jou:
            k -= 11
            while Plate[k] == jou: k -= 11
            if Plate[k] == joueur: return True                

        k = r+11
        if Plate[k] == jou:
            k += 11
            while Plate[k] == jou: k += 11
            if Plate[k] == joueur: return True                

        k = r - 9
        if Plate[k] == jou:
            k -= 9
            while Plate[k] == jou: k -= 9
            if Plate[k] == joueur: return True                

        k = r+9
        if Plate[k] == jou:
            k += 9
            while Plate[k] == jou: k += 9
            if Plate[k] == joueur: return True                
            
    return False

VI-2. DoitPasser(Plate, joueur) et MovePossible(Plate, joueur)

La fonction DoitPasser(Plate, joueur) vérifie si le joueur joueur peut jouer, donc s'il existe au moins une case qui permette au joueur de retourner des pions adverses.

La fonction MovePossible(Plate, joueur) retourne la liste de tous les coups possibles pour le joueur joueur

 
Sélectionnez
def DoitPasser(Plate, joueur):
    for r in glovar['freemove']:
         if TestLeClic(Plate, r, joueur): return False
    return True

def MovePossible(Plate, joueur):
    return [r for r in glovar['freemove'] if TestLeClic(Plate, r, joueur)]

VI-3. Reverse(Plate, r, joueur)

Cette fonction pose un pion de la couleur du joueur joueur sur la case r et retourne les autres pions en conséquence. On teste ainsi, dans les huit directions, s'il est possible de retourner ou non des pions adverses.

 
Sélectionnez
def Reverse(Plate, r, joueur):
    jou = 3 - joueur
    Plate[r] = joueur
    k = r-1
    while Plate[k] == jou: k -= 1
    if Plate[k] == joueur:
        k += 1
        while Plate[k] == jou:
            Plate[k] = joueur
            k += 1
            
    k = r+1
    while Plate[k] == jou: k += 1
    if Plate[k] == joueur:
        k -= 1
        while Plate[k] == jou:
            Plate[k] = joueur
            k -= 1

    k = r-10
    while Plate[k] == jou: k -= 10
    if Plate[k] == joueur:
        k += 10
        while Plate[k] == jou:
            Plate[k] = joueur
            k += 10
            
    k = r+10
    while Plate[k] == jou: k += 10
    if Plate[k] == joueur:
        k -= 10
        while Plate[k] == jou:
            Plate[k] = joueur
            k -= 10

    k = r-11
    while Plate[k] == jou: k -= 11
    if Plate[k] == joueur:
        k += 11
        while Plate[k] == jou:
            Plate[k] = joueur
            k += 11
            
    k = r+11
    while Plate[k] == jou: k += 11
    if Plate[k] == joueur:
        k -= 11
        while Plate[k] == jou:
            Plate[k] = joueur
            k -= 11

    k = r-9
    while Plate[k] == jou: k -= 9
    if Plate[k] == joueur:
        k += 9
        while Plate[k] == jou:
            Plate[k] = joueur
            k += 9
            
    k = r+9
    while Plate[k] == jou: k += 9
    if Plate[k] == joueur:
        k -= 9
        while Plate[k] == jou:
            Plate[k] = joueur
            k -= 9

VI-4. Score(Plate)

Cette fonction retourne le nombre de pions de chaque joueur et permet donc d'avoir le score actuel de la partie.

 
Sélectionnez
def Score(Plate):
    return Plate.count(1), Plate.count(2)

VI-5. Calcul du score d'une position

La réflexion de l'ordinateur est développée par l'algorithme alpha bêta. Celui-ci repose sur le calcul de la valeur (ou score) de la position étudiée du plateau. Le calcul du score d'une position du plateau se fait soit par la fonction Score(Plate) qui retourne basiquement le nombre de pions de chaque joueur soit par la méthode ScoreMove(Plate) qui calcule différents paramètres du jeu et retourne un tuple représentant le score de chaque joueur.
Cette dernière fonction va se servir de plusieurs paramètres :

  • le nombre de pions de chaque joueur ;
  • la valeur des cases sur lesquelles reposent les pions du plateau ;
  • le nombre de coups jouables par chaque joueur ;
  • le nombre de cases imprenables de chaque joueur.

Cette fonction étant très souvent appelée dans la réflexion de l'ordinateur (à chaque feuille de l'arbre d'une série de coups), il est important que celle-ci soit la plus optimisée possible. Il est important de calculer un maximum de paramètres pour obtenir le score le plus réaliste pour la position étudiée du plateau sans pour autant trop en faire pour ne pas perdre trop de temps. Il peut ainsi être plus intéressant de pouvoir augmenter la profondeur de la réflexion en contrepartie d'une fonction du calcul du score d'une position moins ambitieuse.
Je me suis contenté des quatre éléments précédents auxquels j'affecte un coefficient multiplicatif (arbitraire choisi après quelques tests expérimentaux).

Le score de chaque joueur est enregistré dans les variables locales BScore et WScore.

L'algorithme est le suivant :

  • on commence par compter le nombre de pions de chaque joueur ( BScore, WScore = Score(Plate) ) ;
  • si l'un des deux joueurs n'a plus de pion sur le plateau, le joueur adverse gagne et on retourne directement +INFINITY et 0 pour le perdant ;
  • puis on calcule les trois derniers paramètres que l'on ajoute au score de chaque joueur.
 
Sélectionnez
def ScoreMove(Plate):
    BScore, WScore = Score(Plate)
    if BScore == 0 or WScore == 0: return (WScore == 0) * INFINITY, (BScore == 0) * INFINITY
    BScore *= -1
    WScore *= -1
    jou1, jou2 = TabJouable(Plate)
    BScore += 2 * jou1
    WScore += 2 * jou2
    for r in PLATEMOVE:
        if Plate[r] == 1: BScore += TABVALUE[r]
        elif Plate[r] == 2: WScore += TABVALUE[r]
    imp1, imp2 = TabImprenable(Plate)
    BScore += 3 * imp1
    WScore += 3 * imp2                    
    return BScore, WScore

Vous pourrez ainsi créer d'autres fonctions de calcul du score d'une position en changeant soit les constantes multiplicatives soit en calculant d'autres paramètres et confronter les différentes fonctions en faisant jouer deux ordinateurs.

VI-5-1. Valeur d'une case du plateau de jeu

Chaque case possède une valeur qui détermine s’il est intéressant ou non d'avoir un pion dessus. Ces valeurs sont définies dans la liste constante TABVALUE. Ainsi, les quatre coins sont bien cotés (+20) :

 
Sélectionnez
TABVALUE = [0,  0,  0,  0,  0,  0,  0,  0,  0, 0,
            0, 20, -3, -1, -1, -1, -1, -3, 20, 0,
            0, -3, -6, -2, -2, -2, -2, -6, -3, 0,
            0, -1, -2,  0,  0,  0,  0, -2, -1, 0, 
            0, -1, -2,  0,  0,  0,  0, -2, -1, 0,
            0, -1, -2,  0,  0,  0,  0, -2, -1, 0,
            0, -1, -2,  0,  0,  0,  0, -2, -1, 0,
            0, -3, -6, -2, -2, -2, -2, -6, -3, 0,
            0, 20, -3, -1, -1, -1, -1, -3, 20, 0,
            0,  0,  0,  0,  0,  0,  0,  0,  0, 0]

J'ai choisi une constante, mais on aurait très bien pu prendre des valeurs variant en fonction de l'avancée de la partie.

VI-5-2. TabJouable(Plate)

TabJouable(Plate) retourne pour chaque joueur, le nombre de coups jouables (s'il jouait au prochain tour, mais cette valeur n'est en fait effective que pour le joueur qui aurait la main).

 
Sélectionnez
def TabJouable(Plate):
    j1 = 0
    j2 = 0
    for r in glovar['freemove']:
        if Plate[r] == 0:
            j1 += TestLeClic2(Plate, r, 1)
            j2 += TestLeClic2(Plate, r, 2)                
    return j1, j2

VI-5-3. TabImprenable(Plate) et ExisteImprenable(Plate, r)

Pour chaque case du plateau, si un pion est dessus, on teste si celui-ci est entièrement protégé, c'est-à-dire qu'il est entouré dans les 8 directions par un pion adverse ou un bord.
Ce calcul peut ne pas être pertinent et peut-être qu'on peut sans passer pour gagner du temps dans le calcul du score (notamment en début de partie).

 
Sélectionnez
def TabImprenable(Plate):
    j1 = 0
    j2 = 0
    for r in PLATEMOVE:
        if Plate[r] == 1: j1 += IsImprenable(Plate, r)
        elif Plate[r] == 2: j2 += IsImprenable(Plate, r)
    return j1, j2

def IsImprenable(Plate, r):
    
    jou = Plate[r]
    other = 3-jou

    k = r - 10
    while Plate[k] == jou: k -= 10
    if Plate[k] == 0 or Plate[k] == other:
        sidel = Plate[k]
        k = r + 10
        while Plate[k] == jou: k += 10
        if Plate[k] == 0 or (Plate[k] == other and sidel == 0): return False

    k = r - 1
    while Plate[k] == jou: k -= 1
    if Plate[k] == 0 or Plate[k] == other:
        sidel = Plate[k]
        k = r + 1
        while Plate[k] == jou: k += 1
        if Plate[k] == 0 or (Plate[k] == other and sidel == 0): return False
    

    k = r - 11
    while Plate[k] == jou: k -= 11
    if Plate[k] == 0 or Plate[k] == other:
        sidel = Plate[k]
        k = r + 11
        while Plate[k] == jou: k += 11
        if Plate[k] == 0 or (Plate[k] == other and sidel == 0): return False
       

    k = r - 9
    while Plate[k] == jou: k -= 9
    if Plate[k] == 0 or Plate[k] == other:
        sidel = Plate[k]
        k = r + 9
        while Plate[k] == jou: k += 9
        if Plate[k] == 0 or (Plate[k] == other and sidel == 0): return False
    
    return True

précédentsommairesuivant

Copyright © 2008 Guillaume Duriaud. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.