Schachwahrscheinlichkeit

Ein Schachproblem kreiert, dessen Lösung mich sicherlich wieder überfordern wird. Ausgangslage:

schachwahrscheinlichkeit

Die Regeln: Der Turm zieht eine zwischen 0 und ausschließlich 8 zufällige Anzahl an Feldern in die Richtung, in die er am meisten Platz hat. Hat er in zwei Richtungen gleich viel Platz, wie hier am Anfang, dann zieht er nach vorn. Reicht der Platz nicht aus, um den Zug zu vollenden, wird er am Brettrand reflektiert. Danach der Bischof nach demselben Muster, dann wieder der Turm.

Wie weit sind beide Figuren erwartbar voneinander entfernt, nachdem jede fünf Züge gemacht hat?

*

schachwahrscheinlichkeit_tabelle

Ungefähr so würde ich mit roher Kraft vorgehen. Der Turm zieht zwischen 0 und 7 Felder nach vorn, dann der Läufer auch zwischen 0 und 7. Das macht 8^2 = 64 Möglichkeiten, wie die Figuren nach ihren ersten Zügen stehen. Der Läufer ist nach unten aufgetragen, der Turm nach rechts. Der Abstand ist die Wurzel der Summe der Quadrate ihrer Koordinatenunterschiede. Anfangs sind sie zwei Felder in x-Richtung voneinander entfernt und sieben Felder in y-Richtung. Ihr Abstand beträgt da also Wurzel(2^2 + 7^2) = Wurzel(4 + 49) = Wurzel(53) ~= 7,28.

Das für alle möglichen Stellungen rechnen, aufsummieren und durch 64 teilen, um den mittleren Abstand zu gewinnen. Herauskommt ein Erwartungswert von 5,76 nach den beiden ersten Zügen.

Bei fünf Zügen sind es schon arg viele Kombinationen: 8^2^5 = 8^10, das ist eine Milliarde. Auch, wenn es mir gelingen sollte, das zu programmieren, woran ich nicht glaube, wäre das eine Zahl an Schleifendurchläufen, die den heimischen Rechner überfordern dürfte.

*

Die Rechnung mit 64*64 ist machbar. Wenn jedes Feld nach fünf Zügen mit gleicher Wahrscheinlichkeit erreicht wäre, wäre der erwartbare Abstand 4,1365. Dass der Läufer nur die Hälfte der Felder erreichen kann, macht da offenbar nichts aus. Vermutlich eine Spiegelsymmetriesache.

Welche Formel dahinter steckt, wäre mal interessant. Hätte das Schachbrett n*n Felder, kommen als Erwartungsabstände heraus, erlaubt man beide Figuren auf dem gleichen Feld:

n     mittlerer Abstand           dieser *2/n
1 0 0 %
2 0,8536 85,36 %
3 1,4533 96,89 %
4 2,0080 100,40 %
5 2,5476 101,90 %
6 3.0803 102,68 %
7 3,6095 103,13 %
8 4,1365 103,41 %
16 8,3261 104,08 %
24 12,5030 104,19 %
32 16,6770 104,23 %
40 20,8499 104,25 %
48 25,0222 104,26 %
56 29,1942 104,27 %
64 33,3660 104,27 %
128 66,7379 104,28 %
192 100,1085 104,28 %
256 133,4788 104,28 %

Es scheint ein bisschen über n/2 hinauszugehen. Aber wogegen, wenn?

*

Die gewünschte Formel als Polynom in n muss sich aus dem Term Wurzel((k – i)^2 + (l – j)^2) gewinnen lassen, summiert über alle vier natürlichen Zahlen i, j, k und l, jeweils von 0 bis n-1 hochgezählt, und zuletzt durch n^4 geteilt. Mit der gröbsten Schranke abgeschätzt ist der Term unter der Wurzel etwas unter 2*n^2. Dann ist die Wurzel kleiner Wurzel(2)*n und nach der Vierfachsumme kleiner Wurzel(2)*n^5. Das geteilt durch n^4 ist Wurzel(2)*n. Dafür, O(n) auf O(1) runterzubringen, sehe ich unbefangen schwarz, was auch an Unsauberkeiten bei der Abschätzung gelaufen ist. Insofern vermute ich Wachstum irgendwann dennoch ins Unendliche.

*

Vergessen, dass ich ja noch durch n/2 teilen wollte. Das bringt O(n) auf O(1) und es ist 2*Wurzel(2) gewonnen als eine obere Schranke für den mittleren Abstand geteilt durch n/2. Wogegen dieses Konstrukt konvergiert, weiß ich damit noch nicht.

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s


%d Bloggern gefällt das: