Ist es möglich dass, ein 5-gewinnt Programm unschlagbar ist?

Übersicht

Sonstiges

Smalltalk

Gehe zu Seite Zurück 1, 2

	SpionAtom	So, Okt 18, 2009 20:46 Antworten mit Zitat
Wir drehen uns im Kreis hectic. Das perfekte Spiel ist für mich, dass man so spielt, dass man nicht verlieren KANN! D.h. egal wie der Gegner reagiert, man gibt immer den perfekten Konter. Und zwar so, dass man seinem Ziel, schachmatt, immer näher kommt - und sich auf keinen Fall in eine Sackgasse zmanövriert. Man spielt quasi unabhängig vom Gegner, theoretisch kennt man ja alle seine Möglichkeiten. Nochmal zur Unterscheidung: Das perfekte Spiel existiert theoretisch (genau wie eine Primzahl > 2³²³²²³), doch finden werden wir es wohl nie. Also hat es keinen praktischen Nutzen. Als Übung könnte man ein vereinfachtes Schach nehmen, mit 3x3 Felden, und weniger Figuren (zb 3 für jeden). Das hieße, wir hätten 9 Felder, auf denen 6 Figuren unterschiedlichst stehen können. Rechne mal jemand aus, wieviele Kombinationsmöglichkeiten von Spielsituationen es maximal geben kann. EDIT: Könnte 9! / 3! sein: also 9 * 8 * 7 * 6 * 5 * 4 = 60.480. Es gibt also maximal soviele Möglichkeiten, die Figuren beliebig anzuordnen. Je nach Zugmöglichkeiten sind die mögliche Spielsituationen entsprechend weniger (einige Figuren, dürfen nur auf schwarzen/weißen Feldern stehen, andere dürfen nur geradeaus ziehen). Fakt ist, das Spiel ist begrenzt. Jetzt muss man sich nur noch anschauen, aus welchen Spielsituationen man im nächsten Zug gewonnen hat. Diese schreibt man sich ALLE auf. Dann - ihr ahnt es schon - schreibt man sich alle Spielsituationen auf, die zu eben den vorletzten Gewinnzügen-Zügen führen. Und dann alle die, die zu den drittletzten Zügen führen, usw.... Dreht man sich im Kreis, kann man abbrechen, kommt man zur Startsituation, kann man ebenfalls abbrechen. Es entsteht so ein umgekehrter Gewinnpfadbaum. Das Perfekte Spiel wäre dann eben einen der Wege zu nehmen, die unweigerlich zum gewinnzug führen. Und das kann man nunmal auch für Schach machen! Oder Vier Gewinnt! Oder Tic-Tac-Toe (vielleicht mach ich das noch). Es ist eben nur eine Frage der Zeit, bis man so einen Gewinnbaum zusammenhat. Und da es beim Schach soooo "unendlich viele" Möglichkeiten gibt (jetzt hab ich auch unendlich gesagt, wir wissen ja jetzt, dass es nicht unendlich viele Möglichkeiten gibt!!!), wird es uns wohl nicht möglich sein, in akzeptabler Zeit und Rechenleistung diesen Gewinnbaum zu finden.
os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080

SpionAtom

So, Okt 18, 2009 20:46
Antworten mit Zitat

Wir drehen uns im Kreis hectic.

Das perfekte Spiel ist für mich, dass man so spielt, dass man nicht verlieren KANN! D.h. egal wie der Gegner reagiert, man gibt immer den perfekten Konter. Und zwar so, dass man seinem Ziel, schachmatt, immer näher kommt - und sich auf keinen Fall in eine Sackgasse zmanövriert. Man spielt quasi unabhängig vom Gegner, theoretisch kennt man ja alle seine Möglichkeiten.

Nochmal zur Unterscheidung: Das perfekte Spiel existiert theoretisch (genau wie eine Primzahl > 2³²³²²³), doch finden werden wir es wohl nie. Also hat es keinen praktischen Nutzen.

Als Übung könnte man ein vereinfachtes Schach nehmen, mit 3x3 Felden, und weniger Figuren (zb 3 für jeden). Das hieße, wir hätten 9 Felder, auf denen 6 Figuren unterschiedlichst stehen können. Rechne mal jemand aus, wieviele Kombinationsmöglichkeiten von Spielsituationen es maximal geben kann.

EDIT:
Könnte 9! / 3! sein: also 9 * 8 * 7 * 6 * 5 * 4 = 60.480.
Es gibt also maximal soviele Möglichkeiten, die Figuren beliebig anzuordnen. Je nach Zugmöglichkeiten sind die mögliche Spielsituationen entsprechend weniger (einige Figuren, dürfen nur auf schwarzen/weißen Feldern stehen, andere dürfen nur geradeaus ziehen). Fakt ist, das Spiel ist begrenzt.
Jetzt muss man sich nur noch anschauen, aus welchen Spielsituationen man im nächsten Zug gewonnen hat. Diese schreibt man sich ALLE auf. Dann - ihr ahnt es schon - schreibt man sich alle Spielsituationen auf, die zu eben den vorletzten Gewinnzügen-Zügen führen. Und dann alle die, die zu den drittletzten Zügen führen, usw.... Dreht man sich im Kreis, kann man abbrechen, kommt man zur Startsituation, kann man ebenfalls abbrechen. Es entsteht so ein umgekehrter Gewinnpfadbaum. Das Perfekte Spiel wäre dann eben einen der Wege zu nehmen, die unweigerlich zum gewinnzug führen.
Und das kann man nunmal auch für Schach machen! Oder Vier Gewinnt! Oder Tic-Tac-Toe (vielleicht mach ich das noch). Es ist eben nur eine Frage der Zeit, bis man so einen Gewinnbaum zusammenhat. Und da es beim Schach soooo "unendlich viele" Möglichkeiten gibt (jetzt hab ich auch unendlich gesagt, wir wissen ja jetzt, dass es nicht unendlich viele Möglichkeiten gibt!!!), wird es uns wohl nicht möglich sein, in akzeptabler Zeit und Rechenleistung diesen Gewinnbaum zu finden.

os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080

	Silver_Knee	Mo, Okt 19, 2009 1:23 Antworten mit Zitat
ich könnte mir bei schach durchaus einen gewinnast vorstellen der von der wahrscheinlichkeit bei 75% liegt. Das heißt in 3/4 aller züge die der gegner machen könnte würde man gewinnen aber sicherlich nicht einen mit 100%. Und selbst wenn es nur einen gegenzug gibt, kann es keine Perfekte strategie mehr geben

Silver_Knee

Mo, Okt 19, 2009 1:23
Antworten mit Zitat

ich könnte mir bei schach durchaus einen gewinnast vorstellen der von der wahrscheinlichkeit bei 75% liegt. Das heißt in 3/4 aller züge die der gegner machen könnte würde man gewinnen aber sicherlich nicht einen mit 100%. Und selbst wenn es nur einen gegenzug gibt, kann es keine Perfekte strategie mehr geben

	Firstdeathmaker	Mo, Okt 19, 2009 9:15 Antworten mit Zitat
Zitat: ich könnte mir bei schach durchaus einen gewinnast vorstellen der von der wahrscheinlichkeit bei 75% liegt. Umkehrschluss: Also müsste der Gegner, wenn er perfekt spielt, gewinnen? Weil er genau die Züge auswählt, die in den 25% liegen? Ihr müsst doch immer von einem vollkommen bekannten Spiel ausgehen, d.h. beide perfekten Spieler wissen zu 100% was alles eintreten kann wenn sie sich jetzt für genau diesen Spielzug entscheiden. D.h. aber auch, dass es keine "Warscheinlichkeiten" gibt, mit der ein Zug zum Sieg führen kann. Ihr denkt einfach noch zu menschlich, wenn ihr sagt: Ein perfektes Spiel kann dadurch durcheinander gebracht werden, wenn der Gegner etwas "dummes" tut. Denn auch der "dumme" Zug ist in der Planung für ein "perfektes" Spiel enthalten und führt dann nur schneller zum Sieg/Niederlage.
www.illusion-games.de Space War 3 \| Space Race \| Galaxy on Fire \| Razoon Gewinner des BCC #57 User posted image

Firstdeathmaker

Mo, Okt 19, 2009 9:15
Antworten mit Zitat

Zitat:

ich könnte mir bei schach durchaus einen gewinnast vorstellen der von der wahrscheinlichkeit bei 75% liegt.

Umkehrschluss: Also müsste der Gegner, wenn er perfekt spielt, gewinnen? Weil er genau die Züge auswählt, die in den 25% liegen? Ihr müsst doch immer von einem vollkommen bekannten Spiel ausgehen, d.h. beide perfekten Spieler wissen zu 100% was alles eintreten kann wenn sie sich jetzt für genau diesen Spielzug entscheiden.

D.h. aber auch, dass es keine "Warscheinlichkeiten" gibt, mit der ein Zug zum Sieg führen kann. Ihr denkt einfach noch zu menschlich, wenn ihr sagt: Ein perfektes Spiel kann dadurch durcheinander gebracht werden, wenn der Gegner etwas "dummes" tut. Denn auch der "dumme" Zug ist in der Planung für ein "perfektes" Spiel enthalten und führt dann nur schneller zum Sieg/Niederlage.

www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

	DerSlotzer	Do, Dez 17, 2009 22:36 Antworten mit Zitat
Hey an alle! So, nachdem ich auf diesen interessanten Beitrag gestoßen bin muss i euch ja auch mal was schreiben! Ich würd auch gernwissen ob das 5 gewinnt (x mal y), naja sagen wir mal 20x20 forciert gewonnen ist für den, der anfängt. Ganz egal ob Mensch oder Comp. 3 und 4 gewinnt kenn (und kann) ich auch, aber wie is bei 5 gewinnt die optimale Strategie? Hat da wer eine Ahnung? Zum Thema Schach: Ich denk es is viel zu kompliziert, einen forcierten Gewinnweg zu finden... nehmen wir mal an,jeder Spieler hat im Schnitt 20 mögliche Züge. Am Anfang is es ja auch so, und die Partie geht über 50 Züge. Dann sind wir bei 20^100 Möglichkeiten. Und auch wenn das Programm (Fritzi oder Shredder oder wasweißich) Millionen und Abermillionen vo Möglichkeiten die Sekunde ausrechnen können... sind wie bei 10^10 oder 10^14 (und das is scho zuviel). Da wirds wohl noch ein paar Jährchen brauchen bis unsere KIs das können. Hm, und @ TimBo... Lettisch ist ja sogar Lettisches Gambit... spiel ich auch manchmal, aber wennst di nix auskennst bist du schneller tot als du schauen kannst Vor allem wenn du in der Lc4-Variante mit der Dame auf g2 rein musst und sich der Weiße auskennt XD Have fun!

DerSlotzer

Do, Dez 17, 2009 22:36
Antworten mit Zitat

Hey an alle!

So, nachdem ich auf diesen interessanten Beitrag gestoßen bin muss i euch ja auch mal was schreiben!

Ich würd auch gernwissen ob das 5 gewinnt (x mal y), naja sagen wir mal 20x20 forciert gewonnen ist für den, der anfängt. Ganz egal ob Mensch oder Comp. 3 und 4 gewinnt kenn (und kann) ich auch, aber wie is bei 5 gewinnt die optimale Strategie? Hat da wer eine Ahnung?

Zum Thema Schach:
Ich denk es is viel zu kompliziert, einen forcierten Gewinnweg zu finden... nehmen wir mal an,jeder Spieler hat im Schnitt 20 mögliche Züge. Am Anfang is es ja auch so, und die Partie geht über 50 Züge. Dann sind wir bei 20^100 Möglichkeiten. Und auch wenn das Programm (Fritzi oder Shredder oder wasweißich) Millionen und Abermillionen vo Möglichkeiten die Sekunde ausrechnen können... sind wie bei 10^10 oder 10^14 (und das is scho zuviel). Da wirds wohl noch ein paar Jährchen brauchen bis unsere KIs das können.

Hm, und @ TimBo...
Lettisch ist ja sogar Lettisches Gambit... spiel ich auch manchmal, aber wennst di nix auskennst bist du schneller tot als du schauen kannst Smile

Vor allem wenn du in der Lc4-Variante mit der Dame auf g2 rein musst und sich der Weiße auskennt XD

Have fun!

	konstantin	Fr, Dez 18, 2009 10:24 Antworten mit Zitat
ad schach: superschachcomputer sind doch mittlerweile eh nicht mehr vom menschen zu schlagen (siehe kasparov vs deep blue II), und ein durchschnittliches schachprogramm gewinnt gegen jeden fortgeschrittenen gegner. was den gewinnweg angeht: auf den fido-turnieren fuer die weltrangliste ist es mittlerweile so, dass weiss in 90% der spiele einen gewinn, zumindest aber ein remis erzwingen kann. rein theoretisch ist es fuer schwarz tatsaechlich unmoeglich zu gewinnen, so weiss tadellos spielt. es gab, gibt und wird vermutlich auch nie einen menschen geben, der das spiel in dieser perfekton beherscht - aber unsere computer koennen das schon lange zu allen anderen rundenbasierten spielen fuer zwei spieler: bei einem tadellosen spiel von weiss kann schwarz niemals gewinnen. weder beim vier- oder fuenf-gewinnt, noch bei muehle oder dame, denn weiss steuert das spiel und schwarz steht im zugzwang. das hoechste der gefuehle ist, wie beim schach, ein remis. edit: im grunde ist es da bei allen spielen wie bei tic-tac-toe, letztenendes muendet alles in einem patt.

konstantin

Fr, Dez 18, 2009 10:24
Antworten mit Zitat

ad schach: superschachcomputer sind doch mittlerweile eh nicht mehr vom menschen zu schlagen (siehe kasparov vs deep blue II), und ein durchschnittliches schachprogramm gewinnt gegen jeden fortgeschrittenen gegner. was den gewinnweg angeht: auf den fido-turnieren fuer die weltrangliste ist es mittlerweile so, dass weiss in 90% der spiele einen gewinn, zumindest aber ein remis erzwingen kann. rein theoretisch ist es fuer schwarz tatsaechlich unmoeglich zu gewinnen, so weiss tadellos spielt. es gab, gibt und wird vermutlich auch nie einen menschen geben, der das spiel in dieser perfekton beherscht - aber unsere computer koennen das schon lange Wink

zu allen anderen rundenbasierten spielen fuer zwei spieler: bei einem tadellosen spiel von weiss kann schwarz niemals gewinnen. weder beim vier- oder fuenf-gewinnt, noch bei muehle oder dame, denn weiss *steuert* das spiel und schwarz steht im zugzwang. das hoechste der gefuehle ist, wie beim schach, ein remis.

edit: im grunde ist es da bei allen spielen wie bei tic-tac-toe, letztenendes muendet alles in einem patt.

	Silver_Knee	Fr, Dez 18, 2009 11:24 Antworten mit Zitat
ha ich kenne ein spiel bei dem der anfänger verliert Code: [AUSKLAPPEN] [EINKLAPPEN] X XX X X X XX X nimm immer ein,zwei oder 3 X und wer das letzte nimmt verliert.