schachpartie... |
| 03.04.2006, 16:14 | The Rob | Auf diesen Beitrag antworten » | ||||||
| schachpartie... ich komme da nicht weiter und ich verdaechtige, dass man es nicht "berechnen kann", da es ja eigentlich keine regelmaeßigkeiten gibt... je nach dem welchen zug man machen wuerde, oeffnen sich da verschiedene und verschieden viele moeglichkeiten... trivial ist es aber natuerlich, dass es endlich moeglichkeiten geben MUSS! ich werde trotz diesem forum noch weiterueberlegen, falls mir was nuetzliches einfaellt, schreib ich natuerlich rein... |
||||||||
| 03.04.2006, 16:37 | AD | Auf diesen Beitrag antworten » | ||||||
Also ich glaube, das mit dem Berechnen musst du dir aus dem Kopf schlagen. Obere Schranken kann man sich überlegen, aber je weniger Aufwand man da reinsteckt, umso barbarisch schlechter werden die sein. Wesentlich überhaupt für die Endlichkeit der Schachpartie-Anzahlen dürfte allerdings nicht die Wiederhol-, sondern die die 50-Züge-Regel sein. |
||||||||
| 03.04.2006, 16:47 | The Rob | Auf diesen Beitrag antworten » | ||||||
| RE: schachpartie... die wiederhol regel ist sehr wichtig fuer die endlichkeit der verschiedenen schachpartien! ansonsten koennte man unendliche viele verschiedene schachpartien aufstellen, da man ja 1 mal einen zug wiederholen kann und dann einen anderen, oder 2 mal diesem zug wiederholen kann und dann einen anderen, oder 3 mal diesen zug... bekannt ist ja, dass es unendlich viele natuerlich zahlen gibt... 
daher ist das trivial... |
||||||||
| 03.04.2006, 17:01 | JochenX | Auf diesen Beitrag antworten » | ||||||
RE: schachpartie...
Welches immer die "Wiederholregel" sein soll.... sowohl die 50-Zügeregel als auch die Regel der 3-fachen Stellungswiederholung reichen beide allein vollkommen aus, die endliche Anzahl von "möglichen" Partien zu zeigen. 50 Zügeregel: es kann nur endlich viele Bauernzüge geben (96) und es können nur endlich viele Figuren geschlagen werden (30). Das liefert ziemlich schnell eine obere Zugschranke von (126)*50+50 Zügen, in denen man also auch nur endlich viele Zugfolgen fabrizieren kann. 3-fache Stellungswiederholung: Es kann nur endlich viele Positionen überhaupt geben (auch wenn man "Rochaderechte", "en passant-Rechte" alles mit einbezieht). Das liefert diesmal eine obere Schranke an Stellungen, die in einer Partie vorkommen dürfen, und somit findet man wieder eine Zügezahl, die maximal ist; weitaus größer ist diese Schranke aber als die obige! Wobei ganz btw. eine dreifache Stellungswiederholung und auch das verletzen der 50-Zügeregel nicht reklamiert werden MÜSSEN, wobei ich da doch noch mal meine Veerinskameraden mit Schiedsrichterausbildung fragen müsste, ob die Partie offiziell trotzdem als beendet gilt (wie auch "Matt" und "Patt", die in Blitzpartien schon ab und an "nicht zum Ende geführt haben"). Am Ende lässt sich also die Zahl ohne Schiedsrichterwissen (meines ist da leider durch meine Inaktivität gesunken) eh nie bestimmen.
Gruß, Vereinsspieler |
||||||||
| 03.04.2006, 17:05 | AD | Auf diesen Beitrag antworten » | ||||||
Beide, sowohl Wiederhol- als auch 50-Züge-Regel garantieren die Endlichkeit der Partie. Aber laut letzterer kann man zumindest die Zuganzahl vernünftig nach oben abschätzen (es sind maximal 5899), was bei ersterer immer noch eine astronomische Zahl ist. Insofern ist die 50-Züge-Regel auch für Abschätzungen der Partienanzahl die bessere Wahl. EDIT: Oh, hab ich wohl etwas lange zum Formulieren gebraucht. Aber gut, dass jetzt ein Schachexperte da ist, ich verzieh mich... 
|
||||||||
| 03.04.2006, 17:08 | The Rob | Auf diesen Beitrag antworten » | ||||||
| RE: schachpartie... ich habe diese frage hier gestellt, mit dem hintergrund, dass man eigentlich ein programm schreiben koennte, das alle meoglichen stellungen mitbeinhaltet und auf jede moegliche stellung den besten zug zieht... daggn koennte eigentlich KEINER gewinnen...oder? 
und dann muesste auch immer remis herauskommen, wenn man zwei solche programme ggneinanderspielen lassen wuerde... gut ausmoeglich, dass die zahl der moeglichen spiele noch etwas zu groß fuer unseren heutigen pc sei... aber bald muesste es bald DAS unbesiegbare schachprogramm geben... unheimlich fuer mich schachspieler... 
|
||||||||
| Anzeige | ||||||||
|
|
||||||||
| 03.04.2006, 17:09 | JochenX | Auf diesen Beitrag antworten » | ||||||
nix da, Arthur, die "5899" musst du schon erklären 
ich komme auf etwas mehr als 6000, wenn ich davon ausgehe, das Bauernzüge und Schlagfälle je genau im 50. Zug geschehen. Dabei insbesondere natürlich keine Bauern geschlagen werden.
und wer sagt, was "der beste" Zug ist? schon mal was von Sub- vs. Objektivität gehört!? Ich kenne deinen Spielstil ja inzwischen ETWAS, du würdest vermutlich 98% der Partien verlieren, die ich eröffne. Wobei ich stets den für meinen Spielstil besten Zug gewählt hätte. Andersrum würde ich als (sinnloser
) Offensivspieler deine Eröffnungen nur gähnend fortsetzen.... |
||||||||
| 03.04.2006, 17:11 | AD | Auf diesen Beitrag antworten » | ||||||
Ich hab nur aus dem verlinkten Wikipedia-Artikel abgeschrieben, ungeprüft. 
|
||||||||
| 03.04.2006, 17:16 | The Rob | Auf diesen Beitrag antworten » | ||||||
als schwarz eroeffnet mane igentlich mehr als als weiss eine partie... da mann da eher entscheiden kann wie es weitergeht... mit besten zug koennte man meinen, dass viele schachspieler aus der spitze der weltrangliste an diesem prog arbeiten wuerden... so ein spiel waer dann wahrscheinlich voll von fallen... auf die ich eine nach der anderen hineinfallen wuerde...
|
||||||||
| 03.04.2006, 17:22 | The Rob | Auf diesen Beitrag antworten » | ||||||
und was die 98% angeht, koennen wir ja ausprobieren... ich moechte das naehmlich nicht so einfach glauben...
|
||||||||
| 03.04.2006, 17:23 | JochenX | Auf diesen Beitrag antworten » | ||||||
Arthur: 
, das hast du verdient
Rob: Womit dein Programm schon mehrfach gestorben ist 1) kriegen wir nicht alle (relevanten!) Stellungen auf dem Brett gezählt 2) würde es nur Mord und Totschlag geben, wenn sich einige der Spitzenspieler zusammensetzen müssten 3) würde der Nasarechner keine ausreichende Speicherkapazität haben WOBEI: Eigentlich gäbe es nach deiner Idee eh nur noch eine einzige Partie (schließlich wird JEDESMAL aus der einen Datenbank der besten Züge der "eindeutige Beste" gespielt, also kommt nur ein Partie zu Stande) Ganz nebenbei: Für die Endspiele der Wenigsteiner (ich glaube inzwischen bis Fünfsteinerm, teilweise auch schon für Sechssteiner) gibt es das schon "ähnlich": schau mal nach den Endspieldatenbanken von Asimov und wie sie alle heißen, hab aber keine Ahnung, ob es die nicht nur käuflich zu erwerben gilt. Da muss ich selbst mal googlen. |
||||||||
| 03.04.2006, 17:27 | The Rob | Auf diesen Beitrag antworten » | ||||||
da gibt es nicht nur eine partie, da das prog abhaengig vom gegnerische n zug verschieden zuege ziehen muss... |
||||||||
| 03.04.2006, 17:34 | JochenX | Auf diesen Beitrag antworten » | ||||||
achso der Gegner nutzt das Tool also nicht
aber 1 bis 3 sollten ausreichen, um deinen jugendlichen Traum platzen zu lassen.
|
||||||||
| 03.04.2006, 17:35 | AD | Auf diesen Beitrag antworten » | ||||||
@Jochen Damit ich etwas zurückhauen kann:
Du irrst, ein ideales Schachprogramm, welches immer optimal spielt, braucht nicht viel Speicherplatz, ich würde da inklusive Programm mit weniger als 10 MByte auskommen. Die einzige Schwierigkeit ist, dass ich dazu einen nahezu unendlich schnellen Rechner brauche - und da geht's nicht nur um ein paar Zehnerpotenzen gegenüber heute, sondern deutlich mehr. Leider spricht so ziemlich alles in der Relativitätstheorie gegen einen derartigen Geschwindigkeitszuwachs.
|
||||||||
| 03.04.2006, 17:43 | JochenX | Auf diesen Beitrag antworten » | ||||||
existiert nicht; ich habe genug selbst getestet sowohl die Spieler als auch die Computer haben eins gemeinsam: sie irren aber so ne Runde boxen rockt, oder?
|
||||||||
| 03.04.2006, 18:13 | lego | Auf diesen Beitrag antworten » | ||||||
da das programm ja selber die richtigen züge finden wird müssen, hängt die spielstärke vom programm stark von der stellungsbeurteilung ab. und wie das programm die stellung beurteilen soll, gibt ihm ein mensch vor, bzw mehrere, also kann es nur so gut sein wie seine entwickler. und wenn ich mir die stellungbeurteilung bei den gängigsten schachprogrammen momentan so ansehe, vor allem, was ungleiche materialverteilung betrifft, werden sich die entwickler noch ganz schön anstrengen dürfen, bis das programm perfekt arbeitet |
||||||||
| 03.04.2006, 18:16 | JochenX | Auf diesen Beitrag antworten » | ||||||
Traurig zu sehen, dass die Schachelite trotzdem reihenweise von PC-Programmen flachgelegt wird. Gut, dass es da doch den Herrn Carstens aus der "Rochade Europa" gibt.
|
||||||||
| 03.04.2006, 18:20 | AD | Auf diesen Beitrag antworten » | ||||||
So richtig zuende gelesen hast du meinen Beitrag aber nicht.
|
||||||||
| 03.04.2006, 18:27 | JochenX | Auf diesen Beitrag antworten » | ||||||
Doch, aber ich wüsste nicht, warum ein "unendlich schneller Rechner" das Problem lösen sollte. Das wird jetzt Offtopic, aber ich finde es schön, über Schach zu reden. Deiner Meinung nach hängt dann eigentlich auch die Spielstärke EINES JEDEN Programms fast ausschlißelich vom Prozessor und dem Technikrest ab!? Das spielt natürlich eine Rolle, aber ich glaube kaum, dass du mit beliebiger Rechenleistung beliebige Spielleistung in jedes Programm stecken könntest. Und selbst wenn: Rechne dein PC innerhalb von Sekunden beliebig viele Positionen durch, wegen mir kann er auch unendlich viele, dann berechnet er eben in einer Sekunde alle möglichen (<unendlich, oben gesehen). Dann muss er seine Zwischenergebnisse ja trotzdem irgendwo SPEICHERN. Und ich bleibe dabei, in Anbetracht der Tatsache, dass es ******** (umgangssprachlich "ganz viele") mögliche Folgen gibt, wäre der Speicheraufwand, selbst wenn jeder Folgezug nur in einem Bit gemessen wäre, so groß, dass er sämtliche Kapazitäten, die bekannt sind sprengen würde. Ich glaube, beim PC wird das Sprengen durch hashen vereitelt und durch löschen "abgehakter Varianten", bzw. eben dadurch, dass er gar nicht erst so tief rechnen KANN. edit: entschuldigung, vergessen:
|
||||||||
| 03.04.2006, 18:28 | Abakus | Auf diesen Beitrag antworten » | ||||||
Wenn man noch mitrechnet, dass am Ende der Partie die Könige noch 50 Züge alleine herumtappen können, endet eine Partie spätestens mit dem 5.949-sten Zug von Weiß. Mehr geht nicht. (Allerdings nur, wenn bei Eintreten der 50-Züge-Regel jeweils auch Schluß gemacht wird, was ja nicht zwingend ist). Da die Anzahl der Schachstellungen endlich ist, sind es auch die Stellungen, in denen Weiß matt gesetzt hat. Nun kann man diese Stellungsmenge hernehmen und alle Stellungen dazu nehmen, die mit 1 Zug zu so einer Stellung führen und dieses Verfahren iterieren. Irgendwann kommen keine weiteren Stellungen dazu. Nun braucht man nur nachschauen, ob die Anfangsstellung in dieser Menge enthalten ist oder nicht. Wenn ja, wäre jede Partie mit Weiß gewinnbar, entsprechend analoges Verfahren für Schwarz. Grüße Abakus
|
||||||||
| 03.04.2006, 18:33 | JochenX | Auf diesen Beitrag antworten » | ||||||
kann mir irgendjemand denn nun diese Zahl <6000 erklären? Irgendwas muss da ja dran sein an den 5889 von der Wikipedia, wenn du das auch so errechnet hast, Abakus (oder hast du auch von da kopiert?). Die letzten 50 Züge kannst du bei dir sparen Abakus, die Partie gilt als Remis wegen "zum Mattsetzen unzureichendem Material". Aber ich komme dennoch auf über 6000 und will eine Herleitung. *quengel* |
||||||||
| 03.04.2006, 18:54 | AD | Auf diesen Beitrag antworten » | ||||||
Hab ich nirgendwo behauptet!!! 
Zu meiner "Programmidee": Zwischenspeichern muss der Rechner nur den Pfad bis zum Blatt des riesigen Baumes, und wie wir gerade rausgefunden haben, sind das maximal ca. 6000*2 = 12000 Rekursionsebenen. An jedem Zwischenknoten wird die Stellung vermerkt (also Positionen der Figuren, Enpassant- und Rochaderechte, Anzahl Züge ohne Schlagen bzw. Bauernbewegung, und was es sonst so gibt...), da kommt man selbst bei großzügiger Speicherverschwendung mit 100 Byte pro Stellung aus. Und es wird vermerkt, ob man bei Minimax-Strategie in der weiteren Verzweigung des Baumes gewinnt, verliert oder Remis spielt. Das stellt sich natürlich erst bei Verzweigung bis in die letzten Blätter heraus, wo man auf Stellungen stößt, bei denen nach Schachregeln Schluss ist. Ich behaupte nicht, dass das praktikabel ist oder auch nur den Hauch von Effizienz besitzt, aber im Gedankenexperiment ist das möglich ohne große Speicherkapazitäten. |
||||||||
| 03.04.2006, 19:01 | JochenX | Auf diesen Beitrag antworten » | ||||||
ui, ein neuer Smiley, den mag ich aber nicht 
ich bin vielleicht in Sachen programmieren und dynamischem Programmieren etc. auch eingfach zu ungebildet. Was du mit "Minimax" meinst, weiß ich auch nicht. Aber wenn in deinen 12000 (wegen mir auch nur 10000) Rekursionsebenen jeweils auch nur sagen wir genau 5 mögliche Züge zur verfügung stehen, gibt es (theoretisch) doch 5^(10000) mögliche "Endstellungen", die alle mit +/-/= bewertet werden müssten (was ja auch irgendwo vermerkt sein muss) Die Anzahl hat mehr als 1000 Stellen. Ach ich gebs ja zu, ich habe von programmieren keine Ahnung, ich bleibe bei meinem Kopf, wenn's ums Schach geht. achja, diesmal keine Haue zurück, ich bin wohl einfach zu bleed. |
||||||||
| 03.04.2006, 19:02 | Abakus | Auf diesen Beitrag antworten » | ||||||
Die Überlegung ist wie folgt: Weiß und Schwarz können nur 48 Bauernzüge ausführen, von diesen 96 Zügen müssen 8 Schlagzüge sein, weil die Bauern sonst nicht aneinander vorbeikommen. Die verbleibenden (32 - 2 Könige - 16 Bauern - 8 Geschlagene =) 6 Figuren und die umgewandelten 16 Figuren können insgesamt geschlagen werden. Das macht: 96 + 6 + 16 = 118 und 118 * 50 = 5.900 Züge. Ferner muss die Initiative einmal von Schwarz auf Weiß wechseln, was zum Verlust von 1 Zug führt, macht 5.899 Züge. Grüße Abakus
|
||||||||
| 03.04.2006, 19:09 | JochenX | Auf diesen Beitrag antworten » | ||||||
ohje, die Bauern hoppeln (wie man im Fachjargon sagt
) ja nicht aneinder vorbei, ohne Schlag/Bauernzug gleichzeitig auszuführen.Vielen Dank. 
|
||||||||
| 03.04.2006, 19:14 | AD | Auf diesen Beitrag antworten » | ||||||
Richtig, aber nur immer entlang des aktuellen Pfades, nicht in parallelen Verästelungen (d.h. gleicher Rekursionsebene). Und deine Abschätzungen deuten natürlich richtigerweise an, dass kein vernünftiger Mensch ein real nutzbares Schachprogramm so anlegen würde.
P.S.: Den
-Smiley gibt's von mir immer für Leute, die mir irgendwelche Aussagen andichten wollen, die ich nie auch nur annähernd geäußert habe. Also nichts für ungut. |
||||||||
| 03.04.2006, 19:27 | JochenX | Auf diesen Beitrag antworten » | ||||||
aaaaaaaaaah! 
Ich habe also meine Ausgangsstellung und davon aus ganz viiiele Reksursionsebenen (direkt z.B. ausgehend davon 5 Pfade, weil 5 Züge, bzw. vielleicht auch 25 Pfade, weil 25 Zugpaare, wenn man sinnvollerweise alle Erwiderungen noch miteinbezieht; dann kann man das ganze auch realistisch von 5 enorm hochsetzen auf 20,30 mögliche Züge). Betrachte nun einen der Pfade.... Dann wird der genauso rekursiv zu +/-/= bzw. einer genauen Bewertung geführt. Anschließend wird der dann (wie auch immer das dann wieder genau gehen soll) als +0,81 oder so gespeichert und DANN wird ein anderer Pfad angegangen. Irgendwie so könnte das wohl funktionieren.
wenn du das so siehst, dann muss ich mich wohl entschuldigen, das war nicht meine Absicht. |
||||||||
| 03.04.2006, 21:21 | The Rob | Auf diesen Beitrag antworten » | ||||||
zum bearbeiten brauechte man einen sehr schnellen rechner, oder viel ziet, und "etwas" spiecherplatz... das program waere dann aber klein, da es nur die zuege wissen soll, die am besten sind... und das sinde dann nicht mehr sooo viele...das ist dann ein bruchteil, als wenn man alle moeglichkeiten speichern wuerde...und deswgn verliere ich meine hoffnung nicht, dass ich noch ggn solch ein prog kaempfen werde
und dann natuerlich verlieren... |
||||||||
| 03.04.2006, 23:37 | Ben Sisko | Auf diesen Beitrag antworten » | ||||||
Erstmal vorweg: Ich hab wenig Ahnung von Schach, aber mich interessiert das von euch angedachte Programm
Ich hatte es so verstanden, dass das "ideale Programm" alle möglichen Spielsituationen durchrechnen kann und daher kein Expertenwissen, also keine Beurteilung einer Stellung mehr benötigt. Warum führst du, Arthur, dann hier aber die Minimax-Strategie an? Dazu müsste das Programm doch wissen, was "min" und was "max" ist, oder? Also welcher der optimale Zug in der jeweiligen Situation... Hab ich was falsch verstanden? Gruß vom Ben |
||||||||
|
|