Schach theoretisch lösbar

    • FrtZ
      FrtZ
      Black
      Dabei seit: 25.08.2006 Beiträge: 3.412
      Sers,
      hatte mit meiner Profesorrin heute ne längere Diksussion über die prinzipielle Lösbarkeit von Schach, also die Möglichkeit einer perfekten Partie. Sie hat selbige natürlich abgestritten und ich war halt der Meinung, dass es nur an der Rechenleistung scheitert, theoretisch aber möglich sei. Meine, dass es für ne gewisse Anzahl von Figuren left auch schon möglich ist und sehe keinen Grund warum das nich gehen sollte.
      Fidne grade auf die schnelle aber keinen vernünftigen Link- hat wer ne fundierte Meinung dazu? Idealerweise mit nem soliden Link auf den ich mich beziehen kann?
  • 116 Antworten
    • derch3f
      derch3f
      Einsteiger
      Dabei seit: 27.06.2011 Beiträge: 452
      http://de.wikipedia.org/wiki/Spiel_mit_vollst%C3%A4ndiger_Information
      also ja, lösbar
    • MrMarv89
      MrMarv89
      Bronze
      Dabei seit: 03.01.2009 Beiträge: 2.657
      jedes spiel mit absoluten informationen ist theoretisch lösbar
    • AyCaramba44
      AyCaramba44
      Black
      Dabei seit: 27.04.2010 Beiträge: 11.718
      Dame ist zum Beispiel schon komplett gelöst und man kann gegen einen Computer maximal unentschieden spielen. Da Schach genauso wie Dame mit vollständigen Informationen funktioniert (jeder Spieler weiß alles) solle Schach ebenfalls theoretisch lösbar sein. Eine Lösung gibt es bisher allerdings noch nicht, da es einiges komplexer als Dame ist. Wenn die Rechenpower in den nächsten Jahren weiterhin so extrem zunimmt, ist es meiner Meinung nach nur eine Frage der Zeit.

      http://www.welt.de/wissenschaft/article1039400/Computer_kann_bei_Dame_nicht_verlieren.html
    • Faustfan
      Faustfan
      Bronze
      Dabei seit: 19.04.2005 Beiträge: 9.481
      afaik sind alle 6-Steiner komplett gelöst

      Hoffe die Professorin macht nichts naturwissenschaftliches, das ist gesunder menschenverstand
    • Opticom
      Opticom
      Bronze
      Dabei seit: 21.06.2011 Beiträge: 17
      Es gibt verschiedene Wege nach Rom.

      Großmeister Tal wurde eine perfekte Partie spielen mit Opferorgien.
      Karpow eine perfekte Partie mit kleinen dauernden Positionsvorteilen.

      Alle beide gewinnen und haben auf ihre Art perfekt gespielt.
    • generalerror
      generalerror
      Bronze
      Dabei seit: 21.09.2007 Beiträge: 7.122
      Ich hab letztens eine Seminararbeit über Poker geschrieben und dazu parallel einen Artikel für unseren Article-Contest gepostet.

      Darin habe ich geschrieben, dass man eine Situation im Poker vollständig durch durch die Informationen in der Handhistory und durch die Strategie der Gegner und anhand dieser kann man dann die Aktion wählen, die uns in ein Nash-Equilibrium bringt und damit können wir dann nicht mehr exploited werden.

      Also theoretisch ist Poker auch lösbar, das Problem ist dass man dazu die Strategien aller Spieler am Tisch vollständig kennen müsste, die ja ihre Strategien auch wieder auf uns adapten, und dann müssten wir wieder adapten, usw.
    • coolalzi
      coolalzi
      Bronze
      Dabei seit: 01.10.2006 Beiträge: 2.075
      Wenn man "perfekt" so wie in Dame definiert, dass man in jeder Situation jede mögliche Gegenreaktion des Gegners bis zum Ende der Partie durchrechnet, dann sind alle Partien mit 6 (vielleicht mittlerweile 7) Steinen gelöst.

      Bei einer "perfekten" Lösung einer Partie vor dem 1. Zug, wäre die benötigte Rechenpower so groß, dass man das nie hinbekommen wird (Prozessor braucht mehr Si als es auf der Erde gibt, der Computer wäre größer als die Erde, die Sonne geht aus, bevor der PC ausgerechnet hat...). Einzige Hoffnung wäre dann ein Einschnitt in der Computertechnik (Quantencomputer, der besser ist als selbst optimisten erwarten...).

      Dass es Software geben wird, die "fehlerlos" spielt, ist abzusehen. Da wird dann aber "schlau" gerechnet, z.B. alle Möglichkeiten in denen eine Seite einen unaufholbaren Vorsprung hat als "gewonnen" oder "verloren" gewertet ohne diesen Zweig bis zum Matt durchzurechnen. "Perfekt" ist das nach strengster Definition nicht, denn man könnte ja ein unerwartetes Matt/Patt des Unterlegenen "übersehen" haben.

      Also so unrecht hatte die Professorin nicht.
    • Tijfg
      Tijfg
      Bronze
      Dabei seit: 09.07.2009 Beiträge: 7.327
      es spielst doch gar keine rolle wie lange der computer nach welchem stand der technik auch immer rechnen würde. Theoretisch lösbar ist es doch dann trotzdem.
    • ktec
      ktec
      Bronze
      Dabei seit: 17.01.2005 Beiträge: 2.781
      Original von generalerror
      Also theoretisch ist Poker auch lösbar, das Problem ist dass man dazu die Strategien aller Spieler am Tisch vollständig kennen müsste, die ja ihre Strategien auch wieder auf uns adapten, und dann müssten wir wieder adapten, usw.
      das stimmt nicht
    • Knudsen
      Knudsen
      Bronze
      Dabei seit: 19.07.2005 Beiträge: 4.314
      Original von coolalzi
      Wenn man "perfekt" so wie in Dame definiert, dass man in jeder Situation jede mögliche Gegenreaktion des Gegners bis zum Ende der Partie durchrechnet, dann sind alle Partien mit 6 (vielleicht mittlerweile 7) Steinen gelöst.

      Bei einer "perfekten" Lösung einer Partie vor dem 1. Zug, wäre die benötigte Rechenpower so groß, dass man das nie hinbekommen wird (Prozessor braucht mehr Si als es auf der Erde gibt, der Computer wäre größer als die Erde, die Sonne geht aus, bevor der PC ausgerechnet hat...). Einzige Hoffnung wäre dann ein Einschnitt in der Computertechnik (Quantencomputer, der besser ist als selbst optimisten erwarten...).

      Dass es Software geben wird, die "fehlerlos" spielt, ist abzusehen. Da wird dann aber "schlau" gerechnet, z.B. alle Möglichkeiten in denen eine Seite einen unaufholbaren Vorsprung hat als "gewonnen" oder "verloren" gewertet ohne diesen Zweig bis zum Matt durchzurechnen. "Perfekt" ist das nach strengster Definition nicht, denn man könnte ja ein unerwartetes Matt/Patt des Unterlegenen "übersehen" haben.
      Stimme dir hier 100% zu.


      Also so unrecht hatte die Professorin nicht.
      Hier allerdings gar nicht. Verstehe nicht, wie du nun zu der Schlussfolgerung kommst, da du ja oben schon ausführlich begründest hast, dass es zwar grundsätzlich möglich ist, nur an der Rechenlestung und dem benötigten Speicher scheitert.

      Es ist ja auch sofort klar, dass es thoretisch lösbar ist, da es nur endlich viele Stellungen gibt. laut Wiki etwa 2,28 · 10^46. Bedenkt man, dass die Erde ca. 6*10^49 Atome hat, und unter der Annahme, dass man jede Stellung mit je 100 Atomen abspeichern kann, bräuchte man einen Speicher, der etwas mehr als 1/30 der ERdmasse ausmachen müsste. Dass das niemals hinkommen kann, ist sofort klar. Also muss man wie gesagt "geschickt" rechnen. Ob es dann trotzdem jemals gelöst wird, halte ich für unwahrscheinlich, von uns wird es jdenfalls keiner erleben (Sidebet anyone?).
    • coolalzi
      coolalzi
      Bronze
      Dabei seit: 01.10.2006 Beiträge: 2.075
      Original von Tijfg
      es spielst doch gar keine rolle wie lange der computer nach welchem stand der technik auch immer rechnen würde. Theoretisch lösbar ist es doch dann trotzdem.
      Das sehen die Numeriker anders
    • Knudsen
      Knudsen
      Bronze
      Dabei seit: 19.07.2005 Beiträge: 4.314
      Original von ktec
      Original von generalerror
      Also theoretisch ist Poker auch lösbar, das Problem ist dass man dazu die Strategien aller Spieler am Tisch vollständig kennen müsste, die ja ihre Strategien auch wieder auf uns adapten, und dann müssten wir wieder adapten, usw.
      das stimmt nicht
      #2

      spielt man selbst nach Nash, kann ein anderer Spieler maximal gegen einen breakeven spielen (es ist allerdings unklar, ob er dazu selbst nach Nash spielen müsste)
    • Knudsen
      Knudsen
      Bronze
      Dabei seit: 19.07.2005 Beiträge: 4.314
      Original von coolalzi
      Original von Tijfg
      es spielst doch gar keine rolle wie lange der computer nach welchem stand der technik auch immer rechnen würde. Theoretisch lösbar ist es doch dann trotzdem.
      Das sehen die Numeriker anders
      Numeriker heißt ja, dass man es ausrechnen will. Das ist allen klar, dass es nicht geht. Das hat allerdings mit der tatsächlichen Lösbarkeit nix zu tun.
    • coolalzi
      coolalzi
      Bronze
      Dabei seit: 01.10.2006 Beiträge: 2.075
      Original von Knudsen
      Original von coolalzi
      Original von Tijfg
      es spielst doch gar keine rolle wie lange der computer nach welchem stand der technik auch immer rechnen würde. Theoretisch lösbar ist es doch dann trotzdem.
      Das sehen die Numeriker anders
      Numeriker heißt ja, dass man es ausrechnen will. Das ist allen klar, dass es nicht geht. Das hat allerdings mit der tatsächlichen Lösbarkeit nix zu tun.
      Nein, Numerik ist ein Teilgebiet der Mathematik und befasst sich u.a. mit der Lösbarkeit von Problemen. Schach ist ein Problem, das stärker als linear mit der Anzahl der Steine in der Rechenzeit steigt.

      "Lösbar" heißt nicht, dass man einen Code schreiben kann, der theoretisch das gewünschte Ergebnis liefert, sondern auch, dass einem das Problem nicht "um die Ohren fliegt", sobald man die Komplexität minimal erhöht (ein Stein mehr, ein möglicher Gegnerzug mehr,...) und genau das ist beim Schach der Fall.
    • coolalzi
      coolalzi
      Bronze
      Dabei seit: 01.10.2006 Beiträge: 2.075
      .(Doppelpost)
    • hazz
      hazz
      Black
      Dabei seit: 13.02.2006 Beiträge: 4.771
      http://de.wikipedia.org/wiki/Nash-Gleichgewicht

      "Für Zwei-Personen-Nullsummenspiele mit perfekter Information, zu denen Brettspiele wie Schach und Mühle gehören, existiert sogar immer ein Minimax-Gleichgewicht in reinen Strategien, das mit dem Minimax-Algorithmus rekursiv bestimmt werden kann. Dieser Satz wurde bereits 1912 von Ernst Zermelo bewiesen."
    • IgorTheTigor
      IgorTheTigor
      Bronze
      Dabei seit: 12.11.2006 Beiträge: 5.423
      Mach die alte fertig und dich evtl. für immer unbeliebt !
    • FrtZ
      FrtZ
      Black
      Dabei seit: 25.08.2006 Beiträge: 3.412
      Merci

      und nein Faustfan, sie hat nen avl lehrstuhl, da muss man sich nich zwingend mit spieltheorie auskennen ;D
    • NoLimitNOOB
      NoLimitNOOB
      Bronze
      Dabei seit: 10.07.2007 Beiträge: 2.138
      Was studierst du?

      Theologie?
      Philosophie?


      Peinlich die Alte ...