Vier Gewinnt Siegüberprüfung

[cloidnerux]

Vier gewinnt ist ein relativ einfaches Spiel, bei dem es darum geht, 4 Steine gleicher Farbe in einer Reihe, spalte oder Diagonale zu haben.
ich weiß nicht ob ihr es kennt, aber wie man schon lesen konnte besteht das Spielfeld aus einer m*n Matrix mit entsprechend vielen Feldern, dieses muss man sich Senkrecht zum Boden stehend vorstellen, folglich lassen sich die Steine immer nur auf anderen oder eben ganz unten Platzieren(es ist halt nicht Tik Tak Toa),d a sie ja sonst herunterrutschen würden.
Mein Problem ist nun, dass ich eine Überprüfung schreiben muss, die Überprüft ob ein als letztes gesetzter Stein eben nun mit 3 weiteren der selben Farbe in einer reihe/spalte/diagonale liegt.
Der Rahmen des Programmes sieht folgendes vor:
6 Zeilen, 7 Spalten, 2 Farben

Generell ist mir klar, was man machen muss, aber ich suche nach einem eingermaßen "schönen" Algorithmus und nicht Brute-Force Programmierung und eben alle möglichen fälle überprüfen.
Wenn jemand Ideen hat oder irgendwelche Informationen auf lager hat, würde ich mich sehr freuen.

MfG cloidnerux.

[canlot]

Um den Stein alles absuchen, links oder rechts anfangen bis man ein gleichfarbiges Stein gefunden hat Richtung speichern wo man aufgehört hat. Zu den gefundenen Stein gehen in einer Schleife in die gleiche Richtung, wenn insgesamt vier gleichfarbige Steine dann gefunden. Wenn nicht auf den ersten Stein gehen und von der Richtung aus wo man aufgehört hat weitermachen bis man gefunden hat oder bis man ankommt wo man angefangen hat.

War meine Überlegung grade oder brauchst du einen Quellcode?
ich hoffe du hast verstanden was ich geschrieben habe.^^
übrigens: das wäre eine schöne Wettbewerbsaufgabe

[cloidnerux]

Ich habe es schon verstanden, aber es ist mir noch zu "umständlich". So einen Ansatz habe ich ja schon^^
Die Frage ist halt, wie macht man das einfacher?

[nouseforname]

Kommt mir bekannt vor.

Ich habe es damals mit mehreren Schleifen gemacht. Immer dort angefangen wo der letzte Stein gespielt wurde und dann nacheinander in alle Richtungen gesucht. Sind also nur 4 Schleifen. Kann das auch gerne Posten wenn gewünscht.

[cloidnerux]

Sowas habe ich auch, ich suche nach etwas "eleganterem", wenn es denn soetwas gibt.
Denke schon über irgendwelche Binären Pattern nach oder so.

[cloidnerux]

Ein bisschen hübscher ist er geworden, mein Algorithmus, aber immer noch nicht ganz so schön.
Durch ein bisschen Mathe, kann man dann auch ganz einfach durch die Diagonalen Iterieren, denn für die Rechtsseitige Diagonale gilt: dr = x - y = const, wobei links oben das feld x = y = 0 ist.
Damit kann man dann mit einer For-schleife durch die ganze Diagonale iterieren, ohne probleme.
Für die Linkseite diagonale gilt für mein Spielfeld: dl = 6 - y - x

[Onraku]

Denke schon über irgendwelche Binären Pattern nach oder so.

Vielleicht kannst du dann mit sowas mehr anfangen als ich...

http://stackoverflow.com/questions/7033 ... four-field

The source code from the Fhourstones Benchmark from John Tromp uses a fascinating algorithm for testing a connect four game for a win. The algorithm uses following bitboard representation of the game:

Code: Alles auswählen

.  .  .  .  .  .  .  TOP
5 12 19 26 33 40 47
4 11 18 25 32 39 46
3 10 17 24 31 38 45
2  9 16 23 30 37 44
1  8 15 22 29 36 43
0  7 14 21 28 35 42  BOTTOM

There is one bitboard for the red player and one for the yellow player. 0 represents a empty cell, 1 represents a filled cell. The bitboard is stored in an unsigned 64 bit integer variable. The bits 6, 13, 20, 27, 34, 41, >= 48 have to be 0.

The algorithm is:

Code: Alles auswählen

// return whether 'board' includes a win
bool haswon(unsigned __int64 board)
{
    unsigned __int64 y = board & (board >> 6);
    if (y & (y >> 2 * 6))     // check \ diagonal
        return true;
    y = board & (board >> 7);
    if (y & (y >> 2 * 7))     // check horizontal
        return true;
    y = board & (board >> 8);
    if (y & (y >> 2 * 8))     // check / diagonal
        return true;
    y = board & (board >> 1);
    if (y & (y >> 2))         // check vertical
        return true;
    return false;
}

You have to call the function for the bitboard of the player who did the last move

[cloidnerux]

Vielleicht kannst du dann mit sowas mehr anfangen als ich...

http://stackoverflow.com/questions/7033 ... four-field

Danke. Das ist echt mal ein cooler Algorithmus. Auch wenn ich ihn gerade nicht mehr akut benötige und auf einem 8-Bit AVR wrsl schlecht implementieren könnte, so finde ich sowas schon cool.

MfG cloidnerux.