Beispiele für computergestützte optimale Strategien in Spielen

Ich suche nach Beispielen in Spielen wie Go, Chess und Backgammon, bei denen sich der als optimal erachtete Zug als suboptimal herausstellte, da ein Computer bessere Strategien gefunden hat.

Das bekannteste Beispiel sind wahrscheinlich Checkers (auch als Drafts bekannt ), die vor kurzem im Jahr 2007 gelöst wurden (das Spiel ist ein Unentschieden). Weitere Beispiele finden Sie auf der Wikipedia-Seite zu gelösten Spielen . Bemerkenswert unter ihnen sind vier und neun Männer Morris verbinden . Zusätzlich wurden mehrere Schachendspiele gelöst.

Dies scheint vielleicht keine Antwort auf Ihre Frage zu sein, aber wenn ein Experte (wie Marion Tinsley ) gegen ein Computerprogramm verliert, muss der Computer einen "optimaleren" Zug gefunden haben.

Siehe Wolfe und Berlekamp - Mathematical Go . Mithilfe von Conways Spieltheorie zeigen sie, wie bestimmte Arten von Go-Endspielen analysiert werden. Ihre Lösungen erweisen sich als messbar besser als die Lösungen der Top-Go-Spieler. (Keine Antwort auf Ihr Problem, da diese letzteren Lösungen wahrscheinlich nie als optimal bezeichnet wurden.)

Schach-Endgame-Techniken wurden durch das Aufkommen von Endgame-Tabellen erheblich verbessert. Endgame-Tabellen sind Nachschlagetabellen, die Schach lösen, wenn sich nicht mehr als (derzeit) sieben Teile auf dem Brett befinden. Hier ist eine Online-Tabellenbasis, die ich in der Vergangenheit verwendet habe und die für bis zu sechs Teile geeignet ist.

Algorithmisch sind diese Tabellenbasen nicht sehr interessant; Sie werden hauptsächlich durch rohe Gewalt erzeugt. Sie haben jedoch zu mehreren Aspekten der Endgame-Theorie beigetragen. Wikipedia hat hier eine schöne Zusammenfassung einiger interessanter Punkte .

Diese Entdeckungen hatten auch Auswirkungen auf die "Fünfzig-Züge-Regel", die besagt, dass nach fünfzig Zügen ohne Eroberung oder Bauernvorschuss jeder Spieler ein Unentschieden beanspruchen kann. Noch vor der Computeranalyse wurde angenommen, dass mehrere Endspiele mehr als fünfzig Züge benötigen, und die Regel wurde unter diesen Umständen leicht erweitert (das wahrscheinlich berühmteste ist das Endspiel Turm und Bischof gegen Turm ). Als die Anzahl der Positionen, die diese Züge erforderten, größer wurde, wurden diese Erweiterungen entfernt und die normale 50-Züge-Regel wurde in allen Fällen wieder eingeführt. Moderne Analysen haben gezeigt, dass einige Endspiele mehrere hundert Züge benötigen .

Dies ist ein weiterer interessanter Artikel, der einige Auswirkungen von siebenteiligen Tabellen auf die Endgame-Theorie zusammenfasst. Besonders gut gefällt mir der in der letzten Position gezeigte gegenseitige Zugzwang.

Es ist keine richtige "Spielstrategie", doch 2010 stellten Tomas Rokicki, Herbert Kociemba, Morley Davidson und John Dethridge fest, dass alle Rubik-Würfelpositionen mit maximal 20 Gesichtsumdrehungen mithilfe eines computergestützten Beweises gelöst werden können [1]. ... ein schönes Ergebnis.

Der kommentierte Quellcode ist unter http://cube20.org/src/ verfügbar .

Die durchschnittliche Anzahl von Zügen, die mit Standardlösungsmethoden ausgeführt werden, beträgt ~ 50-60, aber es gibt auch eine offizielle Ruhmeshalle für "wenige Züge" :

  #player          #moves
1 Tomoaki Okayama  20  Japan    Czech Open 2012     
2 Moritz Karl      21  Germany  BW Open 2013     
3 István Kocza     22  Hungary  Czech Open 2010     
  Jimmy Coll       22  Belgium  Barcelona Open 2009     
5 Adrian Lehmann   23  Germany  German Open 2013

(Beachten Sie, dass die Obergrenze von 20 im Jahr 2012 nur einmal erreicht wurde ... also sind Menschen in Rubiks Würfel-Meisterschaften weit davon entfernt, die "optimale Strategie" zu spielen :)

[1] Tomas Rokicki, Herbert Kociemba, Morley Davidson und John Dethridge: Der Durchmesser der Rubik's Cube Group beträgt 20. SIAM J. Discrete Math. 27 (2): 1082 & ndash; 1105 (2013)