Author: Christoph Fieberg
Date: 14:29:31 07/11/01
On CSS (German Computer Chess forum) we had an interesting discussion about the complexity of chess, search depths and the maximum ELO. Thomas Kantke gave valuable mathematical insights. In short: He proved that the number of positions in Chess is limited to 10^53. He developed following functions: x = frequence f(x) = ELO If x < e ^ (e ^ (1 / ln (1+1/e)) what is 3,7304889 * 10^10 ,i.e. about 37,3 GHz, then f(x) = 100 * ln x + 538 If x > e ^ (e ^ (1 / ln (1+1/e)) what is 3,7304889 * 10^10 ,i.e. about 37,3 GHz, then f(x) = (100 * ln x + 538) / (ln (1+1/e) * ln ln x) (Using this formula you arrive for x=10^53 at about ELO 8500 as maximum.) He describes in detail also his assumptions for a function between Ply an ELO. The deeper the search depths (ply) the lower the complexity will be and therefore less and less additional search time will be needed to reach the next ply. He estimates that the limit of complexity is at about 10000 ply. (This would mean that at 10^53 Hz a search depths of 10000 ply would be reached). Below find the most interesting parts of the discussion in German (including links). Regards, Christoph http://f23.parsimony.net/forum50826/messages/21632.htm Da Schach ein endliches Spiel ist, muß es eine obere Grenze für die ELO-Spielstärke geben. Aufgrund verschiedener Überlegungen schätze ich die maximale Spielstärke auf ca. ELO 5000. Da die Komplexität von Schach nicht durch die Anzahl der Spielmöglichkeiten sondern durch die Anzahl der Stellungen begrenzt wird ist der Nachweis sehr einfach. Es gibt weniger als 10^53 verschiedene Schachstellungen. Beweis: Von den 64 Feldern bleiben mindestens 32 Felder frei; die Anzahl der Konfigurationen hierdurch ergeben sich durch den Binomialkoeffiztienten 32 aus 64, d.h. 64!/(32!^2). Nun bleiben noch 32 besetzte Felder übrig. Die Anzahl der Stellungen beider Könige beträgt hierfür 32 * 31. Die verbleibenden 30 Felder können maximal 11 verschiedene Zustände haben; sie können durch eine Dame, Turm, Läufer, Springer oder Bauer in beiden Farben besetzt sein oder frei sein. Dies sind also 11^30 Möglichkeiten, d.h. die Komplexität von Schach liegt mit Sicherheit unter der oberen Schranke (64!/(32!^2)) * 32 * 31 * 11^30 und dies ist mit 3,172237... * 10^52 nicht nur endlich sondern auch noch deutlich kleiner als die Anzahl aller Atome im Universum. Grüße, Thomas Kantke http://f23.parsimony.net/forum50826/messages/21636.htm Wir wissen noch zu wenig über den funktionalen Zusammenhang zwiaschen der berechneten Knotenanzahl und der Spielstärke. Bisher ist man immer mit der Schätzung e^(C*x) ganz gut gefahren, d.h. man muß exponenziell mehr Knoten durchrechnen um einen linearen Spielstärkezuwachs zu erreichen. Nun gibt es bereits erste Analysen, die auf einen abnehmenden Grenznutzen hindeuten; in CSS wurde bereits darüber berichtet. Ich habe mal eine empirische Analyse gemacht. Wenngleich die Daten noch sehr unscharf sind spricht - zusammen mit einigen theoretischen Überlegungen - einiges dafür, dass die Exponentialfunktion durch die Fakultät ersetzt werden muß, d.h. man muß - um einen linearen Spielstärkezuwachs zu erreichen fakultätsmäßig mehr Knoten durchrechnen. Das Kräfteverhältnis zwischen Exponentialfunktion und Fakultät (bzw. Gammafunktion) kann man salopp wie folgt beschreiben: Die Fakultät steigt schneller nach unendlich als die Exponentialfunktion aber langsamer als x^x. Die Fakultät steigt so viel schneller nach unendlich, dass der Quotient zwischen Fakultät und Exponentialfunktion wiederum schneller nach unendlich geht als die Exponentialfunktion. Aber in der Größenordnung der Größenordnung steigen alle 3 Funktionen e^x, Fakultät und x^x ungefähr gleich schnell nach unendlich, da bereits e^(x^(1 + epsilon)) für jede unglaublich kleine positive Zahl epsilon alle 3 Funktionen besiegt. Anzumerken sei noch, dass die Analogien zur Zahlentheorie beträchtlich sind; das Produkt der ersten natürlichen Zahlen ist die Fakultät; das Produkt aller Primzahlen bis x steigt ungefär so schnell wie die e-Funktion e^x, d.h. das Kräfteverhältnis zwischen Exponentialfunktion und Faktultät entspricht dem zwischen den Primzahlen und den natürlichen Zahlen. Wen wir also etwas spekulieren wollen: Würde man heute einen Prozessor mit einer Taktfrequenz von ca. 7,2 THz haben käme man (mit der heutigen Software!) mit der Extrapolation über die E-Funktion auf etwa 3500 ELO und mit der Extrapolation über die Fakultät auf etwa 3300 ELO. Grüße, Thomas Kantke http://f23.parsimony.net/forum50826/messages/22053.htm Ursprünglich hatte ich nicht vor, zu so einem frühen Zeitpunkt meine Überlegungen zur Schachkomplexität zu posten, da ich noch mitten in der Forschung stecke, aber aufgrund der zahlreichen Emails werde ich jetzt doch einen Zwischenbereicht posten. Folgende Punkte möchte ich behandeln: Was wird mit der ELO-Zahl genau gemessen? Sind unendlich große ELO-Zahlen möglich? Kann man den Zusammenhang zwischen der Komplexität von Schach, der Prozessorleistung, der Rechentiefe und den ELO-Zahlen quantifizieren? Zunächst einmal gibt die ELO-Zahl nur einen relativen Vergleich zwischen 2 Spielern an. Wie man sich unter www.schachbund.de/WOrdnung/ordwoa2.htm überzeugen kann, stellt die Funktion P(D) = 1 / ( 1 + 10 ^ -0,0025 D ) den Zusammenhang zwischen den prozentual erreichten Punkten und der Differenz zwischen den beiden ELO-Zahlen her. Von der Gewinnwahrscheinlichkeit ist es also zunächst einmal gleichgültig ob 1800 gegen 1700 oder ob 1400 gegen 1300 spielt, da in beiden Fällen der stärkere Spieler vom Erwartungswert her voraussichtlich 64% aller Punkte holen wird. Über die absolute Spielstärke sagt die ELO-Zahl also zunächst einmal nichts aus. Aus der Definitionsformel P(D) = 1 / ( 1 + 10 ^ -0,0025 D ) folgt, dass unendlich große ELO-Zahlen (D geht nach unendlich) nur dann gegeben sind, wenn P(D) EXAKT 1 ist. Wir gehen jetzt einmal davon aus, dass wir stets nur Doppelpartien (jeder der beiden Spieler hat einmal Weiß) spielen. Die Grundstellung ist somit Remis. Damit P(D) = 1 wird, haben wir 2 Möglichkeiten: 1. Schach hat eine unendlich hohe Komplexität 2. Einer der Spieler spielt ABSICHTLICH a priori auf Verlust. Da eine Schachpartie in jedem Fall nach einer endlichen Zugzahl beendet sein muß und in jeder Stellung nur endlich viele Optionen bestehen ist die Komplexität logisch zwingend endlich. Selbst wenn man die 50 Zügeregel ersetzt durch die Regel, das man doppelt so lange Zeit hat um in einer Stellung matt zu setzen wie theoretisch erforderlich (z.B. in der in 59 Zügen gewonnenen Stellung T+L : T statt 50 Züge 118 Züge) ist die Komplexiät von Schach endlich, da es aufgrund der endlichen Anzahl der Stellungen (es sind weniger als 10^53) auch hier stets eine endliche Schranke gibt. Ein Spieler, der absichtlich verliert, spielt de facto ein anderes Spiel als Schach, so dass eine Spielstärkenbestimmung sinnlos ist. Nach allgemeiner Definition ist der schlechteste Spieler also derjenige, der seine Züge auslost, d.h. genau 0 Halbzüge tief rechnet. Da aber mindestens eine Spielvariante des Spielbaums zum Remis führt und die Anzahl der Spielbäume endlich ist, ist die Wahrscheinlichkeit, dass Zufall eine Remisvariante findet, a priori NICHT EXAKT 0, d.h. P(D) kann somit nicht 1 sein. Halten wir also fest, dass es unendlich große ELO-Zahlen nicht nur nicht gibt, sondern auch theoretisch nicht geben kann. Allerdings ist anzumerken, dass man das ELO-System auch für andere Logikspiele verwenden kann, da das ELO-System nicht an das Schachspiel gebunden ist. Würde man das ELO-System beim von mir im April 1983 definierten unendlich komplexen Zahlentheoriespiel Minimum anwenden, so wären sehr wohl unendlich große ELO-Zahlen möglich. Allerdings habe ich eine andere Spielstärkenbestimmung bei Minimum eingeführt. Kommen wir nun zur Frage, ob man den Zusammenhang zwischen der Komplexität von Schach, der Prozessorleistung, der Rechentiefe und den ELO-Zahlen quantifizieren kann? Im CSS-Heft 4/2000 habe ich im Leserforum meine Formel F(x) = 100 * ln x + 538 vorgestellt, die den Zusammenhang zwischen dem Prozessortakt und der ELO-Zahl verdeutlichen soll. Diese Formel habe ich allerdings empirisch gefunden, d.h. von den 3 möglichen wissenschaftlichen Niveaus (Analytisch, empirisch und heuristisch) kann hier das höchste analytische Niveau nicht erreicht werden. Die folgenden Ausführungen bewegen sich auch nur auf empirischen teilweise sogar nur heuristischem Niveau. Der Zusammenhang zwischen dem Prozessortakt und der berechneten Knotenanzahl ist etwa linear. Je nach verwendeter Software kann man ungefähr davon ausgehen, das pro 1000 Takte etwa ein Knoten berechnet wird. Selbstverständlich ist dies nur ein grober Durchschnittswert, da dieser Wert auch von der Stellung und verschiedenen anderen Faktoren abhängig ist. Der Zusammenhang zwischen dem Prozessortakt und der Rechentiefe ist etwa logarithmisch, d.h. die Rechentiefe in Halbzügen ist etwa proportional dem Logarithmus vom Prozessortakt. Da man das Schachspiel sehr gut in einem Baum darstellen kann und von jedem Baumknoten (=Stellung) etwa gleich viele Äste (Züge) zu neuen Baumknoten führen, kann man sehr schnell erkennen, dass mit zunehmender Rechentiefe die Arbeit exponentiell wächst und man somit mit dem Rechenaufwand x etwa O(ln x) Halbzüge weit rechnen kann. Durch zahlreiche Versuche konnte man außerdem eine sehr sarke positive Korrelation zwischen der Rechentiefe und der ELO-Zahl feststellen. Dieser Zusammenhang war ungefähr linear. Durch diese Versuche fand eine de facto Eichung der ELO-Zahl statt, d.h. obwohl die ELO-Zahl ursprünglich nur als relativer Spielstärkenvergleich mit Punktewahrscheinlichkeiten konzipiert war, wird sie nunmehr auch faktisch (auf empirischen Niveau) ein objektivierbares Maß für die Spielstärke. Auch wenn man dem linearen Zusammenhang zwischen der Rechentiefe und der ELO-Zahl nicht ganz traute, konnte man doch recht gute Prognosen erstellen. Mittlerweile sind jedoch die Rechner so schnell geworden, dass der vermutete Effekt der schwächeren Spielstärkezunahme bei größeren Rechentiefen empirisch nachgewiesen werden konnte. Im Heft 4/2000 hat Frank Schubert hierüber ausführlich berichtet. Von großer Bedeutung ist jedoch die Frage WIEVIEL langsamer als linear die ELO-Zahl im Vergleich zur Rechentiefe bei größeren Rechentiefen steigt. Frank Schubert hat hierzu als Approximation ein Polynom 3.Grades angeboten (x-Wert = Rechentiefe in Halbzügen, y-Wert = ELO-Zahl). Aufgrund der Skizze im CSS-Heft 4/2000 habe ich den Term f(x) = 5/14 *x^3 - 55/3 *x^2 + 417,5 x - 399,5 rekonstruiert. Es ist klar, das diese Funktion nur als Approximation bis etwa höchstens x < 22 verwendet werden darf, da dieses Polynom dann zu einem Wendepunkt führt und danach deutlich schneller als linear ansteigt (eben kubisch). Da wir noch nicht über THz Prozessor verfügen, muß man sich andere Möglichkeiten suchen, den funktionalen Zusammenhang zwischen der Rechentiefe und ELO-Zahl oder zwischen dem Prozessortakt und der ELO-Zahl zu finden. Da der Zusammenhang zwischen dem Prozessortakt und der Rechentiefe logarithmisch ist, sind beide Fragestellungen identisch. Nun könnte man einfach einen GHz-Prozessor nicht 3 Minuten sondern 3000 Minuten pro Zug rechnen lassen und so einen THz-Prozessor simulieren. Dann lassen wir mehrere Tausend Partien mit den unterschiedlichen Bedenkzeiten (3 Minuten, 12 Minuten, 1 Stunde, 4 Stunden, 12 Stunden und 50 Stunden pro Zug) in mehreren Versuchsreihen gegeneinander spielen und schon hätten wir einen empirischen Anhaltspunkt für den Verlauf der Funktion. Da wir aber erstens nicht die Zeit haben so eine aufwändige Versuchsreihe durchzuziehen und der Einfluß anderer Parameter diskutiert werden müsste (Hätte ein THz-Prozessor auch 128 GB Hashtables im Endspiel?) ist dies nicht praktikabel. Wir müssen also nach anderen Wegen schauen, um hier weiter zu kommen. Da die Komplexität für Schach (zumindest für mich) zu groß ist, um den Verlauf der Funktion erahnen zu können, habe ich nach Analogien gesucht. Gibt es ein leichteres Spiel, bei dem ich mir Intuition holen könnte? Folgende Bedingungen sollte dieses Spiel erfüllen: 1. Wie Schach muß es von genau 2 Spielern gespielt werden. 2. Es gibt nur endlich viele Positionen/Stellungen. 3. Es gibt a priori eindeutig festgelegte Spielregeln. 4. Die Spieler ziehen abwechselnd. 5. Die Endbedingung ist klar definiert. 6. Es gibt keine Zufallszüge. 7. Es herrscht für beide Spieler vollständige Information, d.h. es gibt keine heimlichen Züge außerhalb des Spielfeldes. 8. Das Spiel läßt sich sehr gut wie im Schach im Baum darstellen. Nach kurzer Suche wurd ich fündig. Ich entschied mich für das Spiel TIC/TAC/TOE. Dieses Spiel wird auf einem 3*3 Schachbrett gespielt. Am Anfang ist das Brett leer (Startposition). Der anziehende Spieler beginnt. Er setzt in genau eines der 9 Felder ein Symbol z.B. ein X. Danach setzt der nachziehende Spieler sein Symbol z.B. ein O in eines der acht verbliebenen Felder. Danach setzt der anziehende Spieler wieder sein X in eines der 7 verbliebenen Felder usw. Wer zuerst seine 3 Symbole in eine Reihe, Linie oder Diagonale (insgesamt also 8 Möglichkeiten) plaziert, gewinnt. Es ist bekannt, dass bei perfektem Spiel Tictactoe remis ist. Ich habe nun verschiedene Simulationen zwischen verschiedenen virtuellen Spielern (von Zufall bis Perfekt ist fast alles vertreten) durchgeführt. Zufall hat die Spielstärke 0 ELO. Man ist bei diesem Spiel bereits dann perfekt, wenn man 9 Halbzüge tief rechnen kann. Anhand der Wahrscheinlichkeitstabelle werden die Spielstärken der anderen Spieler ermittelt. Nun kann man auch die Spielstärke in Abhängigkeit der Rechentiefe bestimmen. Perfekt weiß z.B. dass man als Nachziehender auf das X in der Mitte unbedingt mit einem O in der Ecke antworten muß. Wenn der Anziehende mit dem X in der Gegenecke antwortet (was relativ der beste Zug ist) muß man wiederum sein O in der Ecke plazieren. Beginnt der Anziehende in der Ecke, so ist der Nachziehende gezwungen sein O in die Mitte zu setzen usw. Die Erkenntnisse, die ich hieraus gewinnen konnte, erfüllten zunächst nicht meine Erwartungen. Natürlich ist die maximale ELO-Zahl begrenzt, aber das ist ja nichts neues. Allerdings wurde mir klar, das der Zusammenhang der gesuchten Funktion mit der Anzahl der spielentscheidenen Schlüsselzügen im Verhältnis zu allen anderen Zügen, die bei der Rechentiefe n+k noch gesehen werden, aber bei der Rechentiefe n nicht mehr, eng zusammen hängen muß. Um weiterzukommen habe ich die sehr interessanten Beiträge von Helmut Conrady in den CSS-Heften genauer studiert. Betrachten wir einmal seine Ausführungen zum Endspiel D : T+B im CSS-Heft 3/2001. Nehmen wir an, diese Position D : T+B sei die Grundstellung im Schach. Es spielt nun keine Rolle ob man 207 Halbzüge oder unendlich viele Halbzüge tief rechnet, beides mal spielt man absolut perfekt. Unsere Funktion verläuft also im Bereich x > 207 absolut konstant, die ELO-Zahl wächst nicht mehr, da die Komplexität des Spiels völlig ausgereizt und erschöpft ist. Rechnet man aber nur 206 Halbzüge, so kann man bis auf eine einzige Stellung perfekt spielen. Rechnet man nur 144 Halbzüge, so kann man bis auf 63 Stellungen, die alle im maximalen Variantenpfad liegen, perfekt spielen. In diesem Bereich (143 < x < 207) wächst die ELO-Zahl also extrem langsam an. Rechnet man weniger als 143 Halbzüge, so bricht auf einmal ein zweiter Variantenbaum weg, den man nicht mehr perfekt spielen kann. Im unteren Bereich bei etwa 1 - 7 Halbzügen haben wir das bekannte Verhältnis von x zu ln x zwischen dem Prozessortakt und der Spielstärke. Unsere gesuchte Funktion zwischen dem Prozessortakt (x - Achse) und der ELO-Zahl (y-Achse) wächst also zunächst mit etwa O(ln x) an, kommt dann in einen Zwischen bereich, wo sie langsamer wächst und den wir unbedingt bestimmen müssen und franzt am Schluß in eine konstante Gerade aus, wenn die Komplexität des Spiels erschöpft ist. Man kann heuristisch erkennen, das von unserer Funktion die erste Ableitung stets > oder gleich 0 ist und die zweite Ableitung bis zum perfekten Spiel stets kleiner 0 sein muß. Um ein Gefühl für die Quantifizierbarkeit der Funktion zu bekommen, habe ich ein paar einfache Stellungen analysiert. Wenngleich die Ergebnisse keinesfalls repräsentativ sind und die Steuung doch beachtlich ist, konnte ich doch einen gewissen Trend erkennen. Als ich die Ergebnisse verschiedene Stellungen zusammenfaßte und den Zusammenhang zwischen Rechentiefe und ELO-Zahl anschaute konnte ich z.B. folgende Zahlenreihe aufstellen: x = 6, 7, 8, 9, 10, 11, 12 y = 16, 18, 19, 19, 22, 24, 25 Ich habe lange überlegt, was dies wohl für eine Funktion sein könnte. Hierbei ist zu berücksichtigen, dass sich die Funktion auch hinter einer multiplikativen Konstante verbergen kann. Da ich hier zunächst nicht weiterkam, habe ich mir überlegt, ob man durch die Komprimierbarkeit weiterkommen könnte. Z.B. lassen sich alle Stellungen K + L + falscher Randbauer : K sehr stark komprimieren. Aber auch hier kam ich nicht weiter. Da hatte ich auf einmal einen Einfall. Was wäre, wenn sich die Anzahl der Schlüsselstellungen mit zunehmender Rechentiefe genauso verhalten würden, wie die Primzahlen zu den natürlichen Zahlen (x / ln x). Am Anfang kann man mit der zunehmenden Rechentiefe etwa linear mehr Spielstärke erreichen, aber danach sind bei höherer Spielstärke immer weniger relevante Schlüsselstellungen versteckt (x / ln x), so daß die Aufgabe für den Verteidiger immer leichter wird. Da wir noch ganz am Anfang unserer Untersuchungen stehen, formuliere ich meine Vermutung im folgenden als These: Die Spielstärke im Schach ist durch die Anzahl der nicht erkannten Schlüsselstellungen zwischen der Rechentiefe n und n-k darstellbar. Die nicht erkannten Schlüsselstellungen werden mit zunehmender Rechentiefe pro Halbzug immer seltener. Unter Umständen kann hierfür die Primzahlfunktion (x / ln x) verwendet werden. Aufbauend auf diesen vagen Vermutungen habe ich nun eine neue Regressionsfunk- tion aufgestellt. Meine alte Funktion zwischen der Taktfrequenz und der Spielstärke bleibt für alle x < 3,7304889 * 10^10 also bis etwa 37,3 GHz gültig. Für größere Spielstärken muß die Funktion gemäß der Primzahlfunktion abgeändert werden. Aufbauend auf die Primzahlfunktion (x / ln x) habe ich analog zu den Sätzen der Primzahltheorie die neue Funktion (x = Taktfrequenz, f(x) = ELO) konstruiert: Falls x < e ^ (e ^ (1 / ln (1+1/e)) also 3,7304889 * 10^10 ,d.h. etwa 37,3 GHz, dann ist f(x) = 100 * ln x + 538 (wie bisher) Falls x > e ^ (e ^ (1 / ln (1+1/e)) also 3,7304889 * 10^10 ,d.h. etwa 37,3 GHz, dann ist f(x) = (100 * ln x + 538) / (ln (1+1/e) * ln ln x) Falls meine These zutrifft, kann diese Funktion solange benutzt werden, bis die Komplexität von Schach erschöpft ist. Die Komplexität von Schach ist spätestens bei 10^53 Stellungen erschöpft. Erste Anzeichen von der Komplexitätserschöpfung beim Schach (herausfallen von abgeschlossenen Varianten in signifikantem Umfang) erwarte ich aber schon deutlich früher; gefühlsmäßig glaube ich, dass bei etwa 5000 ELO Schluß ist. Grüße aus München, Thomas Kantke http://f23.parsimony.net/forum50826/messages/22307.htm Hallo Thomas, vielen Dank für Deine Untersuchungen und Deine Formeln! Wenn man die Formeln anwendet erhält man eine maximale Elozahl von ELO 8589 !! Hier die Umrechnungstabelle: Formel 1 = 100 * ln (x) + 538 Formel 2 = (100 * ln (x) + 538) / (ln (1 + 1 / e) * ln (ln (x))) ---------.......---.....Formel 1..Formel 2 HZ (= x )......Elo.......Elo 5,00E+08......----......2541 1,50E+09......----......2651 4,50E+09......----......2761 1,35E+10......----......2871 4,05E+10......2977......2980 1,22E+11......3045 3,65E+11......3113 1,09E+12......3181 ... 1,31E+52......8360 3,93E+52......8418 1,18E+53......8475 3,53E+53......8532 1,06E+54......8589 Gruß, Christoph http://f23.parsimony.net/forum50826/messages/22309.htm Die längste bisher bekannte Tablebase-Stellung sind 523 Halbzüge zum Matt, mit nur einem EINZIGEN Gewinnzug in der Ausgangsstellung! So tief müsste optimales Spiel mindestens gehen. In Wirklichkeit aber wohl 800 oder 1000 Halbzüge, wenn es mal die 7- oder 8-Steiner gibt und auch das ist ja lange noch nicht das Ende. http://f23.parsimony.net/forum50826/messages/22362.htm Wenn die von Thomas Kantke entdeckten Zusammenhänge stimmen, dann wird Elo 8.589 in jedem Fall das Maximum sein! Denn die Formeln sind unabhängig von der erreichten Suchtiefe! Bei 10^53 Stellungen ist Schluß und wenn die alle berechnet wurden, wird perfekt gespielt. Die Frage ist nur, wieviel Ply Suchtiefe denn 10^53 Stellungen (bzw. 10^53 HZ) bedeuten. Das könnten durchaus 800 - 1000 Ply sein. Ich denke mal, der Zusammenhang Suchtiefe und Rechengeschwindigkeit läuft etwa nach folgendem Muster ab. Anfangs braucht man die 3-fache Rechengeschwindigkeit (so die bisherigen Beobachtungen), um 1 Ply tiefer zu gelangen. Später wird es weniger und weniger. Am Ende reichen vielleicht marginale Zuwächse, um von z.B. Ply 567 auf Ply 568 zu kommen. Auf diese Weise liessen sich alles erklären. Wichtig jedoch ist, eine ELO von etwa 8.500 das MAXIMUM darstellt. Die Chance für Kasparow ein Remis gegen ein 8500-Monster zu holen, betrüge etwa 132 Billionen zu Eins. Gruß, Christoph http://f23.parsimony.net/forum50826/messages/22366.htm Je mehr man sich dem perfekten Spiel nähert, umso mehr Spielvarianten fallen weg, da man mit der fundamentalsten Bewertungsfunktion (Matt, -Matt oder Remis) bereits vollständig das Spiel erfaßt. So ist z.B. im Spiel K + T : K bei 35 Halbzügen ohne Tablebasis die absolute Komplexitätsgrenze erreicht. Meine Formel kann aber grundsätzlich nur solange gelten, solange die Komplexitätsgrenze noch nicht erreicht ist, da nach dem Erreichen der Komplexitätsgrenze die Funktion logisch zwingend eine Konstante sein muß. Im Beispiel K + T : K ergeben sich für alle Ply > 35 dieselben Werte wie für Ply = 35. Im folgenden gebe ich eine intuitive Einschätzung der Funktion zwischen Ply und ELO-Zahl. Wenn man auf der x-Achse die Halbzüge (Ply) und auf der y-Achse die ELO-Zahl abträgt, so kann man (nach meinen derzeitigen VERMUTUNGEN!) etwa 4 Bereiche unterteilen (die Übergänge sind natürlich fließend). Bis etwa 16 Ply (Phase 1) ist die Funktion linear. In diesem Bereich ist der Wissenszuwachs proportional der Baumtiefe, da die Taktik mit ihrem proportionalen Wissenszuwachs in diesen geringen Rechentiefen das Sagen hat. Die Komplexität von Schach ist so groß, dass in diesem Bereich bei so einer geringen Baumtiefe Zyklia und Redundanzen noch keine große Rolle spielen. Die Grenze zwischen der Phase 1 und 2 bezeichne ich als Degressionspunkt (16 Ply). Von 16 bis etwa 40 Ply (Phase 2) entspricht die Funktion etwa der Primzahlfunktion li(x) = Integral von 1 / ln x. In diesem Bereich wächst die Funktion schwächer als linear, da aufgrund der größeren Rechentiefe Redundanzen und Zyklia entstehen und somit Informationsverdichtungen möglich sind. Die Taktik tritt nunmehr zusehens in den Hintergrund. Komplexitätsgrenzen spielen in der Phase 2 noch keine signifikante Rolle; zwar gibt es einzelne abgebrochene Bäume (z.B. 1.f3, e5; 2.g4, Dh4) aber die treten nicht in einer signifikant hohen Anzahl auf. So kann man beispielsweise die Bewertungsfunktion für das Endspiel K + L + falscher Randbauer : K zu folgender Regel verdichten: Der verteidigende König muß so schnell wie möglich zum Umwandlungsfeld des Bauern laufen und darf sich anschließend höchstens ein Feld vom Umwandlungsfeld entfernen. Falls das Schachspiel logisch so beschaffen ist, das sich die im Schach mögliche Informationsverdichtung genauso wie sehr viele Prozesse in der Natur, Zahlentheorie und Informationsverarbeitung mit der Funktion li(x) beschreiben läßt, so hätte man mit der angegebenen Funktion einen sehr guten Schätzwert für die Spielstärke. Die Grenze zwischen der Phase 2 und Phase 3 bei etwa 40 Ply bezeichne ich als partielle Komplexitätsgrenze. In der Phase 3 ab etwa 40 Ply treten erstmals Komplexitätsgrenzen in signifikantem Umfang auf, d.h. im Gegensatz zur Phase 2 sind in nicht unerheblichem Umfang bei vorgegebenem Ply ganze Baumbereiche bereits vollständig ausanalysiert und tragen somit nicht mehr zur Komplexitätserhöhung bei. Selbstverständlich gibt es aber noch nicht vollständig ausanalysierte Baumbereiche. Die Formel li(x) darf nur noch für die nicht vollständig ausanalysieren Baumbereiche verwendet werden; für die ausanalysierten Bereiche gilt jetzt bereits die konstante Funktion, d.h. die unsere Gesamtfunktion steigt langsamer als li(x) aber noch schneller als die konstante Funktion. Je mehr man sich der absoluten Komplexitätsgrenze, an der alle Schachvarianten sämtlich ausanalysiert sind und somit die Grenze zwischen der Phase 3 und 4 bildet, nähert, umso langsamer steigt unsere Funktion an und ähnelt mit zunehmendem Ply mehr und mehr der konstanten Funktion. Die angegebene Formel darf also nur bis etwa 40 Ply verwendet werden. Die Grenze zwischen Phase 3 und 4 nenne ich absolute Komplexitätsgrenze. In der Phase 4 sind absolut alle Varianten vollständig ausanalysiert und wir haben eine konstante Funktion. Wir wissen nicht wo die absolute Komplexitätsgrenze ist; es ist lediglich bekannt, dass sie mindestens bei 523 Ply liegt; gefühlsmäßig würde ich für das ganze Schach (unabhängig von den FIDE-Regeln) auf etwa 10000 Ply tippen. Allerdings gehe ich davon aus, dass die Funktion in der Phase 3 extrem degressiv verläuft, d.h. wenn man die Rechentiefe von 5000 Ply auf 10000 Ply verdoppelt gewinnt man vielleicht 3 oder 4 ELO-Punkte. Ausdrücklich möchte ich nochmals betonen, dass es sich bei obenstehenden Ausführungen lediglich um VERMUTUNGEN handelt, die gerade erst einmal (und das auch nur teilweise) das unterste wissenschaftliche heuristische Niveau erreicht haben und somit keinesfalls als wissenschaftliche Erkenntnisse verwendet werden können. Wir alle stehen noch ganz am Anfang der Forschung, aber ich denke es gibt begründete Anhaltspunkte für die Hoffnung, dass im 21. Jahrhundert durchaus ein Durchbruch in der Schachforschung erreicht werden könnte. Grüße aus München, Thomas Kantke
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.