Minimax-Algorithmus

Question

Ich habe eine einfache Frage in Bezug auf dem Minimax-Algorithmus: zum Beispiel für das Tic-Tac-Toe-Spiel, wie bestimme ich die Nutzenfunktion für jeden Spieler spielt das? Es macht das nicht automatisch, nicht wahr? Ich muss hart Code die Werte im Spiel, es ist nicht sie selbst lernen kann, nicht wahr?

Answer 1

Nein, ein MiniMax lernt nicht. Es ist eine intelligentere Version einer Brute-Force-Baumsuche.

Answer 2

Normalerweise würden Sie die Nutzenfunktion direkt implementieren. In diesem Fall würde der Algorithmus nicht lernen, wie man das Spiel zu spielen, wäre es die Informationen, die Sie bei der Implementierung explizit hartcodiert hatten.

Allerdings wäre es möglich, genetische Programmierung (GP) oder eine äquivalente Technik abzuleiten automatisch eine Nutzenfunktion. In diesem Fall würden Sie keine explizite Strategie codieren müssen. Statt die Entwicklung würde auch seine eigene Art und Weise des Spielens des Spiels entdecken.

Sie können entweder kombinieren Sie Ihren Minimax-Code und den GP-Code in ein einziges (wahrscheinlich sehr langsam) adaptives Programm, oder man konnte die GP ersten, finden Sie eine gute Nutzenfunktion und fügen Sie dann diese Funktion, um Ihren Minimax-Code nur, wie Sie laufen würde jede Hand codierte Funktion.

Answer 3

Tic-Tac-Toe klein genug ist, um das Spiel zu Ende und assign 1 Sieg, 0 für Unentschieden und -1 für verlieren laufen.

Ansonsten haben Sie eine Funktion zur Verfügung zu stellen, die den Wert einer Position bestimmt heuristisch. Im Schach zum Beispiel ein großer Faktor ist der Wert des Materials, sondern auch, wer kontrolliert die Mitte oder wie leicht die Stücke bewegen.

Wie für das Lernen, können Sie Gewichtungsfaktoren auf die verschiedenen Aspekte der Position hinzufügen und versuchen, diese durch wiederholtes Spielen zu optimieren.

Answer 4

Wie funktioniert die Nutzenfunktion für jedes Spiel bestimmen?

vorsichtig ;-) Diese Artikel zeigt, wie eine leicht fehlerhaft Bewertungsfunktion (ein für ex., die entweder nicht geht „tief“ genug nach vorn schaut in dem Baum der möglichen Lagen, oder eine, die die relativen strengh einiger Vorstandspositionen erfassen ausfällt) führt zu einem insgesamt schwachen Algorithmus (ein, dass Lose häufiger).

es kann sie nicht lernen, indem sie selbst, nicht wahr?

Nein, tut es nicht. Es gibt Möglichkeiten, aber den Computer, um die relative Stärke der Vorstandspositionen lernen. Zum Beispiel, indem Sie in Donald Mitchie und sein MENACE Programm Sie werden sehen, wie ein stochastischer Prozess verwendet werden kann, das Board ohne a priori Wissen, sondern die Regeln des Spiels zu lernen. Das lustige daran ist, dass, während dies in Computern implementiert werden, ein paar hundert farbigen Perlen und Zündholzschachteln sind alle, die erforderlich ist, dank der relativ geringen Größe des Spielraums, und auch dank verschiedener Symmetrien.

Nach dem Lernen so eine coole Art und Weise, den Computer des Unterrichtens, wie zu spielen, können wir nicht so in zurück zu MinMax geht interessiert sein als an Tic-Tac-Toe angewandt. Schließlich MinMax ist eine relativ einfache Art und Weise einen Entscheidungsbaumes der Beschneidung , die kaum mit Tic-Tac-Toe kleinem Spielraum benötigt wird. Aber, wenn wir müssen ;-) [zum MinMax zurück] ...

Wir können den „Zündholzschachtel“ Blick in Zusammenhang mit dem nächsten Spiel (das heißt nicht tief überhaupt geht), und verwenden Sie den Prozentsatz der Kügelchen, die mit jedem Quadrat verbunden ist, als ein zusätzlicher Faktor. Wir können beurteilen dann einen traditionellen Baum, aber nur gehen, sagen wir 2 oder 3 bewegt sich tief (eine flache Vorgriffstiefe, die typischerweise in der Regel in Verluste oder zieht enden in würde) und bewerten jeden nächsten Schritt auf der Grundlage der einfachen -1 ( Verlust), 0 (Unentschieden / unbekannt), +1 (win) Bewertung. Durch die dann die Perlen Prozentsatz kombiniert und die einfache Bewertung (von sagen wir zusätzlich, schon gar nicht durch Multiplikation), sind wir in der Lage, effektiv MinMax in einer Art und Weise zu verwenden, die eher an die Art und Weise ist es in den Fällen verwendet, wenn es nicht möglich ist, zu beurteilen der Spielbaum zu Ende.

Fazit: Im Fall von Tic-Tac-Toe, MinMax wird nur noch interessanter (zum Beispiel, uns zu helfen, die Wirksamkeit einer bestimmten Nutzenfunktion erkunden), wenn wir die deterministische Natur des Spiels entfernen, im Zusammenhang mit dem einfachen Auswertung der vollständige Baum. Eine weitere Möglichkeit, das Spiel zu machen [mathematisch] interessant ist mit einem Gegner zu spielen, die Fehler macht ...