PDA

Vollständige Version anzeigen : Mathematisches Schachproblem



IcECaFE
29-08-2005, 09:26
An die mathematiker hier im board:

hab mal mit'm kumpel im studium ausgerechnet wieviel verschiedene schachpartien es maximal gibt. zugrundegelegt dass es ja ein endliches problem ist weil immer der x. zug ( ich weiss leider nicht mal mehr welche zahl x ist) ein bauernzug ist, der nicht mehr revidiert werden kann.

ist jetzt aber 20 jahre her und ich wollte es kürzlich nochmal nachvollziehen, komm aber nicht mehr drauf.

kenn jemand den lösungsweg ?

nichtinsgesicht!
29-08-2005, 09:58
Würd sagen das ist unbegrenzt. Stell dir vor, ein Schachgott wie ich steht nur noch mitm König aufm Brett (weil mir die anderen Figuren... äähh... desertiert sind), und mein Gegner hat noch nen Springer und König und bekommts einfach nicht auf die Reihe, mich mattzusetzen. Da könne mer doch ne ganze weile aufm Brett rumlaufe.

IcECaFE
29-08-2005, 10:14
... yup, da gibt es aber noch eine regel die besagt dass man den gleichen zug nicht x-mal wiederholen darf. ist ähnlich wie die regel mit dem bauer oben. ich kenn mich mit schach gar nicht besonders aus.
wie gesagt, grundlage dieser rechnung war ja gerade ihre endlichkeit.

~Roman~
29-08-2005, 10:17
da gibt es aber noch eine regel die besagt dass man den gleichen zug nicht x-mal wiederholen darf

Von dieser Regel hab ich noch nie etwas gehört..

Würd mich aber auch mal sekr interressieren.

vipo
29-08-2005, 10:31
Kann mans auch von oben abschätzen?
In der Größenordnung 2 * 10^43 soll das liegen
Kann natürlich einfach alle Permutationen der Spielfigunren /4 ausrechnen als Obergrenze, die sind aber nicht alle gültige Züge

IcECaFE
29-08-2005, 10:45
Von dieser Regel hab ich noch nie etwas gehört..


sorry, bin mir da nicht so sicher, oder habs vielleicht falsch ausgedrückt. aber besagt nicht eine regel dass mindestens der x. zug ein bauern zug sein muss ? wäre logisch, denn ansonsten schliessen wir einen nichtangriffspakt und eröffnen beide mit z.b. 1. springer b1- c3 / g8 - f6 2.c3-b1/f6-g8 ... usw.

IcECaFE
29-08-2005, 10:47
Kann mans auch von oben abschätzen?
In der Größenordnung 2 * 10^43 soll das liegen
Kann natürlich einfach alle Permutationen der Spielfigunren /4 ausrechnen als Obergrenze, die sind aber nicht alle gültige Züge

ok, wenn du mir sagts wie du das von oben her abschätzt ?

Nomarior
29-08-2005, 10:58
Ich glaube nicht, dass sich das Problem so einfach beschränken lässt. Es kann ja auch sein, dass alle meine Bauern geschlagen wurden. Dann zieht das Bauern-Argument nicht mehr.

Und einen "Nichtangriffspakt" würde schon funktionieren, aber ich denke, dein Gegner würde sich lieber in eine super Position bringen und dich dann angreifen und auseinandernehmen ( wer will schon Schach mit einem Nichtangriffspakt spielen :vogel: :D ?).

Und selbst wenn das abschätzbar wäre 10^43 ist jenseits von Gut und Böse.

Grüsse

IcECaFE
29-08-2005, 11:33
Ich glaube nicht, dass sich das Problem so einfach beschränken lässt.

einfach hab ich nicht gesagt. endlich, und damit lösbar hab ich gesagt.


Es kann ja auch sein, dass alle meine Bauern geschlagen wurden. Dann zieht das Bauern-Argument nicht mehr.

richtig. dafür gibt es eben dann meines wissens die regel dass der selbe zug nicht unbegrenzr wiederholt werden darf.


( wer will schon Schach mit einem Nichtangriffspakt spielen :vogel: :D ?).

das ist unmassgeblich . ich glaube aber gehört zu haben dass es als "vorbeugung" dafür eine regel gibt.



Und selbst wenn das abschätzbar wäre 10^43 ist jenseits von Gut und Böse.


warum ?

Nomarior
29-08-2005, 11:52
@IcECaFE:
Ich glaube du hast recht, es müssen endlich viele mögliche Schachpartien sein, weil jede Partie nach endlicher Anzahl Zügen beendet ist (und wenn es durch ein Pat aufgrund der Regeln ist).
Von daher ist es schon faszinierend, dass die spannende Partie eigentlich nur Ablauf 4325.....3 entspricht ;) . Aber wie man das Abschätzt weiss ich nicht.


Nur kann man keinen praktischen Nutzen daraus ziehen, um im Spiel im Vorteil zu sein, solange die Zahl so überastronomisch gross ist.

Kudos
29-08-2005, 12:05
An die mathematiker hier im board:

hab mal mit'm kumpel im studium ausgerechnet wieviel verschiedene schachpartien es maximal gibt. zugrundegelegt dass es ja ein endliches problem ist weil immer der x. zug ( ich weiss leider nicht mal mehr welche zahl x ist) ein bauernzug ist, der nicht mehr revidiert werden kann.


Die Rechnung möchte ich mal sehen!

Man kann es abschätzen, weil es die Regel gibt, dass nach spätestens 50 Zügen ohne Schach/Schlagen abgebrochen wird.

Größenordnungsmäßig liegt das meines Wissens nach ca. bei 10 hoch 100-200.

Nomarior
29-08-2005, 13:13
Angenommen, nach 50 Zügen wird abgebrochen, wenn nur noch zwei Könige auf dem Feld sind wird auch abgebrochen (oder phantasiere ich da?), dann kann man sagen, die längste Partie hat weniger als 30*50=1'500 Züge (weil 30 Figuren geschlagen werden).

Eine Figur hat weniger oder gleichviele Möglichkeiten wie die Dame, also 32 Felder. Bei jedem Zug kann aus 16 oder weniger Figuren ausgesucht werden.
Dh. jeder Zug hat weniger als 32*16 = 512 Möglichkeiten.

Also gibt es weniger als 512^1'500 Schachpartien, was leider noch keine brauchbare obere Schranke ist.

Auch dieser Versuch bringt nichts: amortisiertes Modell für die Anzahl der möglichen Schritte einer Figur. Im "Durchschnitt" sind auch nicht 16 Figuren auf dem Feld und die max Anzahl Züge ist kleiner gleich 29*49. Man muss Gründe finden, warum der Exponent im Mittel bedeutend kleiner als 1500 ist.

Viel Spass beid er weiteren Suche.

IcECaFE
29-08-2005, 13:14
Die Rechnung möchte ich mal sehen!

da hör ich doch ganz leicht heraus dass du es anzweifelst, ja ? warum eigentlich ? aber ich werds in nem monat nachreichen.


Man kann es abschätzen, weil es die Regel gibt, dass nach spätestens 50 Zügen ohne Schach/Schlagen abgebrochen wird.

aaah, das wars. wusste doch dass es sowas gibt. danke. also: wenn es diese regel gibt, ist die anzahl der spiele ein endlicher wert. ein endlicher wert lässt sich aber berechnen, nicht nur schätzen.


Größenordnungsmäßig liegt das meines Wissens nach ca. bei 10 hoch 100-200.
ok, warum liegt der wert da ? ausgehend von welchen eckdaten ?

Tomate
29-08-2005, 13:23
Leute das mit dem König-Springer vs König geht nicht unendlich denn wenn nur noch diese 3 Figuren auf dem Brett sind, ist es REMIS !!! ein unentschieden es geht nicht weiter, aus , finito , vorbei weil das Mattsetzen unmöglich ist!!!. Wenn angenommen König + Springer + Läufer vs König ist das Mattsetzten möglich aber ziemlich schwer, hier gibt es dann die 50 Züge-Regel, man muss es schaffen innerhalb von 50 Zügen den Gegner Matt zu setzten. Die 3x mal gleichen Zug regel Gibt es auch , und für eure Rechnung auch sehr relevant weil dann können die SPringer beider Spieler nicht immmer nur vor und zurück hüpfen, bzw. von b1 auf c3 und wieder zurück und das 8577365783659736578 mal hintereinander . dennoch halte ich diese Rechnung für so gut wie unmöglich , weil eine Partie kann unendlich viele Züge haben und somit gibt es auch unendlich viele Partien.
Bsp.
Spieler 1 : Sb1-c3 ; Sc3-e5 ; Se5-c3 ; Sc3-b1 usw .....
Spieler 2 : Sb8-c6 ; Sc6-e4 ; Se4-c6 ; Sc6-b8 usw .....

Tomate
29-08-2005, 13:36
ok nach kurzer Überlegung hab ich nochmal was für euch.....

angenommen Spieler 1 besitzt König + Turm + Turm
Spieler 2 besitzt König + Springer + Läufer

das ist kein Remis!!
man kann immernoch nach 50 Zügen Schach sagen, und die 50 Züge Regel ist ausgeschlaten weil beide Spieler noch die Möglichkeit haben Matt zu setzten....
ein Mensch braucht für einen Zug wenn er Blitzt ca. 1 sec pro Zug , rechnet aus wie lange ein Mensch durchschnittlich in Sekunden lebt und dann könnt ihr demnach ausrechnen wieviel Züge maximal Möglich sind und dann habt ihr eine Grenze ^^

Nomarior
29-08-2005, 13:38
Gilt die 50-Zügeregel nur im "Endkampf" oder immer?

Weil wenn sie immer gilt, dann hat die Partie endlich viele Züge. Und dennoch würde es unvorstellbar viele Möglichkeiten geben.

Roland von Gilead
29-08-2005, 15:01
Antwort eines a) (Anfänger :D) Mathematikers b) mittelmäßigen Schachspielers:

Unendlich! Die 50 Züge Regel ist nur eine Möglichkeit welche ergriffen werden kann! Sie muss nicht man kann auch ruhig noch 1 Million Schritte drauf machen wenn man lust und Zeit hat :D meistens sind die Kontrahenten mit dem Remis aber glücklich! Deshalb schreibt man oder merkt man sich die Züge vom Gegner um gegebenfalls Remis zu beantragen...
Und meistens spieln die noch ein paar Züge drauf... da der Spieler der am Zug ist Remis erklären muss. Hab das schon an einem Schach PC gemerkt. Manchmal hat er Remis nach 55 manchmal erst nach 200 Schritten erklährt je nachdem wieviel Figuren er selber noch hat. Wenn ich nur noch 1 oder 2 habe...

Gruß
Tarox

Kudos
29-08-2005, 16:07
da hör ich doch ganz leicht heraus dass du es anzweifelst, ja ? warum eigentlich ? aber ich werds in nem monat nachreichen.


Ja, ich zweifele daran, dass Du dieses Problem exakt lösen kannst, geschweige denn alle Züge aufzählen ;) Obere Schranken, wie die relativ einfach zu findende von 512^1500 (wieviele Stellen hat diese Zahl bloß ;) kann man aber angeben.

Die Komplexität dieses Problems ist sehr hoch. Aber immerhin noch ziemlich gering im Vergleich zu Go...




aaah, das wars. wusste doch dass es sowas gibt. danke. also: wenn es diese regel gibt, ist die anzahl der spiele ein endlicher wert. ein endlicher wert lässt sich aber berechnen, nicht nur schätzen.


Ich bin sehr an dieser Rechnung interessiert. Nicht alles was endlich ist, lässt sich auch berechnen. Theoretisch vielleicht ja, praktisch reicht dafür oft die verfügbare Rechenleistung nicht aus.

Ein Problem ist, dass Du Dir ja irgendwo "merken" musst welche Wege Du bereits gegangen bist, selbst wenn jedes Atom des Universums einen Weg speichern könnte, reicht es nicht aus. Im besten Fall kannst Du eine Formel präsentieren, die evtl. richtig ist. Gut, für einen Mathematiker ist damit das Problem gelöst, für einen Informatiker nicht -- andererseits interessieren sich "echte" Mathematiker (im Gegensatz zu Informatikern) nicht für endliche Probleme (nicht so Ernst nehmen, falls Du Mathematiker bist!) :D

Nomarior
29-08-2005, 21:22
Antwort eines a) (Anfänger :D) Mathematikers b) mittelmäßigen Schachspielers

Das eine schliesst ja das andere nicht aus. Und ja, ich spiele selten Schach und das nichtmal mit Konzept. Ich kenne also nur dürftig die Regeln und würde mich nicht als Schachspieler bezeichnen.

Um eine obere Schranke zu finden, musst man die Länge der Partie irgendwie begränzen, anders geht es kaum (ich lasse mich von dir gerne eines besseren belehren).
Und eine Zahl wie 512^1500 ist überastronomisch gross und findet in der Praxis keine Verwendung (natürlich macht die Zahl mathematisch keine Probleme, sie ist zwar etwas gross, aber doch nur eine Konstante...).

Gruss
Nomarior

Tomate
29-08-2005, 21:34
ich würde sagen dass man die 50 Züge regel bei diesem Problem einfach gelten sobald das Mattsetzten nicht nach 50 Zügen erfolgt, sonst isses echt assi .

IcECaFE
29-08-2005, 22:06
Ich bin sehr an dieser Rechnung interessiert. Nicht alles was endlich ist, lässt sich auch berechnen. Theoretisch vielleicht ja, praktisch reicht dafür oft die verfügbare Rechenleistung nicht aus.
ich liebe skeptiker.du hast recht. ich habs ned genau genug formuliert. soweit ich mich enstinne haben wir natürlich damals auch nur näherungsweise gerechnet. (ich habs mir damals etxra aufbewahrt. liegt nun bei meinem vater aufm speicher, 600 km entfernt... ;) )


Im besten Fall kannst Du eine Formel präsentieren, die evtl. richtig ist.
exact. wir ersetzen nur das wort "eventuell" durch das wort "annähernd"



Gut, für einen Mathematiker ist damit das Problem gelöst, für einen Informatiker nicht -- andererseits interessieren sich "echte" Mathematiker (im Gegensatz zu Informatikern) nicht für endliche Probleme (nicht so Ernst nehmen, falls Du Mathematiker bist!) :D

du hast völlig ins schwarze getroffen. absolut. echte mathematiker sind deshalb sehr oft auch theologen ;)

allerdings sollten wir die 50-züge regel als gegeben nehmen. eine endliche lösung macht die lösung einfach auch für laien transparenter :)

PS.: warum ich es wissen will ? ok, der typ mit dem ich damals an diesem problem gebastelt habe war selbst ein begnadeter schachspieler. er war, ich hoffe ich benutze das richtige wort, mit 19 schon grossmeister in schwaben. daneben war er auch der jüngste assistent des professors an der LMU münchen. man sagte ihm eine unglaubliche karriere voraus. entweder als schachspieler oder mathematiker. eines tages begann er zu trinken und war von heut auf morgen verschwunden. ich hab ihn dann mal als paketfahrer wiedergetroffen. er ist nun am sonntag mit 43 verstorben. leberschaden durch den alk. ich geh ja auf keine beerdigungen, aber ich denke er würde sich freuen wenn er sehen würde wie wir hier rumfummeln.

desertdragon
30-08-2005, 09:09
Von dieser Regel hab ich noch nie etwas gehört..

Würd mich aber auch mal sekr interressieren.

Machen BEIDE Spieler 3x den gleichen Zug hintereinander, wird mit Remis (also unentschieden) abgebrochen.
EIN Spieler kann den gleichen Zug machen, so oft er will.

Kudos
30-08-2005, 09:32
@IcECaFE

100%ige Zustimmung zu Deinem Post!



daneben war er auch der jüngste assistent des professors an der LMU münchen. man sagte ihm eine unglaubliche karriere voraus. entweder als schachspieler oder mathematiker. eines tages begann er zu trinken und war von heut auf morgen verschwunden.

Schade um Deinen Bekannten. Leider liegen Genie und Wahnsinn oft sehr nah beieinander -- muss wohl auch so sein. Einer meiner Lieblingsfilme in dem das auch ganz schön gezeigt wird, ist "A Beautiful Mind". Auch wenn Nash keinesfalls so nett und relativ umgänglich war, wie er in dem Film gezeigt wurde und der Film insofern die Realität nur eingeschränkt wieder gibt. Eine gute Biographie findet man z.B. hier: http://matheplanet.com/matheplanet/nuke/html/article.php?sid=609 (ansonsten ist die Seite auch sehr interessant!)

Wegen dem Schachproblem bzw. der Lösung darfst Dich gerne nochmal bei mir (auch per PM) melden! Mittlerweile glaube ich immer mehr, dass Du was ganz vernünftiges gezeigt hast :D

Bezüglich Schach finde ich das Mensch-Computer-Duell als Problem übrigens auch hochinteressant...

Roland von Gilead
30-08-2005, 09:48
Das eine schliesst ja das andere nicht aus. Und ja, ich spiele selten Schach und das nichtmal mit Konzept. Ich kenne also nur dürftig die Regeln und würde mich nicht als Schachspieler bezeichnen.


Das:


Antwort eines a) (Anfänger :D) Mathematikers b) mittelmäßigen Schachspielers:


war a) auf mich bezogen b) somit auch auf meine Antwort.

Wollte dich nicht beleidigen :)

Gruß
Tarox