4. Programmieren mit Arrays "Vier gewinnt"

Programmieren mit Arrays "Vier gewinnt"


  • fixed:

    #include <stddef.h>
#include <stdbool.h>
#include <stdio.h>

void clear(FILE *is)
{
    int ch;
    while ((ch = fgetc(is)) != EOF && ch != '\n');
}

enum { ROWS = 6, COLS = 7 };
char const player_symbols[] = { ' ', 'X', 'O' };

typedef struct connect_four_tag {
    char field[ROWS][COLS];
    unsigned round;
    unsigned active_player;
    unsigned winner;
} connect_four_t;

connect_four_t connect_four_create()
{
    connect_four_t connect_four = {
            .field = { 0 },
            .round = 1,
            .active_player = 1,
            .winner = 0
    };
	
    return connect_four;
}

char connect_four_get_player_symbol(connect_four_t const *connect_four)
{
    return player_symbols[connect_four->active_player];
}

void connect_four_print(connect_four_t const *connect_four)
{
    printf("\nRound %u, Player %c\n\n ",
           connect_four->round, connect_four_get_player_symbol(connect_four));

    for (size_t x = 0; x < COLS; ++x)
        printf(" %1zu  ", x + 1);
    putchar('\n');

    for (size_t x = 0; x <= COLS * 4; ++x)
        putchar(x % 4 ? '-' : '+');
    putchar('\n');

    for (size_t y = 0; y < ROWS; ++y) {
        putchar('|');
        for (size_t x = 0; x < COLS; ++x)
            printf(" %c |", player_symbols[connect_four->field[y][x]]);
        putchar('\n');
        for (size_t x = 0; x <= COLS * 4; ++x)
            putchar(x % 4 ? '-' : '+');
        putchar('\n');
    }
    putchar('\n');
}

bool connect_four_is_valid_move(connect_four_t const *connect_four, int move)
{
    if (move < 1 || COLS < move)
        return false;

    return connect_four->field[0][move - 1] == 0;
}

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 stones_in_row_vertical = 1;
    if (ROWS - move_y >= 4) {        
        for (size_t y = move_y + 1; y <= ROWS; ++y) {  // down
            if (connect_four->field[y - 1][move_x - 1] == connect_four->active_player)
                ++stones_in_row_vertical;
            else break;
        }
    }

    int stones_in_row_horizontal = 1;
    for (size_t x = move_x - 1; x; --x) {  // left
        if (connect_four->field[move_y - 1][x - 1] == connect_four->active_player)
            ++stones_in_row_horizontal;
        else break;
    }
    for (size_t x = move_x + 1; x <= COLS; ++x) {  // right
        if (connect_four->field[move_y - 1][x - 1] == connect_four->active_player)
            ++stones_in_row_horizontal;
        else break;
    }

    int stones_in_row_diagonal_nw_to_se = 1;
    for (size_t x = move_x - 1, y = move_y + 1; x && y <= ROWS; --x, ++y) {  // nort-west
        if (connect_four->field[y - 1][x - 1] == connect_four->active_player)
            ++stones_in_row_diagonal_nw_to_se;
        else break;
    }
    for (size_t x = move_x + 1, y = move_y - 1; x <= COLS && y; ++x, --y) {  // south-east
        if (connect_four->field[y - 1][x - 1] == connect_four->active_player)
            ++stones_in_row_diagonal_nw_to_se;
        else break;
    }

    int stones_in_row_diagonal_ne_to_sw = 1;
    for (size_t x = move_x + 1, y = move_y + 1; x <= COLS && y <= ROWS; ++x, ++y) {  // nort-east
        if (connect_four->field[y - 1][x - 1] == connect_four->active_player)
            ++stones_in_row_diagonal_ne_to_sw;
        else break;
    }
    for (size_t x = move_x - 1, y = move_y - 1; x && y; --x, --y) {  // south-west
        if (connect_four->field[y - 1][x - 1] == connect_four->active_player)
            ++stones_in_row_diagonal_ne_to_sw;
        else break;
    }

    if (stones_in_row_vertical >= 4 || stones_in_row_horizontal >= 4 ||
        stones_in_row_diagonal_nw_to_se >= 4 || stones_in_row_diagonal_ne_to_sw >= 4)
    {
        connect_four->winner = connect_four->active_player;
        return;
    }

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

unsigned connect_four_get_round(connect_four_t const *connect_four)
{
    return connect_four->round;
}

unsigned connect_four_get_winner(connect_four_t const *connect_four)
{
    return connect_four->winner;
}

int main(void)
{
    connect_four_t connect_four = connect_four_create();

    do {
        int move;
        while (connect_four_print(&connect_four), printf("Your move: "),
               !scanf("%d", &move) || !connect_four_is_valid_move(&connect_four, move))
        {
            fputs("Input Error!\n\n", stderr);
            clear(stdin);
        }
        clear(stdin);

        connect_four_make_move(&connect_four, move);

    } while (!connect_four_get_winner(&connect_four));

    connect_four_print(&connect_four);
    printf("\nPlayer %c won in round %u :)\n\n",
            connect_four_get_player_symbol(&connect_four),
            connect_four_get_round(&connect_four));
}
    1

  • Die Funktion connect_four_make_move kann man aber eleganter (und kürzer) lösen, z.B. mittels eines Arrays von relativen Positionen und einer Schleife dazu.

    1 1 Antwort

  • @Th69 So oder so ähnlich schätze ich?

    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 fields_to_check[][6][2] = {
        { {  1,  0 }, { -1,  0 }, {  2,  0 }, { -2,  0 }, {  3,  0 }, { -3,  0 } },
        { {  0,  1 }, {  0, -1 }, {  0,  2 }, {  0, -2 }, {  0,  3 }, {  0, -3 } },
        { {  1,  1 }, { -1, -1 }, {  2,  2 }, { -2, -2 }, {  3,  3 }, { -3, -3 } },
        { {  1, -1 }, { -1,  1 }, {  2, -2 }, { -2,  2 }, {  3, -3 }, { -3,  3 } },
    };

    int stones_in_row[] = { 1, 1, 1, 1 };

    for (size_t direction = 0; direction < 4; ++direction) {
        for (size_t i = 0; i < 6; ++i) {
            int y = (int)move_y + fields_to_check[direction][i][0];
            int x = (int)move_x + fields_to_check[direction][i][1];

            if (y < 1 || ROWS < y || x < 1 || COLS < x)
                continue;

            if (connect_four->field[y - 1][x - 1] == connect_four->active_player)
                ++stones_in_row[direction];
        }
        
        if (stones_in_row[direction] >= 4) {
            connect_four->winner = connect_four->active_player;
            return;
        }
    }

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

  • Es reicht auch ein kleineres Array:

    struct direction
{
  int x,y;
} directions[4] =
 {
  { 0,1 }, { 1,1 }, { 1,0 }, { 1,-1 }
 };

    und dann (weitere) Schleifen, welche zuerst in positive Richtung und dann in negative Richtung die Anzahl der Spielerfarben-Felder zusammenzählen.

    Dein Code sieht aber jetzt m.E. schon viel besser aus (mein Ansatz würde auch bei anderer Spalten- und Zeilenanzahl ohne weitere Änderung funktionieren).

    PS: Ich hatte es schon 1992 auf dem Amiga so programmiert.

    0

  • @Swordfish
    Erkennt dein Code nicht in folgender Situation fälschlicherweise einen Sieg für X?

    . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . o
x X o x x . o

    X = neuer Stein (aktueller Zug), x = bestehende Steine

    0 1 Antwort

  • @hustbaer Ja. Einen Teil davon wollte ich mit alternierenden relativen Positionsangaben in dem Array fields_to_check umgehen, aber das reicht nicht für eine korrekte Abbruchbedingung. @Th69 dann zeig'.

    0

  • 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--;
 }
}
    0

  • @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.

    0 1 Antwort

  • @hustbaer Ok. Self-facepalm. Danke.

    0

  • Oder alternativ

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

    Was vielleicht eine Spur eleganter ist.

    0 1 Antwort

  • @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;
}
    1

  • @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.

    0 1 Antwort

  • @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?

    0

  • @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.

    0 1 Antwort

  • @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?

    0 1 Antwort

  • @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.

    1
array 25 algorithmus 3 for-schleife 3
Anmelden zum Antworten