[MISC]Gewinnabfrage bei 4gewinnt
Dominik Klein
Also ich muß 4gewinnt in Java programmieren.Ohne KI, nur für 2 Spieler.
Leider komme ich bei der Gewinnabfrage nicht weiter.
Ich geh mal davon aus, jeder kennt das Spiel...
Das Spielfeld ist nxn groß.
Die Vorgabe ist, eine Methode zu schreiben, die eine Gewinnstellung nach dem
letzten Zug abfragt. Übergeben dabei wird der Parameter "Spalte des letzen
Zugs".
Das Spielfeld ist natürlich ein Array. Meine erste Idee war es, das
komplette Array zu durchsuchen. Das wäre prinzipiell glaube ich auch
möglich, ich fange einfach beim Index 0,0 an, halte den ersten Index fest,
lasse den zweiten laufen (z.B. für die Spalten) und überprüfe ob sich 4
"Plättchen" eines Spielers in der der Reihe befinden. Umgekehrt für die
Zeilen. Dann müßte ich noch alle Diagonalen durchsuchen.
Dazu bräuchte ich allerdings nicht die übergebene Spalte. Deswegen ist,
denke ich mal ausgehend von der Position des letzen Steins nur eine Zeile,
eine Spalte und 2 Diagonalen zu untersuchen. Da bin ich aber an den 2
Diagonalen gescheitert. Die Spalte bekomme ich ja übergeben, die Zeile läßt
sich auch noch bestimmen. Nur bei den Diagonalen wird es schwierig, weil ich
ja nicht weiß, bei welchem Index die Diagonale beginnt (und bei welchem sie
aufhört), die durch den letzten gesetzten Spielstein führt. Die Berechnung
dieses Index ist so schwierig, weil ich ja nicht weiß, bis wohin genau das
Array eigentlich ragt (die Vorgabe ist ja ein nxn großes Spielfeld)...
Gibt es noch eine andere Lösung?
Vielen Dank
Dominik Klein
Mick Krippendorf
>
> Also ich muß 4gewinnt in Java programmieren.Ohne KI, nur für 2 Spieler.
> Leider komme ich bei der Gewinnabfrage nicht weiter.
>
>
> Die Vorgabe ist, eine Methode zu schreiben, die eine Gewinnstellung nach
dem
> letzten Zug abfragt. Übergeben dabei wird der Parameter "Spalte des letzen
> Zugs".
> Das Spielfeld ist natürlich ein Array.
So natürlch ist das gar nicht. Ausserdem ist es keine spezifische
Java-Frage, und Deine Hausaufgaben möchte ich auch nicht machen. Aber egal:
Z
4 | . | . | . | . | . |
3 | . | . | . | . | x |
2 | o | . | x | o | o |
1 | x | x | o | o | o |
0 | x | o | o | x | x |
0 1 2 3 4 S
Angenommen x zieht als nächster, und zwar steckt er seinen Stein in Spalte
3. Dies ein Gewinnzug höchstens dann, wenn Z3S3 zu einer Viererkette gehört.
Man könnte zB. von Z3S3 aus nacheinander in alle Richtungen testen, ob das
der Fall ist. Zu beachten ist dabei lediglich, dass man geilchzeitig auch
immer in die entgegengesetzte Richtung testen muss. Benachbarte Felder
berechnet man dabei mittels:
unten = Z - 1
links = S - 1
oben = Z + 1
rechts = S + 1
Keiner dieser Werte darf < 0 oder > n sein, und n sollte bei Spielbeginn
bekannt sein.
Von da ab müsstest Du es alleine schaffen, ansonsten gib ruhig Laut ;-)
Gruß,
Mick.
Hauke Heidtmann
> Hi!
>
> Also ich muß 4gewinnt in Java programmieren.Ohne KI, nur für 2 Spieler.
> Leider komme ich bei der Gewinnabfrage nicht weiter.
Sieh da, sieh da, nochjemand, der vor dem Blatt sitzt :-)
> Das Spielfeld ist nxn groß.
Bei meinem Ansatz eher (n+2)x(n+2), und zunächstmal sind alle Felder
auf "0" initialisiert.
> Die Vorgabe ist, eine Methode zu schreiben, die eine Gewinnstellung nach dem
> letzten Zug abfragt. Übergeben dabei wird der Parameter "Spalte des letzen
> Zugs".
> Das Spielfeld ist natürlich ein Array. Meine erste Idee war es, das
> komplette Array zu durchsuchen. Das wäre prinzipiell glaube ich auch
> möglich, ich fange einfach beim Index 0,0 an, halte den ersten Index fest,
> lasse den zweiten laufen (z.B. für die Spalten) und überprüfe ob sich 4
> "Plättchen" eines Spielers in der der Reihe befinden. Umgekehrt für die
> Zeilen. Dann müßte ich noch alle Diagonalen durchsuchen.
Sei i die Spalte, die du übergeben bekommst, dann ist
spielfeld[i+1][j+1] das Feld in dem du dich befindest, den passenden
Wert für j bekommst du durch eine passende Verwaltung der freien
Felder für jede Spalte, das musst du ja sowieso machen.
Dann musst du die Felder
spielfeld[i][j]
spielfeld[i][j+1]
spielfeld[i][j+2]
spielfeld[i+1][j+2]
untersuchen.
Wenn das Feld 0 enthält, untersuchst du das gegenüberliegende Feld,
wenn auch das Null ist, gehst du zum nächsten weiter. Um keine
Fallunterscheidung zu brauchen habe ich dann eben den Rand eingebaut,
damit ich am Rand des eigentlichen Spielfeldes den gleichen Vergleich
machen kann wie in der Mitte.
Für den Fall, dass du eine Übereinstimmung bekommst, musst du solange
in der Richtung weitersuchen, bist du entweder eine Null findest, oder
4 Felder gefunden hast. Letzteres ist das Spielende, ersteres ist
nicht ganz so schön, weil du dann den Counter, wieviele Steine du in
einer Reihe hast, behalten musst und auf der gegenüberliegenden Seite
des ursprünglichen Steins (sofern nicht schon geschehen) vergleichen
musst.
oO0(Wieso hört sich das gesprochen so einfach an, und geschrieben so
kompliziert?)
Hau "BTW: Aufgabe 4 schon erledigt? Sieht nach mehr aus, als es ist..." ke
--
Ach, _jetzt_ sehe ich, was ich hier mache! [Prof. Mathar]
Dirk Nillmann
versuchs mal so...
wir nehmen beispielhaft 3x3 felder an:
in jedes feld ein wert 2 ^x (also 2^0, 2^1,2^2,..)
0 1 2
4 8 16
32 64 128
eine diagonale von oben links nach unten rechts ergibts 136
bingo.. so einfach ist...
alle möglichen positionen ausrechnen und die
liste nach jedem zug abfragen, -fertig.-
;)
viel spass
dirk
Dirk Nillmann
Dirk Nillmann wrote:
> hi Dominik,
>
> versuchs mal so...
>
> wir nehmen beispielhaft 3x3 felder an:
> in jedes feld ein wert 2 ^x (also 2^0, 2^1,2^2,..)
> 0 1 2
> 4 8 16
> 32 64 128
>
sorry, da war ich wohl noch nicht ganz wach...
1 2 4
8 16 32
64 128 256
und somit 273....
Stefan Matthias Aust
news:9ubskq$d2p$1...@nets3.rz.RWTH-Aachen.DE...
> Also ich muß 4gewinnt in Java programmieren.Ohne KI, nur für 2 Spieler.
> Leider komme ich bei der Gewinnabfrage nicht weiter.
Wo ist das Problem? Heutige Rechner sind doch wohl schnell genug, um
einfach alle Möglichkeiten durchzuprobieren. Wie du schon schreibst ist das
Spielfeld N x M Felder groß. In einem Array
int[][] feld = new int[N][M];
würde ich jetzt LEER=0, ROT=1 und GELB=2 definieren und los geht's: Von
jedem Feld aus könnten in 8 Richtungen 3 Steine der gleichen Farbe kommen.
Ist das Feld leer, ist nichts zu prüfen. Wird vorher der Rand erreicht, kann
dies auch keine Gewinnposition sein. Mit ein bisschen Nachdenken fällt auf,
das man, wenn man etwa oben links beginnt, immer nur die Richtungen nach
rechts, rechts-unten und unten prüfen muss. Somit wäre dies ein
funktionierender Algorithmus:
for (int m = 0; m < M; m++)
for (int n = 0; n < N; n++)
int stein = feld[n][m];
if (stein == LEER) continue;
if (n + 3 < N) {
boolean ok = true;
for (int i = 1; i < 4 && ok; i++)
if (feld[n+i][m] != stein) ok = false;
if (ok) return stein;
}
if (n + 3 < N && m + 3 < M) {
boolean ok = true;
for (int i = 1; i < 4 && ok; i++)
if (feld[n+i][m+i] != stein) ok = false;
if (ok) return stein;
}
if (m + 3 < M) {
boolean ok = true;
for (int i = 1; i < 4 && ok; i++)
if (feld[n][m+i] != stein) ok = false;
if (ok) return stein;
}
return LEER;
Mit etwas mehr Nachdenken erkennt man aber, das das ziemlich umständlich
ist. Wenn überhaupt, kann ja nur der zuletzt gesetzte Stein für einen Sieg
verantwortlich sein. Also muss nur von dieser Position aus geprüft werden,
wieviele Steine links und rechts, oben und unten und entsprechend diagonal
die selbe Farbe haben.
Sei n,m die Steinposition. Dann liefert dies true, falls der letzte Stein
ein "Gewinner" war:
return test(1,0) || test(0,1) || test(1, -1) || test(1, 1);
Dabei ist
boolean test(int dx, int dy) {
int cnt = probe(dx, dy);
if (cnt > 4) throw new Error("oops");
return cnt == 4;
}
int probe(int dx, int dy) {
int cnt = 0, x = n, y = m, stein = feld[n][m];
while (x < N && y < M && feld[x][y]==stein) { cnt++; x += dx; y += dy; }
x = n; y = m; cnt--;
while (x >= 0 && y >= 0 && feld[x][y]==stein) { cnt++; x -= dx; y -= dy; }
return cnt;
}
bye
--
Stefan Matthias Aust // Truth Until Paradox
Stefan Schulze
news:9ubskq$d2p$1...@nets3.rz.RWTH-Aachen.DE...
Ich hab zwar schon ganze Weile nich mehr in Java geschrieben und war auch
noch nie sonderlich gut, aber das ganze müßte doch ungefähr auch so wie
unten geschrieben funktionieren, oder? Hab es nicht compiliert, sind sicher
ohne Ende Syntaxfehler etc. drin und der Stil is bestimmt auch nich der
tollste, aber es is immerhin auch mein erster Versuch, hier mal was zu
posten, also steinigt mich bitte nicht gleich ;-)
CU
Stefan
+++++++ Quellcode +++++++
// int[][] Feld = new int[m][n];
// [Spalte][Zeile]
//
// 0 ist leer, 1 ist rot, 2 ist gelb
boolean gewonnen?(int x, int y, int farbe ) file://x ist Spalte, y ist
Zeile, farbe ist 0|1|2
{
int s;
int z;
int cnt;
boolean test1=false; file://Ergebniss von
Zeile überprüfen
boolean test2=false; file://Ergebniss von
Spalte überprüfen
boolean test3=false; file://Ergebniss
von -Diagonale überprüfen
boolean test4=false; file://Ergebniss von
+Diagonale überprüfen
s=x; z=y; cnt=1;
while((Feld[s][z]==farbe)&&(s-1>=0)){s=s-1}; file://linkestes mögliches
s wird gesucht
while((Feld[s][z]==Feld[s+1][z])&&(s+1<=m)){s=s+1; cnt=cnt+1};
if cnt>=4 then test1=true;
s=x; z=y; cnt=1;
while((Feld[s][z]==farbe)&&(z-1>=0)){z=z-1}; file://unterstes mögliches
z wird gesucht
while((Feld[s][z]==Feld[s][z+1])&&(z+1>=n)){z=z+1; cnt=cnt+1};
if cnt>=4 then test2=true;
s=x; z=y; cnt=1;
while((Feld[s][z]==farbe)&&(z-1>=0)&&(s-1>=0)){s=s-1; z=z-1};
while((Feld[s][z]==Feld[s+1][z+1])&&(s+1<=m)&&(z+1<=n)){s=s+1; z=z+1;
cnt=cnt+1)};
if cnt>=4 then test3=true;
s=x; z=y; cnt=1;
while((Feld[s][z]==farbe)&&(z-1>=0)&&(s+1>=0)){s=s+1; z=z-1};
while((Feld[s][z]==Feld[s-1][z+1])&&(s-1<=m)&&(z+1<=n)){s=s-1; z=z+1;
cnt=cnt+1)};
if cnt>=4 then test3=true;
return (test1 && test2 && test3 && test4);
}
OT-PS: Die "file://" 's sollen eigentlich nur doppelte /'s sein, aber mein
OE stellt das automatisch meistens irgendwie um, kann mir jemand sagen, wie
sich das vermeiden läßt? Habs in den Optionen nirgends gefunden...
Paul Ebermann
> OT-PS: Die "file://" 's sollen eigentlich nur doppelte /'s sein, aber mein
> OE stellt das automatisch meistens irgendwie um, kann mir jemand sagen, wie
> sich das vermeiden läßt? Habs in den Optionen nirgends gefunden...
a) eine neuere Version des Newsreaders verwenden
b) einfach ein Leerzeichen nach // einfügen (sowieso
lesbarer).
HTH
Paul
Stefan Schulze
news:9ugdjn$8fin1$1...@ID-77081.news.dfncis.de...
> a) eine neuere Version des Newsreaders verwenden
> b) einfach ein Leerzeichen nach // einfügen (sowieso
> lesbarer).
Oki, thx! Is der Quellcode ansonsten zumindest einigermaßen verwertbar oder
auf grund von Fehlern unbrauchbar?
CU
Stefan