Wie wähle ich den besten Algorithmus für ein Brettspiel wie Checker?

15

Wie wähle ich den besten Algorithmus für ein Brettspiel wie Checker?

Bisher habe ich nur drei Algorithmen betrachtet, nämlich Minimax, Alpha-Beta-Bereinigung und Monte-Carlo-Baumsuche (MCTS). Offensichtlich sind sowohl das Alpha-Beta-Beschneiden als auch das MCTS Erweiterungen des grundlegenden Minimax-Algorithmus.

Joey
quelle

Antworten:

17

tl; dr:

  • Keiner dieser Algorithmen ist praktisch für die moderne Arbeit, aber sie sind gute Orte, um pädagogisch zu beginnen.

  • Sie sollten es immer vorziehen, die Alpha-Beta-Bereinigung anstelle der Minimax-Suche zu verwenden.

  • Sie sollten es vorziehen, eine Form der heuristisch geführten Suche zu verwenden, wenn Sie eine nützliche Heuristik entwickeln können. Das Aufstellen einer nützlichen Heuristik erfordert normalerweise viel Domänenwissen.

  • Sie sollten die Monte-Carlo-Baumsuche vorziehen, wenn Sie keine gute Heuristik haben, wenn die Rechenressourcen begrenzt sind und wenn Fehler keine übergroßen realen Konsequenzen haben.

Mehr Details:

Bei der Minimax-Suche versuchen wir nicht, sehr schlau zu sein. Wir verwenden nur einen dynamischen Standardprogrammieransatz. Es ist einfach, den Wert von Differenzzügen zu ermitteln, wenn wir uns dem Ende des Spiels nähern (da das Spiel im nächsten Zug endet, müssen wir nicht sehr weit nach vorne schauen). Wenn wir wissen, was unser Gegner im letzten Zug des Spiels tun wird, können wir auch leicht herausfinden, was wir im vorletzten Zug tun sollten. Tatsächlich können wir den vorletzten Zug als den letzten Zug eines kürzeren Spiels behandeln. Diesen Vorgang können wir dann wiederholen. Mit diesem Ansatz lassen sich die besten Strategien in einem Standardspiel mit umfangreicher Form aufdecken. Wir müssen jedoch jeden möglichen Zug berücksichtigen, der mit Ausnahme der einfachsten Spiele für alle nicht durchführbar ist.

Alpha-Beta-Bereinigung ist eine strikte Verbesserung der Minimax-Suche. Es macht sich die Tatsache zunutze, dass einige Züge offensichtlich schlechter sind als andere. Zum Beispiel brauche ich beim Schach keinen Zug in Betracht zu ziehen, der Ihnen die Möglichkeit geben würde, mich in einen Schachmatt zu setzen, selbst wenn Sie von dieser Position aus andere Dinge tun könnten. Sobald ich sehe, dass ein Zug zu einer Niederlage führen könnte, werde ich nicht mehr darüber nachdenken, was ab diesem Zeitpunkt noch passieren könnte. Ich werde mich um andere Dinge kümmern. Dieser Algorithmus liefert mit Sicherheit auch das richtige Ergebnis und ist schneller, muss jedoch die meisten Bewegungen in der Praxis berücksichtigen.

Es gibt zwei Möglichkeiten, wie Sie die extremen Rechenaufwendungen für die exakte Lösung dieser Art von Spielen umgehen können:

  1. Verwenden Sie eine Heuristik (A * -Suche ist der übliche Algorithmus für pädagogische Zwecke, aber die Ruhesuche ist eine ähnliche Idee in Spielen für 2 Spieler). Dies ist nur eine Funktion, die eine Schätzung des Wertes eines Zustands des Spiels liefert . Anstatt alle Züge in einem Spiel zu berücksichtigen, können Sie auch nur Züge bis zu einer bestimmten Entfernung in Betracht ziehen und dann den Wert der Heuristik verwenden, um den Wert der erreichten Zustände zu beurteilen. Wenn Ihre Heuristik konsistent ist (im Wesentlichen: wenn sie die Qualität von Zuständen immer überschätzt ), wird dies immer noch die richtige Antwort liefern, jedoch mit enormen Geschwindigkeitssteigerungen in der Praxis.

  2. Verwenden Sie Rollouts (wie Monte Carlo Tree Search). Grundsätzlich sollten Sie, anstatt jeden Zug zu berücksichtigen, ein paar tausend simulierte Spiele zwischen Spielern ausführen, die zufällig handeln (dies ist schneller als alle möglichen Züge). Weisen Sie Zuständen einen Wert zu, der der durchschnittlichen Gewinnrate von Spielen entspricht, die damit beginnen. Dies liefert möglicherweise nicht die richtige Antwort, führt jedoch bei einigen Arten von Spielen zu einer zuverlässigen Leistung. Es wird oft als Erweiterung genauerer Techniken verwendet, anstatt allein verwendet zu werden.

John Doucette
quelle
Ein * scheint nicht wirklich in den Kontext von Zwei-Spieler-Spielen zu passen, wie es die anderen Algorithmen tun? Hinweis zu MCTS: Bei typischen Implementierungen werden nicht alle Bewegungen bis zu einer festgelegten Tiefe berücksichtigt und anschließend die Rollouts gestartet. Stattdessen wird bei typischen Implementierungen der Baumsuchbaum nach und nach dynamisch vergrößert, wobei er in vielversprechenderen Teilen (Teilen, in denen viele Rollouts durch die Auswahlstrategie angestoßen werden) und in den weniger vielversprechenden Teilen weniger vergrößert wird.
Dennis Soemers
1
@JohnDoucette warum würdest du sagen "Keiner dieser Algorithmen ist praktisch für die moderne Arbeit, aber sie sind gute Orte, um pädagogisch anzufangen." Im Fall von MCTS erscheint es für die moderne Arbeit selbst für die Einzelspieler-Suche sehr geeignet, wenn der Übergang zum nächsten Zustand bei gegebenem Zustand und gegebener Aktion genau definiert ist. Würdest du zustimmen?
Miguel Saraiva
1
@MiguelSaraiva MCTS allein ist nichts, was Sie normalerweise für eine moderne Anwendung verwenden würden. Kombiniert mit so etwas wie einem DNN, um eine erlernte Heuristik bereitzustellen, wäre das allerdings ziemlich gut.
John Doucette
1
@JohnDoucette "MCTS wird normalerweise nicht für moderne Anwendungen verwendet." Zuallererst hatte die "Moderne", von der Sie sprechen, 2016 ihren großen Durchbruch (MCTS + DNN) und es scheint, als würden Sie implizieren, dass alles, was vorher war, obsolet ist (offensichtlich falsch). In der Tat könnte es plausibler sein zu sagen, dass MCTS normalerweise nicht verwendet wird, weil das Gegenteil der Fall ist: Es gibt Unmengen von Anwendungen in der Industrie, die wirklich veraltet sind und auf MCTS AKTUALISIERT werden könnten. Für viele von ihnen ist MCTS + DNN nur ein entfernter Traum, da das Vortraining so gut wie undenkbar ist.
Johan
1
@Johan Das klingt für industrielle Anwendungen richtig , aber die Frage ist "ein Brettspiel wie Dame". Für diese Art von Spielzeugproblemen halte ich MCTS nicht für den richtigen modernen Ansatz. Es gibt definitiv viele Probleme in der realen Welt, bei denen es sich jedoch um eine enorme Verbesserung gegenüber vorhandenen implementierten Systemen handelt.
John Doucette
6

NB Der Grund, warum ich mich nur für diese drei Algorithmen entschieden habe, lag an der Zeit, die mir zur Verfügung stand, um sie zu verstehen. Durch ein wenig Recherche habe ich herausgefunden, dass diese Algorithmen im Grunde genommen in den Minimax-Algorithmus verwoben sind. Wenn ich also einen verstehen kann, werden die beiden anderen einfach zusammenpassen.

In diesem Zusammenhang würde ich empfehlen, mit Minimax zu beginnen . Von den drei Algorithmen ist Minimax am einfachsten zu verstehen.

Alpha-Beta ist , wie andere in anderen Antworten erwähnt haben, eine strikte Verbesserung gegenüber Minimax. Minimax ist im Grunde ein Teil der Alpha-Beta-Implementierung, und ein gutes Verständnis von Alpha-Beta erfordert auf jeden Fall ein gutes Verständnis von Minimax. Wenn Sie nach dem Verstehen und Implementieren von Minimax noch Zeit haben, empfehle ich Ihnen, anschließend zu Alpha-Beta überzugehen und diese auf Minimax aufzubauen. Beginnen Sie mit Alpha-Beta, wenn Sie Minimax noch nicht richtig verstanden haben.

Die Monte-Carlo-Baumsuche ist wahrscheinlich etwas fortgeschrittener und komplizierter zu verstehen. In den letzten zehn Jahren ist MCTS tatsächlich sehr viel populärer geworden als die beiden anderen, weshalb das Verständnis von MCTS unter diesem Gesichtspunkt möglicherweise "nützlicher" ist.

Die Verbindung zwischen Minimax und MCTS ist weniger direkt / offensichtlich als die Verbindung zwischen Minimax und Alpha-Beta, aber es gibt immer noch eine Verbindung zumindest auf konzeptioneller Ebene. Ich würde argumentieren, dass es immer noch von Vorteil ist, zuerst ein gutes Verständnis von Minimax zu haben, bevor man in MCTS eintaucht . Insbesondere das Verstehen von Minimax und seinen Fehlern / Schwachstellen kann einen nützlichen Kontext bieten / Ihnen helfen, zu verstehen, warum MCTS "notwendig" / populär wurde.


Abschließend meiner Meinung nach:

  • Alpha-Beta ist strikt besser als Minimax, aber auch stark verwandt / auf Minimax aufgebaut; Fangen Sie also mit Minimax an und starten Sie Alpha-Beta, wenn es die Zeit erlaubt
  • MCTS hat verschiedene Stärken / Schwächen, ist bei "modernen" Problemen oft besser als Alpha-Beta (aber nicht immer). Ein gutes Verständnis von Minimax ist wahrscheinlich von Vorteil, bevor Sie mit MCTS beginnen
Dennis Soemers
quelle
Gibt es einen anderen Algorithmus, den Sie vorschlagen würden, den ich auch verwenden könnte? Das entspricht einem Alpha-Beta-Schnittniveau
Joey
@ Joey Hmm nein nicht wirklich. Minimax ist ein sehr natürlicher Ausgangspunkt. Ich würde es wärmstens empfehlen, wenn Sie gerade erst anfangen. Das war im Grunde der erste Algorithmus, der für Spiele wie Schach / Dame / Tic Tac Toe / was auch immer entwickelt wurde. Danach wurden Hunderte, wenn nicht Tausende von Verbesserungen entwickelt, von denen viele wahrscheinlich unter chessprogramming.wikispaces.com/Search zu finden sind . Alpha-Beta ist die natürlichste Verbesserung, die Sie zusätzlich zu Minimax ausprobieren sollten.
Dennis Soemers
@Joey Monte-Carlo Tree Search ist ein bisschen anders (es muss nicht unbedingt Minimax als Grundlage haben), interessant, unterhaltsam, beliebt und in der "modernen" KI von hoher Relevanz. Dennoch sind Grundlagen wichtig. Ich würde nicht empfehlen, sofort mit MCTS zu beginnen, wenn Sie Minimax + Alpha-Beta noch nicht verstehen, auch wenn dies technisch möglich ist.
Dennis Soemers
Vielen Dank für diese Seite. Es ist eine Fülle von Kenntnissen, die ich jetzt nachlesen kann. Am schwierigsten ist es, das richtige Material zum besseren Verständnis zu finden.
Joey
@Joey Ich bin mir nicht zu 100% sicher, ob Schachprogrammierung die am einfachsten zu erlernende Site ist (und es scheint eine beängstigende Nachricht zu geben, dass die Site Ende Juli möglicherweise verschwindet). Wenn ich mich richtig erinnere, sind viele Beschreibungen ziemlich kurz / wahrscheinlich nicht leicht zu verstehen, wenn Sie ein Anfänger auf dem Gebiet sind. Zumindest wird es eine gute, umfassende Sammlung von Namen für alle Arten von Algorithmen / Verbesserungen sein, und Sie können versuchen, die Originalquellen zu durchsuchen oder alle diese Namen für detailliertere Informationen an anderer Stelle zu googeln.
Dennis Soemers
1

Wenn Sie zwischen Minimax und Alpha-Beta-Schnitt wählen müssen, sollten Sie Alpha-Beta wählen. Es ist effizienter und schneller, da es einen wesentlichen Teil Ihres Erkundungsbaums beschneiden kann. Sie müssen die Aktionen jedoch in Abhängigkeit von der max- oder min-Position von der besten zur schlechtesten sortieren, damit der Algorithmus schnell erkennen kann, ob die Erkundung erforderlich ist.

Kaizokun
quelle