Mühle Spiel inklusive KI

[theSplit]

Wenn ich das mal einwerfen darf Roin, hat alles Vor- und Nachteile. Aber was so vermutlich nicht ganz richtig ist, das man ohne grafische Ausgabe nicht gewinnen kann.

Es ist schließlich nicht das Ziel die beste grafische Umsetzung zu schreiben mit viel Blink Blink und Glitter, sondern das Spiel Mühle zu programmieren und eine KI zu entwickeln gegen die man als menschlicher Spieler antreten kann.

Die beste Optik nützt nichts wenn die KI oder das Grundspiel nicht richtig funktionieren. Auch wenn "Optik" natürlich bequemer ist... ich würde mich aber nicht selbst deswegen entmutigen lassen.

 

[Roin]

@theSplit: Stimmt - wobei es mir scheint, dass bei den letzten Wettbewerben überall wo etwas grafisch zu lösen war auch solche Lösungen gewonnen haben. Liegt aber vielleicht auch daran, dass die entsprechenden Programmierer da mehr Zeit reingesteckt haben und dadurch die Lösung im Allgemeinen besser war.

 

[theSplit]

@Roin:

Kann Zufall sein oder kommt dir vielleicht Gefühlt so vor? - Wenn alles Objektiv, nach allen andere Faktoren, "gleichwertig" gestaltet ist, Punktet dann natürlich eine schöne Optik - aber vermutlich ist dass nur das Ausstechen ganz am Ende, nachdem Funktionalität und Codequalität überprüft worden sind.

Ist halt ein toller "Bonus", aber ich find eine Konsolenvariante jetzt nicht zwingend unattraktiver wenn die Handhabung clever ist, gibt sogar Leute die würden das vor einer (ver)komplizierten GUI vorziehen, siehe VIM/Nano/Emacs als Editoren, alles über Tasten gesteuert, kaum/kein UI was über die Tastatur hinausgeht - auch wenn man die Maus ja einsetzen kann, man muß nicht - und sowas nutzen eine Menge Leute. Kann also nicht so "scheiße" sein

 

[Seedy]

Eventuell kann man hier den kurzen Tipp einstreuen:

Wenn man das Programm für eine GUI programmiert, also die Eventsteuerung über das Interface laufen soll, ist es häufig von Vorteil "rückwärts" zu programmieren.
Das heißt, dass man erst die GUI baut, dann die Events hinter klatscht.

Wenn man versucht ein fertiges Programm mit einer GUI zu versehen, kann das häufig ziemlich eklige Frickelei werden,

 

[Roin]

@Seedy: Wenn man allerdings so Funktionen wie movePiece() oder so direkt mit Start und Zielpunkt versieht, kann man das durch die Evente ganz fix daran übergeben und im Hintergrund wird dann geprüft ob alles korrekt ist. Und wenn man es sich einfach machen will, zeichnet man die Gui dann nach jedem Spielzug einfach neu.

 

[KaPiTN]

Wenn man versucht ein fertiges Programm mit einer GUI zu versehen, kann das häufig ziemlich eklige Frickelei werden,

Sofern man einfach darauf los programmiert hat. Daher sollte man sich von Anfang an für irgend eine Trennung von Model, View und Controller entscheiden.

 

[Roin]

dann will ich euch mal etwas anstacheln....

Spoiler

[src=python] a_0 ---------------- a_1 ---------------- a_2 o ---------------- o ---------------- o
| | | | | |
| | | | | |
| b_0 --------- b_1 --------- b_2 | | w --------- w --------- w |
| | | | | | | | | |
| | | | | | | | | |
| | c_0 -- c_1 -- c_2 | | | | o -- o -- s | |
| | | | | | | | | | | |
| | | | | | | | | | | |
a_7 -- b_7 -- c_7 c_3 -- b_3 -- a_3 o -- o -- o s -- o -- o
| | | | | | | | | | | |
| | | | | | | | | | | |
| | c_6 -- c_5 -- c_4 | | | | s -- s -- s | |
| | | | | | | | | |
| | | | | | | | | |
| b_6 --------- b_5 --------- b_4 | | o --------- o --------- o |
| | | | | |
| | | | | |
a_6 ---------------- a_5 ---------------- a_3 o ---------------- o ---------------- o[/src]
Für die mit kleineren Bildschirmen...:

So - habe mir erstmal ne Ausgabe gebastelt, damit ich auch gucken kann, was hier passiert^^
Mir kommt die zwar derzeit noch relativ groß vor aber whey - immerhin ne Ausgabe.
Sieht allerdings auch nur aus, wenn das Konsolenfenster entsprechend groß ist.

 

[MingsPing]

Okay, meine Ausgabe kann ich auch schon einmal zeigen:

 

[Roin]

Ich habe jetzt schonmal alle möglichen Regeln programmiert. Alle Fälle abgegriffen, wenn vielleicht mal ein Steinchen nicht gezogen werden kann und sowas.

Fehlt nur noch irgendwas sinnvolles an Strategien für eine KI ...

 

[theSplit]

@MingsPing:

Find ich gut das man bei dir etwas von der Steuerung sieht, das wird die freie Setzphase sein oder?

Ich hab den Teil übersprungen gehabt, weil ich zu faul bin alles von Hand zu setzen um zu testen
Läuft daher rein zufällig ab - Aber dafür ist das normale ziehen und Steine entfernen schon implementiert und ein paar grundlegende Regeln auf die geprüft wird.


@Roin:

Jetzt schon? - Kann ich gar nicht so recht glauben
Alles auch schon ausgiebig getestet?

 

[Roin]

Find ich gut das man bei dir etwas von der Steuerung sieht

Wenn ich das richtig gesehen habe, ist meine Abfrage und so sehr ähnlich wie von MingsPing. Bei mir gibt man auch immer nur sowas wie A3 ein.
(Da fällt mir gerade noch was ein .... Vielleicht später als zusätzliches Feature...)

Jetzt schon? - Kann ich gar nicht so recht glauben
Alles auch schon ausgiebig getestet?

Also wenn ich die Regeln alle richtig verstanden habe, dann habe ich nun die Setzphase, die eigentliche Zieh-Phase und die Endphase wo einer oder beide Spieler rumspringen fertig. Steine können nicht falsch ziehen, oder falscherweise entfernt werden. Wenn was falsches passiert, gibt es eine mehr oder minder gute Beschreibung wieso was nicht geht und es wird erneut nach dem Zug gefragt. Es gibt eine Spielsituation, die ich zwar theoretisch drin habe, aber noch nicht ausprobieren konnte, da man bei mir das Spiel von Anfang an spielen muss.

Derzeit ist mein Spiel ein 1vs1 von Mensch vs Mensch. Der nächste Schritt sind jetzt strategische Felder herausfiltern und irgendwie gewichten (wahrscheinlich anfangs "dumm" gestaltet - also purer Zufall) und von einer KI ziehen lassen. Also einfach die Eingaben des Menschen von der KI machen lassen. Das kommt halt demnächst, wenn mehr Zeit da ist.

Meine morris.py (Morris = Mühle) bzw. fightAgainstMorris hat bisher ca. 500 Zeilen Code. Davon allerdings ca. 80 nur für die vernünftige Ausgabe zuständig sowie weitere 80 für den Input des Menschen. So viele Zeilen sind die Regeln also gar nicht.
Die erste Funktion, die später der KI Daten über das Spiel liefert ist übrigens auch schon fertig (50 Zeilen).

 

[theSplit]

Wenn ich das richtig gesehen habe, ist meine Abfrage und so sehr ähnlich wie von MingsPing. Bei mir gibt man auch immer nur sowas wie A3 ein.
(Da fällt mir gerade noch was ein .... Vielleicht später als zusätzliches Feature...)

Mir ist dazu auch ein Gedanke gekommen, den setze ich aber mal in einen Spoiler:

Spoiler

Man kann sich folgende zwei Punkte zu nutze machen, der Spieler hat immer nur bis zu 9 Steine auf dem Brett. Und im zweiten kann man jeweils nur maximal 4 Felder gleichzeitig ansteuern, zumindest in der normalen Zugphase.

---

Über die KI habe ich mir so noch keine Gedanken gemacht, ich kenne mich aber auch wenig mit dem Thema aus. Aber vermutlich kann man auch hier Kriterien/Strategien entwickeln um die Siegbedinungen zu erfüllen. Zum Beispiel den anderen Spieler "zugunfähig" zu machen.

---

Ein paar Gimmicks habe ich mir auch schon überlegt, zum Beispiel eine Spielstatistik, aber das ist ja nicht ganz Ziel der Aufgabe.

 

[Seedy]

Kleiner Anstoß zur KI:
Baut einen Zufallsgenerator.
Lasst Zufallsgenerator gegen Zufallsgenerator spielen, bis ihr alle möglichen Züge einmal habt.
Speichert die "möglichen" Züge, im Bezug zur jeweiligen Bedingung (wie das Feld zum Zeitpunkt des Zuges aussiehst)

Bewertet diese mit Gut, Mittel, Scheiße.
Lasst nun die "KI" einfach bei jedem Zug das Feld abgleichen und nach Schwierigkeitsgrad (Schwer, Mittel, Leicht) einen Zug aus der Tabelle aussuchen.


Es gibt definitiv besser, schnellere, elegantere Lösungen:
Das hier soll nur eine Anstoß sein, wie man sowas bauen "könnte".

 

[Roin]

Mir ist dazu auch ein Gedanke gekommen, den setze ich aber mal in einen Spoiler:

Mein Gedanke dazu war auch eher ein kleines Gimmick alá Schwierigkeitsstufen. Dein Gedanke im Spoiler gefällt mir allerdings auch sehr gut:

Spoiler

Man kann sich folgende zwei Punkte zu nutze machen, der Spieler hat immer nur bis zu 9 Steine auf dem Brett. Und im zweiten kann man jeweils nur maximal 4 Felder gleichzeitig ansteuern, zumindest in der normalen Zugphase.

Dann wird die Ausgabe allerdings sehr aufgebläht, so wie ich das sehe... Dadurch, dass mein Spielfeld bereits sehr viel Platz einnimmt, wäre das zwar etwas Userfreundlicher aber auch etwas unübersichtlicher vielleicht. Kann man sich später beim "Aufhübschen" Gedanken zu machen.

Lasst nun die "KI" einfach bei jedem Zug das Feld abgleichen und nach Schwierigkeitsgrad (Schwer, Mittel, Leicht) einen Zug aus der Tabelle aussuchen.

Ich denke, dass gehört zu den einfacher, aber sehr wirkungsvollen KI's. Möglich wäre ja auch mehrere KIs zu programmieren. Diese Methode finde ich allerdings, wie du schon gesagt hast, nicht sehr elegant - bei Mühle gibt es zwar nicht so super viele Stellungen aber ich würde die KI auch gerne einfach erweitern und auf andere Spiele anpassen können.

KI-Ideen:

Spoiler

Daher dachte ich eher an sowas wie "Suche Gegnerische Mühlen", "Suche eigene Mühlen", "Suche strategisch gute Punkte" - mach was sinnvolles mit den Infos. Oder wenn es eine ganz dumme KI sein soll einfach "guck alle möglichen Züge an und mache zufällig irgendeinen".

 

[theSplit]

@Seedy

Die Idee wäre zwar so gesehen nicht verkehrt, aber ich glaube die Kunst liegt darin das man nicht eine Datei einließt die versucht alle Möglichen Zugkombinationen abzudecken, sondern das ganze Konzept - wie Roin schreibt, auf gewisse Strategien herunterzubrechen die man als menschlicher Spiele selbst ausführt bzw. wie man reagieren würde. Also einen Algorithmus der sich der Situation anpassen kann, egal wie der Spieler spielt aber auch eigene Ziele verfolgt.

Ich glaube auch nicht das es auf einem Spielfeld immer "den" perfekten Gegenzug gibt, da kommt es auf die Spielweise an und die ist so limitiert wie der, der deine Liste erstellt hat. Das ist natürlich bei einem berechneten Zug nicht anders, aber man ist etwas flexibler und kann zum Beispiel auch Entscheidungen treffen die nicht Konsequent sind, sonder "Taktisch" sein können. Ich glaube was dann einen Schwierigkeitsgrad ausmacht, wäre die Taktik mit der die KI grundsätzlich arbeitet. Das könnte zum Beispiel sein das sie dem Gegner erlaubt eine Mühle zu bilden, um sich selbst Vorteile zu verschaffen die den Spieler nicht direkt aber später im Spielverlauf behindern könnten. Also auch erlaubt zu "riskieren" und den menschlichen Spieler einen "Fehler" in seinem Spiel machen zu lassen der unter Umständen dann bestraft werden könnte.

Mit einer fixen Tabelle die immer nur konsequenz "reagiert" ohne eigene Entscheidung zu treffen oder andere Ziele zu verfolgen, hat man nicht direkt eine Intelligenz geschaffen.

 

[Seedy]

Mit einer fixen Tabelle die immer nur konsequenz "reagiert" ohne eigene Entscheidung zu treffen oder andere Ziele zu verfolgen, hat man nicht direkt eine Intelligenz geschaffen.

Es war ja nur als Anstoß gedacht:
Wohin das ganze führen kann, bzw. sollte:

Spoiler

Ich wollte auf eine KI anhand von Entscheidungsbäumen und Bedingungen hinaus.

Die "Liste" umfasst möglichen Stellungen.
Diese kann man besser Auswerten, als eine "wilkürliche" Stellung.

Wenn du nun Situation+Ziel=Zug Setzt.
Der KI quasi sagst:
Das ist die Ausgangslage!
Da willst du hin!
Gehe nun von Ausgang zu Ziel über das Baumdiagramm.
Wähle dazu wege nach folgenden Kriterien [...]

Man kann für das Ziel eben auch ein "Set" an Stellungen definieren, die in Ordnung sind.
Für die Bedingungen der Entscheidungen kann man auch etwas Fantasy setzen und Peng: langfristige Strategie

Um z.B. eine Mühle zu erkennen, muss das Programm wissen was eine Mühle ist.
Es braucht es IMO eine Referenz.

Da ist es wesentlich einfacher:
"wenn da 3 Steine sind, musst du c6 or b8 or g9

Es ist also schon eine wertige KI, die sich aus dem "Liste + Wahrscheinlichkeit" ableiten lässt.
Die wie gesagt als Anstoss gedacht waren, wie man überhaupt in richtung KI vorgehen kann.

 

[Jester]

Hmm, wenn ich das recht sehe, muss die Summe aller möglichen Züge mit einem Alpha/Beta-System (also Minimal- und Maximalwert, iirc war das was mit Minimax-Prinzip oder so) bewertet werden, wobei die Bewertungs-Prio irgendwo liegen sollte bei:

1. Siegszug durchführen, falls möglich
2. Siegeszug des Gegners verhindern
3. Zwickmühle verhindern
4. Mühle verhindern
5. Zwickmühle schaffen
6. Mühle schaffen
...

... und dann den Zug mit dem höchsten Wert ausführen, wobei ich nicht sicher bin, ob es dabei taktische Fallstricke geben könnte

J.

 

[Roin]

@Jester: Ich denke Mühle schaffen ist wichtiger als Mühle verhindern. Wenn du eine schaffst, kannst du den Gegner ja auch daran hindern eine zu bauen...

 

[Jester]

@Roin: Yup, macht Sinn, ich habe das teilweise zu defensiv zu oberflächlich betrachtet und die nötige Granulierung nicht bedacht. Allerdings sehe ich das als Unterpriorisierung, da das langfristig eher von Erfolg beschieden sein sollte - es kann ja sein, dass ich eine Mühle schaffe, dem Gegner einen Stein nehme, er mich danach aber dennoch blockieren und selbst erfolgreich angreifen kann:

1. Siegszug durchführen, falls möglich
2. Siegeszug des Gegners [im nächsten Zug] verhindern durch
2.1 Zwickmühle
2.2 Mühle
2.3 Sperr-/Blockadezug
3. Zwickmühle [im nächsten Zug] verhindern durch
3.1 Zwickmühle
3.2 Mühle
3.3 Sperr-/Blockadezug
4. Mühle verhindern durch
4.1 Zwickmühle
4.2 Mühle
4.3 Sperr-/Blockadezug
5. Zwickmühle schaffen
6. Mühle schaffen
...


Je länger ich darüber nachdenke, desto mehr glaube ich, dass eine Multi-Pass-Bewertung notwendig wird.
Irgendwie hatte ich mir das leichter vorgestellt ^^

J.

 

[KaPiTN]

Nur am Rande:

Man hat sich in der Informatik schon seit längerem mit dem Mühlespiel auseinandergesetzt und das Spiel gilt als durch den Schweizer Ralph Gasser gelöst. Befolgen beide Spieler eine Strategie und begehen dabei keine Fehler, so endet das Spiel unentschieden.

http://library.msri.org/books/Book29/files/gasser.pdf

Unabhängig von der Informatik gibt es hier noch etwas grundsätzliches zu Strategien bei Mühle:

http://muehlespieler.de/download/so_gewinnt_man_muehle.pdf