Minimax-Algorithmus: Kosten / Auswertungsfunktion?

Question

Ein Schulprojekt hat mir ein Date Spiel in C ++ zu schreiben (zB bei http://www.cut-the-knot.org/Curriculum/Games/Date.shtml ), wo der Computer-Spieler einen Minimax-Algorithmus mit alpha-beta-Suche implementieren müssen. Bis jetzt verstehe ich, was das Ziel hinter dem Algorithmus, der in Bezug auf die Maximierung der potenziellen Gewinne, während der Gegner unter der Annahme wird minify sie.

Doch keine der Ressourcen, die ich half las mir zu verstehen, wie die Bewertungsfunktion zu entwerfen, um die Minimax-Basen alle auf seine Entscheidungen. Alle Beispiele sind beliebige Zahlen mussten den Blattknoten zugewiesen, jedoch muss ich tatsächlich assign sinnvolle Werte zu diesen Knoten.

Intuition sagt mir, es so etwas wie +1 für einen Sieg Blattknoten sein würde, und -1 für einen Verlust, aber wie Zwischenknoten bewerten?

Jede Hilfe wäre am meisten geschätzt.

Answer 1

Die grundlegendsten Minimax auswertet nur Blattknoten, Markierung gewinnt, Verluste und zieht und Rücken, diese Werte auf den Baum der Zwischenknotenwerte zu bestimmen. Im Fall, dass der Spielbaum ist widerspenstig, benötigen Sie eine Cutoff-Tiefe als zusätzlichen Parameter auf Ihre Minimax-Funktionen zu nutzen. Sobald die Tiefe erreicht ist, müssen Sie irgendeine Art von Bewertungsfunktion für unvollständige Staaten ausgeführt werden.

Die meisten Auswertungsfunktionen in einer Minimax-Suche sind domänenspezifische, so Hilfe für Ihr bestimmtes Spiel zu finden, kann schwierig sein. Denken Sie daran, dass die Bewertung eine Art von Prozentsatz Erwartung der Position ein Gewinn für einen bestimmten Spieler zurückgeben muss sein (in der Regel max, aber nicht, wenn eine negamax Implementierung verwendet wird). So gut wie jede weniger erforscht Spiel wird genau ein anderes mehr erforscht Spiel ähneln. Diese eine Bande in sehr eng mit dem Spiel Pickup-Sticks . Mit Minimax und Alpha-Beta nur, ich würde vermuten, das Spiel lenkbar ist.

Wenn Sie müssen eine Bewertungsfunktion für nicht Endpositionen schaffen, ist hier ein wenig Hilfe bei der Analyse des Spiels Sticks, die Sie, wenn sein nützlich für das Datum Spiel entscheiden kann oder nicht.

Starten der Suche nach einem Weg, um ein Ergebnis zu erzwingen, indem Sie an einer terminalen Position suchen und alle Züge, die zu dieser Position führen können. Im Stick Spiel ist ein Terminal Position mit 3 oder weniger Sticks auf dem letzten Zug bleiben. Die Position, die unmittelbar, dass die Terminalposition geht deshalb verlässt 4 klebt an deinen Gegner. Das Ziel ist nun deinen Gegner mit 4 Stöcken lassen, egal was, und das kann von entweder 5, 6 oder 7-Sticks zu Ihnen gelassen wird getan werden, und Sie mögen, dass Ihre Gegner zwingen, in einer dieser Positionen zu verlassen. Der Ort, um Ihre Gegner in sein muss, um für Sie in entweder 5 sein, 6 oder 7 ist 8. Setzen Sie diese Logik weiter und so ein Muster sehr schnell verfügbar wird. Immer dein Gegner mit einer Reihe durch 4 teilbar verlassen und Sie gewinnen, alles andere, Sie verlieren.

Dies ist ein ziemlich trivial Spiel, aber das Verfahren zur Bestimmung der Heuristik ist, was wichtig ist, weil es direkt auf Ihre Zuordnung angewandt werden kann. Da der letzte Schritt zuerst geht, und Sie können nur 1 Tag zu einem Zeitpunkt Attribut ändern, wissen Sie, es zu gewinnen sein muss genau 2 bewegt sich nach links ... und so weiter.

Viel Glück, lassen Sie uns wissen, was Sie am Ende tun.

Answer 2

Der einfachste Fall einer Bewertungsfunktion ist +1 für einen Sieg, -1 für einen Verlust und 0 für jede Nicht-Fertigstellung. Angesichts Ihrem Baum ist tief genug, um selbst diese einfache Funktion gibt Ihnen einen guten Spieler. Für alle nicht-triviale Spiele, mit Faktor hohe Verzweigung, in der Regel müssen Sie eine bessere Funktion, mit einigen Heuristiken (beispielsweise für Schach Sie Gewichte in Stücke zuordnen konnte und eine Summe finden, etc.). Im Fall des Date-Spiels, würde ich nur die einfachste Bewertungsfunktion, mit 0 für alle die Zwischenknoten.

Als Randbemerkung, ist Minimax nicht der beste Algorithmus für dieses spezielle Spiel; aber ich denke, Sie wissen es schon.

Answer 3

Von dem, was ich von dem Date Spiel verstehen Sie verbunden sind, scheint es, dass die einzigen möglichen Ergebnisse für einen Spieler zu gewinnen oder verlieren, gibt es nicht zwischendurch (bitte korrigiert mich wenn ich falsch liege).

In diesem Fall ist es nur eine Frage der einen Wert von 1 zu einer Gewinnposition zuweisen (aktueller Spieler erhält bis 31. Dezember) und ein Wert von -1 bis die Verlustpositionen (andere Spieler erhält bis 31. Dezember).

Ihr Minimax-Algorithmus (ohne Alpha-Beta-Suche) würde wie folgt aussehen:

A_move(day):
   if day==December 31:
       return +1
   else:
       outcome=-1
       for each day obtained by increasing the day or month in cur_date:
           outcome=max(outcome,B_move(day))
       return outcome

B_move(day):
   if day==December 31:
       return -1
   else:
       outcome=+1
       for each day obtained by increasing the day or month in cur_date:
           outcome=min(outcome,A_move(day))
       return outcome