Programmieraufgabe (3): Bao - Das Steinchenspiel

[drfuture]

"Qualität des Zufalls" cooles Wort
Aber warum ist "neu durchwürfeln" schlecht? Ist es nicht besser so oft wie möglich zu würfeln?

 

[Brother John]

Ich bin kein Zufallsexperte, deswegen: Vorsicht, gesundes Halbwissen voraus.

Der Zufallsgenerator macht das Würfeln selbst. Wenn du ständig seedest, versuchst du, ihm seinen Job abzunehmen.

Ein Computer is ein deterministisches Biest. Deswegen gibt es nur Pseudozufall, also etwas, das wie Zufall aussieht und sich so anfühlt, aber kein echter Zufall ist. Der Generator ist dafür ausgelegt, dir gegeben einen Startpunkt – den Seed – eine Sequenz von Zahlen zu liefern, die zufällig genug aussehen, dass sie als echter Zufall durchgehen.

Wenn du den Generator zweimal mit demselben Seed laufen lässt, kriegst du zweimal die identische Zahlensequenz. Deswegen brauchts das Seed. Aber halt nur einmal. Wenn du ständig seedest kriegst du nicht jeweils die nächste Zahl aus ein und derselben Zufallssequenz, sondern die jeweils erste Zahl aus vielen Sequenzen mit minimal unterschiedlichem Seed. Und das kann irgendwas sein. Es gibt dir niemand eine Garantie dafür, wie qualitativ zufällig diese Sequenz ist.

 

[theSplit]

Vielen Dank für den Hinweis mit dem Seed, macht ja irgendwo auch Sinn und irgendwo auch nicht - aber es klingt soweit nachvollziehbar - ich hab mir mal erlaubt ein Paket mit den neuen Versionen zu schnüren - die auch nicht mehr die alten Fehler enthalten (im Anhang).
Enthalten sind Source, 32bit und 64bit Windows Version, 64bit Linux Executable.

Über die Zufallsverteilung bin ich aber ehrlich gesagt immer noch nicht ganz so glücklich, aber ich hab nun gut 45 Minuten versucht etwas mit der Feldposition zu machen, aber so ganz hab ich das nicht hinbekommen. Zwischendrin hatte ich mal eine halbwegs funktionieren Rechnung aber auch dort blieben dann immer die letzten Felder eines jeden Spielers frei. Also auch nicht ganz perfekt.. daher müßt ihr euch bei diesen Versionen leider darauf einstellen das manch ein Feld etwas "überfrachtet" sein kann oder das letzte Feld von Spieler 1 (Vorteil für Spieler Unten) oft sehr viele Steine tragen kann die "übrig" sind.

Eine Idee für eine Erweiterung des Generators - man lässt per Zufall wie aktuell die Felder befüllen, hat ein Feld mehr als 1/8 aller Steine, wird es halbiert und per Zufall auf die anderen verteilt.
ODER
man schreib die Version so um das jeweils aus 16 Feldern ein Feld einen Stein bekommt, bis alle Steine aufgebraucht sind - und macht dann eine Überprüfung um zu hohe Spitzen auszugleichen.

So als Idee.

 

[Brother John]

Dein ODER gefällt mir ziemlich gut. Sehr simpel zu implementieren, weil du nie irgendwas übrig haben kannst. Einfach Stein für Stein zufällig verteilen, bis keine mehr da sind. Ich würde das aber fürs komplette Spielfeld machen; weil mir gerade auffällt, das aktuell Spieler und Gegner immer exakt gleichviele Steine bekommen. Jetzt generieren wir zwar keine garantiert plausiblen Spielzustände, aber genau genommen ist das eine Einschränkung, die nicht sein müsste. Die Implementierung ist die gleiche, egal ob das Spielfeld getrennt ist oder nicht. Also warum den zusätzlichen Nachteil in Kauf nehmen?

Noch ne ganz andere Idee: Warum Zufall? Warum nicht das Spiel spielen? Z.B. fängt man mit dem Start-Board an und dann spielt man einfach immer mit einer zufälligen Startkuhle. Zwischenstände merken und falls es zufällig aussehen soll, die zum Schluss nochmal durchmischen.

 

[theSplit]

Danke für das Lob, jenes wäre glaube ich, auch einfacher umzusetzen. Sagt aber nicht wirklich aus das die Verteilung dadurch besser werden würde - eben weil man nicht sagt es müssen zum Beispiel 35% in der oberen Reihe sein und 65% in der unteren oder ähnliches, damit das Spiel spielbar bleibt. Als kleiner Einwand.

Zu deiner Idee - jein, das Problem wäre, man würde nur so viele Variationen haben, wie es Spielstände gibt, wenn wir von einer Zugreihe für den ersten Spieler ausgehen.

Wenn du natürlich gleich nen BaoComp(uter).exe haben willst, vermutlich wäre auch das machbar. Wenn wir von 2 Spielsteinen je Kuhle beginnen würden. Aber das wäre sehr limitiert, 16 Zugvarianten je Spieler in jedem moment, man könnte aber Bao (auf der Basis mit 2 Steinen) trainieren damit... ja. Aber ich find da die Zufallsverteilung schon anspruchsvoller.
Auf Wikipedia ist das Spiel übrigens als Bao (Mancala-Spiel) unter https://de.wikipedia.org/wiki/Bao_(Mancala-Spiel) noch etwas anders als hier beschrieben.

Aber erstmal war der Generator ja nur dazu da um überhaupt eine Variation an Input zu liefern, mit dem jeder seinen Algo testen kann.

 

[theSplit]

Guten Morgen,

da ich etwas Zeit habe, habe ich nun baoGen2 rausgebracht, im Grunde ist diese Version genau die angesprochene "ODER" Variante. Bei dieser werden die Felder zufällig mit einem Spielstein belegt, bis die Spielsteine aufgebraucht sind.

Im Gegensatz zur Vorgängerversion sollte die Verteilung daher "besser" sein.
Die Ausgabedaten sind einmal in der Konsole und werden parallel dazu in eine "playboard.csv" geschrieben.

Sourcecode ist hier im Post und auch wieder im Paket mit den Builds für Windows, natürlich habe ich auch wieder ein Linux Abbild mit eingebaut.

Dateiinhalte von "baoGen2.zip" (als Anhang beigefügt)
baogen2 (Linux Variante, sollte nur auf 64 bit laufen)
baogen232.exe (Windows 32 bit Build)
baogen264.exe (Windows 64 bit Build)
baoGen2.c (Source wie hier im Beitrag)

Viel Spaß damit und Feedback ist natürlich gern gesehen!

Hier nun die Source:
[src=c]#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <string.h>

int main(int argc, char *argv[]) {

int startPieces = 32;
int fields = 16;
int playboardsToCreate = 10;

// Command parsing
if (argc > 1) {
for (int i = 1; i < argc; ++i) {
char *data[255];
if (argv[0] == 'p') {
startPieces = strtol(argv+1, data, 10);
} else if (argv[0] == 'b') {
playboardsToCreate = strtol(argv+1, data, 10);
} else if (argv[0] == 'f') {
fields = strtol(argv+1, data, 10);
} else {
printf("[ERROR] Unknown command: '%s'\nUse the switches 'p', 'b' or 'f' in combinations.\n\nLike\n'p12': 12 Game pieces\n'b10': 10 Playboards\n'f16': 16 fields.\n\n", argv);
return 1;
}
}
}

// Error messages
if (fields % 2 != 0) {
printf("[ERROR] Fields dont align by 2.\n");
return 1;
} else if (fields < 4) {
printf("[ERROR] Cant create playboards with less than 4 fields.\n");
return 1;
} else if (fields > 32) {
printf("[ERROR] Dont want to create playboards with more than 32 fields. Buy the full edition to continue!\n");
return 1;
}

if (startPieces < 4) {
printf("[ERROR] Need at least 4 gaming pieces to operate\n");
return 1;
} else if (startPieces > fields * 3) {
printf("[ERROR] Too many gaming pieces, cannot be more than 3 times the fields.\n");
return 1;
}

if (playboardsToCreate < 0) {
printf("[ERROR] Need at one playboard to generate, canceling.\n");
return 1;
} else if (playboardsToCreate > 100) {
printf("[ERROR] Too many playboards, in shareware, I generate only 100 a time! We are sorry.\n");
return 1;
}

// Generate the playboards
FILE *playboardStore = fopen("playboard.csv", "w");
if (playboardStore == NULL) {
printf("[ERROR] Cannot open 'playboard.csv' for writing playboard data.\n");
return 1;
}

// Init after errors
int generatedPlayboards = 0;
char data[64];

int rows = fields / 2;
int playboard[2][fields];
int pieces[2];

srand(time(NULL) + clock());

// Playboard setup, filling and output
while (playboardsToCreate--) {
generatedPlayboards++;

// Generate the playboard
printf("\nPlayboard #%d\n\n", generatedPlayboards);

for (int player = 0; player < 2; ++player) {
memset(playboard[player], 0, sizeof(int) * fields);
pieces[player] = startPieces;

for (int j = 0; j < startPieces; j++) {
int field = rand() % fields;
++playboard[player][field];
--pieces[player];
}

for (int i = 1, j = 0; j < fields; ++j) {
if ((j+1) < (i*rows)) {
printf("%d;", playboard[player][j]);
sprintf(data, "%d;", playboard[player][j]);
fputs(data, playboardStore);
} else {
printf("%d", playboard[player][j]);
sprintf(data, "%d", playboard[player][j]);
fputs(data, playboardStore);

printf("\n");
fputc('\n', playboardStore);
++i;
}
}

printf("Pieces left: %d left of %d\n\n", pieces[player], startPieces);
}

fputc('\n', playboardStore);
}

fclose(playboardStore);
}[/src]

 

[KaPiTN]

In #19 hatte ich ja mein Ergebnis gepostet. Aber gar keinen Code. Bevor ich das vergesse, schreib ich das mal eben hier rein.

Ich sehe, ich habe keine Validierung gemacht. Das wäre dann 2Do.

Die eigentliche Funktion zum Probieren der Möglichkeiten ist eigentlich recht klein.

Spoiler

[src=csharp] private void TryAllPossibleMoves()
{
for (int i = 0; i < 16; i++)
{
FillHoles();
int x = i;
int stones;
int benefit = 0;
bool firstMove = true;

while ((stones = _holes[x].Stones) >= 2)
{
_holes[x].Stones = 0;
if (!firstMove)
{
stones = stones + _holes[x].OpponendStones;
benefit = benefit + _holes[x].OpponendStones;
_holes[x].OpponendStones = 0;
}
else
{
firstMove = false;
}

for (int ii = 0; ii < stones; ii++)
{
x = (++x%16);
_holes[x].Stones++;
}
}
_result = new Tuple<int, int, List<Hole>>(i + 1, benefit, _holes.OrderBy(r => r.Id).ToList());
_results.Add(_result);
}
}[/src]

Das schreiben der Ergebnisdatei ist eigentlich da größte, weil ich alle Ergebnisse ausgeben, absteigend sortiert nach erbeuteten Steinen. Das ganze sieht dann so aus:

Spoiler

[src=csharp]using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Bao
{
internal class Bao
{
private string[] _lines;
private List<Hole> _holes = new List<Hole>();
private readonly List<Tuple<int, int, List<Hole>>> _results = new List<Tuple<int, int, List<Hole>>>();
private Tuple<int, int, List<Hole>> _result;

internal int FindBestStart()
{
ReadFile();
TryAllPossibleMoves();
WriteFile();
return 0;
//return (from result in _results
// where result.Item2==_results.Max(r => r.Item2)
// select result.Item1).First();
}
private void ReadFile()
{
_lines = File.ReadAllLines("bao.txt");
}
private void TryAllPossibleMoves()
{
for (int i = 0; i < 16; i++)
{
FillHoles();
int x = i;
int stones;
int benefit = 0;
bool firstMove = true;

while ((stones = _holes[x].Stones) >= 2)
{
_holes[x].Stones = 0;
if (!firstMove)
{
stones = stones + _holes[x].OpponendStones;
benefit = benefit + _holes[x].OpponendStones;
_holes[x].OpponendStones = 0;
}
else
{
firstMove = false;
}

for (int ii = 0; ii < stones; ii++)
{
x = (++x%16);
_holes[x].Stones++;
}
}
_result = new Tuple<int, int, List<Hole>>(i + 1, benefit, _holes.OrderBy(r => r.Id).ToList());
_results.Add(_result);
}
}

private void FillHoles()
{
var line2 = _lines[1].Split(';');
var line3 = _lines[2].Split(';');
var line4 = _lines[3].Split(';');
var x = 0;

_holes.Clear();
for (int i = 9; i <= 16; i++)
{
_holes.Add(new Hole(i, Int32.Parse(line3[x]), Int32.Parse(line2[x])));
x++;
}
x = 0;
for (int i = 8; i >= 1; i--)
{
_holes.Add(new Hole(i, Int32.Parse(line4[x]), 0));
x++;
}
_holes = _holes.OrderBy(y => y.Id).ToList();
}

private void WriteFile()
{
File.WriteAllText("bao.txt", String.Empty);
File.AppendAllText("bao.txt",
Environment.NewLine);
string line1 = string.Empty;
foreach (var result in _results.OrderByDescending(x => x.Item2))
{
line1 += "Kuhle Nr.: " + result.Item1 + " Profit: " + result.Item2 + " Steine";
line1 += Environment.NewLine;
line1 += _lines[0];
line1 += Environment.NewLine;

for (int i = 8; i < 16; i++)
{
line1 += result.Item3.OpponendStones + ";";
}
line1.Remove(line1.Count() - 1);
line1 += Environment.NewLine;
for (int i = 8; i < 16; i++)
{
line1 += result.Item3.Stones + ";";
}
line1.Remove(line1.Count() - 1);
line1 += Environment.NewLine;
for (int i = 7; i > -1; i--)
{
line1 += result.Item3.Stones + ";";
}
line1.Remove(line1.Count() - 1);
line1 += Environment.NewLine;
line1 += Environment.NewLine;
}
File.AppendAllText("bao.txt", line1);
}
}

internal class Hole
{
public int Id { get; private set; }
public int Stones { get; set; }
public int OpponendStones { get; set; }

public Hole(int id, int stones, int opponendStones)
{
Id = id;
Stones = stones;
OpponendStones = opponendStones;
}
}
}[/src]

 

[CroneKorkN]

Oh wie toll, ein Bastelaufgabe! Ich werde mich der mal in Ruby widmen.

Es wäre wirklich eine coole Zusatzaufgabe einen vorausschauenden Algorithmus zu implementieren und die Algorithmen gegeneinander antreten zu lassen. Man bräuchte nur ein Protokoll für den Aufruf der jeweiligen Implementierungen:

"programmname --spielfeld="4;8;2;1;7;3;8;3;0;3;9;5;3;2;5;7;90;6;4;3;3;67;8;6;4;3;67;5;3;3;4;3" -> Gibt Feldnummer des vom Algorithmus gewählten Zuges zurück.

Dann schreibt man ein Boa-Programm, welches mit unseren Implementierungen als Plugin arbeitet.

edit:
Nachdem ich das Spiel jetzt verstanden habe ist mir aber schleierhaft, wie man in Bao strategisch vorgeht. Also ob es noch andere Kriterien für die Qualität eines Zuges gibt, abgesehen von der Anzahl der abgesahnten Züge. Vlt die Anzahl der für einen Zug nutzbaren Felder? Je gleichmäßiger meine Steine verteilt sind, umso eher habe ich die Chance nach dem Zug auf einem Feld zu landen, in dem mindestens zwei Steine liegen. Ist das ein Ansatz?

 

[KaPiTN]

Je gleichmäßiger meine Steine verteilt sind, umso eher habe ich die Chance nach dem Zug auf einem Feld zu landen, in dem mindestens zwei Steine liegen. Ist das ein Ansatz?

Für die gestellte Aufgabe ist das unerheblich.

Aber wenn Du mich nach der einer Strategie für das Spiel fragen würdest, dann wäre meine Antwort nein.

Es gilt aus meiner Sicht die Balance zu halten, daß man in seiner oberen Reihe möglichst wenig Steine gesetzt hat (hier greift der Gegner ab), aber dort genug Felder besetzt sind, um nicht zu verlieren.

 

[Roin]

Es wäre wirklich eine coole Zusatzaufgabe einen vorausschauenden Algorithmus zu implementieren und die Algorithmen gegeneinander antreten zu lassen. Man bräuchte nur ein Protokoll für den Aufruf der jeweiligen Implementierungen:

"programmname --spielfeld="4;8;2;1;7;3;8;3;0;3;9;5;3;2;5;7;90;6;4;3;3;67;8;6;4;3;67;5;3;3;4;3" -> Gibt Feldnummer des vom Algorithmus gewählten Zuges zurück.

Dann schreibt man ein Boa-Programm, welches mit unseren Implementierungen als Plugin arbeitet.

Das wäre eine interessante Sache, die hier geschriebenen Programme gegeneinander antreten zu lassen und so ggf. Stärken zu vergleichen. Bisher ist es ja nur eine Auswertung nach "bester Zug gemäß Steingewinn", doch wenn sich 2 oder 3 die Mühe machen noch andere Strategien zu implementieren, würde so ein Wettkampf sicher spannend werden.

 

[CroneKorkN]

@Kapitn: Ich habe ein anderes Ergebnis:

Spoiler

https://github.com/CroneKorkN/bao-best-draw/blob/master/bao-best-draw.rb

Bei mir ist Feld 14 das Beste. Hier sind die Rechenschritte:

[src=bash]"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"2;2;2;2;2;0;3;2"
"2;2;2;2;2;2;2;2"
3
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"2;2;2;2;2;0;3;3"
"2;2;2;2;2;2;2;2"
2
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"2;2;2;2;2;0;3;3"
"2;2;2;2;2;2;2;3"
1
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"2;2;2;2;2;0;3;3"
"2;2;2;2;2;2;3;3"
0
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"2;2;2;2;2;0;3;3"
"2;2;2;2;2;3;0;3"
2
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"2;2;2;2;2;0;3;3"
"2;2;2;2;3;3;0;3"
1
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"2;2;2;2;2;0;3;3"
"2;2;2;3;3;3;0;3"
0
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"2;2;2;2;2;0;3;3"
"2;2;3;0;3;3;0;3"
2
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"2;2;2;2;2;0;3;3"
"2;3;3;0;3;3;0;3"
1
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"2;2;2;2;2;0;3;3"
"3;3;3;0;3;3;0;3"
0
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"3;2;2;2;2;0;3;3"
"0;3;3;0;3;3;0;3"
2
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"3;3;2;2;2;0;3;3"
"0;3;3;0;3;3;0;3"
1
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;2;2;2;0;2;2"
"3;3;3;2;2;0;3;3"
"0;3;3;0;3;3;0;3"
0
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;2"
"3;3;0;3;2;0;3;3"
"0;3;3;0;3;3;0;3"
4
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;2"
"3;3;0;3;3;0;3;3"
"0;3;3;0;3;3;0;3"
3
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;2"
"3;3;0;3;3;1;3;3"
"0;3;3;0;3;3;0;3"
2
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;2"
"3;3;0;3;3;1;4;3"
"0;3;3;0;3;3;0;3"
1
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;2"
"3;3;0;3;3;1;4;4"
"0;3;3;0;3;3;0;3"
0
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;0"
"3;3;0;3;3;1;4;0"
"0;3;3;0;3;3;0;4"
5
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;0"
"3;3;0;3;3;1;4;0"
"0;3;3;0;3;3;1;4"
4
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;0"
"3;3;0;3;3;1;4;0"
"0;3;3;0;3;4;1;4"
3
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;0"
"3;3;0;3;3;1;4;0"
"0;3;3;0;4;4;1;4"
2
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;0"
"3;3;0;3;3;1;4;0"
"0;3;3;1;4;4;1;4"
1
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;0"
"3;3;0;3;3;1;4;0"
"0;3;4;1;4;4;1;4"
0
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;0"
"3;3;0;3;3;1;4;0"
"0;4;0;1;4;4;1;4"
3
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;0"
"3;3;0;3;3;1;4;0"
"1;4;0;1;4;4;1;4"
2
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;0"
"4;3;0;3;3;1;4;0"
"1;4;0;1;4;4;1;4"
1
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;2;0;2;2;0;2;0"
"4;4;0;3;3;1;4;0"
"1;4;0;1;4;4;1;4"
0
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;0;0;2;2;0;2;0"
"4;0;1;3;3;1;4;0"
"1;4;0;1;4;4;1;4"
5
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;0;0;2;2;0;2;0"
"4;0;1;4;3;1;4;0"
"1;4;0;1;4;4;1;4"
4
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;0;0;2;2;0;2;0"
"4;0;1;4;4;1;4;0"
"1;4;0;1;4;4;1;4"
3
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;0;0;2;2;0;2;0"
"4;0;1;4;4;2;4;0"
"1;4;0;1;4;4;1;4"
2
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;0;0;2;2;0;2;0"
"4;0;1;4;4;2;5;0"
"1;4;0;1;4;4;1;4"
1
"XXXXXXXXXXXXXXXXXXXXXXXXXX"
"2;2;2;2;2;2;2;2"
"2;0;0;2;2;0;2;0"
"4;0;1;4;4;2;5;1"
"1;4;0;1;4;4;1;4"
0
"best draw: 13; 8 stones stolen"
"2;2;2;2;2;2;2;2"
"2;0;0;2;2;0;2;0"
"4;0;1;4;4;2;5;1"
"1;4;0;1;4;4;1;4"[/src]

13 entspricht 14, weil ich bei null Anfange. Die einzelnen Zahlen sind die Anzahl der Steine auf der Hand.

edit:

Mein Fehler: "Wenn der allererste Zug der Runde in der Frontreihe anfängt, nimmst du nur die Steine aus deiner eigenen Kuhle."

edit:

fixed: https://github.com/CroneKorkN/bao-b...699ab213d53b2a32f12530d112c6/bao-best-draw.rb

Der Algo:

Spoiler

[src=ruby]
class Bao
def initialize fields, enemy_fields
@fields = fields
@enemy_fields = enemy_fields
end

public

attr_reader :fields, :enemy_fields

def draw field, first_draw = true
# set position
@position = field

# take own stones in hand
@hand = @fields[@position]
@fields[@position] = 0

# take from enemy
if enemy_bordering? and not first_draw
@hand += @enemy_fields[bordering(@position)]
@enemy_fields[bordering(@position)] = 0
end

# put stones down
while @hand > 0
@position = (@position + 1) % (@fields.length)
@fields[@position] += 1
@hand -= 1
end

# draw again?
draw(@position, false) if @fields[@position] >= 2
end

def balance
(@fields.inject(0, :+) - @enemy_fields.inject(0, :+)) / 2
end

private

def enemy_bordering?
# is an enemy field bordering?
@position > (@fields.count+1)/2
end

def bordering field
@fields.length - 1 - (field - @fields.length/2)
end
end
[/src]

 

[MingsPing]

Oh,

ich hatte meinen Quellcode gar nicht hochgeladen.
Wenn man es ausführen möchte, so muss sich im selben Verzeichnis, in welchem die Lisp-Datei liegt, eine "input.txt" Datei befinden, mit dem Spielfeld. Es wird, wenn man (write-it) ausführt, eine Datei "output.txt" erstellt, die alle Züge simuliert darstellt.

[src=brainfuck]
(defun fill-n-from-m (n m field)
(cond
((= n 0) field)
((= m 16) (fill-n-from-m n 0 field))
((= n 1) (if (> (nth m field) 0)
(maybe-more m field)
(add-one m field)))
('t (fill-n-from-m (1- n) (1+ m) (add-one m field)))))

(defun add-one (m field)
(if (= m 0)
(cons (1+ (car field)) (cdr field))
(cons (car field) (add-one (1- m) (cdr field)))))

(defun maybe-more (m field)
(if (and (> m 7) (> (nth (+ m 8) field) 0))
(fill-n-from-m (+ (nth (+ m 8) field) 1 (nth m field))
(1+ m)
(change-field m 0 (change-field (+ m 8) 0 field)))
(fill-n-from-m (+ 1 (nth m field))
(1+ m)
(change-field m 0 field))))

(defun make-move (m field)
(let ((new-field (fill-n-from-m (nth m field)
(1+ m)
(change-field m 0 field))))
new-field))

(defun change-field (m n field)
(if (= m 0)
(cons n (cdr field))
(cons (car field) (change-field (1- m) n (cdr field)))))

(defun split-by-one-space (string)
(loop for i = 0 then (1+ j)
as j = (position #\Space string :start i)
collect (subseq string i j)
while j))

(defun to-field (lis)
(append
(reverse (cadddr lis))
(caddr lis)
(reverse (cadr lis))
(car lis)))
(defun to-list (field)
(list (take 8 (drop 24 field))
(take 8 (drop 16 field))
(take 8 (drop 8 field))
(reverse (take 8 field))))

(defun draw-field (field stream)
(loop for el in (to-list field) do
(print el stream)))

(defun take (n lis)
(if (= n 0)
nil
(cons (car lis) (take (1- n) (cdr lis)))))
(defun drop (n lis)
(if (= n 0)
lis
(drop (1- n) (cdr lis))))

(defun make-all-moves (stream)
(loop for i from 0 to 15 do
(let* ((new-field (make-move i *field*))
(a (get-points *field* new-field)))
(format stream "~%Kuhle Nr.: ~a, Profit: ~a" i a)
(draw-field new-field stream))))

(defun get-points (old-field new-field)
(let ((old (apply #'+ (take 16 old-field)))
(new (apply #'+ (take 16 new-field))))
(- new old)))

(defun write-it ()
(with-open-file (wr "output.txt" :direction utput :if-exists :supersede)
(defparameter *field* (to-field (get-it)))
(make-all-moves wr)))

(defun get-it ()
(with-open-file (s "input.txt")
(let ((field
(loop for i from 1 to 4 collect
(let ((dat (read-line s)))
(split-by-one-space (substitute #\Space #\; dat))))))
(mapcar (lambda (lis)
(mapcar (lambda (el)
(parse-integer el)) lis))
field))))

[/src]

(Leider gibt es kein Highlighting für Lisp...)

 

[CroneKorkN]

Ich habe mich nicht mehr intensiver mit der Spielmechanik auseinandergesetzt, also habe ich auch keine Idee für eine Strategie, die über den aktuellen Zug hinausgeht.

Und jetzt?

 

[theSplit]

@CroneKorkN: In wie fern, was über den aktuellen Zug hinausgeht? Verstehe jetzt nicht so ganz worauf du hinauswillst?
Eigentlich hast du ja jetzt einen Spielzug für einen Spieler abgeschlossen, also den optimalen Zug für deine gewählte Beispiel-Platzierung der Bao-Steine gefunden.

Ideen für weiteres auf Grundlage eines Algos:
1) Theoretisch kannst du das Spielbrett jetzt um 180 Grad drehen und den Zug des Gegenspielers, als Antwort, kalkulieren lassen.
Das könnte man dann fortführen bis keine Züge mehr möglich sind. Zum Beispiel.

2) Interessant könnte vielleicht auch der Fall sein, wenn man nicht konsequent versucht die meisten Spielsteine zu erobern, aber zum Beispiel die meisten Steine im eigenen Lager zu behalten bzw. dort zu sichern?
Also mehrere Strategien - wie kann ich die wenigstens Steine einsetzen, um den größten Nutzen zu haben, "min-max?", wie kann ich Steine sichern (falls möglich) um den Gegner vor mir "Zugunfähig" zu machen (falls das geht...) - oder eine Balance aus diesen Ansätze.

Ich habe jetzt auch nur die Regeln verinnerlicht, die hier im Thread so geschrieben worden sind; aber da geht bestimmt noch etwas.

 

[CroneKorkN]

Verstehe jetzt nicht so ganz worauf du hinauswillst?

darauf

Also mehrere Strategien

Strategien, die mehr umfassen, als pro Runde möglichst viele Steine abzuräumen. Denn mit dieser Strategie gibt es ungefähr einen Spielverlauf.

 

[theSplit]

Stimmt, in der Tat ist die Situation schnell festgefahren wenn man nur von maximaler Eroberung als Strategie ausgeht. - Das hab ich so auch noch nicht gesehen...

Wenn ich richtig verstanden habe, wird doch aktuell von jedem hier der bestmögliche Zug ermittelt der die meisten Steine erbeutet?

Es wird aber dann zum Beispiel nicht berücksichtigt ob dieser Zug auch die geringsten Eigeneninvestitionen an Spielsteinen beinhaltet bzw. dem Mitspieler zu Verfügung stellt oder mich ein Zug "spielunfähig" setzen würde, wenn man das "Zugunfähigkeit" auch als Spielziel mit einbauen würde um die Schwierigkeit zu erhöhen.

Man könnte eine Partei auch mit einem "Irrationalen Zug" ausstatten bzw. gar beide Seiten, bei dem aus den möglichen Zügen einer ausgewählt wird, egal um welche Strategie (max sparen/max erbeuten/mix sparen und erbeuten) es geht.

Das hab ich eigentlich damit versucht zu erklären.

 

[KaPiTN]

Man muß ein ausgewogenes Verhältnis für die Anzahl der Steine in der eigenen oberen Reihe finden.
Dort sollten sich möglichst wenig Steine befinden, da sie dem Gegner dort angeboten werden. Andererseits müssen dort genug Steine liegen, damit man nicht Gefahr läuft, daß der Gegner die Reihe komplett leert und man das Spiel verloren hat.

 

[CroneKorkN]

Faktoren für einen guten Zug:

1. viele Steine erbeutet
2. Obere Reihe: viele Felder belegt
3. Obere Reihe: wenig Steine pro Feld

So? Noch Ideen?

 

[KaPiTN]

Ja. Das war es

Dann bliebe eigentlich nur noch, daß ein Zug in der oberen Reihe dort Enden sollte, wo der Gegner die meisten Steine angrenzend hat, damit man beim nächsten Zug möglichst viele Steine erbeuten kann.
Aber das ist ein Punkt, den ein normaler Spieler beachten muß, aber bei uns keine Rolle spielt, weil wir im Gegensatz zu einem normalen Spieler ja die Ergiebigkeit aller möglichen Züge testen.
Auch nur für einen normalen Spieler wichtig, ist, daß eine Runde nicht nach nur einem Zug beendet sein sollte, aber auh das wird durch das Bruteforce abgedeckt.

Auf die Wahl des Gegners, wo er seine Runde beginnt, sehe ich keine Möglichkeit der Einflußnahme.

 

[theSplit]

Moin, ich war auch mal tätig, was wollt ihr zuerst den Output bestimmt und nicht den Code - wußte ich doch

Basierend auf der Vorlage bei dem alle Felder auf "2" stehen.
Code ist Python 2.7 (jaja, aber ich hatte kein 3.x installiert, sind auch vermutlich eh wieder nur die Print-Statements und Xrange die man umarbeiten müsste... )

Spoiler

[src=text][BEST RESULT FOR GAME 1: FIELD 5, 8 STOLEN, 8 TURNS


[------------------------- REPLAY WINNING GAME WITH OUTPUT -------------------------]
[GAME START]

[------------------------ MAKETURN 1 -----------------------]
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


[CAPTURED] 2 STONES - OPPONENT FIELD 13
[STONES] 2 [FIELD 5]
[MOVETO] 6 [STONES IN HAND 3 @ FIELD 3]
[MOVETO] 7 [STONES IN HAND 2 @ FIELD 3]
[MOVETO] 8 [STONES IN HAND 1 @ FIELD 3]
[MOVETO] 16 [STONES IN HAND 0 @ FIELD 3]


2;2;2;2;2;2;2;2
2;2;2;2;0;2;2;2
----------------
2;2;2;2;0;3;3;3
2;2;2;2;2;2;2;3

[------------------------ ENDTURN 1 -------------------------]

[------------------------ MAKETURN 2 -----------------------]
2;2;2;2;2;2;2;2
2;2;2;2;0;2;2;2
----------------
2;2;2;2;0;3;3;3
2;2;2;2;2;2;2;3


[STONES] 3 [FIELD 16]
[MOVETO] 15 [STONES IN HAND 2 @ FIELD 3]
[MOVETO] 14 [STONES IN HAND 1 @ FIELD 3]
[MOVETO] 13 [STONES IN HAND 0 @ FIELD 3]


2;2;2;2;2;2;2;2
2;2;2;2;0;2;2;2
----------------
2;2;2;2;0;3;3;3
2;2;2;2;3;3;3;0

[------------------------ ENDTURN 2 -------------------------]

[------------------------ MAKETURN 3 -----------------------]
2;2;2;2;2;2;2;2
2;2;2;2;0;2;2;2
----------------
2;2;2;2;0;3;3;3
2;2;2;2;3;3;3;0


[STONES] 3 [FIELD 13]
[MOVETO] 12 [STONES IN HAND 2 @ FIELD 3]
[MOVETO] 11 [STONES IN HAND 1 @ FIELD 3]
[MOVETO] 10 [STONES IN HAND 0 @ FIELD 3]


2;2;2;2;2;2;2;2
2;2;2;2;0;2;2;2
----------------
2;2;2;2;0;3;3;3
2;3;3;3;0;3;3;0

[------------------------ ENDTURN 3 -------------------------]

[------------------------ MAKETURN 4 -----------------------]
2;2;2;2;2;2;2;2
2;2;2;2;0;2;2;2
----------------
2;2;2;2;0;3;3;3
2;3;3;3;0;3;3;0


[STONES] 3 [FIELD 10]
[MOVETO] 9 [STONES IN HAND 2 @ FIELD 3]
[MOVETO] 1 [STONES IN HAND 1 @ FIELD 3]
[MOVETO] 2 [STONES IN HAND 0 @ FIELD 3]


2;2;2;2;2;2;2;2
2;2;2;2;0;2;2;2
----------------
3;3;2;2;0;3;3;3
3;0;3;3;0;3;3;0

[------------------------ ENDTURN 4 -------------------------]

[------------------------ MAKETURN 5 -----------------------]
2;2;2;2;2;2;2;2
2;2;2;2;0;2;2;2
----------------
3;3;2;2;0;3;3;3
3;0;3;3;0;3;3;0


[CAPTURED] 2 STONES - OPPONENT FIELD 10
[STONES] 3 [FIELD 2]
[MOVETO] 3 [STONES IN HAND 4 @ FIELD 3]
[MOVETO] 4 [STONES IN HAND 3 @ FIELD 3]
[MOVETO] 5 [STONES IN HAND 2 @ FIELD 1]
[MOVETO] 6 [STONES IN HAND 1 @ FIELD 4]
[MOVETO] 7 [STONES IN HAND 0 @ FIELD 4]


2;2;2;2;2;2;2;2
2;0;2;2;0;2;2;2
----------------
3;0;3;3;1;4;4;3
3;0;3;3;0;3;3;0

[------------------------ ENDTURN 5 -------------------------]

[------------------------ MAKETURN 6 -----------------------]
2;2;2;2;2;2;2;2
2;0;2;2;0;2;2;2
----------------
3;0;3;3;1;4;4;3
3;0;3;3;0;3;3;0


[CAPTURED] 2 STONES - OPPONENT FIELD 15
[STONES] 4 [FIELD 7]
[MOVETO] 8 [STONES IN HAND 5 @ FIELD 4]
[MOVETO] 16 [STONES IN HAND 4 @ FIELD 1]
[MOVETO] 15 [STONES IN HAND 3 @ FIELD 4]
[MOVETO] 14 [STONES IN HAND 2 @ FIELD 4]
[MOVETO] 13 [STONES IN HAND 1 @ FIELD 1]
[MOVETO] 12 [STONES IN HAND 0 @ FIELD 4]


2;2;2;2;2;2;2;2
2;0;2;2;0;2;0;2
----------------
3;0;3;3;1;4;0;4
3;0;3;4;1;4;4;1

[------------------------ ENDTURN 6 -------------------------]

[------------------------ MAKETURN 7 -----------------------]
2;2;2;2;2;2;2;2
2;0;2;2;0;2;0;2
----------------
3;0;3;3;1;4;0;4
3;0;3;4;1;4;4;1


[STONES] 4 [FIELD 12]
[MOVETO] 11 [STONES IN HAND 3 @ FIELD 4]
[MOVETO] 10 [STONES IN HAND 2 @ FIELD 1]
[MOVETO] 9 [STONES IN HAND 1 @ FIELD 4]
[MOVETO] 1 [STONES IN HAND 0 @ FIELD 4]


2;2;2;2;2;2;2;2
2;0;2;2;0;2;0;2
----------------
4;0;3;3;1;4;0;4
4;1;4;0;1;4;4;1

[------------------------ ENDTURN 7 -------------------------]
[------------------------ MAKETURN 8 -----------------------]
2;2;2;2;2;2;2;2
2;0;2;2;0;2;0;2
----------------
4;0;3;3;1;4;0;4
4;1;4;0;1;4;4;1


[CAPTURED] 2 STONES - OPPONENT FIELD 9
[STONES] 4 [FIELD 1]
[MOVETO] 2 [STONES IN HAND 5 @ FIELD 1]
[MOVETO] 3 [STONES IN HAND 4 @ FIELD 4]
[MOVETO] 4 [STONES IN HAND 3 @ FIELD 4]
[MOVETO] 5 [STONES IN HAND 2 @ FIELD 2]
[MOVETO] 6 [STONES IN HAND 1 @ FIELD 5]
[MOVETO] 7 [STONES IN HAND 0 @ FIELD 1]


2;2;2;2;2;2;2;2
0;0;2;2;0;2;0;2
----------------
0;1;4;4;2;5;1;4
4;1;4;0;1;4;4;1

[------------------------ ENDTURN 8 -------------------------]
[OUT OF MOVES] 1 STONES @ FIELD 7

[GAME END SUMMARY]
STONES STOLEN: 8
TURNS: 8

2;2;2;2;2;2;2;2
0;0;2;2;0;2;0;2
----------------
0;1;4;4;2;5;1;4
4;1;4;0;1;4;4;1[/src]

Eine Zip des Codes ist im Anhang, enthalten sind:

Das Skript:
"baoSolve.py"

Eingabe-Datei:
"input.txt"

Die Eingabe-Datei ist noch hardcoded, aber es geht ja erstmal um die Problemlösung.


Und damit ihr wisst was ihr da runterladet:

Spoiler

[src=python]#-------------------------------------------------------------------------------
# Auhor: theSplit [ngb] Code competition 3
#-------------------------------------------------------------------------------

def getNextField(currentField, fieldsInRow, direction):
if currentField > fieldsInRow:
return currentField - 1
elif currentField < fieldsInRow-1:
return currentField + 1;
else:
if direction == 0:
return 0
else:
return (fieldsInRow * 2) - 1


def outputRows(rowsData, fieldsInRow):
print ";".join([str(num) for num in rowsData[:fieldsInRow]])
print ";".join([str(num) for num in rowsData[fieldsInRow:]])



def printPlayboard(rowsA, rowsB):
fieldsInRow = len(rowsA) / 2
fieldSep = "--" * fieldsInRow;

outputRows(rowsA, fieldsInRow)
print fieldSep
outputRows(rowsB, fieldsInRow)

#-------------------------------------------------------------------------------

def playGame(rowsA, rowsB, fieldToStart, beVerbose):

totalFields = len(rowsB)
fieldsInRow = len(rowsB) / 2

currentField = fieldToStart
direction = 0

if currentField < fieldsInRow:
direction = 1
else:
direction = 0

movesMade = 0
stonesStolen = 0

if (beVerbose):
print "[GAME START]"

while(True):

stonesInHand = 0


if (rowsB[currentField] >= 2):

if (beVerbose):
print "\n[------------------------ MAKETURN %d -----------------------]" %(movesMade+1)
printPlayboard(rowsA, rowsB)
print "\n"

stonesInHand = rowsB[currentField]
enemyStones = 0

if (currentField < fieldsInRow):
enemyField = (fieldsInRow)+currentField;
enemyStones = rowsA[enemyField]

rowsA[enemyField] = 0

if (enemyStones != 0):
stonesStolen += enemyStones

if (beVerbose):
print "[CAPTURED] %3d STONES - OPPONENT FIELD %d" %(enemyStones, enemyField+1)

rowsB[currentField] = 0

if (beVerbose):
print "[STONES] %3d [FIELD %d]" %(stonesInHand, currentField+1)

stonesInHand += enemyStones
else:
if (beVerbose):
print "[OUT OF MOVES] %d STONES @ FIELD %d" %(rowsB[nextField], nextField+1)

break

while (stonesInHand != 0):
nextField = getNextField(currentField, fieldsInRow, direction)

if nextField == 0:
direction = 1
elif nextField == totalFields - 1:
direction = 0

currentField = nextField
rowsB[nextField] += 1
stonesInHand -= 1;

if (beVerbose):
print "[MOVETO] %3d [STONES IN HAND %d @ FIELD %d]" %(nextField+1, stonesInHand, rowsB[nextField])

if (beVerbose):
print "\n"
printPlayboard(rowsA, rowsB)
print "\n[------------------------ ENDTURN %d -------------------------]" %(movesMade+1)

movesMade += 1

if (beVerbose):
print "\n[GAME END SUMMARY]"
print "STONES STOLEN: %d" %(stonesStolen)
print "TURNS: %d\n" %(movesMade)

printPlayboard(rowsA, rowsB)
print "\n"

return [fieldToStart, stonesStolen, movesMade]


#-------------------------------------------------------------------------------



if __name__ == "__main__":

rowsA = [] # Player A
rowsB = [] # Player B (played)

rowsAOriginal = []
rowsBOriginal = []

rowsABestGame = []
rowsBBestGame = []

beVerbose = False

with open("input.txt", "r") as inputFile:

row = 0
game = 0

for lineData in inputFile:

if (lineData[0] == '\n'):
row = 0
continue

data = [int(num) for num in lineData.rstrip().split(";")]

if (row < 2):
rowsA.extend(data)
rowsAOriginal.extend(data)
else:
rowsB.extend(data)
rowsBOriginal.extend(data)

row += 1

if (row == 4):
game += 1

gameResult = [0,0,0] # [field started, stolen, turns made]
bestResult = [0,0,0]

# The field is zero based
for field in xrange(len(rowsB) - 1, 7, -1):
gameResult = playGame(rowsA, rowsB, field, beVerbose)

if (gameResult[1] > bestResult[1]):
bestResult = gameResult
rowsABestGame = []
rowsABestGame.extend(rowsA)

rowsBBestGame = []
rowsBBestGame.extend(rowsB)

rowsA = []
rowsA.extend(rowsAOriginal)

rowsB = []
rowsB.extend(rowsBOriginal)

for field in xrange(0, 8, 1):

gameResult = playGame(rowsA, rowsB, field, beVerbose)

if (gameResult[1] > bestResult[1]):
bestResult = gameResult
rowsABestGame = []
rowsABestGame.extend(rowsA)

rowsBBestGame = []
rowsBBestGame.extend(rowsB)

rowsA = []
rowsA.extend(rowsAOriginal)

rowsB = []
rowsB.extend(rowsBOriginal)


print "BEST RESULT FOR GAME %4d: FIELD %d, %d STOLEN, %d TURNS\n\n" %(game, bestResult[0]+1, bestResult[1], bestResult[2])

print "[------------------------- REPLAY WINNING GAME WITH OUTPUT -------------------------]"
playGame(rowsA, rowsB, bestResult[0], True)
print "[------------------------------------ END REPLAY -----------------------------------]"

[/src]

Ich sehe gerade bei der Hauptroutine bei dem die einzelnen Felder durchgetestet werden (die beiden For-Schleifen), ist die Anzahl der Felder einer Reihe hardgecoded...

-----------

Kleines Update: Keine Hardgecoden Feldlängen mehr und vor allem korrekte verwendung von xrange..., plus Unterstützung für multiple Spielfelder in einer Datei Names "playboard.csv" (hardcoded), also die Ausgabe von "baoGen" was hier in Thread auch zu finden ist.

Die Ausgabe sollte ein wenig freundlicher sein, so kann man sehen bei welchem Feld der Zug startet, das war vorher etwas verwirrend und ein wenig Error Handling, falls doch mal etwas schiefgehen sollte.

Die neue Version ist als ZIP im Anhang mit Beispieldatei.