Vier Gewinnt Siegüberprüfung

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Antworten
Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Vier Gewinnt Siegüberprüfung

Beitrag von cloidnerux » So Jun 03, 2012 2:43 pm

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.
Redundanz macht wiederholen unnötig.
quod erat expectandum

canlot
Beiträge: 393
Registriert: Di Mär 08, 2011 11:01 pm
Wohnort: NRW

Re: Vier Gewinnt Siegüberprüfung

Beitrag von canlot » So Jun 03, 2012 3:05 pm

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 :D
Unwissenheit ist ein Segen

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Vier Gewinnt Siegüberprüfung

Beitrag von cloidnerux » So Jun 03, 2012 3:12 pm

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?
Redundanz macht wiederholen unnötig.
quod erat expectandum

nouseforname
Beiträge: 236
Registriert: Do Feb 10, 2011 6:31 pm

Re: Vier Gewinnt Siegüberprüfung

Beitrag von nouseforname » So Jun 03, 2012 3:45 pm

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.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Vier Gewinnt Siegüberprüfung

Beitrag von cloidnerux » So Jun 03, 2012 3:59 pm

Sowas habe ich auch, ich suche nach etwas "eleganterem", wenn es denn soetwas gibt.
Denke schon über irgendwelche Binären Pattern nach oder so.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Vier Gewinnt Siegüberprüfung

Beitrag von cloidnerux » So Jun 03, 2012 8:17 pm

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
Redundanz macht wiederholen unnötig.
quod erat expectandum

Onraku
Beiträge: 43
Registriert: Fr Sep 09, 2011 2:14 pm

Re: Vier Gewinnt Siegüberprüfung

Beitrag von Onraku » Do Jun 14, 2012 10:34 pm

cloidnerux hat geschrieben: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

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Vier Gewinnt Siegüberprüfung

Beitrag von cloidnerux » Fr Jun 15, 2012 8:01 am

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.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Antworten