Checkers

Moderator: Einführung in die Künstliche Intelligenz

doerrhoe
Neuling
Neuling
Beiträge: 1
Registriert: 19. Jul 2007 20:36

Checkers

Beitrag von doerrhoe »

Jetzt war der doch tatsächlich einen halben Tag schneller als ich. Nur, weil mir gestern das Papier ausgegangen ist, um die letzte Variante noch zu berechnen.

http://www.heise.de/newsticker/meldung/92996

Benutzeravatar
Rodent Bait
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 26. Apr 2005 14:50
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Rodent Bait »

Ein Satz macht mich hier jetzt schon stutzig:
Gegen den perfekten Datenbank-Mühle-Spieler können Interessierte auf Inetplay antreten, aber ebenfalls kaum auf mehr als ein Remis hoffen.
Das klingt jetzt so, als hätte man doch eine klitzekleine Chance, einen perfekten Spieler (in einem deterministischen Spiel!) zu schlagen. Ist das tatsächlich der Fall?

Allgemeiner gefragt: die behandelten Algorithmen spielen ja perfekt unter der Annahme, dass auch der Gegner perfekt spielt. Kann man einen solchen Spieler mit nicht-perfektem Spiel schlagen?

Benutzeravatar
klospatz
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 230
Registriert: 16. Dez 2003 14:01
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von klospatz »

Rodent Bait hat geschrieben:Das klingt jetzt so, als hätte man doch eine klitzekleine Chance, einen perfekten Spieler (in einem deterministischen Spiel!) zu schlagen. Ist das tatsächlich der Fall?
steht da nicht, dass man ihn nicht schlagen und bestenfalls ein unentschieden erspielen kann?

Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Beitrag von Tillmann »

Rodent Bait hat geschrieben:Allgemeiner gefragt: die behandelten Algorithmen spielen ja perfekt unter der Annahme, dass auch der Gegner perfekt spielt. Kann man einen solchen Spieler mit nicht-perfektem Spiel schlagen?
Perfektes Spiel bedeudet doch bloß: Wenn es einen Zug gibt, mit dem ich sicher gewinne, dann mache ich ihn auch. Nicht-perfektes Spiel bedeutet daher: Obwohl es einen Zug gibt, mit dem ich sicher gewinne, mache ich ihn nicht. Ob ein Spieler perfekt spielt oder nicht macht also nur für den Fall einen Unterschied, ob er einen Zug machen kann, mit dem er sicher gewinnt.

Eine perfekte Strategie sorgt nun dafür, daß der Gegner niemals Züge machen kann, mit denen er sicher gewinnt. Also sollte es für eine perfekte Strategie ganz unerheblich sein, ob der Gegner perfekt spielt oder nicht.


Wenn wir aber eine gute (aber nicht perfekte) Strategie entwickeln wollen, die zum Beispiel gegen schlechte Gegner gewinnen kann, indem sie diese "austrickst", dürfen wir nicht mehr einfach von schlechten Gegner ausgehen. Zum Beispiel könnte unsere Strategie bewußt einen Zug machen, der eigentlich zum Verlieren führt, in der Hoffnung, daß der Gegner die (dann existierende) Gewinnstrategie nicht findet und selber einen Verlieren-Zug macht. Wann das angebracht ist, könnte zum Beispiel eine Heuristik entscheiden, die die nötige Suchtiefe ermittelt, um Gewinn- von Verlust-Strategien zu unterscheiden.

So spielen ja auch Menschen: Wenn ich Mühle spiele, spiele ich nicht "auf Untentschieden", indem ich nur "sichere" Züge mache, sondern ich spiele "auf Gewinn", indem ich versuche, Zwickmühlen aufzubauen, in der Hoffnung, daß es meinem Gegner nicht rechtzeitig auffällt. Gegen gute Mühle-Spieler würde das sicherlich nicht funktionieren, aber für meinen Bekanntenkreis reicht es meist.

Bei einfacheren Spielen wie Tic-Tac-Toe ist das anders. Das Spiel ist so einfach, daß ich davon ausgehen kann, daß mein Gegner mit perfekter Strategie spielt. Also spiele ich selber auch mit der perfekten Unentschieden-Strategie und versuche gar nicht erst, den Gegner auszutrickens. Ist natürlich dann langweilig, weil immer dasselbe rauskommt. :(

Benutzeravatar
klospatz
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 230
Registriert: 16. Dez 2003 14:01
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von klospatz »

ich behaupte einfach mal dreist, dass es nichts bringt einem computerprogramm suboptimale zuege vorzusetzen und darauf zu spekulieren, dass er dadurch verwirrt wird. der wird dich einfach nur noch schneller fertig machen.

ich kann mir auch nur schwerlich vorstellen ob das bei menschlichen spielern erfolg haben wird, wenn die etwas von dem spiel verstehen.

Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Beitrag von Tillmann »

klospatz hat geschrieben:ich behaupte einfach mal dreist, dass es nichts bringt einem computerprogramm suboptimale zuege vorzusetzen und darauf zu spekulieren, dass er dadurch verwirrt wird. der wird dich einfach nur noch schneller fertig machen.
Naja, wir müssen ja nicht spekulieren, Computer arbeiten ja deterministisch. Wir kennen also z.B. die Suchtiefe und die verwendete Heuristik unseres (Computer-)Gegners. Wir können also im vorhinein berechnen, wie der Computer auf eine Spielsituation reagiert. Also konstruieren wir einfach folgendes Suchproblem:

Ein Zustand ist ein Zustand des ursprünglichen Spiels, bei dem wir am Zug sind.
Gültige Aktionen sind unsere gültigen Züge.
Resultate der Aktionen sind das Ergebnis des Computerzuges nach dem Ergebnis unseres Zuges. (Also immer zwei Aktionen auf einmal, die Computerzüge sind ja deterministisch, wenn der verwendete Algorithmus bekannt ist).

Wenn wir in diesem Suchraum einen Weg zum Gewinn finden, können wir ihn gegen den Computer nachspielen und gewinnen. Das geht natürlich nur, wenn die Strategie des Computers nicht perfekt ist, denn wenn sie es doch ist, gibt es keinen solchen Weg. Aber gegen nicht-perfekte Computergegner (z.B. mit begrenzter Suchtiefe oder ungenauer Heuristik) sollte es doch gehen?

Meines Wissens kommt es auch bei menschlichen Schachspielern wesentlich auf die maximale Suchtiefe an, also sollte diese Methode "im Prinzip" auch gegen Menschen funktionieren.

Benutzeravatar
Rodent Bait
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 26. Apr 2005 14:50
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Rodent Bait »

ich behaupte einfach mal dreist, dass es nichts bringt einem computerprogramm suboptimale zuege vorzusetzen und darauf zu spekulieren, dass er dadurch verwirrt wird. der wird dich einfach nur noch schneller fertig machen.
Ich bin eben dadurch irritiert, dass es z.B. auf Folie 26 heißt:
Optimality - Yes, if the opponent also plays optimally.
Das klingt jetzt schon ein bisschen so, dass man mit suboptimalen Zügen eine Chance hätte. Aber wenn ich mir, nachdem ich noch einmal über mein gestriges Posting geschlafen habe, den MiniMax so in Aktion vorstelle, kann ich das eigentlich nur verneinen, genauso, wie hier von Tillmann formuliert:
Eine perfekte Strategie sorgt nun dafür, daß der Gegner niemals Züge machen kann, mit denen er sicher gewinnt. Also sollte es für eine perfekte Strategie ganz unerheblich sein, ob der Gegner perfekt spielt oder nicht.
Das, was Tillmann unter "Suchtiefe" erwähnt, ist bei dem Ausgangsbeispiel der kompletten Checkers-Berechnung nicht gegeben, weil ja hier alle Stellungen bis zum Schluss berechnet sind, also stets mit maximaler Suchtiefe vorgegangen wird. Ansonsten trifft das prinzipiell schon zu: wenn ich Utility-Funktion u und Suchtiefe n des Gegners kenne, dann kann ich ihn zu einem Zug bewegen, der zwar auf der Tiefe n mit der Funktion u gut aussieht, aber auf der Tiefe n+k für mich einen Vorteil bringt.

Einfaches Beispiel: im Zug n schlägt der Computer meine Dame, weswegen er die Situation, sofern er nicht weitersucht (Suchtiefe n), toll findet (bei einer Utility-Funktion mit starkem Schwerpunkt auf Materialvorteilen) und sich daher in diesen Ast bewegt. Er "übersieht" aber aufgrund seiner Suchtiefe, dass ich ihn im Zug n+1 mit einer anderen Figur mattsetzen kann.
ich kann mir auch nur schwerlich vorstellen ob das bei menschlichen spielern erfolg haben wird, wenn die etwas von dem spiel verstehen.
Ich habe mal gelesen, dass es durchaus sinnvoller sein, mit einer unkonventionellen (und möglicherweise nicht ganz optimalen) Eröffnung gegen einen überlegenen Menschen zu spielen, denn dann ist die Wahrscheinlichkeit größer, dass beide sich auf gleich dünnem Eis bewegen. Bei einer gewöhnlichen (und evtl. optimaleren) Eröffnung wird der überlegene Gegner aufgrund seiner größeren Erfahrung sehr viel besser wissen, was zu tun ist, und einen schneller an die Wand spielen.

Benutzeravatar
klospatz
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 230
Registriert: 16. Dez 2003 14:01
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von klospatz »

sicherlich wird es wohl stellungen geben, die auf eine gewisse suchtiefe beschraenkt, gut aussehen und im weiteren spielverlauf schlecht verlaufen koennen.

aber schlagt ihr gerade tatsaechlich vor gegen einen perfekt-spielenden computergegner, welcher wohlgemerkt den suchraum seiner gegeben rechen- und speicherkapzitaeten ausschoepft, dadurch ueberlisten wollt, dass ihr tiefer sucht als er? und nebenbei noch ausrechnet bis wohin er wohl gerechnet haben koennte um eure zuege darauf auszurichten? ihr wollt also deep blue schlagen indem ihr ihm einen anderen rechner vorsetzt der ihm in puncto rechenleistung und speicherkapazitaet exponentiell ueberlegen ist?

koennte vielleicht funktionieren. auf die diplomarbeit bin ich gespannt...

Benutzeravatar
Rodent Bait
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 26. Apr 2005 14:50
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Rodent Bait »

Wieso Computer? Das rechne ich doch im Kopf aus! :D

Aber im Ernst: Deep Blue ist eben gerade kein perfekt spielender Gegner im Sinne der Definition, da ein perfekt spielender Gegner immer bis zum Ende des Suchraums suchen muss, und zwar im gesamten Baum (abzüglich der Äste, die sich alpha-beta-prunen lassen).

Antworten

Zurück zu „Einführung in die Künstliche Intelligenz“