Algorithme pour le jeu de Chomp

Question

Je suis en train d'écrire un programme pour le jeu de Chomp. Vous pouvez lire la description du jeu sur Wikipedia , mais je vais vous décrire brièvement de toute façon.

On joue sur une tablette de chocolat de dimension n x m, à savoir la barre est divisée en carrés n x m. A chaque tour, le joueur actif choisit un carré et mange tout ci-dessous et à droite de la place choisie. Ainsi, par exemple, ce qui suit est une première valide mouvement:

L'objectif est de forcer votre adversaire à manger le dernier morceau de chocolat (il est empoisonnée).

En ce qui concerne la partie AI, I a utilisé un algorithme Minimax avec troncature de la profondeur. Cependant, je ne peux pas venir avec une fonction d'évaluation de position appropriée. Le résultat est que, avec ma fonction d'évaluation, il est assez facile pour un joueur humain à gagner contre mon programme.

Quelqu'un peut-il:

• suggérer une bonne fonction d'évaluation de position ou
• fournir une référence utile ou
• suggérer un autre algorithme?

Answer 1

Quelle est la taille sont vos conseils?

Si vos cartes sont assez petites, vous pouvez alors résoudre le jeu exactement avec la programmation dynamique. En Python:

n,m = 6,6
init = frozenset((x,y) for x in range(n) for y in range(m))

def moves(board):
    return [frozenset([(x,y) for (x,y) in board if x < px or y < py]) for (px,py) in board]

@memoize
def wins(board):
    if not board: return True
    return any(not wins(move) for move in moves(board))

Les gains de fonction (de bord) calcule si la carte est une position gagnante. La représentation de la carte est un ensemble de tuples (x, y) indiquant si pièce (x, y) est toujours sur le bord. La fonction liste des mouvements des cartes accessibles en un seul mouvement.

La logique derrière la fonction victoires fonctionne comme ça. Si la carte est vide sur notre déménagement l'autre joueur doit avoir mangé le dernier morceau, donc nous avons gagné. Si le conseil n'est pas vide alors nous pouvons gagner s'il y a déplacer any que nous pouvons faire de telle sorte que la position résultante est une position perdante (c.-à ne pas gagner-à-dire not wins(move)), parce que nous avons obtenu l'autre joueur dans une position perdante.

Vous aurez également besoin de la fonction d'assistance memoize qui met en cache les résultats:

def memoize(f):
    cache = dict()
    def memof(x):
        try: return cache[x]
        except:
            cache[x] = f(x)
            return cache[x]
    return memof

Par la mise en cache nous unique- qui est le gagnant pour une position donnée une fois, même si cette position est accessible de plusieurs façons. Par exemple, la position d'une seule rangée de chocolat peut être obtenue si le premier joueur mange tout en restant rangées dans son premier mouvement, mais il peut également être obtenue par d'autres séries de mouvements. Il serait inutile de calculer qui gagne encore et encore sur la carte de ligne unique, de sorte que nous cache le résultat. Cela améliore les performances asymptotique de quelque chose comme O((n*m)^(n+m)) à O((n+m)!/(n!m!)), une grande amélioration mais encore lent pour les grands panneaux.

Et voici une fonction d'impression de débogage pour des raisons pratiques:

def show(board):
    for x in range(n):
        print '|' + ''.join('x ' if (x,y) in board else '  ' for y in range(m))

Ce code est encore assez lent car le code est pas optimisé en aucune façon (ce qui est Python ...). Si vous écrivez en C ou Java, vous pouvez améliorer efficacement les performances probablement plus de 100 fois. Vous devriez facilement pouvoir gérer 10x10 conseils, et vous pouvez probablement gérer jusqu'à 15x15 planches. Vous devez également utiliser une représentation du conseil d'administration différente, par exemple une carte de bits. Peut-être vous même être en mesure d'accélérer 1000x si vous utilisez de plusieurs processeurs.

Voici une dérivation de Minimax

Nous allons commencer par Minimax:

def minimax(board, depth):
  if depth > maxdepth: return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -minimax(move, depth-1))
    return alpha

Nous pouvons supprimer la vérification de la profondeur pour faire une recherche complète:

def minimax(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -minimax(move))
    return alpha

Parce que le jeu est terminé, heuristique retourne soit -1 ou 1, selon le joueur a gagné. Si nous représentons -1 comme faux et 1 vrai, max(a,b) devient a or b et -a devient not a:

def minimax(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = False
    for move in moves(board):
      alpha = alpha or not minimax(move)
    return alpha

Vous pouvez voir cela équivaut à:

def minimax(board):
  if not board: return True
  return any([not minimax(move) for move in moves(board)])

Si nous avions commencé avec la place minimax avec la taille alpha-bêta:

def alphabeta(board, alpha, beta):
  if game_ended(board): return heuristic(board)
  else:
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move, -beta, -alpha))
      if alpha >= beta: break
    return alpha

// start the search:
alphabeta(initial_board, -1, 1)

La recherche commence avec alpha = -1 et bêta = 1. Dès que l'alpha devient 1, les sauts de boucle. On peut donc supposer que les séjours alpha-1 et séjours bêta 1 dans les appels récursifs. Le code est donc équivalent à ceci:

def alphabeta(board, alpha, beta):
  if game_ended(board): return heuristic(board)
  else:
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move, -1, 1))
      if alpha == 1: break
    return alpha

// start the search:
alphabeta(initial_board, -1, 1)

Nous pouvons simplement supprimer les paramètres, car ils sont toujours passés dans les mêmes valeurs:

def alphabeta(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move))
      if alpha == 1: break
    return alpha

// start the search:
alphabeta(initial_board)

Nous pouvons à nouveau faire le passage de -1 et 1 à booléens:

def alphabeta(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = False
    for move in moves(board):
      alpha = alpha or not alphabeta(move))
      if alpha: break
    return alpha

Vous pouvez voir cela équivaut à utiliser tout avec un générateur qui arrête l'itération dès qu'il a trouvé une valeur véritable au lieu de toujours calculer la liste complète des enfants:

def alphabeta(board):
  if not board: return True
  return any(not alphabeta(move) for move in moves(board))

Notez que nous avons ici any(not alphabeta(move) for move in moves(board)) au lieu de any([not minimax(move) for move in moves(board)]). Cela accélère la recherche d'un facteur de 10 pour les cartes de taille raisonnable. Non pas parce que la première forme est plus rapide, mais parce qu'il nous permet de passer toute repos de la boucle, y compris les appels récursifs dès que nous avons trouvé une valeur qui est vrai.

Donc là vous l'avez, la fonction gagne était juste la recherche alphabeta déguisé. Le prochain nous truc utilisé pour des victoires est à memoize il. Dans la programmation de jeu ce serait appelé à l'aide des « tables de transposition ». Ainsi, la fonction gagne fait alphAbeta recherche avec des tables de transposition. Bien sûr, il est plus simple d'écrire cet algorithme directement au lieu de passer par cette dérivation;)

Answer 2

Je ne pense pas une bonne fonction d'évaluation de position est possible ici, parce que contrairement à des jeux comme les échecs, il n'y a pas de « progrès » à court de gagner ou de perdre. L'article de Wikipedia propose une solution exhaustive est pratique pour les ordinateurs modernes, et je pense que vous trouverez c'est le cas, étant donné memoization et l'optimisation appropriée.

Un jeu lié vous pouvez trouver l'intérêt est Nim .