Künstliche Intelligenz beim Skat

Skat gegen den Computer

Künstliche Intelligenz beim Skat

Beitragvon marvin » 30. Aug 2008 11:01

Nach langer Abstinenz melde ich mich mit ein paar Gedanken zum Thema "Künstliche Intelligenz beim Skat" zurück. Da die Ausführungen nicht speziell auf ein Programm gemünzt sind (wenngleich mich Skat-Stübl und Siegfried zu den Gedanken inspiriert haben), eröffne ich einen neuen Thread. Es wird ein ziemlich langer Startbeitrag und ich hoffe, dass ich niemanden damit abschrecke. Wenn sich eine intensive Diskussion um einzelne meiner Thesen entwickelt, kann man die ja vielleicht auskoppeln.

Heuristiken

Wie funktioniert eigentlich ein Skatprogramm oder allgemeiner, ein vom Computer gesteuerter Teilnehmer an einem Mehrpersonenspiel? Ein weit verbreiteter Ansatz ist die Verwendung von Heuristiken. Eine Heuristik ist eine Regel der Form "Wenn die Spielsituation das Merkmal X aufweist, so tue Y". Auf Skat bezogen sind das also zum Beispiel Leitsätze wie "Kläre als Alleinspieler möglichst schnell die Trümpfe", "Spiele als Gegenspieler über den langen Weg möglichst eine blanke Karte an", "Zeige beim Abwerfen die Gegenfarbe an" und ähnlich. Ob sie nun gut oder schlecht sind, tut bei der Verwendung des Begriffs Heuristik im Weiteren Sinne nichts zur Sache. Im engeren Sinne versteht man unter einer Heuristik freilich eine sinnvolle Regel.

Eine heuristisch programmierte KI funktioniert nun im Wesentlichen so: Die Programmierer sammeln so viele sinnvolle Heuristiken, wie sie finden können. Das Programm prüft nun alle auf ihre Anwendbarkeit in der konkreten Situation und spielt dann die Karte, die von den meisten anwendbaren Heuristiken vorgeschlagen wird. Dabei kann man die Heuristiken natürlich unterschiedlich gewichten (Regel 1 zählt mehr als Regel 17) oder in vorrangige und nachrangige einteilen (Regeln 50 bis 200 werden nur geprüft, wenn keine der Regeln 1 bis 49 anwendbar war). oder noch kompliziertere Sachen machen.

Wichtig ist, dass ein solches Programm auf Erfahrungswerten basiert. Es wird niemals eigenständige Spielzüge entwickeln, sondern immer nur Bekanntes nachspielen. Insbesondere wird es keine genialen Spielzüge finden, auf die die Programmierer nicht gekommen wären. Wenn einzelne Heuristiken Unsinn sind, wird es immer wieder dieselben Fehler machen.

Der Minimax-Algorithmus

Schachcomputer verfolgen in der Regel einen anderen Ansatz. Bei der Beurteilung der Stellung wird zunächst ein sogenannter Suchbaum aufgebaut. Das muss man sich wie folgt vorstellen: Auf einem großen Blatt Papier wird die aktuelle Stellung durch einen Punkt am unteren Rand markiert. Von dort wird nach oben ein Pfeil für jeden legalen Zug gemalt und die daraus entstandene Stellung durch einen weiteren Punkt markiert. Von diesen Stellungen ausgehend wird wieder jeder legale Zug mit einem Pfeil nach oben zur daraus entstehenden Stellung markiert. Das geht so lange, wie der Computer Zeit und Speicherplatz hat. Es entsteht eine Art Baum mit der aktuellen Stellung als Wurzel, Ästen für jeden legalen Zug und Blättern in jeder erreichbaren Stellung.
Bei kleineren Spielen kann man auf diese Weise die komplette Zukunft des Spiels aufmalen und die Endstellungen dahingehend bewerten, ob sie für den KI-Spieler gewonnen (1) oder verloren (0) sind. Schach ist aber schon wieder so groß, dass nicht der gesamte Baum in den Computer passt. Deshalb wird er nach einer gewissen Zahl Züge abgebrochen und die entstandenen Stellungen mit einer Heuristik hinsichtlich ihrer Gewinnwahrscheinlichkeit bewertet, von 1 (sicher gewonnen) bis 0 (sicher verloren).
nachdem der Spielbaum aufgemalt und alle Blätter bewertet sind, werden die Züge von den Blättern rückwärts ausgewertet. Die Stellungen unmittelbar vor den Blättern bekommen einen Wert, der sich aus dem Maximum der Werte der erreichbaren Blätter ergibt, falls der KI-Spieler den letzten Zug macht, und aus dem Minimum, wenn es sein Gegner ist. Anschließend werden die Blätter aus dem Baum entfernt, so dass die soeben bewerteten Knoten die neuen Blätter sind. So geht das Spiel weiter, bis ich beim nächsten auszuführenden Zug bin. Nun wird der Zug ausgeführt, welcher zu der am höchsten bewerteten Stellung führt.
Das hört sich komplizierter an als es ist. Am Beispiel geht es vielleicht besser. Das Spiel möge so einfach sein, dass man in jeder Situation nur zwei mögliche Züge hat. Der Computer wiederum ist so klein, dass er nur drei Halbzüge fortentwickeln kann und dann die Stellungen mit Heuristiken bewertet. Im Beispiel sei Weiß am Zug und habe die Möglichkeiten A und B. Anschließend Schwarz mit den Zügen C und D. Im dritten Halbzug, der noch entwickelt wird, kann Weiß E oder F ziehen. Daraus ergibt sich folgender Suchbaum, den ich mit zufällig ausgewählten Gewinnwahrscheinlichkeiten versehen habe

_0.1__1.0__0.0_0.3___0.1_0.9___0.7_0.6
__E___F____E___F____E___F____E___F
____C________D________C________D
_________A_________________B

Da der dritte Zug von Weiß, dem KI-Spieler, auszuführen ist, werden die höheren der beiden Werte an den übergeordneten Knoten durchgereicht. Das ergibt folgende Situation

___1.0_______0.3_______0.9______0.7
____C________D________C________D
_________A_________________B

Nun wird der Zug von Schwarz ausgewertet, so dass die kleinere der Zahlen zurückgegeben wird

________0.3________________0.7
_________A_________________B

Somit ergibt sich, dass Weiß als nächstes den Zug B ausführen sollte und dann mit mindestens 70% Wahrscheinlichkeit gewinnt, sofern er selbst optimal weiterspielt und die Heuristik an den Blättern recht hatte. Sollte Schwarz nicht optimal spielen, ist die Gewinn-WSK für Weiß sogar noch höher.

Das dumme am Minimax-Algorithmus ist, dass er nur bei Spielen mit vollständiger Information funktioniert - d.h. wenn die Stellung wie beim Schach jedem Spieler vollständig bekannt ist. Skat gehört nicht dazu, denn hier kennt man zu Spielbeginn nur seine eigenen Karten und erfährt erst im Laufe des Spiels die vollständige Verteilung. In den meisten Situationen, wo man sich für eine Karte entscheiden muss, wird man sie noch nicht kennen. Dann aber kann der Computer nicht die Züge der Gegner vorhersehen.

Beim "Glaskartenskat" dagegen würde der Algorithmus gut funktionieren, wahrscheinlich könnte man sogar auf haushaltsüblichen Computern den vollständigen Spielbaum entwickeln. Dann würde der Computer optimal spielen.

Viele Welten und Minimax

Der nächste Ansatz, der laut der hier bereits vorgestellten Arbeit von Jan Schäfer erfolgreich beim Bridge gewesen sei, beruht auf folgender Idee. Man konstruiere einfach alle denkbaren Kartenverteilungen ("Welten"), führe dann in jeder Welt den Minimax durch und spiele anschließend die Karte, die im Durchschnitt über alle Welten den höchsten Erfolg verspricht. Setzen wir das obige Beispiel fort und nehmen an, in einer zweiten Welt würde Zug A einen Wert von 0.8 und Zug B einen Wert von 0.2 bekommen. Dann hätte A im Durchschnitt Wert 0.55 und B im Durchschnitt 0.45, deshalb wäre A zu spielen.

In der Praxis sind beim Skat zumindest während der ersten Züge Zigtausend Welten denkbar, so dass aus Gründen der Rechenzeit nicht alle untersucht werden können. Das ist auch gar nicht notwendig, denn wie die Arbeit von Schäfer zeigt, hat der Computer nach Untersuchung von 250 zufällig ausgewählten Welten im Normalfall ein so gutes Gefühl, dass die Hinzunahme weiterer Welten keine Verbesserung bringt. Einen Mathematiker wundert das nicht, aber das führt zu weit vom Thema weg...

Dies ist, wenn ich die Autoren richtig verstanden habe, auch der Ansatz von Siegfried und Skat-Stübl, wobei derzeit wohl weit weniger als 250 Welten untersucht werden und außerdem in den ersten Zügen statt der Suche in vielen Welten eine Heuristik bemüht wird.

Viele Welten und Heuristik

Schäfer hat dagegen nicht die Baumsuche in vielen Welten umgesetzt. Er hat in jeder simulierten Welt für jeden Zug, den die KI als nächstes tun könnte, die Stellung an ein heuristisch arbeitendes Skatprogramm übergeben, von diesem zu Ende spielen lassen und das Ergebnis als Bewertung für den Zug genommen. Sein Programm hat dann den Zug gespielt, der im Durchschnitt über alle Welten das beste Ergebnis gebracht hat.

Damit ist es ihm gelungen, ein Programm zu schreiben, dass besser war als das heuristisch arbeitende Skatprogramm, welches er als Hilfsprogramm verwendet hat.

Kritik an "Viele Welten und Minimax"

Im folgenden will ich ein paar Bedenken gegen den Ansatz von Skat-Stübl und Siegfried vorbringen. Dies soll keineswegs bedeuten, dass ich ihre Versuche als zum Scheitern verurteilt ansehe, sondern soll mögliche Schwächen des reinen Algorithmus aufzeigen, um Ansätze für Verbesserungen zu haben.

Der Algorithmus sucht die optimale Lösung für das falsche Problem

Da der Algorithmus bei der Untersuchung der Welten mit offenen Karten spielt, sucht er die bestmögliche Karte für folgendes Spiel: Der Spieler am Zug muss eine Karte ausspielen. Anschließend wird alles aufgedeckt, so dass jeder Spieler unter Kenntnis der konkreten Kartenverteilung optimal spielen kann.

Das muss aber nicht zwangsweise die beste Karte für das Spiel mit verdeckten Karten sein, da die optimale Spielweise bei bekannter Kartenverteilung oftmals völlig anders ist als bei unbekannter Verteilung. Auch die Durchschnittsbildung hilft da nicht notwendig weiter, ja ich behaupte: Im Fall von Skat tut sie es nicht. Mag sein, dass man bei Bridge damit gute Erfahrungen gemacht hat, aber das was da gilt, muss nicht auf Skat übertragbar sein.

Als Alleinspieler baut der Computer sein Spiel oft auf wenige exotische Verteilungen auf

Viele Spiele sitzen aus Sicht des Alleinspielers auf Verlust, werden aber trotzdem gewonnen, da die Gegenspieler am Anfang aus Unkenntnis der genauen Verteilung nicht optimal spielen. In solchen Spielen wird der Computer nur wenige Kartenverteilungen finden, in denen er überhaupt gewinnen kann. Der Computer sucht dann die Karte, die in solchen exotischen Verteilungen zwingend gewinnt, während die Mehrzahl der Verteilungen, nämlich die, wo er den Sieg nicht erzwingen kann, gar nicht in die Berechnung eingeht.

Als Gegenspieler vertraut der Computer darauf, dass sein Partner optimal spielt

Das klassische Anwendungsgebiet des Minimax sind 2-Personen-Spiele, wo streng abwechselnd gezogen wird (wie Schach). Skat wird zwar in der Spieltheorie als 2-Personen-Spiel bezeichnet, richtiger wäre aber 2-Parteien-Spiel, wobei eine Partei aus zwei Personen besteht. Somit kommen auf einen Zug der Partei des Alleinspielers im Durchschnitt 2 Züge der Gegenpartei. Hinzu kommt, dass die Züge nicht streng abwechselnd laufen, da der Gewinner des vorherigen Stichs zum nächsten ausspielt. Dadurch kann z.B. folgende Zugfolge entstehen
1. AS G1 G2
2. G2 AS G1
...
Wenn nun G1 von der KI simuliert wird, so ist zwischen seinen beiden Zügen zweimal sein Partner dran. Der Minimax unterstellt nun, dass alle anderen am Spiel beteiligten Personen dieselben Gedanken wie G1 haben und daher aus Sicht von G1 die für die jeweilige Partei optimalen Züge spielen. Wählt der AS einen anderen, so ist das also ein schwächerer Zug und somit steigt die Gewinn-WSK für die Gegenpartei. Also kein Nachteil. Wählt aber G2 einen anderen Zug, so ist das für die Gegenpartei schlecht und die Gewinn-WSK sinkt!

Das Problem ist nun, dass G2 möglicherweise gar nicht wissen kann, welchen Zug G1 erwartet hat.

Ohne Heuristiken geht es nicht

Gute menschliche Spieler versuchen im Gegenspiel die Karten so zuzugeben, dass ihr Partner möglichst viele Informationen über die tatsächliche Verteilung gewinnen kann. Dazu gehören dann auch solche "unausgesprochenen Absprachen" wie Gegenfarbe zeigen oder die Reihenfolge der Luschenzugabe. Oder das Eingehen auf den Reizwert. Solche überlegungen kriegt man aber nur mit Heuristiken in den Computer.

Ein schönes Beispiel ist das Zeigen von Karo-Bube:
Vorhand (spielt Kreuz)
krbu pibu kr10 krko kr08 ...
Mittelhand
kabu kr09 kr07 ...
Hinterhand
hebu kras krda ...

1. krbu kr07 krda
2. pibu ...
Der Mensch spielt ohne zu zögern Karo-Bube, damit HH evtl. Trumpf-As schonen kann. Der Computer würde folgende Überlegungen anstellen:
Wenn HH den Herz-Buben und mindestens einen weiteren Trumpf hat, macht er einen Trumpf-Stich. In den tue ich besser den Karo-Buben als Kreuz-9, weil er 2 Augen mehr bringt. In allen anderen Fällen ist es egal, welche Karte ich zugebe. Also spiele ich jetzt Kreuz-9. Er würde nicht auf die Idee kommen, den Karo-Buben zu zeigen, da ja in seinem Algorithmus jede Welt mit offenen Karten gespielt wird. Daher tut er beim Durchspielen der Welten so, als ob HH weiß, dass MH den Karo-Buben hat.

Soviel für heute (ist sicher mehr als genug). Zu einem späteren Zeitpunkt kommt vielleicht noch mehr.
marvin
 
Beiträge: 1158
Registriert: 23. Mär 2007 01:31
Wohnort: Idstein

Beitragvon Skatfuchs » 30. Aug 2008 21:03

Hallo marvin,

grundsätzlich sehe ich dass auch so wie du- bei der Anwendung der Monte-Carlo-Methode auf das Skatspiel in den ersten Stichen sogar noch etwas kritischer!
Das Hauptproblem ist wohl, dass ein Computer nach einer solchen Methode niemals eine "aufklärende Farbe" bringt, wie es menschliche Spieler tun!
Eine generelle Methode fehlt aber noch in deiner Systematik: ein kybernetisches Modell, wo man anhand gleichartiger von Menschen gespielter Skatspiele danach sucht, was ein solcher (möglichst guter) Spieler in einer gleichartigen Situation getan hätte und danach die nächste Karte auswählt.
Was hältst du den davon? :wink:
Ein Gut Blatt

Skatfuchs

Wer sich nach Regeln ängstlich richtet und hinter die Schablone flüchtet, den weihte nie mit seinem Kuß des Skates höchster Genius!
www.skatfuchs.eu
Benutzeravatar
Skatfuchs
 
Beiträge: 7375
Registriert: 25. Sep 2005 14:31
Wohnort: Chemnitz

Beitragvon Chevalier » 30. Aug 2008 21:54

Ein Pool "gut gespielter Partien" wäre sehr interessant.
Benutzeravatar
Chevalier
 
Beiträge: 3758
Registriert: 2. Aug 2006 09:23
Wohnort: Planet Erde

Re: Künstliche Intelligenz beim Skat

Beitragvon b0n541 » 31. Aug 2008 18:32

Der Algorithmus sucht die optimale Lösung für das falsche Problem

Da der Algorithmus bei der Untersuchung der Welten mit offenen Karten spielt, sucht er die bestmögliche Karte für folgendes Spiel: Der Spieler am Zug muss eine Karte ausspielen. Anschließend wird alles aufgedeckt, so dass jeder Spieler unter Kenntnis der konkreten Kartenverteilung optimal spielen kann.


Ich bin der schon mehrfach zitierte Jan Schäfer und muss deshalb Einspruch einlegen:

Beim oben genannten Einsatz des Algorithmus für Bridge war es so, dass die simulierten Kartenverteilungen mit offenen Karten gespielt wurden. Ich habe aber in den Simulationen in meinen Arbeiten die verdeckten Karten beibehalten. Es wurde immer eine mögliche Welt gewürfelt und dann von drei Instanzen des Skatspieles XSkat unabhängig von einander zuende gespielt. Die drei Instanzen hatten also zu jedem Zeitpunkt nur das Wissen der jeweiligen Hand zur Verfügung.
Benutzeravatar
b0n541
 
Beiträge: 2
Registriert: 26. Aug 2008 11:06

Beitragvon marvin » 31. Aug 2008 19:12

Hallo Jan,

erst mal schön, dass du dich zu Wort meldest. Um es nochmal deutlich zu sagen: Meine Kritik zielt auf den Ansatz von Skat-Stübl und Siegfried, bei denen jede Welt mit offenen Karten via Minimax untersucht wurde. Ich habe schon verstanden, dass du mit einem heuristisch arbeitendem Skatprogramm die Welt zu Ende gespielt hast - das ist ein völlig anderer Ansatz!

Sorry, wenn ich mich nicht klar ausgedrückt hatte.
marvin
 
Beiträge: 1158
Registriert: 23. Mär 2007 01:31
Wohnort: Idstein

Beitragvon Skatfuchs » 31. Aug 2008 21:58

Hallo Jan,

erst einmal ein recht herzliches Willkommen hier am Board- wir freuen uns schon auf rege Diskussionen mit dir!

Ich schließe mich der Auffassung von marvin an: dein Ansatz einer Kombination heuristischer Modelle mit der Monte-Carlo-Simulation halte ich schon für wesentlich erfolgversprechender, als deren alleinige Anwendung!

Nur schade, dass du da veraltete Heuristiken nehmen musstest, da ja bekanntlich an diesen von dir verwendeten seit einigen Jahren nichts mehr entwickelt wurde. :oops:
Ein Gut Blatt

Skatfuchs

Wer sich nach Regeln ängstlich richtet und hinter die Schablone flüchtet, den weihte nie mit seinem Kuß des Skates höchster Genius!
www.skatfuchs.eu
Benutzeravatar
Skatfuchs
 
Beiträge: 7375
Registriert: 25. Sep 2005 14:31
Wohnort: Chemnitz

Beitragvon Karlzberg » 1. Sep 2008 03:56

hallo marvin,

ein schöner, ausführlicher und informativer beitrag :)

allerdings muss ich sagen, dass in den verwendeten methoden meiner meinung nach nicht allzu viel von künstlicher INTELLIGENZ zu sehen ist.
nun gut, bis man wirklich von intelligenz sprechen kann, ist es wohl noch ein sehr weiter weg, nicht nur in bezug auf skat, wenngleich "kleinere" dinge, wie "schwarmintelligenz" schon recht gut funktionieren.

daher würde ich bei der programmierung einer ki für skat einen ganz anderen weg einschlagen. ich denke, mien angedachter weg käme den heuristiken am nächsten. letzlich "funktionieren" wir menschen ja auch nach heuristiken, wenn man es streng sehen will.

das problem an den heuristiken ist meiner meinung nach nicht, dass sie fehlerhaft in sich selbst sind, sondern, dass sie schliuchtweg nur falsch umgesetzt werden. scheinbar hauptsächlich von leuten, die eben nicht den großen einblick in skat haben.

so wäre es anderenfalls z.b. denkbar, dass man die k.i. für jedem zug zunächst einmal haupt- und nebenpläne entwickeln lässt, so, wie es der mensch auch tut (bzw. tun sollte). anhand dieser lassen sich schon sehr viele züge ableiten, da man berechnen kann, welcher spielzug überhaupt zu einem gewinn führen kann. problematisch ist dabei sicherlich -speziell im gegenspiel-, dass man der k.i. irgendwie beibringen müsste, wie ein realistisches spiel des as aussehen könnte. hierzu könnte man sich als erste hilfestellung ein reizsystem (z.b. das von kinback, oder das von van stegen) zur hilfe nehmen. dadurch könnte sich die k.i. schon jede menge möglicher kartenverteilungen für den ermitteln und daraufhin anhand der eigenen karten einen gewinnweg suchen. würde die k.i. dann -basierend auf den eignen karten- keinen weg finden können, würde sie -bei zuhilfenahme eines reizsystem, das auf 10 pkt. basiert- dem as nurnoch 9 punkte geben. sieht sie dann noch immer keinen weg, werden es nurnoch 7 pkt. usw..
im weiteren verlauf klärt sich die stellung der karten dann immer weiter auf. gerade die erkenntnisse zur symmetrie oder schlichtweg die ermittlung der möglichen restfarben helfen hier schon stark weiter. als simples beispiel sei hier genannt:

ki ist im gegenspiel in hh. vh ist der ms der k.i. (menschlich), as in mh wird durch die k.i. ersetzt. herz ist trumpf.
vh spielt nun kreuz auf, as sticht, die k.i. in hh muss BLANKES kreuz hinzugeben.
nun weiß die k.i. also, dass vh schonmal mind. 4 kreuzen hat, und max. 6.
folglich bleiben auch nurnoch ebensoviele karten für die anderen farben übrig. zusätzlich kann nun die k.i. auch noch ermitteln, ob das ass in kreuz auf den stich gefallen ist, oder nicht. ist es nicht gefallen, hat die k.i. damit schonmal eine sichere karte bei vh ermittelt und kann schon erste hochrechnungen erstellen:
um nun besser ermitteln zu können, ob vh nun 4,5 oder 6 kreuzen führt, kann die k.i. nun abermals ein reizsystem zur hilfe nehmen. noch ergeben sich nach diesem stich wohl zuviele möglichkeiten, weitere aufklärung bringt dann aber der folgende trumpfzug des as. nehmen wir an, im angesprochenen beispiel hätte vh auf den nächsten zug einen bauern gezeigt. dann stünden für die k.i. schonmal folgende informationen zur verüfgung, in zwei möglichkeiten, abhängig von der reizung:
1.) vh hat nciht gereizt, hat mind. einen bauern und lang kreuz mit dem ass. nach dem hier im forum von mir eingestellten reizsystem wären das bei 6 kreuzen schon 9 reizpunkte. ist die zehn ebenfalls nciht im ersten stich vorgekommen, kämen damit sogar schon 10 reizpunkte zusammen. folglich wird vh also keine 6 kreuzen führen. usw. usf...
2.) bei reizung sieht es wieder ähnlich aus: mit 6 kreuzen und den beiden vollen in vh können alle anderen farben einfach besetzt stehen (bleiben nurnoch drei karten übrig), bei 5 und 4 kreuzen ändert sich das beiblatt entsprechend.

über diesen weg können dann auch weitere farblängen- bzw. kürzen bei vh ermittelt werden. somit verdichtet sich langsam, aber sicher das blatt von vh und die vorher aufgestellten pläne zum legen des spiels könne immer weiter verdichtet werden, bis schließlich nurnoch ein einziger zwingender gewinnweg überbleibt.

für das alleinspiel ist das natürlich alles wesentlich leichter zu berechnen. hierbei helfen z.b. auch schon die theorien zu den zählmethodiken sehr viel weiter.

nullspiele hingegen sind wesentlich leichter zu berechnen. hierzu würde ich schlichtweg das nullsystem von kannix anwenden, welches eine mehr als ausreichend hohe trefferquote aufweist.
gez.: Das einzig wahre Bier
Karlzberg
 
Beiträge: 3287
Registriert: 29. Sep 2005 23:56

Beitragvon marvin » 3. Sep 2008 20:55

Ja, ich habe nicht alle denkbaren Algorithmen vorgestellt. Sondern nur die, die meines Wissens bisher in Skatprogrammen umgesetzt sind. Die handelsüblichen spielen mit Heuristiken. Außerdem habe ich mal ein Programm gesehen, was in der höchsten Schwierigkeitsstufe gemogelt hat und bei der Berechnung der optimalen Züge von der tatsächlichen Verteilung ausgegangen ist. Ich nehme an, da hat man den Minimax mit Glaskarten programmiert. Ferner die Programme von Jan Schäfer (Viele Welten und Heuristik) sowie Skat-Stübl und Siegfried (Viele Welten und Minimax).

Eines habe ich noch vergessen: Ich habe mal ein Skat-Programm gesehen, welches von sich behauptet hat, mit Neuronalen Netzen zu spielen. Wie ein NN funktioniert, davon habe höchstens eine vage Vorstellung. Die Idee dahinter ist, dass das Programm lernfähig ist.

Als Nicht-Programmierer sollte man sich das vielleicht wie eine riesige Sammlung von Heuristiken (sinnvollen wie unsinnigen) vorstellen, die alle eine gewisse Wahrscheinlichkeit haben, angewandt zu werden. Wenn das Programm einen Zug machen muss, sucht es alle anwendbaren Heuristiken und würfelt aus, welche es davon diesmal anwendet (dabei werden die angehefteten Wahrscheinlichkeiten beachtet). Nach dem Spiel beurteilt das Programm den Erfolg. War es gut, so werden alle angewandten Heuristiken verstärkt, d.h. ihre Wahrscheinlichkeiten erhöht. War es schlecht, werden die Wahrscheinlichkeiten der angewandten Heuristiken verringert. Die Idee ist nun, dass sich im Laufe der Zeit die sinnvollen Heuristiken herauskristallisieren und so das Programm immer besser wird.

Tatsächlich werden im NN aber keine Heuristiken programmiert, sondern irgendwelche abstrakten Schaltkreise. Damit könnte es sogar möglich sein, dass das Programm neue Heuristiken "aus dem Nichts" zaubert und bei Erfolg weiter anwendet. Jedenfalls halte ich einen solchen Ansatz für vielversprechend.
marvin
 
Beiträge: 1158
Registriert: 23. Mär 2007 01:31
Wohnort: Idstein

Beitragvon Skatfuchs » 19. Sep 2008 12:02

Hallo marvin,

du beschreibst, dass deiner Meinung nach die "neuronalen Netze" so funktionieren: Als Nicht-Programmierer sollte man sich das vielleicht wie eine riesige Sammlung von Heuristiken (sinnvollen wie unsinnigen) vorstellen, die alle eine gewisse Wahrscheinlichkeit haben, angewandt zu werden. Wenn das Programm einen Zug machen muss, sucht es alle anwendbaren Heuristiken und würfelt aus, welche es davon diesmal anwendet (dabei werden die angehefteten Wahrscheinlichkeiten beachtet).

Es gibt aber sicherlich auch viele Fälle, wo "viele Wege nach Rom", d.h. zum Spielgewinn führen. Da nur willkürlich- möglicherweise gewertet- eine Heuristik verwendet wird und der Spieler dann sein Spiel gewinnt, so wird diese zusätzlich positiv bewertet, obwohl auch viele andere zum Sieg gekommen wären. Wie will man das da unterscheiden?

Ich glaube, so wird das auch nichts!

Was hälst du aber von der von chevi und mir angeregten Methode, einen Spielepool vieler von "Experten" gespielten Spiele zu hinterlegen und dann "nachzuschauen", was ein menschlicher Spieler in einer vergleichbaren Situation gespielt hätte?
Sicherlich sind da die 4.000 Spiele, die bei einem Programm hinterlegt wurden, wohl völlig indiskutabel! :cry:
Ein Gut Blatt

Skatfuchs

Wer sich nach Regeln ängstlich richtet und hinter die Schablone flüchtet, den weihte nie mit seinem Kuß des Skates höchster Genius!
www.skatfuchs.eu
Benutzeravatar
Skatfuchs
 
Beiträge: 7375
Registriert: 25. Sep 2005 14:31
Wohnort: Chemnitz


Zurück zu Skatprogramme

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast