Algorithmus zum Lösen von Solitär

Moin,
in einem sonntäglichen Langeweileanfall habe ich zum ersten Mal überhaupt das Windows Solitär gespielt (7 Stapel, aufsteigende Anzahl, 24 Karten in 3er Gruppen auf Hauptstapel).

Habe dabei festgestellt, dass es gar nicht so trivial ist wie ich dachte, im Gegenteil habe ich trotz mehrerer Versuche keine Lösung geschafft. Habe mir dann erstmal angeschaut wie die mathematische Grundlage aussieht (ca. 90% aller Spiele sind lösbar wenn man keine Fehler macht) und dann überlegt wie man algorithmisch da ran geht.

Es scheint sinnvoll zu sein, am Anfang erstmal den 24 Stapel komplett durchzuschauen um einen Überblick zu bekommen. Es wird dann aber schon problematisch wenn ich mir überlege dass man dann opportune Karten rausnimmt (zB Asse) und dann berechnen (??) muss, wie die neue 3er Verteilung sein wird, wenn der Stapel erneut durchgelaufen wird. Dazu scheint mir trotzdem noch soviel zuviel drin zu sein, dass man nichtmal annährend auf die 90% Siegquote kommen kann?

Hat sich jemand schonmal hiermit befasst? Bin grade am liebäugeln eine kleine KI-Implementierung zu machen^^ hab ja noch Semesterferien.

Dazu scheint mir trotzdem noch soviel zuviel drin zu sein, dass man nichtmal annährend auf die 90% Siegquote kommen kann?

soll natürlich heißen "soviel Zufall"

krümelkacker

wo kommt denn die zahl 90% her? Solitaire gibt's ja auch in mehreren Varianten. In der Version, die ich früher mal spielte, wurde z.B. immer nur eine Karte vom Stapel gezogen. Das dürfte etwas einfacher sein. Aber 90% habe ich da auch nie geschafft. Eher 20%.

asc

krümelkacker schrieb:

wo kommt denn die zahl 90% her?

Wundert mich ebenso. Nach mehreren Regeln die ich kenne liegt die Quote ebenso merklich niedriger (Zum einen kenne ich die Variante wie bei dir, das man nur eine Karte ziehen kann, zum anderen ist auch schon die Frage ob man den Kartenstapel Neugeben kann, und wenn ja: wie oft...).

Ich selbst kenne alleine schon so viele Solitärvarianten, das ich garnicht ahnen kann, welche Variante er nun meint...

Moin,
hier die Quelle:
http://www.techuser.net/klondikeprob.html

wie gesagt geht es um die Variante die bei Windows dabei ist.

und ja, mit der 1 Karten Variante dürfte es deutlich einfacher sein, aber mit 3 Karten finde ich es echt knackig und sehe so wirklich keine Möglichkeit wie man es ohne Glück gut schaffen kann?

Fedaykin

Ich glaube kaum das man da wirklich was über KI reisen kann. Bzw nur mit extrem viel Aufwand.
Man könnte wohl damit anfangen eine KI zu schreiben der alle Karten bekannt ist. (also alles offen) dort müsste man wohl schon mit Backtracking weiterkommen. Die KI erkennt dann auch recht schnell ob ein Spiel lösbar ist oder nicht. Ab dann könnte man versuchen ein Teil der Karten verdeckt zu machen und die KI irgendwie lernen zu lassen welcher Schritt als nächstes sinnvoll ist. Manchmal ist es ja nicht unbedingt das beste eine Karte auf die Asse zu legen). Ggf könnte man hier nun per Backtracking alle möglichen Züge ausführen lassen ohne Verdeckte Karten aufzudecken, und dann bewerten welcher Zug der effektivste ist (z.B. bei welcher Zugreihenfolge kriege ich die meisten Karten los bzw darf am meisten Karten neu aufdecken.) Dabei ist noch nicht berücksichtigt das man ggf die Reihenfolge der Karten im Spielstapel noch auserten muss, ggf könnte man in erste instanz noch mit offenen Nachziehstapel Simulieren und sich später dafür noch etwas einfallen lassen, wie die KI immer noch Sinnvolle entscheidungen trifft ohne das der Nachziehstapel komplett bekannt ist (Wäre ja nur beim ersten durchspielen interessant).

krümelkacker

Der letzte Absatz ist interessant:

Some players might be surprised by the above numbers. These numbers imply that majority of Klondike games are winnable; however, experience playing the game indicates otherwise. The reason players do not win majority of Klondike games is mainly the tremendous amount of guesswork involved in playing Klondike. A few wrong moves can easily make a player lose and this is what happens most of the time.

Um all die lösbaren Spiele auch zu schaffen, scheint es aber erforderlich, extrem viel Glück zu haben oder zu wissen, welche Karten wo verdeckt liegen.

Interessant ist natürlich die Suche nach einer Strategie, mit der die meisten lösbaren Spiele auch tatsächlich gelöst werden können, ohne dass man vorher all die verdeckten Karten kennt. Was man da -- als "optimaler" Spieler, der nicht hellsehen kann -- für eine Quote erreichen kann, würde mich mal interessieren.

"Was man da -- als "optimaler" Spieler, der nicht hellsehen kann -- für eine Quote erreichen kann, würde mich mal interessieren."

Genau das war der Ausgangspunkt meiner Fragestellung, gut dass ich nicht der einzige bin der das interessant findet

hustbaer

SolitärNoob schrieb:

Moin,
hier die Quelle:
http://www.techuser.net/klondikeprob.html

Da ist keine Berechnung sondern nur eine Schätzung.

Auch sind Solitair Spiele nur mit etwas Glück lösbar. Es gibt sicher eine optimale Strategie, nur wird diese sehr komplex sein, und in vielen Fällen auch Spiele nicht lösen die - wenn man sie anders angegangen wäre - grundsätzlich lösbar sind.

D.h. selbst wenn die Schätzung zutrifft, und 90% aller Spiele lösbar sind, heisst das noch lange nicht dass es eine Strategie gibt die auch nur annähernd alle lösbaren Spiele auch wirklich "schafft".

EDIT: OK, sorry, ich sollte erstmal den ganzen Beitrag lesen, der Punkt ist ja schon durch. Und interessieren würde es mich auch. Kann mir aber grad nicht vorstellen dass man das irgendwie berechnen kann. EDIT2: also "irgendwie" berechenbar im Sinn von theoretisch berechenbar ist es sicher. Ich meine natürlich in der Praxis.