hallo, nix mit doppelposting ;-)
ich hab im brett 'programmierung' eben einen artikel dazu gepostet. es waere nett, wenn ihr da mal hinschauen koenntet.
und bitte gegebenfalls auch da antworten.
gruss, stefan
Also, zur Einfachheit nehmen wir mal an, dass es kein Remis gibt, d.h. sagen wir mal Weiss hat gewonnen, wenn er gewinnt oder Remis erreicht. Dann gibt es zunaechseteinmal Stellungen in denen Weiss gewonnen hat, und solche in denen Schwarz gewonnen hat. Nun betrachtet man alle Stellungen, die zu diesen Stellungen fuehren koennen, wenn es aus einer soclhen Stellung einen Zug fuer den
Ziehenden gibt, der zu einer als "gewonnen" markierten Stellung fuehrt nennen wir diesen Zug "gewonnen", wenn alle zu verlorenen
Stellungen fuehren "verloren". Wenn das ganze Azyklisch waere, waeren wir jetzt fertig und koennten so rekursiv einen "Wert" fuer die Anfangsstellung finden, so dass die beiden Rechner sofort und immer auf das gleiche Ergebnis kaemen ohne einen Zug zu machen. Nun besteht aber die Moeglichkeit, die selben Zuege immer zu wiederholen, was nach den Schachregeln zu Remis fuehrt.
Wir muessen also zusaetzlich diese Kreise identifizieren. Wenn von diesem Kreis eine kante abgeht, die bei Schwarz am Zug einen weg zu einer"verlorenen" (also gut fuer Schwarz) Stellung fuehrt, wird Schwarz diese benutzen und wir koennen eine kante aus dem Kreis rauswerfen - sprich der Kreis ist weg. Wenn nicht, dann sind alle Knoten des Kreises fuer Weiss gewonnen und wir koennen den Kreis de Fakto zu einem Knoten schrumpfen und diesen "gewonnen" nennen, da Remis ein Gewinn fuer Weiss ist. Sprich wir sind den Kreis los und koennen wieder wie oben weitermachen.
D.h man kann eine eindeutige "optomale" strategie festlegen und die rechner einigen sich sofort.
MFG
Martin
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
hi martin,
Wenn das ganze Azyklisch waere,
waeren wir jetzt fertig und koennten so rekursiv einen "Wert"
fuer die Anfangsstellung finden, so dass die beiden Rechner
sofort und immer auf das gleiche Ergebnis kaemen ohne einen
Zug zu machen.
eben. aber die fangen ja doch an zu spielen.
Wir muessen also zusaetzlich diese Kreise identifizieren. Wenn
von diesem Kreis eine kante abgeht, die bei Schwarz am Zug
einen weg zu einer"verlorenen" (also gut fuer Schwarz)
Stellung fuehrt, wird Schwarz diese benutzen und wir koennen
eine kante aus dem Kreis rauswerfen - sprich der Kreis ist
weg.
das ist ja die frage, wird es jemals zu dieser situation kommen?
D.h man kann eine eindeutige "optomale" strategie festlegen
und die rechner einigen sich sofort.
das bedeutet ja quasi, dass weiss schon mit dem ersten zug das ganze spielgeschehen steuern kann und eigentlich immer gewinnen muesste (remis einbezogen). schwarz wird das aber nicht zugeben, da er ja nur reagiert. nur falls weiss den ersten zug 'falsch' setzt, was ja nicht sein kann, haette schwarz ueberhaupt eine chance. weiss geht aber auch von einem genialen gegenspieler aus und ahnt, dass das ergebnis 'nur' remis ist. also bietet er es vor dem ersten zug an.
wahrscheinlich ne rein philosophische frage, ob die beiden wirklich spielen oder energiesparend auf schwache gegner warten...
gruss, stefan
Ok, wenn man den Rechnern vorher nicht mitteilt, dass der jeweils andere die Optimalen Strategien kennt, wuerden Sie beide jeweils die Zuege machen, die sie von einer Niederlage am weitesten entfernen. Ergebnis: Einer optimal einer nicht (auch nicht durch Zufall)-> Der optimale gewinnt. Beide Optimal -> Immer das gleiche Spiel, sofern die Rechner "Erinnerungslos" sind und daher
nicht versuchen auszutesten wie gut der andere den Spielbaum wirklich kennt. Gibt es mehrere Optimale Strategien, so kann man
natuerlich randomisieren. Aber die Frage ist wirklich rein philosophisch.
MFG
Martin
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
<snip theoretische beschreibung>
bliebe nur ein problem, du gehst davon aus, dass du einen kompletten spielbaum fuer schach hast. dann ist das spiel in der tat "geloest". leider ist der spielbaum fuer so etwas komplexes wie schach ein _bisschen_ zu gross fuer heutige speichersysteme, mal abgesehen von der zeit die es kosten wuerde ihn zu erstellen.
joachim