Geh und Mathematik - Go and mathematics

Teil einer Serie über
gehen
Go board part.jpg
Spieldetails
Geschichte und Kultur
Spieler und Organisationen
Computer und Mathematik

Das Spiel Go ist eines der beliebtesten Spiele der Welt. Aufgrund seiner eleganten und einfachen Regeln ist das Spiel seit langem eine Inspiration für die mathematische Forschung. Shen Kuo , ein chinesischer Gelehrter im 11. Jahrhundert, schätzt , dass die Anzahl der möglichen Vorstandspositionen liegt bei etwa 10 172 in The Dream Pool Essays . In den letzten Jahren führte die Erforschung des Spiels von John H. Conway zur Erfindung der surrealen Zahlen und trug zur Entwicklung der kombinatorischen Spieltheorie bei (wobei Go Infinitesimals ein spezifisches Beispiel für seine Verwendung in Go ist).

Rechenkomplexität

Verallgemeinertes Go wird auf n × n Brettern gespielt, und die Rechenkomplexität der Ermittlung des Gewinners in einer gegebenen Position des verallgemeinerten Go hängt entscheidend von den ko-Regeln ab .

Go ist „fast“ in PSPACE , da im normalen Spiel Züge nicht umkehrbar sind und nur durch das Fangen die Möglichkeit besteht, dass sich die für eine härtere Komplexität notwendigen Muster wiederholen.

Ohne ko

Ohne ko ist Go PSPACE-hart . Dies wird bewiesen, indem die True Quantified Boolean Formula , die bekanntermaßen PSPACE-vollständig ist, auf generalisierte Geographie , auf planare generalisierte Geographie, auf planare generalisierte Geographie mit maximalem Grad 3 und schließlich auf Go-Positionen reduziert wird .

Go with superko ist in PSPACE nicht bekannt. Obwohl tatsächliche Partien nie länger als Züge dauern , ist im Allgemeinen nicht bekannt, ob es eine polynomielle Schranke für die Länge von Go-Partien gibt. Wenn ja, wäre Go PSPACE-komplett. So wie es derzeit aussieht, könnte es PSPACE-vollständig, EXPTIME-vollständig oder sogar EXPSPACE-vollständig sein.

Japanische Ko-Regel

Japanische Ko-Regeln besagen, dass nur das grundlegende Ko, dh ein Zug, der das Brett in die Situation einen Zug zuvor zurückversetzt, verboten ist. Längere, sich wiederholende Situationen sind erlaubt, wodurch ein Spiel möglicherweise endlos wiederholt werden kann, wie zum Beispiel das Triple-Ko, bei dem es drei Kos gleichzeitig gibt, was einen Zyklus von 12 Zügen ermöglicht.

Nach japanischen Ko-Regeln ist Go EXPTIME- vollständig.

Superko-Regel

Die Superko-Regel (auch Positions-Superko-Regel genannt) besagt, dass eine Wiederholung einer zuvor aufgetretenen Brettposition verboten ist. Dies ist die Ko-Regel, die in den meisten chinesischen und US-amerikanischen Regelsätzen verwendet wird.

Es ist ein offenes Problem, was die Komplexitätsklasse von Go unter der Superko-Regel ist. Obwohl die Go with Japanese Ko-Regel EXPTIME-vollständig ist, brechen sowohl die untere als auch die obere Grenze von Robsons EXPTIME-Vollständigkeitsbeweis, wenn die Superko-Regel hinzugefügt wird.

Es ist bekannt, dass es zumindest PSPACE-hart ist, da der Beweis der PSPACE-Härte von Go nicht auf der ko-Regel oder dem Fehlen der ko-Regel beruht. Es ist auch bekannt, dass Go in EXPSPACE ist.

Robson zeigte, dass, wenn die Superko-Regel, d. h. „keine vorherige Position darf jemals wiederhergestellt werden“, bestimmten Zwei-Spieler-Spielen hinzugefügt wird, die EXPTIME-vollständig sind, dann die neuen Spiele EXPSPACE-vollständig sind. Intuitiv liegt dies daran, dass selbst für die Bestimmung der legalen Züge aus einer Stellung exponentiell viel Platz benötigt wird, da die Spielgeschichte, die zu einer Stellung führt, exponentiell lang sein könnte.

Als Ergebnis sind Superko-Varianten (Züge, die eine vorherige Brettposition wiederholen, sind nicht erlaubt) von generalisiertem Schach und Dame EXPSPACE-vollständig, da generalisiertes Schach und Dame EXPTIME-vollständig sind. Dieses Ergebnis gilt jedoch nicht für Go.

Komplexität bestimmter Go-Konfigurationen

Ein Go-Endspiel beginnt, wenn das Brett in Bereiche unterteilt ist, die durch lebende Steine ​​von allen anderen lokalen Bereichen isoliert sind, so dass jeder lokale Bereich einen kanonischen Spielbaum von polynomialer Größe hat. In der Sprache der kombinatorischen Spieltheorie geschieht dies, wenn ein Go-Spiel in eine Summe von Teilspielen mit kanonischen Spielbäumen polynomialer Größe zerfällt.

Mit dieser Definition sind Go-Endspiele PSPACE-hart.

Dies wird durch Umwandeln des PSPACE-vollständigen Problems der quantifizierten Booleschen Formel in eine Summe kleiner (mit polynomialer Größe kanonischer Spielbäume) Go-Teilspiele bewiesen. Beachten Sie, dass das Papier nicht beweist, dass Go-Endspiele in PSPACE enthalten sind, sodass sie möglicherweise nicht PSPACE-vollständig sind.

Die Entscheidung, welche Seite ein Ladder- Capture-Rennen gewinnt , ist PSPACE-komplett, unabhängig davon, ob die japanische Ko-Regel oder die Superko-Regel gilt. Dies wird durch die Simulation von QBF, bekannt als PSPACE-komplett, mit Leitern, die wie Lichtstrahlen über das Board hüpfen, bewiesen.

Rechtspositionen

Da jede Stelle auf dem Brett entweder leer, schwarz oder weiß sein kann, gibt es auf einem quadratischen Brett der Länge n insgesamt 3 n 2 mögliche Brettpositionen ; jedoch sind nicht alle von ihnen legal. Tromp und Farnebäck leiteten eine rekursive Formel für die Rechtspositionen eines rechteckigen Bretts der Länge m und n her . Die genaue Anzahl von wurde 2016 ermittelt. Sie finden auch eine asymptotische Formel , wobei , und . Es wurde geschätzt, dass das beobachtbare Universum etwa 10 80 Atome enthält, weit weniger als die Anzahl der möglichen legalen Positionen der regulären Plattengröße (m = n = 19). Wenn das Board größer wird, nimmt der Prozentsatz der legalen Positionen ab.

Plattengröße n×n 3 n 2 Prozent legal (Rechtspositionen) ( A094777 )
1 × 1 3 33,33 % 1
2 × 2 81 70,37% 57
3 × 3 19.683 64,40% 12.675
4 × 4 43.046.721 56,49 % 24.318.165
5 × 5 847.288.609.443 48,90% 414.295.148.741
9 × 9 4.43426488243 × 10 38 23,44% 1.03919148791 × 10 38
13 × 13 4.3002359390 × 10 80 8,66% 3.72497923077 × 10 79
19 × 19 1.74089650659 × 10 172 1,20% 2.08168199382 × 10 170

Komplexität des Spielbaums

Der Informatiker Victor Allis stellt fest, dass typische Spiele zwischen Experten etwa 150 Züge dauern, mit durchschnittlich etwa 250 Wahlmöglichkeiten pro Zug, was auf eine Spielbaumkomplexität von 10 360 hinweist . Für die Anzahl der theoretisch möglichen Spiele, einschließlich der Spiele, die in der Praxis nicht spielbar sind, geben Tromp und Farnebäck Unter- und Obergrenzen von 10 10 48 bzw. 10 10 171 an. Die untere Schranke wurde von Walraet und Tromp zu einem Googolplex verbessert . Die am häufigsten genannte Zahl für die Anzahl der möglichen Partien, 10 700, ergibt sich aus einer einfachen Permutation von 361 Zügen oder 361! = 10 768 . Eine andere übliche Herleitung besteht darin, N Schnittpunkte und L längstes Spiel für N L Gesamtspiele anzunehmen . Zum Beispiel wären 400 Züge, wie sie in einigen professionellen Spielen zu sehen sind, eine von 361 400 oder 1 × 10 1023 möglichen Spielen.

Die Gesamtzahl der möglichen Spiele hängt sowohl von der Größe des Bretts als auch von der Anzahl der gespielten Züge ab. Während die meisten Spiele weniger als 400 oder sogar 200 Züge dauern, sind viel mehr möglich.

Spielgröße Plattengröße N (Kreuzungen) N ! Durchschnittliche Spiellänge L N L Maximale Spiellänge (Anzahl Züge) Untergrenze der Spiele Obergrenze der Spiele
2 × 2 4 24 3 64 386.356.909.593 386.356.909.593
3 × 3 9 3,6 × 10 5 5 5,9 × 10 4
4 × 4 16 2,1 × 10 13 9 6,9 × 10 10
5 × 5 25 1,6 × 10 25 fünfzehn 9,3 × 10 20
9 × 9 81 5,8 × 10 120 45 7,6 × 10 85
13 × 13 169 4,3 × 10 304 90 3,2 × 10 200
19 × 19 361 1,0 × 10 768 200 3 × 10 511 10 48 10 10 48 10 10 171
21 × 21 441 2,5 × 10 976 250 1,3 × 10 661

Die Gesamtzahl der möglichen Spiele kann anhand der Brettgröße auf verschiedene Weise geschätzt werden, einige strenger als andere. Die einfachste, eine Permutation der Brettgröße, ( N ) L , enthält keine illegalen Captures und Positionen. Nimmt man N als Brettgröße (19 × 19 = 361) und L als das längste Spiel, bildet N L eine Obergrenze. Eine genauere Grenze wird im Papier von Tromp/Farnebäck vorgestellt.

Längstes Spiel L (19 × 19) ( N ) L Untergrenze der Spiele Obergrenze der Spiele Anmerkungen
1 361 361 361 Weiß gibt nach dem ersten Zug auf, 361 ignoriert alle Symmetrien einschließlich y = x sonst (Abstände von der Ecke) 10×10−10=90 90/2=45 +10 (Hinzufügen von x = y Symmetriepunkten) = 55.
2 722 721 Schwarz gibt nach dem ersten Zug von Weiß auf, 721 ignoriert alle Symmetrien einschließlich y=x sonst 19×19−19=342 342/2=171 +19 = 190 − 1 = 189.
50 2,1 × 10 126 7,5 × 10 127
100 1,4 × 10 249 5,6 × 10 255
150 6,4 × 10 367 4,2 × 10 383
200 1,9 × 10 481 3,2 × 10 511
250 8,2 × 10 587 2,4 × 10 639
300 2,8 × 10 684 7,8 × 10 766
350 3,6 × 10 760 1,3 × 10 895
361 1,4 × 10 768 1,8 × 10 923 Längstes Spiel mit 181 schwarzen und 180 weißen Steinen
411 n / A 1,3 × 10 1051 Längstes professionelles Spiel
500 n / A 5,7 × 10 1278
1000 n / A 3,2 × 10 2557
47 Millionen n / A 10 10 8 361 3 Züge
10 48 n / A 10 10 48 10 10 171 Längstes Spiel

10 700 ist somit eine Überschätzung der Anzahl möglicher Partien, die in 200 Zügen gespielt werden können, und eine Unterschätzung der Anzahl der Partien, die in 361 Zügen gespielt werden können. Da ein Jahr etwa 31 Millionen Sekunden hat, würde es etwa 2 . dauern+1 ⁄ 4 Jahre, 16 Stunden am Tag mit einem Zug pro Sekunde spielen, um 47 Millionen Züge zu spielen.

Siehe auch

Anmerkungen

Verweise

Externe Links