Entwickler-Ecke
Off Topic - Mehr eine Mathe/Informatik Frage....aber
catweasel - Di 16.07.02 21:55
Titel: Mehr eine Mathe/Informatik Frage....aber
Hi,
Erst mal sorry, wegen dem megaPosting, aber was ich wissen will is auch megakompliziert.
Danke für Geduld und Verständniss....
Also:
Mein "Problem" dreht sich um Schach. (und ein Problem das ich mit einem Programm lösen will). Es gibt in der Mathematik einen Bereich der sich mit "Spieltheorie" beschäftigt. Hier versucht man anhand der Regeln eines Spiels herauszufinden, ob der beginnende Spieler oder sein Gegner
eine Möglichkeit (Strategie) hat das Süieö in JEDEM Fall zu gewinnen. Ein solches Spiel ist "unfair".
Ein kleines Beispiel für ein unfaires Spiel: Das Spiel beginnt bei 0 und jeder zählt abwechselnd zur zahl 1 oder zwei dazu. Die Wahl hat der Spieler. Der beginnende Spieler sagt z.b. 1-2, so kann der zweite spiere entweder 3 oder 3-4 sagen. etc. Wer zuerst 20 sagen kann hat gewonnen.
Das Süiel ist unfair, da: wer z.b. 17 sagen kann hat im Prinzip schon gewonnen. Sagt der andere 18 sagt man 19-20; sagt er 18-19, sagt man selbst 20. Dies klappt auch schon bei 14, denn man kann auf jeden Fall danach auf 17 kommen was ja zum Sieg führt. U.s.w.
Fazit: Wer beginnt MUSS verlieren, selbst wenn er UND der Gegenspieler diese Strategie kennen.
Anmerkung: Eine andere Form des "unfairen" Spiels (also ohne Gewinnmöglichkeit), ist das gute alte Tic-Tac-Toe. Hier kann man auch unmöglich gewinnen. Aber auch nicht verlieren. Ein solches Spiel geht
immer unentschieden aus.
Aber zurück zu Schach:
Wir konzentrieren uns auf eine Siegstrategie und interssieren und daher nur für die Bedingungen einer unentschiedenen Partie:
- Nur noch 2 Könige auf dem Brett.
- König nicht im Schach, aber kein Zug möglich.
- 50 Züge kein Bauer bewegt oder Figur geschlagen.
- 3 Mal hintereinander selbe Brettstellung.
Daraus ist zu folgern, dass eine Schachpartie, selbst theoretisch, nicht beliebig lang sein kann.
Die Anzahl der Zuglisten jeder möglichen Schachpartie ist also endlich.
Würde man alle diese Listen erstellen, (also alle möglichen Partien "durchspielen"), könnte man, beispielsweise für Schwarz, prüfen, ob es eine Möglichkeit für Schwarz gibt,auf jeden Zug von Weiss
DEN Gegenzug zu wählen, der zum gewünschten Ergebniss "Schwarz gewinnt" führt.
Dazu muss ja mehrere "Teilbäume" geben, die früher oder später zum gewünschten Strang führen.
Manche Spieler (und auch Computer) erkennen solche Teilbäume in Endpielen teilweise (man kennt ja dieses prophetische "Matt in 5 Zügen" und so). Mit diesen Listen hiesse es: "Matt nach dem X(?) Zügen" nach dem ersten Zug.....
Die Aufgabe besteht also darin, per Programm (vermutlich rekursiv) alle möglichen Partien (nicht Brettstellungen!!) aufzulisten....
Wenn ihr jetzt nur Bahnhof und Kofferklau versteht, liegt es daran dass ich das so umständlich beschrieben habe. der grundlegende Gedanke is aber logisch richtig... ehrlich
Noch ein Wort zur Durchführbarkeit:
Es ist klar, das selbst die kürzesten Zuglisten sehr viele Kombinationen enthält.
Man müsste mit den KÜRZESTEN liste anfangen und sie erweitern, wenn keine unfaire Strategie existiert.
Achja: Oben beschreibene frage habe ich mal in einem Mathebuch gelesen. Bei Dame gibts solche Strategien in Endspielsituationen bereits. D.h. bei einer bestimmten Brettsituation kann ein Spieler den anderen mit je einem passenden Zug zum verlieren Zwingen.
Mailt mal eure Ideen und/oder Fragen...
Catweasel
Udontknow - Mi 17.07.02 08:40
Hallo!
Ist nicht jedes Spiel, daß nicht das Element des Zufalls (zum Bsp. Würfel bei "Mensch, ärgere dich nicht") enthält, ein in diesem Sinne "unfaires" Spiel? :roll:
Ohne Zufall (bei Schach: mit der Rechenleistung, sämtliche Züge rekursiv durchzugehen) sind es schliesslich komplett determinierte Systeme, man kann zu 100% bestimmen, welcher Zug der beste für einen selbst wäre, der Gegner würde ebenfalls den für sich besten Zug wählen, und so weiter. Sämtliche Spielpartien würden dann ganz gleich ablaufen. (gleiche Bedingungen, gleiche Wirkung -> Determinismus).
Cu,
Udontknow
catweasel - Mi 17.07.02 11:17
Titel: Determinismus
Hi,
Erst mal Danke für die Antwort.. (hoffe es werden noch mehr.. Ich will das mal ausdiskutieren).. :wink:
Du hast Recht was die Spiele wie Mensch Ärgere dich nicht, Prinzipiell auch alle Kartenspiele und ähnliches angeht.
Aber bei Schach, selbst wenn jeder Spieler den für sich besten Zug
herausfindet, kann es Variationen geben. Unentschiedene Tic-Tac-Toe Spiele haben auch mehrere "Stellungsbilder"......
Eine Brettstellung im Schach, die in der "ultimativen Strategie" vorkommt, taucht auch in zig anderen Spielen auf, somit ist die Zahl der Baumstränge am Anfang ssehr gross und dünnt sich erst mit Fortschreiten der Partie, dh. Weniger Zugmöglichkeiten insgesamt aus. (Wie gesagt dieses "Matt in 5 Zügen" zeigt dass es bei Bäumen von "nur" 5 Zügen ja schon möglich ist, was übrigens MAXIMAL 5 Zühe heisst. Als Trotteliger Spieler kann ich das immernoch verzocken, oder als blöder Gegenspieler kann aich auch schon nach 3 Zügen matt gehen).
Vorrausgesetzt du hast mein Beispiel mit dem Zählen bis 20 richtig verstanden: Es ist auch hier möglich z.b. erst bei 11 auf dieses "unfairen" Pfad zu wechseln... Wer 11 Sagen kann, kann auch AUF JEDEN ´FALL 14....17...und schliesslich 20 sagen.
D.h.: Dem oder den Spielern ist schon vor der Partie klar wer gewinnen wird. (Entweder Schwarz oder weiss, je nachdem ob der Beginnende oder der Nichtbeginnende Spieler einen "unfairen" Vorteil hat).
Also bei der Frage "Gibt es eine Möglichkeit für Schwarz, IMMER zu gewinnen, weil Schwarz nicht beginnen muss". Exisitiert also zu JEDEM BELIEBIGEN Zug ein Konterzug der zum Ergebniss: Schwarz gewinnt führt.
hmmm.. wie gesagt, weitere Kommentare sind sehr willkommen....
Catweasel
Udontknow - Mi 17.07.02 11:47
Hallo nochmal!
| Zitat: |
Aber bei Schach, selbst wenn jeder Spieler den für sich besten Zug
herausfindet, kann es Variationen geben. |
Moment, wir gehen doch davon aus, daß man sämtliche Züge überblicken kann und man eben keine (Denk-)Fehler macht!
Natürlich machen Spieler unterschiedliche Züge, aber die sind ja auch nicht in der Lage, SÄMTLICHE Züge fehlerfrei vorauszuahnen!
Wenn ich (im Besitz der weissen Figuren) zu Beginn eines Schachspieles meinen SuperMegaHyper-Computer anschmeisse, der den besten Zug anhand rekursiven Durchgehens sämtlicher möglichen Spielverläufe für mich ermittelt, wieso sollte er am Anfang einer anderen Partie plötzlich einen anderen Zug empfehlen?
Mein Gegner schmeisst nach meinem Zug ebenfalls seinen SuperComputer an. Er wird selbstverständlich auch den für sich besten Zug ausführen. Und dieser wird sich in einer anderen Partie, in der genau derselbe Zug gekommen ist, nicht anders verhalten, er wird genau denselben Zug wieder empfehlen.
Dies ist in allen Partien dann immer genau dieselbe Abfolge von Zügen!
Und genau das ist dann auch wieder die Sache mit dem Determinismus. Das es eine solche ultimative Spielweise gibt, steht für mich ausser Frage.
Die Frage ist jetzt: Führt ein solcher Überblick zum Sieg des Beginners, zur Niederlage des Beginners, oder etwa zum Remis? Gibt es evtl. einen im wahrsten Sinne des Wortes
unschlagbaren Vorteil, weiss oder schwarz zu haben?
Ich schätze, diese Frage wird dir so schnell niemand beantworten können, da es, so habe ich es mal vernommen, mehr Spielkombinationen im Schach als Teilchen im Universum gibt.
Cu, :D
Udontknow
catweasel - Mi 17.07.02 12:43
Titel: Variationen...
Hi,
Nehmen wir mal zwei Bauern (pro Spieler) auf dem Schabrett.
Es vergehen zwei Zugpaare.
Am Ende der jeweils zwei Züge befinden sich beide Bauern (je Spieler) ein Feld weiter "vorne".
Nun gubt es die Möglichkeiten:
Spieler 1 Bauer A nach vorne
Spieler 2 Bauer A nach vorne
Spieler 1 Bauer B nach vorne
Spieler 2 Bauer B nach vorne
oder:
Spieler 1 Bauer A nach vorne
Spieler 2 Bauer B nach vorne
Spieler 1 Bauer B nach vorne
Spieler 2 Bauer A nach vorne
oder:
Spieler 1 Bauer B nach vorne
Spieler 2 Bauer B nach vorne
Spieler 1 Bauer A nach vorne
Spieler 2 Bauer A nach vorne
oder:
Spieler 1 Bauer B nach vorne
Spieler 2 Bauer A nach vorne
Spieler 1 Bauer A nach vorne
Spieler 2 Bauer B nach vorne
... Das erbegniss sieht von der Brettstellung in jedem dieser Fälle identisch aus.
Also sind gewisse Variationen die zum selben Ergebniss führen möglich.
Das ist wie bei den Lottozahlen.
Es gibt meherere Möglichkeiten 6 richtige zu ziehen, da die Reihenfolge (bei lotto) beliebig ist. Bei Schach würden die Möglichkeiten obiger Bauernzüge von eventuellem Schach bei Zug eines Bauern, etc abhängen, aber manchen Fällen (vor allem in der Anfangsphase) ist es tatsächlich "fast" egal wie man zieht (im Sinne von:"alles ist trotzdem noch drin").
Noch etwas zum Thema Supercomputer und besten Zug....
Bei Tic-Tac-Toe wird auch ein bester Computer nur ein Unendschieden erreichen;
Bei meinem Beispiel mit "bis 20 zählen" kann selbst der beste Supercomputer NUR VERLIEREN wenn er beginnen muss, selbst wenn er die Strategie kennt ist er machtlos. ER KANN NICHT GEWINNEN. Probiers mal aus...Die Strategie bei diesem "Spiel" ist recht leicht zu durchschauen.
Catweasel.
ps: Das die Rechenleistung gewaltig sein müsste is schon klar, aber man müsste sie ja auch nur einmal ausführen und als Datenbank archivieren (am besten DBase).
Für jemand mit dieser Datenbank wäre Schach dann ebenso witzlos wie Tic-Tac-Toe.
Udontknow - Mi 17.07.02 13:00
Wir reden aneinander vorbei. :?
Mir ist völlig bewusst, das auch ein Supercomputer bei dem Nimmspiel "den kürzeren zieht". Meiner Meinung ganz einfach deswegen, weil dieses Spiel ohne Zufallselemente daherkommt.
Ich behaupte:
Sobald der Zufall in einem System (ob nun Schach oder Nimmspiel) ausgeschlossen ist, ist dieses System determiniert, in der Theorie bis aufs kleinste vorhersehbar.
Natürlich stimmt es, daß man durch die verschiedensten Zugkombinationen ein und dieselbe Situation auf dem Schachbrett erzeugen kann.
Aber darum geht es gar nicht: Die Beispiele mit dem Supercomputer sollten verdeutlichen, daß es, wenn zwei Computerprogramme mit ein und denselben Voraussetzungen gegeneinander spielen würden, und diese Programme ultimativ Schach spielen (also alle Zugfolgen berücksichtigen könnten), ohne in irgendeiner Weise Zufallsentscheidungen zu treffen, immer und immer wieder zu ein und derselben Partie kommen würde.
BTW: Dbase für alle zugkombinationen im Schach, gewagt, gewagt... :shock: Wenn das nicht die Grenze für DBase-Datenbanken sprengt???
Cu,
Udontknow
catweasel - Mi 17.07.02 15:57
Titel: Okok der Zufall ist da.....
Hi....
Has mit DBase war nicht ernst gemeint...
Ich glaube kaum das ein gegenwärtig ein Datenbanksystem diese Menge an Informationen verwalten kann....
Der "Zufall" wenn man so will liegt beim Schach darin, Weiss oder Schwarz zu haben........
Darum geht es ja: MUSS einer verlieren weil er anfangt, oder MUSS er verlieren weil er nicht anfängt......
Was auch nicht ganz ausgeschlossen ist: Ist es etwa möglich von vorneherein auf Remis zu spielen und dieses auch zu ERZWINGEN ?
Cu
Catweasel...
Udontknow - Mi 17.07.02 16:12
Hmm, das hatte ich aber schon versucht, auszudrücken:
Ich glaube, daß man sehr wohl ein Ergebnis erzwingen kann. Nur welches, das ist die Frage (hihi, schon mal versucht, eine Niederlage zu erzwingen? Das könnte auch lustig sein: Gewonnen hat, wer geschlagen wurde. :D ...)
Der Ausgang einer solchen Partie ist in der Theorie definitiv bestimmbar.
Wir wissen aus rein praktischen Gründen (mangelnde Rechenpower, um sämtliche möglichen Züge zu überblicken) jedoch nicht, welches der drei Ergebnisse (Weiss gewinnt/Remis/Schwarz gewinnt) es nun ist (werden es wohl auch noch nicht so schnell herausfinden).
Bist du da anderer Meinung?
Cu,
Udontknow
catweasel - Mi 17.07.02 20:21
Titel: Keineswegs....
Da bin ich keineswegs anderer Meinung....
Man doch Schach komplett den Reiz nehmen, oder?
Nur wieviel Rechenpower bräuchte man eigentlich?
Ich denke da an SuperComputer wie den "EathSimulator" bei Tokio.
Oder an das MultiClient Projekt SETI@home.
Ob so eine Art der Analyse in Frage kommt hängt jedoch davon ab, ob und wie sich die mathematischen Abhängigkeiten innerhalb des Algorhytmus auflösen lassen.....
Man müsste doch zumindest Grob abschätzen können wieviel Partien es gibt.?!
Catweasel
ps: Man macht etwas sehr altes Kaputt.(Vgl. Zeile 2) Fällt das dann unter "Zerstörung Kulturellen irgendwas", quasi ein "geistiger Terroranschlag" . :lol: :lol: (nich so ernst gemeint :wink: )
tommie-lie - Di 23.07.02 10:17
Hi Leute,
Schon wieder poste ich, obwohl das Topic eigentlich geschlossen ist. Ich glaub ich werde wahnsinnig.
Aber ich denke trotzdem, daß ich für unser Wiesel etwas betragen kann.
Verzeiht mir, wenn es etwas zu einer Art "Vorlesung" ausartet.
Wenn man von Anfang an, jeden Zug berechnen müsste, bräuchte man eine Rechenleistung, die in keinem PC vorhanden ist.
Doch wir bewegen uns hier jetzt mal etwas fernab von Raum und Zeit, und ich werde nur gelegentlich anmerken, wofür die Rechenleistung draufgeht.
Der Computer hat keine Intelligenz. Normalerweise könnte er nicht Schach spielen. Das kann er genaugenommen auch nicht, sondern er macht lediglich Wahrscheinlichkeitsrechnung. Er überprüft, mit welchem Zug komme ich am kürzesten zum Sieg?
Doch damit er das kann, muss er alle Züge wissen, die möglich sind.
Wenn man vorbereitungszeit hat, erstellt man dafür am besten eine Art Verzeichnis, mit allen Zügen.
Zum verständnis ein vereinfachtes Beispiel:
Nur noch 2 Könige auf dem Brett. Die umliegenden Felder erhalten nummern von 1-8 (der König kann ja immer um 1 Feld, das um ihn herum liegt ziehen).
Dann schreibt man eine Schleife, die jedes Feld auf seine Gültigkeit überprüft (steht da schon der andere König? ist da der Rand des Spielbrettes?) Die verbleibenden Felder jagt man wieder durch eine Schleife. Jeder gültige Schritt wird aufgezeichnet (Eine Datenbank ist der einzig Mögliche weg, der übersichtlich genug ist, wenn man auch für eine Text-File-Liste weniger Rechenkraft braucht, benötigt man bei dieser mehr Zeit zum suchen).
Dann, wenn der König um ein Feld gezogen wurde, werden die Felder um ihn herum wieder nummeriert und wieder geht's durch die Schelife, die ihn wieder eins weiterzeiht.
Das Baumdiagramm dafür würde dann in etwa so aussehen:
Quelltext
1: 2: 3:
| 1--------------------------2 1 1 1 usw. 2 2 2 1 1 1 1 2 3 1 2 3 1 2 3 |
Wobei die erste Zeile für den ersten Zug steht, die zweite für den zweiten Zug usw.
Die einzelnen Splaten stellen die Dimensionen dar, die das Szenario haben kann.
Man sieht also, alle möglichen Züge in einer Art Liste. Natürlich muss der "Ast" abgebrochen werden, wenn Schachmatt ist (ich weiß mit zwei Königen geht das nciht, aber wenn mehr Figuren drauf sind, muss so eine prüfung erfolgen).
Jetzt hat man eine Liste, die sämtliche Züge anzeigt.
Natürlich muss man das dann mit allen Figuren machen. Und man darf nicht vergessen, man muss _*ZEITGLEICH'_, aber nicht in einem zweiten Thread, sondern immer abwechselnd, den anderen Spieler mitberechnen. Da wird's schon schwieriger. Man muss, wenn man alle Züge für den weißen Spieler berechnet hat, die des schwarzen zu berechnen. Dann kommt man in eine hypotetische Spielwelt hinein, die für jeden Zug eine parallele Dimension hat.
Das würde dann so ablaufen:
(w=weiß s=schwarz)
wenn w die Figur nach 1, dann s auch nach 1
wenn w die Figur nach 1, dann s nach 2
wenn w nach 1, dann s nach 3
Also wieder nach dem gleichen Prinzip wie bei dem Baum.
Man kommt dabei recht schnell an die Grenzen der Computer.
Schachprogramme lösen das Problem der Resourcen übrigens, indem sie nicht bis zum Ende denken, wie es hier verlangt wird, sondern immer nur eine bestimmt Anzahl von hypotetischen Zügen voraussehen und davon dann den besten aussuchen.
Wenn man nun vor dem Spiel so eine Zug-Liste hat, dann könnte der Computer immer noch nicht wissen, welcher Zug der beste ist. Im Endeffekt, führt jeder Zug nach längerer oder kürzerer Zeit zum Sieg, oder zur Niederlage. Das einzige, was man machen muss, ist zu schauen, welcher Zug am schnellsten zum Ziel führt.
Das geht recht einfach:
Ist der Computer weiß, überprüft er in seinem Verzeichnis, welcher der kürzeste Ast im Baum ist. Den arbeitet er ab, indem er den ersten Zug macht.
Ist er schwarz, guckt er, was der weiße getan hat, und schaut in seinem Verzeichnis, welcher Baum so anfängt. Hat der den Ast gefunden, arbeitet er auch diesen ab.
Vorraussetzung bleibt immer wieder, daß man eine Liste mit BEIDEN Spielern hat.
Somit ließe sich das Problem von catweasel lösen, und man erfährt, wie ist die Partie am schnellsten zu ende, was muss man machen, um genau nach X Zügen zu gewinnen, usw.
Doch leider ist genau da auch das Problem. Man brächte für das Erstellen der Liste enorm viel Rechenleistung. Ganz zu schweigen vom Speicher, um die Liste zu speichern.
Wenn man Schachprogramme anschaut, und beobachtet, wie lange der Rechner braucht, um nur ein einziges Problem mit beschränter Zu,kunft von etwa 10 Zügen zu berechnen, kann man immer noch nicht einschätzen, wieviel Zeit er braucht, um ALLE Schach-Probleme mit ALLEN Zügen zu berechnen.
Das war's. Theoretisch ist es möglich, aber praktisch fehlt die Hardware für eine Echtzeitanwendung.
Aber wenn du (catweasle) einen alten Pentium, oder so, hast, den du so nicht brauchst kannst du es ja mal probieren. Den musst du dann aber Tag und Nacht laufen lassen, und wahrscheinlich für mehrere Wochen oder Monate. Monitor brauchst du ja nicht. Einfach als Numbercruncher laufen lassen. Vorraussetzung ist natürlich eine große Festplatte, denn ich kann die Datenmengen nicht überschauen, aber ein paar Megabyte werden's bestimmt ;-)
Falls einer das ernsthaft vorhat, würde ich's gern wissen, dann würde ich mit ihm gern ein Essay für meine HP schreiben.
Eins ist noch zu sagen:
Es wäre doch langweilig, gegen so einen Computer zu spielen, denn er kann nur gewinnen. Man würde dauernd deprimiert das Spiel beenden, und hätte nie ein Erfolgserlebnis, denn der Rechner weiß über die Zukunft und über die Vergangenheit bescheid, und er weiß auch, welchen Zug er machen muss, um das Problem gar nicht erst zu machen, denn beim Schach kann man nur verlieren, wenn man dumm genug ist. Ein solcher Computer könnte das "Schach in 5 Zügen" umgehen, indem er genau merkt "aha, der Gegenspieler geht den typischen Weg, den ich nehmen würde um so schnell wie möglich zu gewinnen" und er kann durch sein Verzeichnis relativ schnell den Weg verbauen.
Das wäre doch total langweilig.
(Denk-)Fehler werden gern entgegengenommen!!!
Bye
tommie-lie
tommie-lie - Di 23.07.02 10:20
hey, der hat ja die leerzeichen bei meinem Baum weggemacht.
Naja, vielleicht erkennt ihr trotzdem was ich meine
Tino - Di 23.07.02 10:27
| tommie-lie hat folgendes geschrieben: |
| hey, der hat ja die leerzeichen bei meinem Baum weggemacht. |
Ich hab mal Code-Tags eingefügt. Vielleicht kann man es so besser lesen!
tommie-lie - Di 23.07.02 11:01
nein, die Zahlen sollen genau untereinander
111
123
222
123
111
123
catweasel - Mi 24.07.02 22:14
Titel: Wahrscheinlichkeit hmmmm.. eigentlich nicht...
Hi....
Eigentlich schon toll wie sich aus der Frage eine Diskussion entwickelt hat... :wink:
Mit dem was tommy geschrieben hat kann ich mich on eonigen Punkten nicht so ganz anfreunden.
Ein Schachprogramm wie Fritz z.b. plant seine Züge nicht nach wahrscheinlichkeiten, sondern nach Stellungswert. Jede Figur hat dabei eine Wertigkeit von 1-10 die auch ihrer Grundwertigkeit entspricht (Bauer 1; König 10). Das Feld auf dem sie steht spielt auch eine Rolle. Felder in der Mitte sind wertvoller als am Rand, etc....
Da ist nix mit Wahrscheinlichkeiten. Die "Strategie" komm dadurch zustande, dass schlaue Leute ihm beigebracht (Eröffnungsbibliotheken, Endspielbibliotheken, etc), haben wie man gut spielt.
Die Züge des Gegners muss man NICHT mitberechnen, da sie, wenn man ALLE möglichen Partien durchrechnet darin ja schon enthalten sind.
ALLE möglichen Partien eben..
Dass der Computer mit eben dieser Datenbank immer gewinnen muss hängt davon ab ob er mit schwarz oder weiss spielt (warum, siehe postings diverser verfasser weiter oben).
Es wäre ja auch ein Remis möglich, welches sich IMMER erzwingen lässt (TicTacToe).
Was die benötigte Rechenleistung angeht.....
Das SETI@home Project läuft zur Zeit mit etwa 38 TeraFlops...
Das is doch schonmal was, oder.... (is das viel?)
Catweasel
tommie-lie - Do 25.07.02 13:46
Wenn Fritz (kenn ich nicht) das auf diese Art und Weise macht, berechnet er das ja nicht selbst. die Leistung kommt von demjenigen, der die Bibliothek erstellt hat. Bei meiner Möglichkeit ist es die Leistung des Rechners, sodaß der Rechner gegen den Spieler gewonnen hatm nicht der Programmierer.
Schwarz/weiß:
Hab ich ja auch gesagt, daß es drauf ankommt wer weiß spielt.
Rechenleistung:
SETI@home hat demzufolge 38Milliarden Fließkomma-Operationen pro sekunde. Das ist schon viel, aber man muss bedenken, daß beim SETI@home mehrere hunderttausende Rechner vernetzt sind.
Ein einziger Rechner schafft das nicht. Wie gesagt einen alten Rechner könnte man dafür einspannen, für ein paar Wochen/Monate/Jahre.
Bye
tommi-lie
weiti - Do 26.09.02 11:24
Titel: Schach
Computer kann nicht Schach spieln? ansichtssache, ob einer, der zu dumm ist sich alle Möglichekeiten zu merken und deswegen nur nach gewissen 'Regeln' bzw seinem persönlichen besten Zug spielt(Mensch) oder ein Computer, der logisch vorgeht indem er alle Zügekennt...
zu den Meinungen, dass Schach durch so etwas langweilig wird... denkt einmal nach wieviele Zugmöglichkeiten, vom Gegner, es gibt, welche man nicht berechnen kann(sonst spielt man irgendwie nicht gegeneinander). Schach würde nur langweilig werden, wenn man weiß, was der Gegner macht, solange man dass nicht weiß(und das wird man nie) wird Schach bestimmt nie langweilig. Im Gegenteil durch solche Strategien werden solche 5-Züge-Siege vermieden und damit das Spiel interessanter und länger!
Aber ich glaube/weiß/vermute oder sonst was, dass es bei Schach keinen Anfangszug gibt, mit dem man(egal was der Gegner später für Züge macht) einen bestimmten Ausgang des Spieles erzwingen kann(nicht einmal verlieren.
Aber ein wirklich interessantes Thema... :D
Gruß weiti
Anonymous - Di 01.10.02 13:36
Titel: die strategie ist doch vorhanden
Moin Weiti und all die anderen hier im Thread,
du sagst man weiss nie was der geneer macht.. Doch weisst du wenn du hinsiehst...(nachdem er den zug gemacht hat)
Aufgrund der Determinierbarkeit des Systems "Schach" aufgrund eines zufallsunabhängigen Regelwerks (das unendlich lange Spielverläufe unterbindet), ist es mathematisch beweisbar das eine solche Strategie existiert.
(Vergleiche dazu das Spielebeispiel "Zählen bis 20"in postings weiter oben)
Diese Strategie aus der Schar allr möglichen Strategien herauszufinden ist das eigentliche Interessante. Das ginge nur durch Ausprobieren..
(Studiert hier vielleicht jemand Mathematik oder so, oder hat an der Uni Connections zu so nem Prof) ?
Catweasel
tommie-lie - Di 01.10.02 14:49
Hallo catweasel,
Wie sieht'S denn bisher aus? Hast du unsere Vorschläge mal in ein Programm umgesetzt?
Wenn ja, wie lange rechnet er denn schon?
Tschüß
Thomas
Udontknow - Mi 02.10.02 13:03
Hi nochmal,
Ich habe gerade was vom neuen Seti@home gehört, das bald anläuft. Dort werden dann auch andere Dinge erforscht (siehe
hier [
http://www.heise.de/newsticker/data/hps-02.10.02-000/]).
Wer weiss, vielleicht ergründen durch vernetztes Rechnen ja bald Millionen PC´s auf der Welt auch genau die hier gestellte Frage?
Cu,
Udontknow
tommie-lie - Mi 02.10.02 14:31
stimmt, die wollten sich 'ne neue Antenne besorgen, weil die alte wohl nicht die gesamte Hemisphäre abgedeckt hat.
Ich dachte das dauert noch ein weilchen...
catweasel - Mo 07.10.02 23:05
Titel: Kein Programm, aber ne hochrechnung
Hi...
Um auf ne Frage weiter oben zu antworten....
Nein, es gibt noch kein programm dazu, aber ich habe einmal hochgerechnet welchen umfang die Datenbank am ende haben müsste....
Nach meinen Überlegungen dürfte es etwa "(50 hoch 32) und davon die Fakultät" verschiedene Partien geben.
Von denen bräuchte man jetzt die Zuglisten..... Also alle Permutationen von Partien die möglich sind........
Allerdings düfte es schon schwer fallen die Fakultät von 50 hoch 32 zu berechnen....
Catweasel
tommie-lie - Di 08.10.02 13:06
Ich hab' doch gesagt das das eine weie dauert um alle Züge zu berechnen. Daher auch meine Empfehlung, nciht den Arbeitsrechner dafür einzuspannen sondern einen alten Rechner der ruhig mal länger laufen kann. Aber wenn's wirklich so ernorm ist, sollte man wohl lieber doch einen neuen Rechner nehmen, mit schneller und vor allem großer Festplatte...
Tschüß
Thomas
Udontknow - Do 24.10.02 11:37
Hallo!
Habe gerade einen interessanten Artikel über dieses Thema gefunden.
http://www.guardian.co.uk/online/story/0,3605,817484,00.html
Es gibt also bereits einige Spiele (nein, Schach ist nicht dabei), bei denen sämtliche Zugkombinationen durchgerechnet wurden und die z.B. durch den anfangenden Spieler zu gewinnen sind.
Cu, :D
Udontknow
catweasel - Sa 04.10.03 11:17
Titel: Mal wieder reingeschaut
Hi,
nach langer Programmier-Abstinenz hab ich mal wieder den Weg ins Delphi Forum gefunden..
Schon toll das die ganzen alten Beiträge noch hier sind.. :D
Diesen Thread hier fand ich eigentlich ganz erbaulich *gg*
Den wollt ich grad mal wiederbeleben :lol:
Den Artikel (schon ne weile her) aus dem guardian ist tatsächlich interessant :shock:
Auch wenns nur ein Jahr her ist, aber das mit der Rechenleistung sollte inzwischen etwas besser geworden sein .. :D
Catweasel
JoelH - Sa 04.10.03 12:12
Titel: Re: Mehr eine Mathe/Informatik Frage....aber
| catweasel hat folgendes geschrieben: |
- Nur noch 2 Könige auf dem Brett.
- König nicht im Schach, aber kein Zug möglich.
- 50 Züge kein Bauer bewegt oder Figur geschlagen.
- 3 Mal hintereinander selbe Brettstellung. |
Leider ist diese 50 Zügeregel eine Krux, weil sie durch eben solche rekursive Berechnungen ad absurdum gefürht wurde. Man verhindert durch diese Regel dass die Siegerseite gewinnt.
Es gibt zb. eine sogenannte Kling-Horwitz Verteidigungsstellung, diese galt als 100% Remis, bis Ken Thompson (Erfinder von Unix aber auch ein alter Schachtüftler) herraschfand, bzw. berechnetet, dass die maximale Gewinnführung 66 Züge bedarf. Wer hat nun recht, die Regel die von Menschen gemacht wurde oder die Wirklichkeit ? Des weiteren gibt es einige Stellungen KTL gegen KSS , diese sind nach spätestens 223 Zügen gewonnen. zB. wKa7, Tb2, Lb3 gegen sKd3, Sc6, Sd6 . Nach 223 Zügen gewinnt weiss einen Springer und nach ein paar weiteren die Partie.
Damit gehst du dann leider von einer falschen Vorraussetzung aus.
Die vierte Regel du anführst ist auch nicht richtig, denn die Stellung muss NICHT dreimal HINTEREINANDER auftretten sondern sondern einfach nur 3x entstehen bei gleichem Zugrecht, identischen enPassent Zuständen etc. Dazwischen können aber sehr wohl xyz viele Züge liegen.
Wie auch immer, die dritte Vorrausetzung darf man so nicht als gegeben werten und dadurch werden die Partien fast unendlich lang, weil zugfolgen zyklisch auftreten können. Aber wenn masn die vierte Regel mit drin läst dann enden auch diese Partien. Allerdings hast du dann noch immer ein winziges Problem, es sind einfach zuviele Stellungen. Kommen wir auf die KTL-KSS dingens zurück, dafür berechnete Lewis Stiller 1991 > 100000000000 Stellungen und das bei nur 6 vorhanden Steinen, wieviele werden das dann wohl bei 32 Steinen sein, vor allem weil durch die Bauern die ganzen symetrieen auf dem Brett flach fallen ?
Gausi - So 05.10.03 18:48
Mal ein paar Anmerken dazu:
| catweasel hat folgendes geschrieben: |
| Nach meinen Überlegungen dürfte es etwa "(50 hoch 32) und davon die Fakultät" verschiedene Partien geben. |
Kann sein. Auf jeden Fall stimmt das mit dem "etwas hoch irgendwas"
| catweasel hat folgendes geschrieben: |
| Auch wenns nur ein Jahr her ist, aber das mit der Rechenleistung sollte inzwischen etwas besser geworden sein .. |
Ich hoffe ernsthaft, dass das nur ein Scherz war. Die Rechenleistung hat sich evtl. verdoppelt, ok, aber bei DER Menge an Partien is das ungefähr so, als würde man die Sahara nicht mit einem Schäufelchen, sondern mit zweien umgraben wollen.
Überleg mal, wielange unser Universum existiert...ca. 2^17 Sekunden. Diese Laufzeit mit der Seti-Rechenleistung (btw.:810 DataUnits completed) ergibt 2^29. Also: selbst wenn die "50" nur eine "2" wäre, und wenn man für jeden PARTIE nur einen "Flop" bräuchte, dann würde man 8 mal mehr Zeit brauchen, als unser Universum bisher existiert. Und das mit der Fakultät habe ich dann noch vergessen...und die Tatsache, dass man für eine Partie wohl auch MEHR als 1 Flop benötigt.
Ein alter Pentium im Keller richtet da ungefähr genauso viel aus wie ein Kind mit ner Schaufel in der Sahara, oder ne Flasche Wasser um die Sonne zu löschen. Und wenn man nen neuen nimmt...gut dann sinds halt 6 Kinder, oder ein halber Kasten.
catweasel - Mo 06.10.03 19:07
Zu den Anmerkungen:
Das mit dem "besser" geworden war tatsächlich eher uronisch gemeint....
Aber was du im Bezug auf die Rechenleistung sagst ist etwas unrichtig (aber auch nicht ganz falsch)..
Es stimmt das in einem Jahr sich die Rechenleistung die möglich ist verdoppelt, aaaaaber trotzdem ist die gesamtrechenleistung
gestiegen.
Nehmen wir mal SETI@home als Beispiel....
wenn alle Benutzer ihren Rechner upgraden im Laufe des Jahres wird die Performance von Seti grösser...Aber eben höchstens doppelt so gross, wie du sagst.
Aber es gibt auch immer mehr Rechner auf der Welt.
Die Rechenleistung erhöht sich mit jeder CPU die verbaut wird...
(Teilweise erreicht SETI@home bis zu 93 TeraFLOPS)
Es ging mir bei der Frage ja nur darum mal abzuschätzen wie gross der Aufwand sein dürfte...
... und etwas das ein bischen untergegangen ist:
Ich wollte wissen on sich so ein "spiele-alle-partien-auf-und-schreib-sie-in-eine-datenbank" Algorhytmus überhaupt als distributed process laufen könnte. Das ginge nur wenn man genügend Abhängigkeiten innerhalb des Algorhytmus auflösen kann. (Sonst muss ja doch wieder eine CPU auf andere warten).
Ich habe mich mit Algorhytmen noch nicht so sehr beschäftigt, ausser einigeen banalen Sortiergeschichten.....
Ich würde aber gern das Grundprinzig von Algorhytmen näher verstehen und wissen WIE man solche Abhängigkeiten erkennt und Auflöst...
catweasel - Mo 06.10.03 19:16
Ahh eins noch:
"Das Programm" nennen wir es mal so :wink: müsste gar keine grossartigen "Berechnungen" (kompliziertes Rechen für jeden Zug..)
ausführen, sondern nur stupide jede mögliche Partie durchziehen.
Der Gedanke daran das es auch nur eine begrenzte Anzahl möglicher TICTACTOE Spielverläufe gibt lässt sich vielleicht leichter nachvollziehen.
Hier könnte man das sogar noch relativ leicht berechnen....
Die Anzweisung würe lauten..: "Fülle ein 3*3 Raster abwechselnd mit Kreuzen und Kreisen in allen Möglichkeiten dies zu tun."
Danach müsste einem auffallen, wenn man alle möglichen Partien betrachtet, das bei einigen Kreuz, bei einigen Kreis gewinnt und das es einige "Unentschieden"-Spielverläufe gibt.
Nach weiterem Nachdenken fält dann auf das man von JEDEM Kreis-gewinnt Spielverlauf und von JEDEM Kreuz-gewinnt Spielverlauf auf den Unentschieden-Ast wechseln kann.
Deshalb lässt sich bei Tic Tac Toe IMMER ein unentschieden erzwingen..
Catweasel
Gausi - Mo 06.10.03 20:29
| Zitat: |
| Aber es gibt auch immer mehr Rechner auf der Welt. |
Ok, ja, es gibt immer mehr Rechner auf der Welt. Dann kipp ich eben ne LKW-Ladung mit Wasserkästen in die Sonne..UND?
| Zitat: |
| Ich würde aber gern das Grundprinzig von Algorhytmen näher verstehen und wissen WIE man solche Abhängigkeiten erkennt und Auflöst... |
Grundprinzip von Algorithmen? Das gibts nicht. Aber ne Definition
| Abu Jafar Hohammed ibu Musa al-Khowarizimi (825) hat folgendes geschrieben: |
Ein Algorithmus ist eine präzise Vorschrift, um aus vorgegebenen Eingaben in endlich vielen Schritten eine bestimmte Ausgabe zu ermitteln.
|
Wenn man also einen neuen Algorithmus schreibt, muss man sich "nur" überlegen, was man eingeben kann, was man ausgeben will, und wie man von der Eingabe zur Ausgabe kommt.
| Zitat: |
| Ich wollte wissen on sich so ein "spiele-alle-partien-auf-und-schreib-sie-in-eine-datenbank" Algorhytmus überhaupt als distributed process laufen könnte. Das ginge nur wenn man genügend Abhängigkeiten innerhalb des Algorhytmus auflösen kann. (Sonst muss ja doch wieder eine CPU auf andere warten). |
Hmm..Das Thema "parallele Algorithmen" ist mal noch ne Ecke komplizierter.
Aber prinzipiell müßte das gehen, schliesslich sind die einzelnen Partien doch von einander unabhängig, oder nicht? D.h. jeder Rechner könnte sich eine Partie=Folge_von_Zügen nehmen und kontrollieren, wer gewinnt. Diese kann man dann eine Datenbank in einer Baumstruktur speichern, und diesen Baum könnte man dann daraufhin untersuchen, ob es eine Gewinnstrategie für weiss gibt, d.h. egal welchen Zug schwarz wählt gibt es immer wieder einen Zug, so dass weiss noch gewinnen kann.
Aber wie gesagt: Praktisch durchführbar ist das nicht. Die Rechenleistung reicht nicht aus. Nicht heute, nicht in 100 Jahren. Es ist nicht das Problem, dass die Rechner zu langsam sind. Es ist ja auch ein Speicher-Problem: Es gibt nur ca. 10^78 Atome im Universum, wie willst du da (50^32)! Partien drin speichern? (Komm mir bitte nicht mit: Es gibt ja noch Quarks ....:roll: )
Ok, ich ersetz in meinem Rechner die Harddisk durch ein Paralleluniversum, beschleunige mich auf 99,9999% Lichtgeschwindigkeit, warte ein paar Jahre, in der Zeit sind zuhause mehrere Milliarden Jahre vergangen und dann kann ich mir das Ergebnis angucken...Und dann such ich mir einen dummen, der gegen mich Schach spielt :lol:
worm - Mo 06.10.03 23:06
Wirklich interessantes Thema! Ich geb mal meinen Senf dazu, aber ich bin kein Profi...
Also gut... die Anzahl der möglichen Partien ist wohl wirklich unüberschaubar (und auch nicht so einfach mit Exponenten und Fakultäten zu berechnen, da man ja immer die Spielregeln beachten muss und nicht bei jedem Brett eine so leicht berechenbare Anzahl an Zugmöglichkeiten hat). Die einzige Chance, die Fragestellung "Ist Schach ein unfaires Spiel?" zu lösen, wäre, dass in einem der 20 Partiebäume, die vom ersten Zug von Weiß ausgehen (8x Bauer einen vor + 8x Bauer 2 vor + je 2 Möglichkeiten für die 2 Springer... was vergessen? Hab ewig kein Schachbrett mehr gesehen), sich rechtzeitig herausstellt, dass es sich dabei um einen "unfairen Baum" handelt und man so gar nicht
alle Partien berechnen muss. Das heißt, die Bäume müssten alle gleichzeitig abgearbeitet werden.
Das ließe sich verteilen auf mehrere Rechner: Ein Rechner beginnt und berechnet alle möglichen Züge von weiß. Einen dieser Züge nimmt er sich und rechnet damit weiter, die restlichen (inklusive gesamtem bisherigem Partieverlauf) gibt er an 19 (?) andere Rechner weiter. Jetzt berechnen alle 20 Rechner jeweils alle Möglichkeiten für Zug 2 (den ersten Zug von schwarz). Jeder dieser 20 Rechner nimmt sich eine seiner errechneten N Möglichkeiten und gibt alle übrigen (inkl. Partieverlauf) wieder weiter an je N-1 Rechner. Kommt irgendein Rechner zum Ende einer Partie, muss der Partieverlauf irgendwo zentral gespeichert werden und dann stellt sich der Rechner wieder zur Verfügung und nimmt von anderen Rechnern offene Partiebäume entgegen.
Irgendwann wird der Punkt erreicht sein, an dem kein Rechner mehr zur Verfügung steht, der weitere offene Bäume entgegennimmt. Ab dann müssen die Rechner anders arbeiten. Statt die offenen Bäume zu verteilen, merkt sich jeder Rechner die offenen Bäume. Jetzt berechnet er zu jedem offenen Baum die Möglichkeiten für je einen weiteren Zug, hängt also bei jedem Baum eine neue Ebene an. Dies kann er jetzt noch eine ganze Weile ausführen, bis nicht mehr genug Speicherplatz für das Anlegen der Daten für eine neue Ebene zur Verfügung steht.
Und jetzt komm ich nicht weiter... ist es jetzt eigentlich theoretisch möglich, dass man aus den bisher gewonnenen fertigen Partieverläufen ermitteln kann, ob Schach ein unfaires Spiel ist? Benötigt man dazu wirklich unbedingt
alle Partieverläufe? Wie lassen sich die Ergebnisse "Schach ist ein faires Spiel" und "Schach ist ein unfaires Spiel" definieren? Reichen also eventuell nur einige Partieverläufe, um das eine oder das andere zu beweisen oder zu widerlegen? :?!?:
Nachtrag: Hab grad noch was interessantes gefunden:
http://mitglied.lycos.de/assiac/fakten.htm
Punkte ix) und xi) sind von Interesse. Demnach gäbe es entweder 10^18900 oder 10^(10^70,5) mögliche Schachpartien... vielleicht sollte man das ganze Problem doch nicht mit BruteForce angehen :?
Gausi - Di 07.10.03 10:54
| Zitat: |
| Wie lassen sich die Ergebnisse "Schach ist ein faires Spiel" und "Schach ist ein unfaires Spiel" definieren? |
Wie ich das im Kopf habe, wäre Schach ein "unfaires Spiel", wenn es einen Zug für Weiss gibt, so dass es für jeden Zug für Schwarz einen Zug für Weiss gibt, so dass es für jeden Zug für Schwarz einen Zug für Weiss gibt, [....], so dass Weiss gewinnt. (d.h. es gibt eine Gewinnstrategie für Weiss)
Ein faires Spiel wäre dann die Veneinung dieser Aussage, also: Für alle Züge von Weiss gibt es einen Zug für Schwarz, so dass für jeden Zug von Weiss es einen Zug für Schwarz gibt,[...], so dass Weiss nicht gewinnt. (d.h. es gibt keine Gewinnstrategie für Weiss).
worm - Di 07.10.03 16:31
Das, was du als faires Spiel angegeben hast, wäre ja auch wieder ein unfaires Spiel. Dann gäbe es ja eine sichere Strategie für Schwarz, oder? Schwarz hätte ja dann die Macht, ein Unentschieden oder seinen Gewinn zu erzwingen. Bei einem fairen Spiel müssen ja immer alle Möglichkeiten offen sein, oder?
Ich wollte aber eigentlich wissen: Ergibt sich aus dieser Definition noch etwas anderes? Es lässt sich ja dann nicht sagen: "Ein Spiel ist nur unfair, wenn alle Partien, die von einem bestimmten Ausgangsbaum ausgehen, damit enden, dass weiß gewinnt". Das wäre zwar auch ein unfaires Spiel, aber schon mehr, als nötig. Aber ergeben sich noch irgendwelche ähnlichen Aussagen aus der Aussage "Es handelt sich um ein (un)faires Spiel"?
recall - Di 07.10.03 16:41
Hallo,
Ich muss dazu jetzt mal was lustiges schreiben, weil ich es einfach nur komisch finde, dass ihr euch ECHT darüber unterhaltet, dass man eventuell alle Schach-Kombinationen auflisten, abspeichern und überhaupt berechnen könnte :)
Dazu 3 Szenarien:
1. Mein PC rechnet unendlich schnell. Ich will jetzt alle berechneten Wege abspeichern. Das muss ich zumindest temporär tun, um zu speichern, was ich alles schon ausprobiert habe, und was ich noch ausprobieren muss ! Dann brauche ich laut worm eine Speicherkapazität von 10^18900 bit. ANgenommen ich könnte ein Elementarteilchen (meinetwegen auch ein Quark) so manipulieren, dass es die Information eines bit trägt (Das wäre eine Speicherdichte, die um das Trilliardenfache größer ist, als unsere Festplatten heute !) Dann bräuchte ich als Festplatte 10^120 Universen !!!! um den Mist zu speichern.
2. Mein PC ist endlich schnell. Nehmen wir an, die Lichtgeschwindigkeit kann nicht überschritten werden. Allein daraus folgt schon die Rechendauere mehrerer Milliarden Jahre-Milliarden - Jahr-Milliarden !!! Und das nur, wenn ich einen Transistor aus EINEM! Molekül aufbauen kann :(
3. Mein PC ist unendlich schnell und ich kann alles speichern (wie auch immer). Dann ist zwar bewiesen, dass es nur endlich viele Speilzüge gibt. Tatsächlich kann ein solches Spiel bei einer Zugdauer von einer Minute aber bis zu 70 Stunden dauern (würde keiner mehr spielen) !
Als Anmerkung: Um diese Zeitspanne einzuhalten (1 Minute) müsstest du
unser Universum 10^120-mal durchsuchen (dabei jedes Quark einzeln überprüfen) um den richtigen Antwortzug zu finden !
Viele Grüsse und viel Erfolg beim Erfinden ( :) )
Gausi - Di 07.10.03 16:57
@recall: Ganz meine Meinung. Ich glaube, aus meinen letzten Beiträgen hier geht hervor, dass ich das für genauso bekloppt habe. Es gibt halt Sachen, die gehen nicht. Und nein, das ist nicht damit vergleichbar, dass man vor 100 Jahren eine Mondlandung für unmöglich gehalten hat...
Aber man kann ja auch mal über was sinnloses diskutieren, oder nicht?
catweasel - Di 07.10.03 18:18
Titel: @ so einige :-)
@gausi @recall @worm,
aaallso :wink:
@gausi
was du meintest bei Algorhytmen gibt es kein "Konzept", sondern nur eine Definition.
Vielleicht war Konzept etwas ungeschickt von mir ausgedrückt, aber was worn so Pronzipiell mit meheren Rechnern und Vorgehensweise veranschaulicht hat kommt dem nahe was ich unter "Konzept" (im Sinner von Vorgehensweise) verstehe.
In sofern wäre dieser Teil meiner Frage bantwortet :D
@worm
ja, was du sagst ist richtig, das Spiel wäre "nur" unfair wenn alle Partien "ab einem Bestimmten Baum" damit ausgehen dass weiss gewinnt.
Und in meiner Fragestellung ist mein Baum der, der mit der Grundstellung beginnt....
@recall
also ich denke mal das wir inzwischen alle wissen (ich übrigends schon beim Stellen der Frage), das es faktisch unmöglich sein wird (Resourcenmangel) dieses Problem zu lösen.
Aber darum ging es auch nie wirklich.
Sondern um die prinzipielle Frage an sich : Ist Schach fair.
oder nicht ?
Wei es darum etwas Verwirrung gab:
Meine Definition eines fairen und unfairen Spiels finden sich mit zwei Beispielen gaaaaanz am Anfang dieses Threads....
niemand hat die Absicht eine Mauer zu ..ähh das Universum zum Speichern zu nutzen :wink:
Aber ist doch ein nettes Thema... und sinnlos?
Naja, so sinnlos ist es garnicht wenn man mal vernachlässigt das man es nicht durchrechnen kann (berechnen ginge ja prinzipiell).
Ich denke mal das die Leute die in den Artiklen erwähnt werden..
Nochmal gepostet wegen Übersichtlichkeit:
http://mitglied.lycos.de/assiac/fakten.htm
http://www.guardian.co.uk/online/story/0,3605,817484,00.html
Ich denke die Faszination (für manche) an der Frage ist, das es etwas ist was wir theoretisch wissen könnten, aber dazu nicht im Stande sind.
Nicht etwa so wie bei der Frage Warum gabs den Urknall?
Das kann man nicht rausbekommen und basta (Prinzipiell nicht).
Bei der Schachfrage hat man auch etwas von dem man weiss das man es nie rausbekommen wird. Es aber
könnte.
Wie Gaussi gesagt hat:
Es ist nicht vergleichbar mit der Sache das vor 100 Jahren eine Mondlandung auch für unmöglich gehalten wurde,
aber wenn sich selbst vor über 100 Jahren intelligente und fachlich gebildete Leute (offensichtlich ohne Computer), ernsthafte Gedanken (bishin zur Publikation) gemacht haben,
dann sollten unsere Überlegungen heute zumindest nicht "sinnloser" sein....
Es geht eben ums Prinzip :wink:
Achja:
Wer meint mit einer solchen Frage wäre man schon in jeglichen Regionen des "Grössenwahns" verloren..... :lol:
Stellen wir doch mal die Frage für ein anderes Spiel....
GO :twisted: *muhahahaha*
(falls jemandem "GO" nichts sagt... es ist noch viiiieeeelllll komplexer als Schach.. Gegen GO ist Schach wirklich sowas wie TicTac Toe......
Catweasel
Adrian - Mi 08.10.03 14:34
Servus!
| Gausi hat folgendes geschrieben: |
Überleg mal, wielange unser Universum existiert...ca. 2^17 Sekunden. |
2^17 Sek.=131072 Sek = ca. 1,5 Tage
Jetzt frage ich mich nicht mehr, was ich vorletzte Nacht gemacht habe... :wink:
Gruß,
Adrian
Gausi - Mi 08.10.03 14:50
aargh..da hab ich doch tatsächlich die falsche Basis im Kopp gehabt. Selbstverständlich existiert das Universum mehr als 2 Tage. Es muss natürlich heissen 10^17 Sekunden, mit einem Faktor von ca. 5 davor. An der grundlegenden Aussage, die ich in dem betreffenden Post gemacht habe, ändert sich aber durch diese kleine Ungenauigkeit nichs...
Ausserdem: Es gibt ja bekanntlich 10 Arten von Menschen: solche die binär denken, und solche, die es nicht tun...
worm - Do 09.10.03 00:52
Titel: Re: @ so einige :-)
| recall hat folgendes geschrieben: |
| dass ihr euch ECHT darüber unterhaltet, dass man eventuell alle Schach-Kombinationen auflisten, abspeichern und überhaupt berechnen könnte |
Das tatsächlich zu realisieren, ist in diesem Thread schon ziemlich früh verworfen worden. Aber es ist trotzdem interessant, sich mal zu überlegen, wie man es
theoretisch realisieren könnte...
| catweasel hat folgendes geschrieben: |
| ja, was du sagst ist richtig, das Spiel wäre "nur" unfair wenn alle Partien "ab einem Bestimmten Baum" damit ausgehen dass weiss gewinnt. |
Nein, eben nicht... dann wäre es ja egal, was Weiß macht (
und egal, was Schwarz macht); Weiß gewinnt auf jeden Fall. Das ist ja schon zu viel. Unfair ist das Spiel auch, wenn Weiß immer
nur die Möglichkeit hat, einen Sieg zu erzwingen. Es können also auch Partien mit z.B. Unentschieden enden, aber eben nur, wenn Weiß irgendwann einmal nicht die Möglichkeit nutzt, die zum Erzwingen des Sieges nötig ist.
| catweasel hat folgendes geschrieben: |
Aber darum ging es auch nie wirklich.
Sondern um die prinzipielle Frage an sich : Ist Schach fair.
oder nicht ? |
Ja genau. Und mir ging es jetzt um die Frage: Ist es vielleicht möglich, diese Frage zu beantworten,
ohne alle möglichen Partien berechnen zu müssen? Das heißt, könnte sich die Frage vielleicht doch beantworten lassen?
| catweasel hat folgendes geschrieben: |
Wei es darum etwas Verwirrung gab:
Meine Definition eines fairen und unfairen Spiels finden sich mit zwei Beispielen gaaaaanz am Anfang dieses Threads.... |
Ja. Aber wenn man direkt nach dieser Definition vorgeht, müsste man doch alle Partien kennen, oder? Ergibt sich aus dieser Definition noch irgendetwas, was das Problem vereinfachen und vielleicht lösbar machen würde?
Geht man beispielsweise von der Definition "ein Spiel ist unfair, wenn alle von einem bestimmten Ausgangszug ausgehenden Partien mit dem gleichen Ergebnis enden" aus, so kann man dies nämlich recht leicht widerlegen, indem man einfach für jeden der 20 Ausgangszüge je 2 verschiedene Partieausgänge findet. Man muss also nicht alle möglichen Partien berechnen. Damit hat man allerdings, da die Definition nicht lautet "ein Spiel ist
genau dann und nur dann unfair, wenn ...", noch nicht bewiesen, dass Schach fair ist.
Aber gibt es vielleicht noch irgendetwas anderes in der Art? Um zu beweisen, dass Schach ein faires Spiel ist, muss man dazu alle Partien kennen und analysieren? Oder gibt es da etwas einfacheres, was man zeigen muss?
| catweasel hat folgendes geschrieben: |
Ich denke die Faszination (für manche) an der Frage ist, das es etwas ist was wir theoretisch wissen könnten, aber dazu nicht im Stande sind.
Nicht etwa so wie bei der Frage Warum gabs den Urknall? |
Oder bei der Frage: Warum sind beim Urknall nicht genügend Teilchen entstanden, um alle möglichen Partien eines Schachspiels zu speichern? :wink:
Moment mal, ich hab noch eine Idee: Könnte man mit den Teilchen des Universums denn eine sichere Gewinnstrategie überhaupt speichern? Wenn nein, wäre Schach ja quasi ein faires Spiel.
Für eine sichere Gewinnstrategie müsste man ja, ausgehend von einem bestimmten der 20 Ausgangszüge (wenn man weiß ist) oder für jeden der 20 Ausgangszüge (wenn man schwarz ist), auf jeden möglichen Zug des Gegners mindestens einen Zug wissen, der den Gegner irgendwann sicher Schach Matt zwingt. Ist diese Menge an Daten auch schon unspeicherbar in unserem Universum, dann ist Schach quasi ein faires Spiel (quasi, weil eine sichere Gewinnstrategie ja doch
theoretisch existieren könnte... :nut:).
PS:
| Gausi hat folgendes geschrieben: |
| Ausserdem: Es gibt ja bekanntlich 10 Arten von Menschen: solche die binär denken, und solche, die es nicht tun... |
Und für erstere lautet die Antwort 101010 :P!
Udontknow - Mo 13.10.03 09:36
Hallo!
| Zitat: |
| Ist diese Menge an Daten auch schon unspeicherbar in unserem Universum, dann ist Schach quasi ein faires Spiel (quasi, weil eine sichere Gewinnstrategie ja doch theoretisch existieren könnte... ). |
Wieso? Alle Daten müssen doch nicht abgelegt werden und permanent verfügbar sein. In jeder Stellung
berechnet der Computer eben den besten Zug, anstatt ihn aus einer riesigen Datenbank zu fischen.
@recall:
Nur weil ich 20000 Verzeichnisse auf meiner HD habe, benötige ich zum Rekursiven Durchforsten nicht Platz für diese 20000, sondern nur Platz in Relation zur maximalen Verzeichnistiefe. Das gleiche gilt auch für diese Problematik.
Cu,
Udontknow
catweasel - Di 14.10.03 13:58
HalliHallo,
| Zitat: |
Wieso? Alle Daten müssen doch nicht abgelegt werden und permanent verfügbar sein. In jeder Stellung berechnet der Computer eben den besten Zug, anstatt ihn aus einer riesigen Datenbank zu fischen.
@recall:
Nur weil ich 20000 Verzeichnisse auf meiner HD habe, benötige ich zum Rekursiven Durchforsten nicht Platz für diese 20000, sondern nur Platz in Relation zur maximalen Verzeichnistiefe. Das gleiche gilt auch für diese Problematik. |
Ja, das stimmt schon, dann wird dieser Rechenaufwand aber bei JEDEM Zug von neuem nötig.
Er nimmt zwar mit weniger werdenden Figuren auf dem Brett ab, aber wäre immernoch gewaltig.
Würde man alles jedoch in einer Datenbank ablegen, wäre die Rechenarbeit ein für allemal erledigt. Der Rechner müsste NIE wieder "rechnen" sondern wirklich nur noch "nachschlagen"....
Catweasel
BenBE - Mo 19.07.04 19:20
Anmerkung zum Distributed Computing:
Es müsste MINDESTENS 3 Programmteile geben:
Ein Programmteil kümmert sich um das Suchen der Stellung in einer zentralen Datenbank um die Speicherung und Auffinden von Datensätzen (Server).
Ein weitere müsste Von vorgegebenen Spielsituationen ALLE Möglichen Züge ermitteln und diese übermitteln (Client).
Und der dritte Teil müsste aus diesen Informationen die Partien zusammensetzen (Client\Server möglich IMHO).
Achso: Ein weiterer Teil könnte sich um die Bewertung der Spielsituationen kümmern (Client).
Aber so wirklich pures Distributed Computing wird bei diesem Problem nicht möglich sein.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!