Mühle Spiel inklusive KI

[Roin]

Hey Leute,

ich habe wieder von einer neuen Code-Competition gelesen, an der ich vermutlich wieder teilnehme. Diese wird wieder von IT-Talents veranstaltet und es gibt auch wieder etwas zu gewinnen.

Derzeit bin ich mir noch nicht sicher, ob ich überhaupt eine sinnvolle KI geschrieben kriege, aber ich werde einfach mal ein wenig was ausprobieren.

Vielleicht möchte ja noch jemand mitmachen und sich da ein wenig mit auseinandersetzen und sich mit mir austauschen.

Link

Ich denke, ich werde dieses Mal die Competition in Python angehen - bisher habe ich ja bei meinen Teilnahmen ausschließlich Java genutzt.

Viel Spaß Leute!

--- [2016-08-03 13:11 CEST] Automatisch zusammengeführter Beitrag ---

Dann fange ich einfach mal mit der ersten Frage hierzu an:
Ich habe mir überlegt, dass zuerst das Spielfeld aufgebaut werden muss.
Dabei ist mir aufgefallen, dass durch die ungewöhnlichen Verbindungen das etwas schwieriger wird.

Mein Lösungsansatz ist nun das Feld in ein 7x7 Feld aufzuspalten und einige der Felder "nicht setzbar" zu machen und allen anderen Feldern eine kleine Liste mitzugeben, in welche Richtung gezogen werden darf (also wie die Linien verbunden sind).
Das ist leider relativ umständlich aber bisher ist mir noch keine andere Lösung dazu eingefallen.

 

[MingsPing]

Ich mache mit und setze mich heute Abend mal dran!

 

[theSplit]

"Do you hear the call?"

Wohl denn... - es ist keine Challenge wenn ich nicht daran teilnehme...

Fehlt nur nochmal ein Blick auf die Regeln zu werfen wie das Spiel aufgebaut ist... ich hab um ehrlich zu sein die Spielregeln dazu nicht im Kopf und muß bei Null anfangen. Aber das wird Spaß machen!

 

[theSplit]

Dann fange ich einfach mal mit der ersten Frage hierzu an:
Ich habe mir überlegt, dass zuerst das Spielfeld aufgebaut werden muss.
Dabei ist mir aufgefallen, dass durch die ungewöhnlichen Verbindungen das etwas schwieriger wird.

Mein Lösungsansatz ist nun das Feld in ein 7x7 Feld aufzuspalten und einige der Felder "nicht setzbar" zu machen und allen anderen Feldern eine kleine Liste mitzugeben, in welche Richtung gezogen werden darf (also wie die Linien verbunden sind).
Das ist leider relativ umständlich aber bisher ist mir noch keine andere Lösung dazu eingefallen.

Folgende Beobachtungen und ein Tip:
Es gibt 8 Felder in jedem Quadrat, jedes Feld kann bis zu 4 Nachbarn in jede Richtung haben. Egal welches Quadrat wir uns ansehen, der Aufbau ist, von Quadrat zu Quadrat, gleich.

Spoiler

Tip: Zähle mal die Felder durch und beobachte wie es sich mit den Verbindungen verhält. Ergibt sich dabei ein Muster?

Mehr verrate ich jetzt nicht

 

[virtus]

Eigentlich wollte ich dir hier eine mögliche (sinnvolle Lösung) posten, aber das wäre nicht im Sinne des Wettbewerbs: Eine geeignete Datenstruktur für deine Lösung zu finden, ist Teil der Aufgabe.
Auch wenn du im Netz mit Sicherheit einige sinnvolle Ansätze finden wirst.
Vielleicht reicht dir der Tipp, dass du das Feld als Netz von verbundenen Knoten betrachten kannst.

 

[Brother John]

Noch eine Idee zum Spielbrett, ähnlich der von virtus: Ich hab ja ständig mit Graphen zu tun. Und das Mühlebrett ist auch so eine Art Graph. Es gibt Knoten und Kanten zwischen den Knoten. Dass die Knoten physisch traditionell in geschachtelten Quadraten angeordnet sind, spielt fürs Funktionieren der Datenstruktur keine besondere Rolle. Also warum daran festhalten …

 

[MingsPing]

Ich hab es auch als Graph implementiert. Leider ist dann die Überprüfung, ob einer ne Mühle hat, nicht so schön... Bzw. komme ich dabei auf eine eher unelegante Lösung (was übrigens auch das Zeichnen des Brettes betrifft).
Noch hab ich aber nix wirklich vorzeigbares.

 

[Brother John]

Die Kanten sind jedenfalls nicht alle gleich. Da müssen Gewichte, oder vielleicht besser Affinitäten, dran. Meine Vermutung ist, dass das physische Layout zwar für Menschen sehr intuitiv, aber für einen Algorithmus eher lästig ist. Es gibt zu viele verschiedene Arten von Kanten und Kreuzungen. Die auf eine allgemeinere Art abzubilden – natürlich ohne Informationen zu verlieren – könnte nützlich sein. … Kann natürlich auch sein, dass ich komplett daneben liege …

 

[Roin]

Folgende Beobachtungen und ein Tip:
Es gibt 8 Felder in jedem Quadrat, jedes Feld kann bis zu 4 Nachbarn in jede Richtung haben. Egal welches Quadrat wir uns ansehen, der Aufbau ist, von Quadrat zu Quadrat, gleich.

Es gibt Knoten und Kanten zwischen den Knoten. Dass die Knoten physisch traditionell in geschachtelten Quadraten angeordnet sind, spielt fürs Funktionieren der Datenstruktur keine besondere Rolle. Also warum daran festhalten …

Vielleicht reicht dir der Tipp, dass du das Feld als Netz von verbundenen Knoten betrachten kannst.

Ich denke ich werde meine Felder einfach miteinander verlinken und gucken, welches in welcher Richtung liegt Ähnlich wie die Netze, von denen hier bereits gesprochen wurde. Allerdings werde ich das meiste vom Spielfeld hartcoden, genau wie die Überprüfung auf Mühlen.

Zwar ist die Lösung dafür nicht ganz so schön, aber erstmal zweckmäßig - wie man so ein "bescheidenes" Spielfeld sinnvoll generieren soll, ohne da zu viel hardcoded vorzugeben will mir nicht in den Sinn kommen.

Das Spielfeld später darstellen wird auch etwas knifflig - es wird bei mir auf ein Konsolenspiel hinauslaufen. Mit Python irgendwas schön darstellen und dann ggf. noch interaktiv machen kriege ich auf keinen Fall hin - das übersteigt da eindeutig meine Arbeitslust und Zeit für dieses kleine Projekt.

 

[KaPiTN]

Es gibt zu viele verschiedene Arten von Kanten und Kreuzungen.

Ja? Brechen wir das doch mal herunter.

Sagen wir mal, jedes Quadrat wäre eine Ebene und sie lägen übereinander. Das große Quadrat bildet die unterste Ebene.
Spätestens dann sehen wir, daß jeder Knoten Teil von jeweils 2 Mühlen ist. Die Eckknoten von jeweils 2 Mühlen auf der Ebene, die mittleren Knoten jeweils auf einer Ebenen-Mühle und einer Mühle über alle Ebenen.

 

[Brother John]

Guter Punkt. Das heißt dann auch, dass zumindest aus dieser Sicht alle Knoten gleich wichtig sind.

 

[theSplit]

Ich denke ich werde meine Felder einfach miteinander verlinken und gucken, welches in welcher Richtung liegt Ähnlich wie die Netze, von denen hier bereits gesprochen wurde. Allerdings werde ich das meiste vom Spielfeld hartcoden, genau wie die Überprüfung auf Mühlen.

Nun ja, mal meine Erkenntnisse für den Aufbau:
Ungerade Feldnummern sind immer Eckpunkte (1,3,5,7)
Felder die teilbar durch 2 sind, (2, 6) sind vertikal verbundene Felder.
Felder die teilbar durch 4 sind (4, 8) sind horizontal verbundene Felder.

Soweit zu den Regeln zur Bestimmung von Punkten.

Es bleibt auch festzuhalten, alle Gerade Feldnummer haben mindestens 3, in der inneren "Ebene" 4 Zugmöglichkeiten.

Wie ich die Felder intern anordnernen würde, verknüpft auf den oberen Erkenntnissen zu seinen direkten Nachbarn die einmal Zugmöglichkeit wie auch für die Überprüfung auf Mühlen genutzt werden und man in eine "Richtung" wandert.

Nur kann man diese Struktur ja generieren lassen.

Übrigens hab ich mich für Javascript entschieden

 

[virtus]

Noch eine Idee zum Spielbrett, ähnlich der von virtus: Ich hab ja ständig mit Graphen zu tun. Und das Mühlebrett ist auch so eine Art Graph. Es gibt Knoten und Kanten zwischen den Knoten. Dass die Knoten physisch traditionell in geschachtelten Quadraten angeordnet sind, spielt fürs Funktionieren der Datenstruktur keine besondere Rolle. Also warum daran festhalten …

Die Existenz von Kanten muss nur implizit modelliert werden. Relevant sind die Knoten selbst. Natürlich sollte man erfassen, dass es einen Übergang von einem zu einem anderen Knoten gibt und welcher Orientierung der Übergang entspricht:

[src=text]
[A]--------------------[C]
| | |
| ------[J]------[K] |
| | | | |
| | [Q]--[R]-- | |
| | | | | |
[D]-[L]-[T] -[M]-[E]
| | | | | |
| | [V]--[W]--[X] | |
| | | | |
| [N]------[O]------[P] |
| | |
[F]----------[G]----------[H]
[/src]

Dass D-A-B verbunden sind, ist zwar korrekt und dieses Wissen brauchst du, um valide Züge durchführen zu können.
Zur Erkennung einer Mühle musst du allerdings auch noch wissen, wie die Knoten verbunden sind.
Eine Mühle kann immer nur an drei Knoten entstehen, die in gleicher Nachbarschaftsbeziehung liegen. Also A "hat rechten Nachbarn" (B), B "hat rechten Nachbarn" (C) hier kann eine Mühle entstehen. F "hat obigen Nachbarn" (D), D "hat obigen Nachbarn" (A) kann ebenfalls eine Mühle bilden. Aber: D "hat obigen Nachbarn" (A), A "hat rechten Nachbarn" (B) kann keine Mühle darstellen.

Ich hab es auch als Graph implementiert. Leider ist dann die Überprüfung, ob einer ne Mühle hat, nicht so schön... Bzw. komme ich dabei auf eine eher unelegante Lösung (was übrigens auch das Zeichnen des Brettes betrifft).
Noch hab ich aber nix wirklich vorzeigbares.

Ausgehend von einem bestimmten Knoten musst du nur prüfen, ob es einen Nachbarn in eine Richtung gibt und dieser wiederum einen Nachbarn in die gleiche Richtung hat. Zusätzlich musst du natürlich prüfen, ob die Felder alle mit der gleichen Farbe besetzt sind. Da das Feld relativ klein und statisch ist, könntest du sogar alle Nachbarschaftsbeziehungen hard coden. Es ist allerdings auch möglich für ein beliebig geartetes Feld einen Algorithmus zu schreiben, der Mühlen erkennt. Hier kommt die Erklärung weiter oben zum Tragen.

Die Kanten sind jedenfalls nicht alle gleich. Da müssen Gewichte, oder vielleicht besser Affinitäten, dran.

Doch, die Kanten sind alle gleich. Gewichte kannst du höchstens für eine KI implementieren. Der Übergang von A nach B ist genauso teuer, wie der von V nach W. Relevant ist nur, wie viele Übergänge nötig sind, wenn du einen Stein von einem zu einem anderen Knoten führen willst. Zum Beispiel: F-D-A ist teurer, als F-G
Dafür musst du allerdings nicht explizit Kanten und zugehörige Gewichte modellieren. Außerdem ist es natürlich nur relevant, wenn deine KI Abstände zum Berechnen des optimalen Zuges benötigt.

Meine Vermutung ist, dass das physische Layout zwar für Menschen sehr intuitiv, aber für einen Algorithmus eher lästig ist. Es gibt zu viele verschiedene Arten von Kanten und Kreuzungen.

Nicht wirklich. Dem Algorithmus ist die Orientierung egal.
Eine oben-rechts, oben-links, unten-recht, unten-links Kante sollte für deinen Algorithmus egal sein: |_ _| etc
Ich würde aber gar nicht einen Algorithmus schreiben, bei dem du dich um die konkrete Ausrichtung sorgen musst, sondern nur, ob es gleichartige Bewegungsrichtungen/ Verbindungen gibt.

 

[theSplit]

Dann will ich euch mal etwas anstacheln....

Links: Das Spielbrett in der Normalansicht, mit Mühlenanzeige
Rechts: Mit Zugmöglichkeitenanzeige (die Felder die Orange sind, das Orange eingerahmte ist das Feld an der der Cursor sich befindet)

Allerdings alles noch mit Zufallsplazierung der Spielsteine

Und hier noch eine andere Aufstellung:

Und jetzt noch etwas EyeCandy... ich kanns halt nicht lassen... , sind die Farbkombos gut?

 

[MingsPing]

haha, richtig blöd, da habe ich jetzt schon einiges programmiert und nun gesehen, dass man in Lisp gar nicht abgeben darf -.-
Was ist das denn?! :-P

 

[Roin]

@theSplit: Da kann ich nicht mithalten. Hätte ich das in Java geschrieben vielleicht, doch mit Python wird es auf eine reine Konsolenausgabe hinauslaufen.

Das wird noch schön die ganzen Striche da reinzuschreiben und so.
Mache ich allerdings erst in ein oder zwei Wochen. Bin jetzt erstmal wieder beschäftigt.

 

[theSplit]

Roin, das ist ja auch bisher mit Javascript gelöst - wobei man in Python auch was grafisches machen kann.
Pygame oder gar mit Tkinter - ist auch wirklich nicht schwer, einfach mal googlen.

Ansonsten bist du eine Sissi das du jetzt was zu tun hast.

Im Browser mit all den möglichkeiten ist das auch leichter schnell was grafisches auf die Beine zu stellen, da muß man sich nicht mehr um den Code dafür kümmern wie etwas im "UI" angesprochen oder gezeichnet wird, die Basics sind ja schon da.

Von daher mache ich es mir nur leicht(er).

Aber mit Python geht auch vieles, selbst wenn man Frameworks zu Hilfe nimmt, die nehmen einem ja nicht die Logik und Aufbau ab.

@Mingsping:

Haha... das ist wirklich witzig, aber würdest du auf eine der Sprachen umswitchen die man wählen darf? Oder machst du das "Hardcore" in Lisp nun bis zum bitteren Ende, für den Fame? Willst du deinen Source-Code dann hier teilen, falls du bei Lisp bleibst? Natürlich nach Ende des Wettbewerbs, sonst ist es ja keiner mehr.

 

[KaPiTN]

haha, richtig blöd, da habe ich jetzt schon einiges programmiert und nun gesehen, dass man in Lisp gar nicht abgeben darf -.-

Ich 'qoute' das mal nur exemplarisch. Wie kann man denn da schon etwas programmiert haben? Ich habe jetzt noch nicht weiter darüber nachgedacht, außer für einen Antwortpost für Brother John, aber selbst wenn, wäre ich bestimmt noch keine Zeile Code geschrieben.

Ich stelle da mal eine Frage in den Raum. Das muß ja nicht hier sein, sondern wäre mal einen Thread wert, nämlich wie verschieden Leute zu ihren Lösungen kommen.

Ich persönlich mache die Entwicklungsumgebung ja erst recht spät auf und 'code' dann recht zügig, weil ich erst einmal die Teilbereiche definiere und dann Modellierung und Strukturierung durchführe.

Bei "Spaß an der Freude" Projekten ist man ja niemand eine Zeitplanung schuldig, von daher braucht man das da eigentlich nicht, aber viele Sachen bleiben meiner Einschätzung bei Freizeitgeschichten unvollendet, weil die Leute etwas spannend finden und denken, daß schaue ich mir mal an 2 Abenden an und dann merken, was sich da noch an offenen Fragen ergibt.

Ich finde die Frage nach einer Mühle Strategie schon einmal "heftig". Ich mochte das Spiel nie besonders und kann dazu erst mal gar nicht sagen, wie ich spielen würde. Somit kann daraus auch erst mal keine KI werden.

Auch ohne Graphik ist die Ein- und Ausgabe sicher ein Thema. Konsole gilt irgend wie immer Programmierung für Anfänger , aber , aber wie macht man dem Benutzer das Spielfeld per Text begreiflich?
Sicher ein Meilenstein, oder nicht?

Es gibt wohl 2 Phasen im Spiel. Erst das Setzen und dann das Ziehen.

Also grob:

-In und Out
-Datenstruktur
-Regeln Setzen
-Regeln Ziehen
-KI

Dann müßte man sich Gedanken über benötigte Funktionen und evtl. Klassen machen.


Einige hier scheinen auch nicht von vorne herein auf die Sprache festgelegt zu sein.
Gerade dann verstehe ich nicht, warum man sich erst die Sprache aussucht und dann über die Aufgabe nachdenkt.

Antworten auf die Fragestellung der Projektplanung dann bitte hier.

 

[MingsPing]

Klingt etwas überheblich, dein Posting.

 

[Roin]

@KaPiTN: Also ich habe mich beispielsweise auf Python festgelegt, da ich die Sprache mir erst relativ frisch angeeignet habe und ich, da ich keine grafische Ausgabe versuchen werde vermutlich eh nicht gewinnen werde, das eher als Herausforderung zum Lernen ansehe. Ich schaue einfach wie gut ich das Problem mit Python bearbeiten kann - auch ohne mich in Frameworks oder so reinzuarbeiten, wie es theSplit erwähnt hat.