3
\$\begingroup\$

I am just trying to understand the minimax algorithm better and how it works, so I made this basic connect4 game with raylib. It works fine, but I think there must be some kind of flaw in the logic, because the algorithm sometimes doesn't choose the fastest way to a winning situation. This is my core problem, but there are also some minor ones:

  • The win (see GitHub link) function also has some logic flaws, because it doesn't detect won boards sometimes, if they are close to the right-end of the board. (I think resolved)
  • How could I resolve the problem that if I set the depth of the minimax search higher, the computer needs more time (this isn't the problem), but in that time I cannot update anything on the screen.
  • Is it a bad practise that in the main function I only initialize basic things and the main game loop only consist of a switch statement which calls a function for different game-states.
  • Is it bad practise to use global variables? Because in this state my program has kinda fixed parameters so it would be hard to resize anything, but I want to make the whole window/game resizable.

The whole code can be found here: https://github.com/mrnuqname/connect4/tree/main/connect4_gui

Edit: I finally found what caused the bugs with not detecting a won situation (it was trying to read data outside of the array) and also why the evaluation function was buggy (it checked the diagonals twice and it didn't check for columns), but im still interested about the other questions.

main.c is the core game and connect.c is just the minimax function and some other helper functions for interpreting the gamestate.

main.c:

#include "include/raylib.h"
#include "include/connect.h"
#include <stdlib.h>
#include <string.h>

#define SC_WIDTH 800
#define SC_HEIGHT 800

typedef enum GameScreen {TITLE, PLAYERTURN, COMPUTERTURN, ENDING} GameScreen;

void titleScreen(GameScreen *gamestate);
void renderBoard(state board[ROWS][COLS]);
void playerTurn(GameScreen *gamestate, state board[ROWS][COLS]);
void endScreen(GameScreen *gamestate, state board[ROWS][COLS]);
void computerTurn(GameScreen *gamestate, state board[ROWS][COLS]);
void animate(int posX, int posY, state player, state board[ROWS][COLS]);
void drawScore();
void drawEnd(state board[ROWS][COLS]);

int COMPSCORE = 0;
int PLAYERSCORE = 0;

int main(void)
{
    // Initialization
    const int screenWidth = SC_WIDTH;
    const int screenHeight = SC_HEIGHT;
    Image icon = LoadImage("dep/icon.png");
    
    InitWindow(screenWidth, screenHeight, "Connect4");
    SetWindowIcon(icon);
    UnloadImage(icon);

    state board[ROWS][COLS] = {0};
    board[6][7] = COMP;
    GameScreen gamestate = TITLE;

    SetTargetFPS(60);

    // Main game loop
    while (!WindowShouldClose())    // Detect window close button or ESC key
    {
        HideCursor();
        switch(gamestate){
            
            case TITLE: titleScreen(&gamestate);
                break;
            case PLAYERTURN: playerTurn(&gamestate, board);
                break;
            case COMPUTERTURN: computerTurn(&gamestate, board);
                break;
            case ENDING: endScreen(&gamestate, board);
                break;
            default: titleScreen(&gamestate);
                break;
        }
    }

    CloseWindow();        // Close window and OpenGL context

    return 0;
}

void titleScreen(GameScreen *gamestate){

    while (!WindowShouldClose()){
        if(IsKeyPressed(KEY_ENTER)){
            *gamestate = PLAYERTURN;
            return;
        }

        BeginDrawing();

            ClearBackground(LIGHTGRAY);
            DrawText("PRESS [ENTER] TO START", SC_WIDTH/2 - MeasureText("PRESS [ENTER] TO START", 40)/2, SC_HEIGHT/2 - 50, 40, DARKGRAY);
            DrawText("\n\n\nRules:\n - You have to connect 4 dots in any way\n - Your dots always fall to the bottom\n - Just [click] on the column to place your circle there", GetScreenWidth()/2 - MeasureText("PRESS [ENTER] TO START", 40)/2, GetScreenHeight()/2 - 50, 20, DARKGRAY);

        EndDrawing();
    }
    CloseWindow();
}

void endScreen(GameScreen *gamestate, state board[ROWS][COLS]){

    char text[128];
    if(win(board) == 1){
        strcpy(text, "PLAYER WON!");
        PLAYERSCORE++;
    }
    else if(win(board) == 2){
        strcpy(text, "COMPUTER WON!");
        COMPSCORE++;
    }
    else if(win(board) == -1){
        strcpy(text, "DRAW!");;
    }

    while (!WindowShouldClose()){
        if(IsKeyPressed(KEY_ENTER)){
            memset(board, EMPTY, ROWS*COLS*(sizeof(board[0][0])));
            *gamestate = TITLE;
            return;
        }

        BeginDrawing();

            ClearBackground(LIGHTGRAY);
            DrawText(text, GetScreenWidth()/2 - MeasureText(text, 40)/2, 60, 40, DARKGRAY);
            DrawText("PRESS [ENTER] TO PLAY AGAIN", GetScreenWidth()/2 - MeasureText("PRESS [ENTER] TO PLAY AGAIN", 20)/2, 30, 20, DARKGRAY);
            renderBoard(board);
            drawEnd(board);
            drawScore();

        EndDrawing();
    }
    CloseWindow();
}

void playerTurn(GameScreen *gamestate, state board[ROWS][COLS]){

    int col = 3;

    while (!WindowShouldClose()){

        Rectangle r = {.x = 50 + col*(SC_WIDTH - 100)/COLS, .y =  (SC_WIDTH-100)/COLS, .height = SC_HEIGHT-200, .width = (SC_WIDTH-100)/COLS};
        BeginDrawing();

            ClearBackground(LIGHTGRAY);
            DrawText("YOUR TURN", GetScreenWidth()/2 - MeasureText("YOUR TURN", 40)/2, 30, 40, DARKGRAY);
            renderBoard(board);
            DrawRectangleLinesEx(r, 5.0f, DARKPURPLE);
            drawScore();

        EndDrawing();

        if((IsKeyPressed(KEY_RIGHT) || IsKeyPressed(KEY_D)) && col < COLS-1){
            col++;
        }
        else if ((IsKeyPressed(KEY_LEFT) || IsKeyPressed(KEY_A)) && col > 0){
            col--;
        }
        if(IsKeyPressed(KEY_SPACE)){
            if(board[0][col] == EMPTY){
                for(int i = ROWS-1; i >= 0; i--){
                    if(board[i][col] == EMPTY){
                        animate(50 + col * (SC_WIDTH - 100)/COLS, 100 + i*(SC_HEIGHT- 200)/ROWS, PLAYER, board);
                        board[i][col] = PLAYER;
                        if(win(board)){
                            *gamestate = ENDING;
                            return;
                        }
                        else{
                            *gamestate = COMPUTERTURN; 
                            return;
                        }
                    }
                }
            }
        }
    }
    CloseWindow();
}

void computerTurn(GameScreen *gamestate, state board[ROWS][COLS]){

    BeginDrawing();

            ClearBackground(LIGHTGRAY);
            DrawText("WAIT FOR THE COMPUTER", GetScreenWidth()/2 - MeasureText("WAIT FOR THE COMPUTER", 40)/2, 30, 40, DARKGRAY);
            renderBoard(board);
            drawScore();

    EndDrawing();
    position temp = findBestmove(board);
    animate(50 + temp.col * (SC_WIDTH - 100)/COLS, 100 + temp.row*(SC_HEIGHT- 200)/ROWS, COMP, board);
    computermove(board, temp);
    if(win(board)){
        *gamestate = ENDING;
        return;
    }
    else{
        *gamestate = PLAYERTURN;
    }
}

void renderBoard(state board[ROWS][COLS]){
    for(int i = ROWS-1; i >=0; i--){
        for(int j = 0; j < COLS; j++){
            int posX = 50 + j*(SC_WIDTH - 100)/COLS;
            int posY = 100 + i*(SC_HEIGHT- 200)/ROWS;
            DrawRectangleLines(posX, posY, (SC_WIDTH - 100)/COLS, (SC_HEIGHT-200)/ROWS, BLACK);
            switch(board[i][j]){
                case PLAYER: DrawCircle(posX+50, posY+50, 48, RED); 
                    break;
                case COMP: DrawCircle(posX+50, posY+50, 48, ORANGE); 
                    break;
                default: continue;
                    break;
            }
        }
    }
}

void animate(int posX, int posY, state player, state board[ROWS][COLS]){
    Vector2 position= {.x = posX, .y = -100};
    Vector2 speed = { 0.0f, 25.0f };
    Color color;
    if(player == COMP) color = ORANGE;
    else if(player == PLAYER) color = RED;
    while(position.y < posY){
        position.y += speed.y;
        BeginDrawing();

            ClearBackground(LIGHTGRAY);
            renderBoard(board);
            DrawCircle(position.x+50, position.y+50, 48, color);
            drawScore();

        EndDrawing();
    }
}

void drawScore(){
    char pscore[10];
    char cscore[10];
    itoa(PLAYERSCORE, pscore, 10);
    itoa(COMPSCORE, cscore, 10);
    DrawCircle(40,47,30,Fade(RED, 0.5f));
    DrawCircle(SC_WIDTH-40,47,30,Fade(YELLOW, 0.5f));
    DrawText(pscore, 30, 30, 40, BLACK);
    DrawText(cscore, SC_WIDTH - 30 - MeasureText(cscore, 40), 30, 40, BLACK);
}

void drawEnd(state board[ROWS][COLS]){
    for(int i = ROWS-1; i >=0; i--){
        for(int j = 0; j < COLS; j++){
            if(board[i][j] != EMPTY){
                if (checkCol(board, i, j) == 4){
                    Vector2 st = {.x = 100 + j*(SC_WIDTH - 100)/COLS, .y = 150 + i*(SC_HEIGHT- 200)/ROWS};
                    Vector2 en = {.x = 100 + j*(SC_WIDTH - 100)/COLS, .y = 150 + (i-3)*(SC_HEIGHT- 200)/ROWS};
                    DrawLineEx(st, en, 10.0f, DARKGREEN);
                }
                else if(checkRow(board, i, j) == 4){
                    Vector2 st = {.x = 100 + j*(SC_WIDTH - 100)/COLS, .y = 150 + i*(SC_HEIGHT- 200)/ROWS};
                    Vector2 en = {.x = 100 + (j+3)*(SC_WIDTH - 100)/COLS, .y = 150 + i*(SC_HEIGHT- 200)/ROWS};
                    DrawLineEx(st, en, 10.0f, DARKGREEN);
                }
                else if(checkDiag(board, i, j) == 4){
                    Vector2 st = {.x = 100 + j*(SC_WIDTH - 100)/COLS, .y = 150 + i*(SC_HEIGHT- 200)/ROWS};
                    Vector2 en = {.x = 100 + (j+3)*(SC_WIDTH - 100)/COLS, .y = 150 + (i-3)*(SC_HEIGHT- 200)/ROWS};
                    DrawLineEx(st, en, 10.0f, DARKGREEN);
                }
                else if(checkDiagb(board, i, j) == 4){
                    Vector2 st = {.x = 100 + j*(SC_WIDTH - 100)/COLS, .y = 150 + i*(SC_HEIGHT- 200)/ROWS};
                    Vector2 en = {.x = 100 + (j-3)*(SC_WIDTH - 100)/COLS, .y = 150 + (i-3)*(SC_HEIGHT- 200)/ROWS};
                    DrawLineEx(st, en, 10.0f, DARKGREEN);
                }
            }
        }
    }
}

And connect.c + the typedefs:

typedef enum{
    EMPTY = 0,
    PLAYER = 1,
    COMP = 2,
}state;

typedef struct{
    int row;
    int col;
}position;
#include "include/connect.h"
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ROWS 6
#define COLS 7

bool inInterval(int x, int min, int max){ // inclusive
    if(x <= max && x >= min){
        return true;
    }
    return false;
}

int checkCol(state board[ROWS][COLS], int startRow, int startCol){
    int cnt = 0;
    int i = startRow;
    if (i-3 < 0) return 0;
    while(board[i][startCol] == board[startRow][startCol]){
        cnt++;
        i--;
    }
    return cnt;
}

int checkRow(state board[ROWS][COLS], int startRow, int startCol){
    int cnt = 0;
    int i = startCol;
    if(i+3 > COLS-1) return 0;
    while(board[startRow][i] == board[startRow][startCol]){
        cnt++;
        i++;
    }
    return cnt;
}

int checkDiag(state board[ROWS][COLS], int startRow, int startCol){
    int cnt = 0;
    int row = startRow;
    int col = startCol;
    if(row - 3 < 0 || col + 3 > COLS-1) return 0;
    while(board[row][col] == board[startRow][startCol]){
        cnt++;
        row--;
        col++;
    }
    return cnt;
}

int checkDiagb(state board[ROWS][COLS], int startRow, int startCol){
    int cnt = 0;
    int row = startRow;
    int col = startCol;
    if(row-3 < 0 || col -3 < 0) return 0;
    while(board[row][col] == board[startRow][startCol]){
        cnt++;
        row--;
        col--;
    }
    return cnt;
}

bool boardFull(state board[ROWS][COLS]){
    for(int i = 0; i < ROWS; i++){
        for(int j = 0; j < COLS; j++){
            if(board[i][j] == EMPTY){
                return false;
            }
        }
    }
    return true;
}

int win(state board[ROWS][COLS]){
    for(int i = ROWS-1; i >= 0; i--){
        for(int j = 0; j < COLS; j++){
            if(board[i][j] != EMPTY){
                if(checkCol(board, i, j) == 4 || checkRow(board, i, j) == 4 || checkDiag(board, i, j) == 4 || checkDiagb(board, i,j) == 4){
                    switch(board[i][j]){
                        case PLAYER: return PLAYER;
                            break;
                        case COMP: return COMP;
                            break;
                        case EMPTY: continue;
                            break;
                    }
                }
            }
        }
    }
    if(boardFull(board)) return -1;
    return 0;
}

int max(int a, int b){
    if(a>b) return a;
    else return b;
}

int min(int a, int b){
    if(a>b) return b;
    else return a;
}

// win > block enemy > make3s > make 2s
// win if tmp == 1 || 2 --> ez külön eset rögtön return
// block enemy: if enemy has 3 in a row and the next one is yours
// make3s ugyanaz mint eddig
// make 2s ugyanaz

int newevaluate(state arr[ROWS][COLS]){
    int won = win(arr);
    if(won == 2) return 100;
    else if(won == 1) return -100;
    else if(won == -1) return 0;

    int blockP = 0, threeP = 0, twoP = 0, blockP2 = 0; 
    int blockC = 0, threeC = 0, twoC = 0, blockC2 = 0;

    for(int i = ROWS-1; i >= 0; i--){
        for(int j = 0; j < COLS ; j++){
            if(arr[i][j] == COMP){
                if(checkDiag(arr, i, j) == 3){
                    threeC++;
                    if(arr[i-3][j+3] == PLAYER) blockP++;
                }
                else if(checkDiag(arr, i, j) == 2){
                    twoC++;
                    if(arr[i-2][i+2] == PLAYER) blockP2++;
                }
                if(checkDiagb(arr, i, j) == 3){
                    threeC++;
                    if(arr[i-3][j-3] == PLAYER) blockP++;
                }
                else if(checkDiagb(arr, i, j) == 2){
                    twoC++;
                    if(arr[i-2][j-2] == PLAYER) blockP2++;
                }
                if(checkRow(arr, i, j) == 3){
                    threeC++;
                    if(arr[i][j+3] == PLAYER) blockP++;
                }
                else if(checkRow(arr, i, j) == 2){
                    twoC++;
                    if(arr[i][j+2] == PLAYER) blockP2++;
                } 
                if(checkCol(arr, i, j) == 3){
                    threeC++;
                    if(arr[i-3][j] == PLAYER) blockP++;
                }
                else if(checkCol(arr, i, j) == 2){
                    twoC++;
                    if(arr[i-2][j] == PLAYER) blockP2++;
                }
            }
            else if(arr[i][j] == PLAYER){
                if(checkDiag(arr, i, j) == 3){
                    threeP++;
                    if(arr[i-3][j+3] == COMP) blockC++;
                }
                else if(checkDiag(arr, i, j) == 2){
                    twoP++;
                    if(arr[i-2][j+2] == COMP) blockC2++;
                }
                if(checkDiagb(arr, i, j) == 3){
                    threeP++;
                    if(arr[i-3][j-3] == COMP) blockC++;
                }
                else if(checkDiagb(arr, i, j) == 2){
                    twoP++;
                    if(arr[i-2][j-2] == COMP) blockC2++;
                }
                if(checkRow(arr, i, j) == 3){
                    threeP++;
                    if(arr[i][j+3] == COMP) blockC++;
                }
                else if(checkRow(arr, i, j) == 2){
                    twoP++;
                    if(arr[i][j+2] == COMP) blockC2++;
                }
                if(checkCol(arr, i, j) == 3){
                    threeP++;
                    if(arr[i-3][j] == COMP) blockC++;
                }
                else if(checkCol(arr, i, j) == 2){
                    twoP++;
                    if(arr[i-2][j] == COMP) blockC2++;
                } 
            }
        }
    }
    int ret = (2*blockC2 + blockC + 2*threeC + twoC) - (2*blockP2 + blockP + 2*threeP + twoP);
    return ret;
}

void legalmoves(state board[ROWS][COLS], position moves[COLS]){
    int cnt = 0;
    for(int i = 0; i < COLS; i++){
        for(int j = ROWS-1; j >= 0; j--){
            if(board[j][i] == EMPTY) {
                moves[cnt].row = j;
                moves[cnt].col = i;
                cnt++;
                if(cnt >= COLS) return;
                break;
            }
        }
    }
}

int minmax(state arr[ROWS][COLS], int isMaximizing, int depth, int alpha, int beta){

    int score = newevaluate(arr);
    if(score == -100 || score == 100 || depth > 7) return score;
    else if(boardFull(arr)) return 0;

    position moves[COLS];  
    memset(moves, -1, sizeof(moves));

    if(isMaximizing){
        int best = -10000;
        legalmoves(arr, moves);
        for(int i = 0; i < COLS; i++){
            if(moves[i].row != -1){
                arr[moves[i].row][moves[i].col] = COMP;
                int eval = minmax(arr, 0, depth + 1, alpha, beta);
                best = max(best, eval);
                arr[moves[i].row][moves[i].col] = EMPTY;
                // if(eval == 100) return eval;
                alpha = max(alpha, eval);
                if(beta <= alpha) break;
            }
            else break;
        }
        return best - depth;
    }
    else{
        int best = 10000;
        legalmoves(arr, moves);
        for(int i = 0; i < COLS; i++){
            if(moves[i].row != -1){
                arr[moves[i].row][moves[i].col] = PLAYER;
                int eval = minmax(arr, 1, depth + 1, alpha, beta);
                best = min(best, eval);
                arr[moves[i].row][moves[i].col] = EMPTY;
                // if(eval == -100) return eval;
                beta = min(beta, eval);
                if(beta <= alpha) break;
            }
            else break;
        }
        return best + depth;
    }
}

position findBestmove(state arr[ROWS][COLS]){
    int bestVal = -10000;
    position bestMove;
    position moves[COLS];
    memset(moves, -1, sizeof(moves));

    legalmoves(arr, moves);
    for(int i = 0; i < COLS; i++){
        if(moves[i].row != -1){
            arr[moves[i].row][moves[i].col] = COMP;
            int moveVal = minmax(arr, 0, 0, -10000000, 10000000);
            if(moveVal > bestVal){
                bestMove.row = moves[i].row;
                bestMove.col = moves[i].col;
                bestVal = moveVal;
            }
            arr[moves[i].row][moves[i].col] = EMPTY;
            // if(bestVal == 100) return  bestMove;
        } 
    }
    return bestMove;
}

void computermove(state arr[ROWS][COLS], position move){
    arr[move.row][move.col] = COMP;
}
\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$

Is it bad practice to use global variables?

In this case, yes, a weak practice. Better if the game used a struct with all the game elements in it and then a pointer to that struct was passed around.

Is it a bad practice that in the main function I only initialize basic things ... ?

This goes along with the above. An important goal of coding is re-use and abstraction - only exposing what the higher level code needs to see. Try to make the entire game play as a function, say called game_play().

// Illustrative code
int main(int argc, char *argv[]) {
  struct game_options go = { 0 };  // Game rows, columns, depth limits, ... 
  if (game_process_options(&go, argc, argv)) {
    fprintf(stderr, "Invalid game options.\n");
    return EXIT_FAILURE;
  }

  struct game g = { 0 }; // Game state
  return game_play(&g, &go);
}

  

Minor Stuff

Simplify bool creation

//if(x <= max && x >= min){
//    return true;
//}
//return false;
return x <= max && x >= min;

Use const for referenced data that does not change

This allows usage with const data and may allow optimizations not readily seen by the compiler.

// int checkCol(state board[ROWS][COLS], int startRow, int startCol){
int checkCol(const state board[ROWS][COLS], int startRow, int startCol){

Naked magic numbers

Code has too many constants just laying around with not documentation. What is 100?, -10000?

// if(score == -100 || score == 100 || depth > 7) return score;
#define WIN_SCORE 100
#define LOSE_SCORE (-WIN_SCORE)
#define DEPTH_MAX 7
if(score == LOSE_SCORE || score == WINL_SCORE || depth > DEPTH_MAX) return score;

if(isMaximizing){
    // int best = -10000;
    int best = INT_MIN;

Advanced: Think big

Consider col + 3 may overflow int math. Of course that would mean col is some large value near INT_MAX - not a concern for this learner code.

if(row - 3 < 0 || col + 3 > COLS-1) return 0;

Yet start to think big - at what point does code fail? Consider the alternative - it has no such limit for all row, col.

if(row < 3 || col > COLS-1-3) return 0;

For now code for clarity. As time goes on, you can code for clarity and for the entire range of variables.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks! One more follow up on the constants. Is it enough to define them in the header file or should I define them in every file? I know it compiles if they are only in the header file, but maybe for better readability. \$\endgroup\$
    – Maxell
    Commented Jul 6, 2022 at 23:21
  • \$\begingroup\$ @Maxell In connect4.h, define everything that the user needs to know. In connect4_private.h, define all that only your implementation needs if you are using multiple .c files, else define those in the beginning of connect4.c. Do not define in multiple places. \$\endgroup\$ Commented Jul 6, 2022 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.