Programmieren mit Arrays "Vier gewinnt"

Th69

Das ist doch trivial...

Aber hier mein alter K&R-C Code:

short aufreihepruefen(sp,x,y)
char sp;
short x,y;
{
 short max=0;
 for(k=0;k<4;k++)
 {
  kk=1;
  pruefen(sp,x,y,k,1);
  pruefen(sp,x,y,k,-1);
  if(kk>max) max=kk;
 }
 return max;
}

pruefen(sp,x,y,k,l)
char sp;
short x,y;
int k,l;
{
 int j,i;
 while(1)
 {
  j=x+richtung[k].x*l;
  if(j<1 || j>MAXX) return;
  i=y+richtung[k].y*l;
  if(i<1 || i>MAXY) return;
  if(gitterfeld[j-1][i-1]!=sp) return;
  kk++;
  if(l>0) l++;
  else l--;
 }
}

hustbaer

@Swordfish
Ich hätte das einfach als

int const length = runLength(pos + dir, dir, color) + runLength(pos - dir, -dir, color) + 1;
return length >= 4;

implementiert.

Swordfish

@hustbaer Ok. Self-facepalm. Danke.

hustbaer

Oder alternativ

int const length = runLength(pos, dir) + runLength(pos, -dir) - 1;
return length >= 4;

Was vielleicht eine Spur eleganter ist.

Swordfish

@hustbaer

size_t connect_four_try_run(connect_four_t const *connect_four, size_t origin_y, size_t origin_x, int dir_y, int dir_x)
{
    size_t length = 0;
    for (size_t y = origin_y, x = origin_x; y && x && y <= ROWS && x <= COLS; y += dir_y, x += dir_x) {
        if (connect_four->field[y - 1][x - 1] == connect_four->active_player)
            ++length;
        else break;
    }
    return length;
}

void connect_four_make_move(connect_four_t *connect_four, int move)
{
    size_t move_x = move;
    size_t move_y = 1;

    for (size_t y = ROWS; y; --y) {
        if (!connect_four->field[y - 1][move_x - 1]) {
            connect_four->field[y - 1][move_x - 1] = connect_four->active_player;
            move_y = y;
            break;
        }
    }

    int directions[][2] = {
        {  1,  0 },  // north (irrelevant) / south
        {  0,  1 },  // east / west
        {  1,  1 },  // north-east / south-west
        {  1, -1 },  // north-west / south-east
    };

    for (size_t i = 0; i < sizeof directions / sizeof *directions; ++i) {
        size_t stones_in_row = connect_four_try_run(connect_four, move_y, move_x, directions[i][0], directions[i][1])
                             + connect_four_try_run(connect_four, move_y, move_x, directions[i][0] * -1, directions[i][1] * -1) - 1;

        if (stones_in_row >= 4) {
            connect_four->winner = connect_four->active_player;
            return;
        }
    }

    connect_four->round += 1;
    connect_four->active_player = connect_four->active_player == 1 ? 2 : 1;
}

hustbaer

@Swordfish
Sieht nett aus.

Kleinigkeiten die ich anders machen würde: 1) ich würde int für die Koordinaten verwenden und 2) ich würde intern mit 0-basierten Koordinaten rechnen 3) ich würde den Vergleich mit connect_four->field[y][x ] == connect_four->field[origin_y][origin_x] machen.
Sind aber nicht wirklich wichtig, eher Geschmackssache.

Swordfish

@hustbaer Nächster schritt richtung KI wäre wohl ein Bitboard zur Repräsentation. Ich frage mich ob es Sinn macht da die Spielfelddimensionen variabel zu halten?

hustbaer

@Swordfish
Bitboard is eine Optimierung, ich verstehe nicht wie das "der nächste Schritt richtung KI" sein soll. Eine Optimierung die wohl durchaus oft Sinn macht, aber wenn's einem erstmal darum geht wie man eine KI so baut würde ich mir den Schritt für später aufheben.

Was die Dimensionen angeht: Wenn du keine (bzw. kaum) Performance-Einbussen dadurch haben willst, wird das richtig viel Arbeit. Ich würde mich da im Spielen flacher Bälle üben.

Swordfish

@hustbaer sagte in Programmieren mit Arrays "Vier gewinnt":

Bitboard is eine Optimierung, ich verstehe nicht wie das "der nächste Schritt richtung KI" sein soll. Eine Optimierung die wohl durchaus oft Sinn macht, aber wenn's einem erstmal darum geht wie man eine KI so baut würde ich mir den Schritt für später aufheben.

Wie Du wahrscheinlich aus dem Zeugs gesehen hast das ich hier im Forum forciere und poste bin ich ein sehr modularer Typ. Der Gedanke war die Repräsentation zu ändern und soweit wegzukapseln daß man nur noch high level Zugriffe braucht.

@hustbaer sagte in Programmieren mit Arrays "Vier gewinnt":

Was die Dimensionen angeht: Wenn du keine (bzw. kaum) Performance-Einbussen dadurch haben willst, wird das richtig viel Arbeit.

Im Bezug auf ein Bitboard? Allignment?

hustbaer

@Swordfish sagte in Programmieren mit Arrays "Vier gewinnt":

Wie Du wahrscheinlich aus dem Zeugs gesehen hast das ich hier im Forum forciere und poste bin ich ein sehr modularer Typ. Der Gedanke war die Repräsentation zu ändern und soweit wegzukapseln daß man nur noch high level Zugriffe braucht.

Gerade dann verstehe ich es nicht. Wenn du es wegkapselst, dann ist doch erstmal egal was für eine Implementierung dahinter steckt. Da muss das erstmal kein Bitboard sein. Man kann gleich mit der KI anfangen, und danach das Bitboard reinstöpseln.

@hustbaer sagte in Programmieren mit Arrays "Vier gewinnt":

Was die Dimensionen angeht: Wenn du keine (bzw. kaum) Performance-Einbussen dadurch haben willst, wird das richtig viel Arbeit.

Im Bezug auf ein Bitboard? Allignment?

Weiss nicht, ich würde annehmen alles mögliche. Ich z.B. würde vermutlich versuchen mir möglichst viel Umrechnungen zwischen X/Y Position und Index/Shift im Bitboard zu sparen. Angenommen ich will gucken will ob links neben dem aktuellen Feld noch was frei ist...
Ich hab also einen "Iterator" für mein Bitboard der auf eine bestimmte Position zeigt, und will den jetzt ein Feld nach links verschieben.
Wenn ich z.B. weiss dass eine Zeile des Spielfelds immer in ein "Wort" des Bitboards passt, dann weiss ich dass ich nur den Shift-Wert im Iterator anpassen muss, nicht aber den Wort-Index.
Wenn das aber nicht fix ist, müsste ich ja immer checken ob mein Shift-Index jetzt z.B. negativ geworden ist, und dann den Wort-Index anpassen.

Dinge dieser Art. Ist jetzt aber nur eine grobe Schätzung aus der Ferne. Da ich sowas noch nie selbst implementiert habe (weder hard-coded noch generisch) kann ich nichts konkreteres anbieten.