Bitboards

StupidAttack

StupidAttack

Bekanntes Mitglied
Hallo liebe Community

Die Forensuche nach dem Stichwort "Bitboard" hat keinen Treffer gelandet, weshalb ich mich wage ein neues Thema zu eröffnen.

Und zwar will ich die Datenstrukturen meines Spiels, 4 Gewinnt, in Bitboards abspeichern, nämlich aus Performancegründen.

Nun meine äusserst dämliche Frage:

Ich habe ja 2 Long Variablen die das Spielfeld beschreiben:
Java: 
Long white = 000000000000000000000000000000000000000000000000000000000000000;//64 Felder, obwohl nur 42 (7*6 Spielfeld) benötigt werden, 0 == kein Stein und 1 == weisser Stein
Long black = 000000000000000000000000000000000000000000000000000000000000000;//trivial

Um nun aber die Daten zu verarbeiten, zu vergleichen und nach Mustern zu überprüfen, wie stelle ich das an?


Wenn ich beispielsweise nen speicherfressenden int array baue, dann ist das überprüfen auf 4 gleiche Steine in einer Reihe ja einfach, aber mit einer Long-Variablen?

Mein bisheriger Ansatz das Spielfeld (ein 2D int array mit der grösse 16*16 (in meinem 4 gewinnt habe ich ein 8*8 Feld) nach 4 diagonalen und vertikalen und horizontalen Reihen zu überprüfen:
Achja; ich nehme einen riesigen 16*16 Array (model), um den array exceptions zu entgehen.
Java: 
public boolean gameIsWon(int color) {
    //yellow ==1
    //red == 2
int help_array[] = new int[4];

        for( int c = 3; c < model.length;c++) {  //immer 0+4 da ich mein 8*8 Feld in ein 16*16 feld eingebettet habe, schrecklich, ich weiss
            for( int d = 3; d < model.length;d++) {


               if (model[c][d] == color)
                   help_array[0] = model[c][d];

             if(model[c][d]==color && model[c][d+1]==color && model[c][d+2]==color && model[c][d+3]==color)
             return true;

             }
            }

        for( int c = 3; c < model.length;c++) {
            for( int d = 3; d < model.length;d++) {

             if(model[d][c]==color && model[d+1][c]==color && model[d+2][c]==color && model[d+3][c]==color)
             return true;

            }
            }
        
        for( int c = 3; c < model.length;c++) {
            for( int d = 3; d < model.length;d++) {

             if(model[d][c]==color && model[d+1][c+1]==color && model[d+2][c+2]==color && model[d+3][c+3]==color)
             return true;
             
            }
            }
        
        for( int c = 3; c < model.length;c++) {
            for( int d = 3; d < model.length;d++) {

             if(model[d][c]==color && model[d-1][c+1]==color && model[d-2][c+2]==color && model[d-3][c+3]==color)
             return true;
             
            }
            }

        return false;

    }

Ich finde im Forum und im Inet nicht wirklich etwas was mir weiter hilft (wobei beide Behauptungen wohl eine Lüge sind), könnt ihr mir Tips für einen vergleichbaren Überprüfungs-Algorithmus für die oben angesprochenen LONG Datenfelder geben? Mir fehlt komplett der Ansatz...
Das wäre grossartig!

Liebe Grüsse
 
Zuletzt bearbeitet:
G

Gast2

Gast
Hast du die "einfache" lösung mit nem 2d Array mal implementiert? Ist die wirklich zu langsam?

Es gibt eine Klasse BitSet, vllt hilft dir die weiter.
 
StupidAttack

StupidAttack

Bekanntes Mitglied
EikeB hat gesagt.:
Hast du die "einfache" lösung mit nem 2d Array mal implementiert? Ist die wirklich zu langsam?

Es gibt eine Klasse BitSet, vllt hilft dir die weiter.
Zum Vergrößern anklicken....

Ja ich will unbedingt Bitboards benutzen, seit ich folgenden Teil einer Masterarbeit gelesen habe, (Copyriht liegt beim Ersteller, nicht bei mir, ich war so frei, den Ausschnitt zu zitieren, URL:Der Alpha-Beta-Algorithmus und Erweiterungen bei Vier Gewinnt - Knowledge Engineering Publications - Aigaion 2.0).

Wie kann ich mit diesen Long Typen arbeiten, ein konkretes Beispiel wäre GENIAL.
ps: BitSet schaue ich mir an, danke :)


Beim Design jedes Spiels muß ein Weg gefunden werden, die Information über dessen aktuellen Zustand - das heißt im Falle von Vier Gewinnt, die Information über Farbe und Lage der bereits gesetzten Scheiben - in einer geeigneten Art und Weise zu codieren. Hierbei ist die Effizienz, mit der bestimmte Manipulationen (z.B. „mache Zug X“) und Abfragen (z.B. „hat Spieler Y gewonnen?“) an der Datenstruktur vorgenommen werden können, von größter Wichtigkeit. In der Schachprogrammierung hat sich nun schon früh herausgestellt, daß der naive Ansatz – das Brett durch ein Array von Integern zu reprä- sentieren, von denen ein jeder für ein leeres Feld oder für eine bestimmte Figur steht – den Effizienzanforderungen in vielerlei Hinsicht nicht genügt.
Stattdessen hat sich das Bitboard-Prinzip durchgesetzt (siehe [9]). Zur Veranschauli- chung vergleiche man die Abbildungen 4.2 und 4.3: In beiden wurde die in Abbildung 4.1 dargestellte Spielstellung codiert. Die Variante in Abb. 4.2 verwendet hierfür ein Array von 42 Integern (je 32 bit), die Variante in Abb. 4.3 jedoch lediglich zwei Variablen vom Typ long (je 64 bit). Diese Variablen stehen einerseits für die weißen, andererseits für die schwarzen Scheiben, wobei die Bits 22 bis 63 die Felder des Spielbretts von a1 bis g6 repräsentieren: Jedes einzelne Bit zeigt das Vorhandensein (1) oder das Fehlen (0) einer weißen respektive schwarzen Scheibe auf seinem jeweiligen Feld an.
Obwohl diese Codierung nicht wie ein Schach-Bitboard den vollen Gebrauch von mo- dernen 64-Bit-Architekturen machen kann – 2∗22 Bits bleiben ungenutzt – ist leicht zu erkennen, daß sie sehr wenig Speicherplatz erfordert. Wichtiger noch sind jedoch ihre Geschwindigkeitsvorteile durch die effiziente Beantwortung häufig gestellter Anfragen. Ein simples Beispiel hierfür: Um festzustellen, ob Spieler Weiß eine Viererkette von a2 bis d5 gelegt und somit gewonnen hat, muß man in der naiven Implementierungsvariante vier Werte aus dem Brett-Array entnehmen und jeden einzelnen mit dem Wert für „weiße Scheibe“ vergleichen. Mit Bitboards genügt eine einzige bitweise und-Operation sowie ein Vergleich (siehe Abb. 4.4). Auf ähnliche Weise kann mittels bitweiser Operatoren das Setzen und Zurücknehmen von Zügen und vieles andere realisiert werden.
Zum Vergrößern anklicken....
 
StupidAttack

StupidAttack

Bekanntes Mitglied
Noctarius hat gesagt.:
Was du suchst sind Binär-Operatoren. << >> | & (shift left, shift right, xor, and)
Zum Vergrößern anklicken....
Jau genau, werde ich mir definitiv anschauen und ist genau das was ich brauche. Aber ich lasse den Thread noch offen damit er für die Suchenden nicht immer Einbahnstrassen (ohne dir jetzt vor de Kopf zu stossen) sondern auch evetuell ein wenig illustrierte informationen entstehen könnten ;)
 
M

Marco13

Top Contributor
Mit long ist man halt auf 8x8-Felder beschränkt (bzw weniger, wenn man nicht die beiden Farben getrennt speichert). Aber wenn das OK ist, könnte man sowas machen (der Übersichtlichkeit halber hier 4x4 und Binärdarstellung)
Code: 
int board = .... .... .... ....;
int row = 1111 0000 0000 0000;

int currentRow = row;
if (board & currentRow == currentRow) ersteReiheVoll();
currentRow >>= 4;
if (board & currentRow == currentRow) zweiteReiheVoll();
...

int column = 1000 1000 1000 1000;
int currentColumn = column;
if (board & currentColumn == currentColumn) ersteSpalteVoll();
currentColumn >>= 4;
...


int diag0 = 1000 0100 0010 0001;
if (board & diag0 == diag0) diagonaleVoll();
Man könnte auch alle Gewinnkonfigurationen von vornherein in einem Array speichern damit man sich das shiften spart, aber das dürfte kaum einen Geschwindigkeitsvorteil bringen.
 

Aktuelle Jobs

Neue Themen


Oben