Algorithmus für das Spiel von Chomp

Question

Ich schreibe ein Programm für das Spiel von Chomp. Sie können die Beschreibung des Spiels lesen Wikipedia, Ich werde es jedoch sowieso kurz beschreiben.

Wir spielen auf einer Schokoladentafel mit NXM, dh die Bar ist in NXM -Quadraten geteilt. Bei jedem Runden wählt der aktuelle Spieler ein Quadrat aus und isst alles unten und rechts vom gewählten Quadrat. Zum Beispiel ist Folgendes ein gültiger erster Schritt:

Ziel ist es, Ihren Gegner zu zwingen, das letzte Stück Schokolade zu essen (es ist vergiftet).

In Bezug auf den AI-Teil habe ich einen Minimax-Algorithmus mit Tiefenverhandlung verwendet. Ich kann jedoch keine geeignete Positionsbewertungsfunktion finden. Das Ergebnis ist, dass es für einen menschlichen Spieler mit meiner Bewertungsfunktion für mein Programm recht einfach ist.

Kann jemand:

• eine gute Position Bewertung vorschlagen oder
• geben eine nützliche Referenz oder
• einen alternativen Algorithmus vorschlagen?

Answer 1

Wie groß sind deine Boards?

Wenn Ihre Boards ziemlich klein sind, können Sie das Spiel genau mit dynamischer Programmierung lösen. In 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))

Die Funktion Wins (Board) berechnet, ob das Board eine Gewinnposition ist. Die Board -Darstellung ist eine Reihe von Tupeln (x, y), die angeben, ob das Stück (x, y) noch auf der Tafel ist. Die Funktionsbewegungen berechnen die Liste der in einem Schritt erreichbaren Boards.

Die Logik hinter der Siegesfunktion funktioniert wie diese. Wenn das Board auf unserem Umzug leer ist, muss der andere Spieler das letzte Stück gegessen haben, also haben wir gewonnen. Wenn das Board nicht leer ist, können wir gewinnen, wenn es vorhanden ist any Bewegen können wir so tun, dass die resultierende Position eine verloren not wins(move)), weil wir dann den anderen Spieler in eine verlorene Position gebracht haben.

Sie benötigen auch die Memoize -Helferfunktion, die die Ergebnisse zwischengespeichert:

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

Durch das Zwischenspeichern berechnen wir nur, wer der Gewinner für eine bestimmte Position ist, auch wenn diese Position auf verschiedene Weise erreichbar ist. Zum Beispiel kann die Position einer einzigen Schokoladenreihe erhalten werden, wenn der erste Spieler in seinem ersten Schritt alle verbleibenden Zeilen isst, aber er kann auch durch viele andere Reihe von Bewegungen erhalten werden. Es wäre verschwenderisch zu berechnen, wer immer wieder auf der einzelnen Zeilenplatine gewinnt, also zwischenspeichern wir das Ergebnis. Dies verbessert die asymptotische Leistung von so etwas wie O((n*m)^(n+m)) zu O((n+m)!/(n!m!)), eine enorme Verbesserung, obwohl für große Bretter immer noch langsam.

Und hier ist eine Debugging -Druckfunktion aus Gründen der Bequemlichkeit:

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

Dieser Code ist immer noch ziemlich langsam, da der Code in keiner Weise optimiert ist (und dies ist Python ...). Wenn Sie es effizient in C oder Java schreiben, können Sie wahrscheinlich die Leistung über 100 Falten verbessern. Sie sollten leicht in der Lage sein, 10x10 Boards zu handhaben, und wahrscheinlich können Sie bis zu 15x15 Boards verarbeiten. Sie sollten auch eine andere Board -Darstellung verwenden, zum Beispiel ein Bit -Board. Vielleicht könnten Sie sogar 1000x beschleunigen, wenn Sie mehrere Prozessoren verwenden.

Hier ist eine Ableitung von Minimax

Wir beginnen mit 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

Wir können die Tiefenprüfung entfernen, um eine vollständige Suche durchzuführen:

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

Da das Spiel endete, wird Heuristic entweder -1 oder 1 zurückkehren, je nachdem, welchen Spieler gewonnen hat. Wenn wir -1 als falsch und 1 als wahr darstellen, dann dann max(a,b) wird a or b, und -a wird 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

Sie können sehen, dass dies entspricht:

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

Wenn wir stattdessen mit Minimax mit Alpha-Beta-Beschneidung angefangen hatten:

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)

Die Suche beginnt mit Alpha = -1 und Beta = 1. Sobald Alpha 1 wird, bricht die Schleife. Wir können also annehmen, dass Alpha -1 und Beta 1 in den rekursiven Anrufen bleiben. Der Code entspricht also:

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)

So können wir einfach die Parameter entfernen, da sie immer als die gleichen Werte übergeben werden:

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)

Wir können wieder den Schalter von -1 und 1 zu Booleschen machen:

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

Sie können also sehen, dass dies gleichwertig der Verwendung eines Generators mit einem Generator entspricht, der die Iteration stoppt, sobald sie einen echten Wert gefunden hat, anstatt immer die gesamte Liste der Kinder zu berechnen:

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

Beachten Sie, dass wir hier haben any(not alphabeta(move) for move in moves(board)) Anstatt von any([not minimax(move) for move in moves(board)]). Dies beschleunigt die Suche um etwa den Faktor 10 für vernünftige Boards. Nicht weil die erste Form schneller ist, sondern weil wir es uns ermöglichen, den gesamten Rest der Schleife einschließlich der rekursiven Anrufe zu überspringen, sobald wir einen Wert gefunden haben, der wahr ist.

Da haben Sie es also, die Siegenfunktion war nur Alphabeta -Suche in Verkleidung. Der nächste Trick, den wir für Siege verwendet haben, ist die Memoisierung. In der Spielprogrammierung würde dies mit "Transpositionstabellen" bezeichnet. Die WINS -Funktion führt also Alphabeta -Suche mit Transpositionstabellen durch. Natürlich ist es einfacher, diesen Algorithmus direkt aufzuschreiben, anstatt diese Ableitung zu durchlaufen;)

Answer 2

Ich denke nicht, dass hier eine gute Positionsbewertungsfunktion möglich ist, da es im Gegensatz zu Spielen wie Schach keinen „Fortschritt“ gibt, der nicht gewinnt oder verliert. Der Artikel von Wikipedia schlägt vor, dass eine umfassende Lösung für moderne Computer praktisch ist, und ich denke, dass dies bei geeigneter Memoisierung und Optimierung der Fall ist.

Ein verwandtes Spiel, das Sie möglicherweise von Interesse finden, ist Nim.