Programmieraufgabe (3): Bao - Das Steinchenspiel

[KaPiTN]

Hallo.

Nach Absprache mit Larius eine neue Herausforderung:





EINLEITUNG:

Bao- Das Steinchenspiel

Spoiler

Beim sogenannten Steinchenspiel hat jeder 2x8 Kuhlen, somit gibt es 4 Reihen. In jeder Kugel liegen zu Beginn 2 Steine. Ein Spieler führt mindestens einen Zug pro Runde aus, je nach Verteilung sind es aber in der Regel mehrere. Bei einem Zug entnimmt man die Steine aus einer Kuhle mit mind. 2 Steinen und verteil sie dann im Uhrzeigersinn auf die nachfolgenden Kuhlen, jeweils mit einem Stein. Ist in der letzten Kuhle abschließend mehr als 1 Stein, zieht man in der gleichen Art wieder, wobei man, wenn eine Kuhle des Gegners angrenzt (also man in seiner eigenen oberen Reihe ist), man auch alle Steine dieser Kuhle entnimmt

(Wer programmieren möchte, sollte diesen Teil zweifelsfrei verstanden haben. Lieber einmal mehr fragen, als späterer Frust oder Ärger)


AUFGABE: Ermittle die Nummer der Kuhle, von der man eine Runde starten muß, um die meisten gegnerischen Steine zu erbeuten
Dafür nummerieren wird unsere eigenen Kuhlen von unten rechts im Uhrzeigersinn (1-16)

DURCHFÜHRUNG:

Um die Ausgangslage der Steine festzulegen, erstelle man eine Textdatei:

2;2;2;2;2;2;2;2
2;2;2;2;2;2;2;2
2;2;2;2;2;2;2;2
2;2;2;2;2;2;2;2

für die Ausgangsstellung.Es sollen aber auch andere Spielstellungen möglich sein. Mit der Textdatei lassen sich die Ergebnisse schnell gegeneinander abgleichen.

ERGEBNIS:

Das Ergebnis ist
a) die Nummer einer Kuhle
b) die Lage der Steine in der Textdatei wie oben.

SPRACHE/Lösung: . Kein GUI nötig. Sprache völlig egal. Gerne Excel Makro

ENDE: 15.06.2016

VERÖFFENTLICHUNG: Offen. Wie waren die Erfahrungen mit GIT?

BEMERKUNGEN: Crashsicherheit wäre schön. Validierung der Eingangsdaten e.g.




Alle Klarheiten beseitigt?






Viel Spaß KaPiTN

 

[BurnerR]

Also immer wenn ich die Steine aus einer meiner vorderen Kuhle nehme, dann auch die Steine vom Gegner aus der angrenzenden Kuhle?
Ich platziere im Uhrzeigersinn. Aber wo fange ich an, beliebig? Und wie verteilt man 'in selbige' im Uhrzeigersinn? Die Mitte zählt man normal nicht zum Uhrzeigersinn dazu.
Wann genau führe ich einen weiteren Zug aus?

 

[KaPiTN]

Also immer wenn ich die Steine aus einer meiner vorderen Kuhle nehme, dann auch die Steine vom Gegner aus der angrenzenden Kuhle?

Nein. Deine Kuhlen sind die vorderen 2 Reihen. Wenn ein Zug in der 2 Reihe endet, d.h. Du hast Deinen letzten Stein in der Hand gesetzt, und in der letzten Kuhle sind jetzt mindestens 2 Steine, dann ist diese Kuhle der Start für den nächsten Zug. Du entnimmst die Steine und die der angrenzenden Kuhle aus der 3. Reihe.

Ich platziere im Uhrzeigersinn. Aber wo fange ich an, beliebig? Und wie verteilt man 'in selbige' im Uhrzeigersinn? Die Mitte zählt man normal nicht zum Uhrzeigersinn dazu.

Deine Kuhlen sind die unteren 2 Reihen

09 10 11 12 13 14 15 16
08 07 06 05 04 03 02 01

Im Uhrzeigersinn bedeutet, Du legt jeweils einen Stein in die nachfolgenden Kuhlen. Also z.B. 07 nach der 06.

Wann genau führe ich einen weiteren Zug aus?

Wenn in der letzten Kuhle nach Legen des letzten Stein mindestens 2 Steine liegen. War die Kuhle leer und es liegt zum Schluß nur 1 Stein darin, ist die Runde für Dich beendet.

 

[theSplit]

Was mir noch nicht so ganz klar ist:

Wenn einem die unteren 2 Reihen gehören:
09 10 11 12 13 14 15 16
08 07 06 05 04 03 02 01

Und ich von 13 anfangen würde zu legen, also aus meiner 13 und dann aus den Feldern des Mitspielers 04 03 (die darüber angrenzen) dann wieder meine 14?
Und 14 wäre dann das Startfeld für den nächsten Zug weil dort als letztes gelegt worden ist. Ist das so korrekt oder habe ich das falsch verstanden?

Oder bezieht sich wirklich alles ausschließlich auf meine 2 Reihen?

Ist mir noch unklar.

PS: Kannst du vielleicht mal ein Beispiel zeigen wie ein oder zwei korrekte Züge aussehen?
Im Grunde ist mir das schon klar, aber auch wie es sich mit den oberen Reihen verhällt. Wäre gut

 

[Brother John]

Ja, irgendwas hab ich auch noch nicht ganz verstanden. Wenn ichs mir aus der Grundstellung mit überall 2 Steinen durchüberlege, endet die Runde für den ersten Spieler nie. Das kann ja nicht sein.

Wenn ich z.B. ganz naiv auf der 01 anfange. Dann nehme ich 2 Steine dort raus und lege einen in die 01 und einen in die 02. In der 02 sind jetzt 3 Steine. Also nehme ich die und lege je einen in die 02, 03 und 04. Jetzt sind in der 04 3 Steine … usw … Problem. So entsteht niemals irgendwo ein leeres Feld und ich kann niemals in die Situation kommen, dass mein Zug auf einem Feld mit nur 1 Stein endet. Also endet meine Runde nie.

Wo hab ich jetzt den Fehler drin?

 

[KaPiTN]

Der Fehler liegt bei mir. Mea maxima culpa . Asche über mein Haupt. Wenn man die Steine Anfassen kann ist das sofort klar.

Wir haben das Spiel gerade ausgepackt und ich mußte mich daran erinnern lassen, daß die Entnahmekuhle leer bleibt.


Ich überlege mal, ob man das visualisieren kann.

 

[KaPiTN]

Ich bitte nochmal um Entschuldigung. Ich habe jetzt mal 2 Beispiele gebaut:

http://webmshare.com/play/eRq7Y

http://webmshare.com/play/74g5B

EDIT:
theSplit hat sich mal die Mühe gemacht, die Einzelschritte des ersten Videos aufzuschreiben.
Danke dafür

Spoiler

In dem ersten Video sieht es so aus als ob das dritte Feld aus der zweiten Reihe von rechts leer bleibt, ich glaube das ist auch wichtig nachzuvollziehen:

So das sich folgendes Szenario ergibt:

-------------------


Anzahl der Spielsteine und x = Startfeld/Kuhle des Zuges (nur die eigenen 2 Reihen!)

2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2x
=>
2 2 2 2 2 2 2 2
2 2 2 2 2 3x 3 0 (Zug 1 Ende)

2 2 2 2 2 2 2 2
2 2 3 3 3 3x 3 0 (Zug 2)

2 2 2 2 2 2 2 2
2 2 3x 3 3 0 3 0 (Zug 2 Ende)

2 2 2 2 2 2 2 2
2 2 3x 3 3 0 3 0 (Zug 3)

3x 2 2 2 2 2 2 2
3 3 0 3 3 0 3 0 (Zug 3 Ende)

Da Zug 3 in einem oberen Feld endet, darf man jetzt die Spielsteine aus der Kuhle oberhalb, des Mitspielers, im nächsten Zug auf seine Felder, zu denen 3en aus seiner Kuhle, verteilen und mit diesen seine Felder befüllen. ( Zug 4)

Zug 4, mit gesamten Brett:

2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
--------------------
3x 2 2 2 2 2 2 2 <- Zug startet oberhalb, alle Steine aus der Kuhle des Mitspielers entnehmen und aus seiner Kuhle alle =5 (2 Mitspieler + 3 eigene)
3 3 0 3 3 0 3 0

2 2 2 2 2 2 2 2
0 2 2 2 2 2 2 2
--------------------
0 3 3 3 3 3x 2 2 (Zug 4 Ende)
3 3 0 3 3 0 3 0

Zug 5:
2 2 2 2 2 2 2 2
0 2 2 2 2 2 2 2
--------------------
0 3 3 3 3 3x 3 3 (Zug 5 Start) (wieder die 3 aus der eigenen Kuhle, dann die Steine (2) aus der Kuhle oberhalb des Mitspielers entnehmen
3 3 0 3 3 0 3 0

2 2 2 2 2 2 2 2
0 2 2 2 2 0 2 2
--------------------
0 3 3 3 3 0 3 3 (Zug 5 Ende)
3 3 0 3 3 1x 4 1

Da Zug 5 mit einem Spielstein in der Kuhle endet, ist nun der andere Spieler dran.

 

[exomo]

Also die Spielregeln für einen Zug habe ich jetzt glaube ich verstanden. Danke für die Videos.
Aber der Vollständigkeit halber:
- Wie endet das Spiel? Intuitiv würde ich sagen, dass man verloren hat, wenn man keine Kuhle mit 2 Steinen mehr hat, weil man dann nicht mehr ziehen kann. Gibt es noch andere Bedingungen?

Was mir nicht ganz klar ist:
- Was soll das Program ausgeben, wenn kein Zug möglich ist?
- Woher weiß ich, ob ich eine optimale Lösung habe? Also ich schreibe ein Programm, dass mir für eine bestimmte Spielsituation sagt "Nimm Feld 5", aber wie kann ich prüfen ob das stimmt? Hast du Beispiele mit Spielfeld und erwarteter Lösung, mit denen man sein Programm testen kann?

Thema Veröffentlichung:
Ich bin großer Fan von Git und würde es auch wieder nutzen. Ich hatte aber beim letzen Mal das Gefühl dass nicht viele das nutzen wollten. Ich würde vorschlagen das offen zu machen, wer mitmachen will soll das halt hochladen wo er will und hier einen Link posten.

Weiterer Vorschlag:
Die Aufgabe für einen Zug scheint mir recht einfach zu sein. Wenn jemand Interesse hat könnte man sich auch überlegen die Programm gegeneinander antreten zu lassen. Dann wäre es nicht nur wichtig die meisten Steine zu erbeuten, sondern auch mehrere Runden im Voraus zu planen was der Gegnen tun könnte. Da ich das Spiel bisher nicht kenne weiß ich nicht ob das überhaupt machbar ist, oder ob die Komplexität so hoch ist dass man den AlphaGo Rechner braucht

 

[KaPiTN]

@exomo:

Richtig. Ist kein Zug mehr möglich hat man verloren. Ebenso wenn der Gegner Deine obere Reihe geleert hat (9-16)

Die Möglichkeit, daß man eine Ausgangslage eingibt, wo keine Kuhle mehr als einen Stein hat, ergibt eigentlich keinen Sinn. Aber für den Fall, würde ich eine 0 als Ergebnis und eine unveränderte Datei erwarten.

Da ich mir die Aufgabe selber ausgedacht habe, habe ich da noch keine Lösungen. Aber da die Ausgabe eine Zahl und eine CSV ist, werden wir das hier im Thread gegeneinander prüfen können.

Deployment: Auf keinen Fall sollte jemand von der Teilnahme abgehalten werden, weil er sich nicht in eine unbekannte Technik einarbeiten möchte.

Tatsächlich hatte ich letztes Jahr an dieses Spiel gedacht, als der Wettbewerbsgedanke noch im Vordergrund stand. Als Projekt habe ich immer noch die Idee, DLLs mit verschieden Strategieren gegeneinander antreten zu lassen.
Für das ngb habe ich den Gedanken aber verworfen, weil weder OS noch Sprache vorgeschrieben sind und ich da keine (einfache )Möglichkeit sehe.

Spoiler

Bei einem Zug möglichst viele gegnerischen Steine zu erbeuten, muß auch nicht der beste Zug für einen Sieg sein.

Ich denke, der Schwierigkeitsgrad ist hoch genug, um nicht langweilig zu sein, aber auf der anderen Seite nicht zu aufwendig, daß ein Großteil die Zusage zur Teilnahme wieder zurücknehmen muß.

Aber wir sind uns einig, daß da noch mehr Potential drinsteckt.

@ALL
Zusätzlich zu meinem ersten Video hat theSplit noch eine Einzelschrittanalyse erstellt, die ich in obigen Beitrag rein editiert habe

 

[theSplit]

Ich frage mich gerade, wie kann man bei dieser Aufgabe das Optimum ermitteln, wenn der Zug des Gegners nicht geplant ist?

Egal welche Strategie ich spiele, ohne das ich vorher weiß welche Züge der Gegner macht, kann ich kein optimalen Wert ermitteln? Kann das sein?

Schließlich müsste ich jeden "möglichen" Zug und Folgezüge des Nachbarn ermitteln, bevor ich meinen nächsten Zug auswählen könnte, und wenn dann auch nur den für mich bequemsten Weg wo ich die meisten Vorteile davontragen würde!

Oder habe ich gerade einen Denkfehler?

 

[Brother John]

Woher weiß ich, ob ich eine optimale Lösung habe?

Ich denke, ich habe einen Algorithmus, der garantiert die richtige Lösung liefert … weil Bruteforce. Den werde ich auch im Lauf der Woche implementieren. Dann können wir uns überlegen, ob er als Referenzalgo taugt.

Ich bin großer Fan von Git und würde es auch wieder nutzen.

Dann sind wir schon zu zweit. Bin zwar kein Mega-Git-Freund (die GUIs sind im Vergleich zur TortoiseHg-Workbench alle Rotz), aber der GitHub-Account muss mal ein bisschen Content kriegen.

Zwang macht denke ich keinen Sinn. Wäre schade, wenn jemand nur wegen der Versionskontrolle vom Mitmachen abgehalten würde. Sofern keiner was dagegen hat, könnten wir ja zum Schluss alle Beiträge auf dem ngb-Gitlab-Account mirrorn oder zumindest von dort verlinken.

Wenn jemand Interesse hat könnte man sich auch überlegen die Programm gegeneinander antreten zu lassen.

Es muss eh jeder das Ergebnis als CSV ausgeben. Wenn alle Programme ohne Userinteraktion ablaufen können, könnte man automatisch die Ausgabe vom ersten als Quelle an den nächsten verfüttern. Das ist in Python ratz-fatz hingeklöppelt.

 

[KaPiTN]

Egal welche Strategie ich spiele, ohne das ich vorher weiß welche Züge der Gegner macht, kann ich kein optimalen Wert ermitteln? Kann das sein?

Denk nicht zu weit. Momentan geht es immer nur um eine beliebige Ausganssituation
einer Runde, und dann darum, welcher von maximal 16 möglichen Zügen den meisten Gewinn bringt

Ich denke, ich habe einen Algorithmus, der garantiert die richtige Lösung liefert … weil Bruteforce.

[..]

Es muss eh jeder das Ergebnis als CSV ausgeben. Wenn alle Programme ohne Userinteraktion ablaufen können, könnte man automatisch die Ausgabe vom ersten als Quelle an den nächsten verfüttern. Das ist in Python ratz-fatz hingeklöppelt.

Bruteforce finde ich ein hartes Wort.
Aber ja, hier geht ein um Ausprobieren von max 16 Runden

Die Kommunikation über csv hatte ich auch überlegt, daher stammt eigentlich die Idee mit csv als Eingabe. Aber wie willst Du das jeweils triggern? Wenn das automatisiert laufen soll, müßte man ja zu mindestens das OS festlegen, wo der battle abläuft.

Netzwerk wäre zwar eine Möglichkeit, aber eindeutig overkill.

 

[exomo]

OS sollte für die meisten Programmiersprachen kein Problem sein. Es gibt für die meisten doch Interpreter/Compiler/Laufzeit für Windows/Linux/Mac. Das Problem sollte überschaubar genug sein, dass man auch ohne irgendwelche systemabhängigen Bibliotheken klarkommt. Lediglich ganz exotische Lösungen wie LabView oder Excel wären vielleicht problematisch, aber wenn nicht noch jemand was ausgräbt was nur auf Mac läuft, dann sollte auf einem Windows so gut wie alles gehen.


Aber vielleicht sollten wir erstmal bei der ursprünglichen Aufgabe bleiben, und sehen wer überhaupt interesse hat. Ich werde wenn ich dazu komme diese Woche mal eine Version implementieren, und dann weitersehen. Für einen richtigen KI-Wettbewerb fehlt ja dann doch wieder die Zeit.

 

[KaPiTN]

Aber vielleicht sollten wir erstmal bei der ursprünglichen Aufgabe bleiben, und sehen wer überhaupt interesse hat. Ich werde wenn ich dazu komme diese Woche mal eine Version implementieren, und dann weitersehen. Für einen richtigen KI-Wettbewerb fehlt ja dann doch wieder die Zeit.

so schaut's aus. Dann haben wir nächstes WE vielleicht bereits 3 Lösungen.
Interessant schien mir diesmal, bei einer überschaubaren Aufgabe, die unterschiedlichen Ansätze.
Ich bin gewohnt mit C# dabei, bei Brother John würde ich auf Python tippen. Was ist Deine Wahl?

Ich hoffe ja, das jemand mit einer Scriptsrache kommt, pur und ohne Klassen

 

[werner]

Imgrunde soll das Programm den Spielaufbau hernehmen, und mir sagen, welches Feld für den ersten Zug am meisten Steine einbringt?

 

[Brother John]

Wenns mit den OSen hart auf hart kommt, kann man notfalls mit einer gemeinsamen Datei auf einem Netzlaufwerk und Polling ne ganze Menge erschlagen. Aber warten wirs erstmal ab.

Bei mir wirds tatsächlich Python. Ich hatte kurz C++ überlegt, aber Python hat halt CSV-Unterstützung direkt an Bord. Man kommt damit einfach rasend schnell zu ersten Ergebnissen.

@werner
Im Prinzip ja. Wobei es nicht unbedingt die erste Runde im ganzen Spiel sein muss, sondern eine beliebige Ausgangslage.

 

[exomo]

Bei mir wird es C++, ich versuche standardkonformen Code zu schreiben, dann sollte das System keine Rolle spielen so lange es dafür einen aktuellen Compiler gibt.

 

[Roin]

Ich denke ich setzte dieses Mal aus.
Irgendwie verstehe ich die Regeln noch nicht wirklich...
Habe aber derzeit sowieso mit dem Studium zu kämpfen.

 

[KaPiTN]

@Roin:

Das ist schade, denn das ganze ist, wenn man die Regeln verstanden hat, keine große Sache. Ich habe gestern Abend so neben ngb und Fernsehen angefangen und heute abend die Fehler korrigiert. Das ganze hat jetzt nur länger gedauert, weil man Fehler schwer findet, wenn der Debugger bei der Parameterübergabe die Werte richtig sortiert anzeigt, die aber so in der aufgerufenen Funktion nicht so ankommen. Egal. Visual Studio halt.

@ALL Das Ergebnis ist jetzt allerdings nicht das, was ich erwartet habe. Ich hatte zwar befürchtet, daß das mal nicht ganz eindeutig sein könnte, aber nicht in dem Ausmaß.
Aber hätte ich das Ergebnis gekannt, hätte ich nicht programmieren müssen.
Jedenfalls ist das Ergebnis nicht als Zahl von 1.16 und der Belegung der 32 Felder in der txt darzustellen. Ich habe das ganze bei mir jetzt so ausgeben lassen:

Spoiler

Kuhle Nr.: 1 Profit: 4 Steine
2;2;2;2;2;2;2;2
0;2;2;2;2;0;2;2;
0;3;3;3;3;0;3;3;
3;3;0;3;3;1;4;1;

Kuhle Nr.: 2 Profit: 4 Steine
2;2;2;2;2;2;2;2
2;0;2;2;2;2;0;2;
3;0;3;3;3;3;0;3;
3;0;3;3;1;4;1;3;

Kuhle Nr.: 3 Profit: 4 Steine
2;2;2;2;2;2;2;2
2;2;0;2;2;2;2;0;
3;3;0;3;3;3;3;0;
0;3;3;1;4;1;3;3;

Kuhle Nr.: 4 Profit: 4 Steine
2;2;2;2;2;2;2;2
0;2;2;2;2;0;2;2;
0;3;3;3;3;0;3;3;
3;3;1;4;1;0;3;3;

Kuhle Nr.: 5 Profit: 4 Steine
2;2;2;2;2;2;2;2
2;0;2;2;2;2;0;2;
3;0;3;3;3;3;0;3;
3;1;4;1;0;3;3;3;

Kuhle Nr.: 6 Profit: 4 Steine
2;2;2;2;2;2;2;2
2;2;0;2;2;2;2;0;
3;3;0;3;3;3;3;0;
1;4;1;0;3;3;3;3;

Kuhle Nr.: 7 Profit: 4 Steine
2;2;2;2;2;2;2;2
0;2;2;2;2;0;2;2;
1;3;3;3;3;0;3;3;
4;1;0;3;3;0;3;3;

Kuhle Nr.: 8 Profit: 4 Steine
2;2;2;2;2;2;2;2
2;0;2;2;2;2;0;2;
4;1;3;3;3;3;0;3;
1;0;3;3;0;3;3;3;

Kuhle Nr.: 9 Profit: 4 Steine
2;2;2;2;2;2;2;2
2;2;0;2;2;2;2;0;
1;4;1;3;3;3;3;0;
0;3;3;0;3;3;3;3;

Kuhle Nr.: 10 Profit: 2 Steine
2;2;2;2;2;2;2;2
2;2;2;0;2;2;2;2;
3;1;3;0;3;3;3;3;
3;0;3;3;0;3;3;0;

Kuhle Nr.: 11 Profit: 2 Steine
2;2;2;2;2;2;2;2
2;2;2;2;0;2;2;2;
3;3;1;3;0;3;3;3;
0;3;3;0;3;3;0;3;

Kuhle Nr.: 12 Profit: 4 Steine
2;2;2;2;2;2;2;2
0;2;2;2;2;0;2;2;
0;3;3;1;4;1;3;3;
3;3;0;3;3;0;3;3;

Kuhle Nr.: 13 Profit: 4 Steine
2;2;2;2;2;2;2;2
2;0;2;2;2;2;0;2;
3;0;3;3;1;4;1;3;
3;0;3;3;0;3;3;3;

Kuhle Nr.: 14 Profit: 4 Steine
2;2;2;2;2;2;2;2
2;2;0;2;2;2;2;0;
3;3;0;3;3;1;4;1;
0;3;3;0;3;3;3;3;

Kuhle Nr.: 15 Profit: 2 Steine
2;2;2;2;2;2;2;2
2;0;2;2;2;2;2;2;
3;0;3;3;3;3;1;3;
3;0;3;3;0;3;3;0;

Kuhle Nr.: 16 Profit: 2 Steine
2;2;2;2;2;2;2;2
2;2;0;2;2;2;2;2;
3;3;0;3;3;3;3;1;
0;3;3;0;3;3;0;3;

 

[theSplit]

Das würde ich kürzen, auf 4 Zeilen pro Ergebnis, ist wenig Boilerplate den man rausfiltern muß, um etwas auszuwerten bzw. das Ergebnis zu sehen.

@Roin,

die Frist der Abgabe ist doch lange lange lange lange hin, was verstehst du nicht? Vielleicht kann man dir das erklären?