Squava Game with Mini_Max algorithm
Hey guys, I've been working for a while on a game code called Squava which is basically a game similar to tic-tac-toe but in [5x5] array.
The difference here is if a player reaches 3 in a row first loses, but if reaches 4 in a row first wins.
I use the Mini_Max algorithm to get the best next possible step first, but I stucked in an infinity loop.:/
If you have any advice I'd really appreciate it.
Please post the relevant section of the code here - People don't like downloading files from strangers off the internet
Here you goCode:#include <stdio.h> #include <stdlib.h> #include <time.h> #include <ctype.h> int won = 0; #define max(a,b) (((a) > (b)) ? (a) : (b)) #define min(a,b) (((a) > (b)) ? (b) : (a)) typedef enum { false, true } bool; /* For player moves */ struct move { int x; int y; }move; /* Moves are defined as: */ char player1 = 'X'; char player2 = 'O'; int losing_triplets(char board[5][5]) { int losing[48][6]={ { 0, 0 , 1, 0 , 2, 0 }, { 0, 0 , 0, 1 , 0, 2 }, { 0, 0 , 1, 1 , 2, 2 }, { 1, 0 , 2, 0 , 3, 0 }, { 1, 0 , 1, 1 , 1, 2 }, { 1, 0 , 2, 1 , 3, 2 }, { 2, 0 , 3, 0 , 4, 0 }, { 2, 0 , 2, 1 , 2, 2 }, { 2, 0 , 1, 1 , 0, 2 }, { 2, 0 , 3, 1 , 4, 2 }, { 3, 0 , 3, 1 , 3, 2 }, { 3, 0 , 2, 1 , 1, 2 }, { 4, 0 , 4, 1 , 4, 2 }, { 4, 0 , 3, 1 , 2, 2 }, { 0, 1 , 1, 1 , 2, 1 }, { 0, 1 , 0, 2 , 0, 3 }, { 0, 1 , 1, 2 , 2, 3 }, { 1, 1 , 2, 1 , 3, 1 }, { 1, 1 , 1, 2 , 1, 3 }, { 1, 1 , 2, 2 , 3, 3 }, { 2, 1 , 3, 1 , 4, 1 }, { 2, 1 , 2, 2 , 2, 3 }, { 2, 1 , 1, 2 , 0, 3 }, { 2, 1 , 3, 2 , 4, 3 }, { 3, 1 , 3, 2 , 3, 3 }, { 3, 1 , 2, 2 , 1, 3 }, { 4, 1 , 4, 2 , 4, 3 }, { 4, 1 , 3, 2 , 2, 3 }, { 0, 2 , 1, 2 , 2, 2 }, { 0, 2 , 0, 3 , 0, 4 }, { 0, 2 , 1, 3 , 2, 4 }, { 1, 2 , 2, 2 , 3, 2 }, { 1, 2 , 1, 3 , 1, 4 }, { 1, 2 , 2, 3 , 3, 4 }, { 2, 2 , 3, 2 , 4, 2 }, { 2, 2 , 2, 3 , 2, 4 }, { 2, 2 , 1, 3 , 0, 4 }, { 2, 2 , 3, 3 , 4, 4 }, { 3, 2 , 3, 3 , 3, 4 }, { 3, 2 , 2, 3 , 1, 4 }, { 4, 2 , 4, 3 , 4, 4 }, { 4, 2 , 3, 3 , 2, 4 }, { 0, 3 , 1, 3 , 2, 3 }, { 1, 3 , 2, 3 , 3, 3 }, { 2, 3 , 3, 3 , 4, 3 }, { 0, 4 , 1, 4 , 2, 4 }, { 1, 4 , 2, 4 , 3, 4 }, { 2, 4 , 3, 4 , 4, 4 }}; int i,j; int sum_player1=0; int sum_player2=0; for(i=0;i<48;i++){ for(j=0;j<6;j+=2) { int a=losing[i][j]; int b=losing[i][j+1]; if(board[a][b]==player1) sum_player1++; else if(board[a][b]==player2) sum_player2++; } if(sum_player1==3) return 1; else if(sum_player2==3) return 2; sum_player1=0; sum_player2=0; }; return 0; } int winning_quads(char board[5][5]){ int winning[28][8]={ { 0, 0 , 1, 0 , 2, 0 , 3, 0 }, { 0, 0 , 0, 1 , 0, 2 , 0, 3 }, { 0, 0 , 1, 1 , 2, 2 , 3, 3 }, { 0, 1 , 1, 1 , 2, 1 , 3, 1 }, { 0, 1 , 0, 2 , 0, 3 , 0, 4 }, { 0, 1 , 1, 2 , 2, 3 , 3, 4 }, { 0, 2 , 1, 2 , 2, 2 , 3, 2 }, { 0, 3 , 1, 3 , 2, 3 , 3, 3 }, { 0, 4 , 1, 4 , 2, 4 , 3, 4 }, { 1, 0 , 2, 0 , 3, 0 , 4, 0 }, { 1, 0 , 1, 1 , 1, 2 , 1, 3 }, { 1, 0 , 2, 1 , 3, 2 , 4, 3 }, { 1, 1 , 2, 1 , 3, 1 , 4, 1 }, { 1, 1 , 1, 2 , 1, 3 , 1, 4 }, { 1, 1 , 2, 2 , 3, 3 , 4, 4 }, { 1, 2 , 2, 2 , 3, 2 , 4, 2 }, { 1, 3 , 2, 3 , 3, 3 , 4, 3 }, { 1, 4 , 2, 4 , 3, 4 , 4, 4 }, { 2, 0 , 2, 1 , 2, 2 , 2, 3 }, { 2, 1 , 2, 2 , 2, 3 , 2, 4 }, { 3, 0 , 3, 1 , 3, 2 , 3, 3 }, { 3, 0 , 2, 1 , 1, 2 , 0, 3 }, { 3, 1 , 3, 2 , 3, 3 , 3, 4 }, { 3, 1 , 2, 2 , 1, 3 , 0, 4 }, { 4, 0 , 4, 1 , 4, 2 , 4, 3 }, { 4, 0 , 3, 1 , 2, 2 , 1, 3 }, { 4, 1 , 4, 2 , 4, 3 , 4, 4 }, { 4, 1 , 3, 2 , 2, 3 , 1, 4 }}; int i,j; int sum_player1=0; int sum_player2=0; for(i=0;i<28;i++){ for(j=0;j<8;j+=2) { int a=winning[i][j]; int b=winning[i][j+1]; if(board[a][b]==player1) sum_player1++; else if(board[a][b]==player2) sum_player2++; } if(sum_player1==4) return 10; else if(sum_player2==4) return -10; sum_player1=0; sum_player2=0; } return 0; } void rules () { printf("* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - *\n"); printf("Squava_with_MiniMax_Algorithm\n"); printf("Adja meg a jatek jelenlegi allasat, ha nincs implementalva\n"); printf("Az algoritmus megadja a rakovetkezo legjobb lepest\n"); printf("* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - *\n"); } void board_initialization (char board[5][5]) { /* To initialize every cell as '_' */ for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { board[i][j] = '_'; } } } void print_board (char board[5][5]) { for(int i=0;i<5;i++) { for(int j=0;j<5;j++) { printf("%c\t",board[i][j]); } printf("\n"); } } void check_board (char board[5][5]) { if(winning_quads(board)!=0) won++; else if(losing_triplets(board)!=0) won++; } int move_verification (char board[5][5]) { /* To check if any more moves can be made */ for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) if (board[i][j] == '_') return true; return false; } int minimax (char board[5][5], int depth, int isMax) { /* Check for the terminal points ( will return 0 if the depth is yet to be reached ) */ int score = winning_quads(board); int score_lose= losing_triplets(board); /* We will first check whether the game can be terminated with the current possible score */ /* If maximizer has won / minimizer has lost */ if (score == 10 || score_lose == 2) return score; /* If minimizer has won / maximizer has lost */ if (score == -10 || score_lose == 1) return score; /* If no more moves can be made */ if (move_verification(board) == false) return 0; /* If it is maximizer's move * Remember that the goal of maximizer is to attain the highest possible score */ if (isMax == 1) { /* Initialize a lowest point of comparision */ int best = -1000; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { if (board[i][j]=='_') { board[i][j] = player1; /* Make your move */ /* We are traversing one more step in the tree and are making minimizer play the next move */ best = max(best, minimax(board,depth+1,0)); /* Find the maximizer's move */ board[i][j] = '_'; /* Undo your move */ } } } return best; } /* If it is minimizer's move * Remember that the goal of minimizer is to attain the lowest possible score */ else { /* Initialize a lowest point of comparision */ int best = 1000; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { if (board[i][j]=='_') { board[i][j] = player2; /* Make your move */ /* We are traversing one more step in the tree and are making maximizer play the next move */ best = min(best, minimax(board,depth+1,1)); /* Find the minimizer's move */ board[i][j] = '_'; /* Undo your move */ } } } return best; } } void player1_plays (char board[5][5]) { /* Initialize the player1 moves */ struct move play; play.x = -1; play.y = -1; /* Initialize a lowest point of comparision */ int best_val = -1000; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { /* If a move is valid, try it */ if (board[i][j] == '_') { board[i][j] = player1; /* Make the move */ int move_val = minimax(board, 0, 0); /* Find the value from the minimax function */ board[i][j] = '_'; /* Undo the move */ /* If the current move is better than the best move, then change the best move */ if (move_val > best_val) { best_val = move_val; play.x = i; play.y = j; } } } } /* Finally make the player1 Move */ board[play.x][play.y] = player1; } void player2_plays (char board[5][5]) { /* Initialize the player2 moves */ struct move play; play.x = -1; play.y = -1; int best_val = 1000; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { /* If a move is valid, try it */ if (board[i][j] == '_') { board[i][j] = player2; /* Make the move */ int move_val = minimax(board, 0, 0); /* Find the value from the minimax function */ board[i][j] = '_'; /* Undo the move */ /* If the current move is better than the best move, then change the best move */ if (move_val < best_val) { best_val = move_val; play.x = i; play.y = j; } } } } /* Finally make the player2 Move */ board[play.x][play.y] = player2; } void player1_move (char board[5][5]) { player1_plays(board); check_board(board); print_board(board); } void player2_move (char board[5][5]) { player2_plays(board); check_board(board); print_board(board); } int get_player(){ int player=0; printf("Adja meg melyik jatekos kovetkezik 1 vagy 2:\n"); scanf("%d",&player); if(player==1) return 1; else if(player==2) return 2; else return 0; } int main (void) { char board[5][5]={ {'_','_','_','O','_',}, {'_','X','_','_','_',}, {'_','_','_','O','_',}, {' ','X','_','O','_',}, {'_','X','_','_','_',}, }; rules(); //board_initialization(board); print_board(board); int plyr=get_player(); while(won != 1 && move_verification(board) == true) { if(plyr==1){ player1_move(board); if(won==1) break; } else if(plyr==2){ player2_move(board); if(won==1) break; } else break; if (move_verification(board) == false) { printf("It's a draw !\n"); break; } } return 0; }
C has had a standard boolean type called "bool" since C99 (and it is a true boolean because a bool variable can't be any value besides 0 or 1). I would recommend using that instead of making your own type. Be sure to #include <stdbool.h>.Originally Posted by gszab
I've added in something to help you understand what is happening in your code...
I select user 1 and the programme does not stop - Run the code above and see where it is goingCode:#include <stdio.h> #include <stdlib.h> #include <time.h> #include <ctype.h> int won = 0; #define max(a,b) (((a) > (b)) ? (a) : (b)) #define min(a,b) (((a) > (b)) ? (b) : (a)) #define DEBUG typedef enum { false, true } bool; /* For player moves */ struct move { int x; int y; } move; /* Moves are defined as: */ char player1 = 'X'; char player2 = 'O'; int losing_triplets(char board[5][5]) { #ifdef DEBUG puts("losing_triplets"); getchar(); #endif // DEBUG int losing[48][6]= { { 0, 0, 1, 0, 2, 0 }, { 0, 0, 0, 1, 0, 2 }, { 0, 0, 1, 1, 2, 2 }, { 1, 0, 2, 0, 3, 0 }, { 1, 0, 1, 1, 1, 2 }, { 1, 0, 2, 1, 3, 2 }, { 2, 0, 3, 0, 4, 0 }, { 2, 0, 2, 1, 2, 2 }, { 2, 0, 1, 1, 0, 2 }, { 2, 0, 3, 1, 4, 2 }, { 3, 0, 3, 1, 3, 2 }, { 3, 0, 2, 1, 1, 2 }, { 4, 0, 4, 1, 4, 2 }, { 4, 0, 3, 1, 2, 2 }, { 0, 1, 1, 1, 2, 1 }, { 0, 1, 0, 2, 0, 3 }, { 0, 1, 1, 2, 2, 3 }, { 1, 1, 2, 1, 3, 1 }, { 1, 1, 1, 2, 1, 3 }, { 1, 1, 2, 2, 3, 3 }, { 2, 1, 3, 1, 4, 1 }, { 2, 1, 2, 2, 2, 3 }, { 2, 1, 1, 2, 0, 3 }, { 2, 1, 3, 2, 4, 3 }, { 3, 1, 3, 2, 3, 3 }, { 3, 1, 2, 2, 1, 3 }, { 4, 1, 4, 2, 4, 3 }, { 4, 1, 3, 2, 2, 3 }, { 0, 2, 1, 2, 2, 2 }, { 0, 2, 0, 3, 0, 4 }, { 0, 2, 1, 3, 2, 4 }, { 1, 2, 2, 2, 3, 2 }, { 1, 2, 1, 3, 1, 4 }, { 1, 2, 2, 3, 3, 4 }, { 2, 2, 3, 2, 4, 2 }, { 2, 2, 2, 3, 2, 4 }, { 2, 2, 1, 3, 0, 4 }, { 2, 2, 3, 3, 4, 4 }, { 3, 2, 3, 3, 3, 4 }, { 3, 2, 2, 3, 1, 4 }, { 4, 2, 4, 3, 4, 4 }, { 4, 2, 3, 3, 2, 4 }, { 0, 3, 1, 3, 2, 3 }, { 1, 3, 2, 3, 3, 3 }, { 2, 3, 3, 3, 4, 3 }, { 0, 4, 1, 4, 2, 4 }, { 1, 4, 2, 4, 3, 4 }, { 2, 4, 3, 4, 4, 4 } }; int i,j; int sum_player1=0; int sum_player2=0; for(i=0; i<48; i++) { for(j=0; j<6; j+=2) { int a=losing[i][j]; int b=losing[i][j+1]; if(board[a][b]==player1) sum_player1++; else if(board[a][b]==player2) sum_player2++; } if(sum_player1==3) return 1; else if(sum_player2==3) return 2; sum_player1=0; sum_player2=0; }; return 0; } int winning_quads(char board[5][5]) { #ifdef DEBUG puts("winning_quads");getchar(); #endif // DEBUG int winning[28][8]= { { 0, 0, 1, 0, 2, 0, 3, 0 }, { 0, 0, 0, 1, 0, 2, 0, 3 }, { 0, 0, 1, 1, 2, 2, 3, 3 }, { 0, 1, 1, 1, 2, 1, 3, 1 }, { 0, 1, 0, 2, 0, 3, 0, 4 }, { 0, 1, 1, 2, 2, 3, 3, 4 }, { 0, 2, 1, 2, 2, 2, 3, 2 }, { 0, 3, 1, 3, 2, 3, 3, 3 }, { 0, 4, 1, 4, 2, 4, 3, 4 }, { 1, 0, 2, 0, 3, 0, 4, 0 }, { 1, 0, 1, 1, 1, 2, 1, 3 }, { 1, 0, 2, 1, 3, 2, 4, 3 }, { 1, 1, 2, 1, 3, 1, 4, 1 }, { 1, 1, 1, 2, 1, 3, 1, 4 }, { 1, 1, 2, 2, 3, 3, 4, 4 }, { 1, 2, 2, 2, 3, 2, 4, 2 }, { 1, 3, 2, 3, 3, 3, 4, 3 }, { 1, 4, 2, 4, 3, 4, 4, 4 }, { 2, 0, 2, 1, 2, 2, 2, 3 }, { 2, 1, 2, 2, 2, 3, 2, 4 }, { 3, 0, 3, 1, 3, 2, 3, 3 }, { 3, 0, 2, 1, 1, 2, 0, 3 }, { 3, 1, 3, 2, 3, 3, 3, 4 }, { 3, 1, 2, 2, 1, 3, 0, 4 }, { 4, 0, 4, 1, 4, 2, 4, 3 }, { 4, 0, 3, 1, 2, 2, 1, 3 }, { 4, 1, 4, 2, 4, 3, 4, 4 }, { 4, 1, 3, 2, 2, 3, 1, 4 } }; int i,j; int sum_player1=0; int sum_player2=0; for(i=0; i<28; i++) { for(j=0; j<8; j+=2) { int a=winning[i][j]; int b=winning[i][j+1]; if(board[a][b]==player1) sum_player1++; else if(board[a][b]==player2) sum_player2++; } if(sum_player1==4) return 10; else if(sum_player2==4) return -10; sum_player1=0; sum_player2=0; } return 0; } void rules () { #ifdef DEBUG puts("rules");getchar(); #endif // DEBUG printf("* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - *\n"); printf("Squava_with_MiniMax_Algorithm\n"); printf("Adja meg a jatek jelenlegi allasat, ha nincs implementalva\n"); printf("Az algoritmus megadja a rakovetkezo legjobb lepest\n"); printf("* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - *\n"); } void board_initialization (char board[5][5]) { #ifdef DEBUG puts("board_initialization");getchar(); #endif // DEBUG /* To initialize every cell as '_' */ for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { board[i][j] = '_'; } } } void print_board (char board[5][5]) { #ifdef DEBUG puts("print_board");getchar(); #endif // DEBUG for(int i=0; i<5; i++) { for(int j=0; j<5; j++) { printf("%c\t",board[i][j]); } printf("\n"); } } void check_board (char board[5][5]) { #ifdef DEBUG puts("check_board");getchar(); #endif // DEBUG if(winning_quads(board)!=0) won++; else if(losing_triplets(board)!=0) won++; } int move_verification (char board[5][5]) { #ifdef DEBUG puts("move_verification");getchar(); #endif // DEBUG /* To check if any more moves can be made */ for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) if (board[i][j] == '_') return true; return false; } int minimax (char board[5][5], int depth, int isMax) { #ifdef DEBUG puts("minimax");getchar(); #endif // DEBUG /* Check for the terminal points ( will return 0 if the depth is yet to be reached ) */ int score = winning_quads(board); int score_lose= losing_triplets(board); /* We will first check whether the game can be terminated with the current possible score */ /* If maximizer has won / minimizer has lost */ if (score == 10 || score_lose == 2) return score; /* If minimizer has won / maximizer has lost */ if (score == -10 || score_lose == 1) return score; /* If no more moves can be made */ if (move_verification(board) == false) return 0; /* If it is maximizer's move * Remember that the goal of maximizer is to attain the highest possible score */ if (isMax == 1) { /* Initialize a lowest point of comparision */ int best = -1000; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { if (board[i][j]=='_') { board[i][j] = player1; /* Make your move */ /* We are traversing one more step in the tree and are making minimizer play the next move */ best = max(best, minimax(board,depth+1,0)); /* Find the maximizer's move */ board[i][j] = '_'; /* Undo your move */ } } } return best; } /* If it is minimizer's move * Remember that the goal of minimizer is to attain the lowest possible score */ else { /* Initialize a lowest point of comparision */ int best = 1000; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { if (board[i][j]=='_') { board[i][j] = player2; /* Make your move */ /* We are traversing one more step in the tree and are making maximizer play the next move */ best = min(best, minimax(board,depth+1,1)); /* Find the minimizer's move */ board[i][j] = '_'; /* Undo your move */ } } } return best; } } void player1_plays (char board[5][5]) { #ifdef DEBUG puts("player1_plays"); getchar(); #endif // DEBUG /* Initialize the player1 moves */ struct move play; play.x = -1; play.y = -1; /* Initialize a lowest point of comparision */ int best_val = -1000; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { /* If a move is valid, try it */ if (board[i][j] == '_') { board[i][j] = player1; /* Make the move */ int move_val = minimax(board, 0, 0); /* Find the value from the minimax function */ board[i][j] = '_'; /* Undo the move */ /* If the current move is better than the best move, then change the best move */ if (move_val > best_val) { best_val = move_val; play.x = i; play.y = j; } } } } /* Finally make the player1 Move */ board[play.x][play.y] = player1; } void player2_plays (char board[5][5]) { #ifdef DEBUG puts("player2_plays");getchar(); #endif // DEBUG /* Initialize the player2 moves */ struct move play; play.x = -1; play.y = -1; int best_val = 1000; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { /* If a move is valid, try it */ if (board[i][j] == '_') { board[i][j] = player2; /* Make the move */ int move_val = minimax(board, 0, 0); /* Find the value from the minimax function */ board[i][j] = '_'; /* Undo the move */ /* If the current move is better than the best move, then change the best move */ if (move_val < best_val) { best_val = move_val; play.x = i; play.y = j; } } } } /* Finally make the player2 Move */ board[play.x][play.y] = player2; } void player1_move (char board[5][5]) { #ifdef DEBUG puts("player1_move");getchar(); #endif // DEBUG player1_plays(board); check_board(board); print_board(board); } void player2_move (char board[5][5]) { #ifdef DEBUG puts("player2_move");getchar(); #endif // DEBUG player2_plays(board); check_board(board); print_board(board); } int get_player() { #ifdef DEBUG puts("get_player");getchar(); #endif // DEBUG int player=0; printf("Adja meg melyik jatekos kovetkezik 1 vagy 2:\n"); scanf("%d",&player); if(player==1) return 1; else if(player==2) return 2; else return 0; } int main (void) { char board[5][5]= { {'_','_','_','O','_',}, {'_','X','_','_','_',}, {'_','_','_','O','_',}, {' ','X','_','O','_',}, {'_','X','_','_','_',}, }; rules(); //board_initialization(board); print_board(board); int plyr=get_player(); while(won != 1 && move_verification(board) == true) { if(plyr==1) { player1_move(board); if(won==1) break; } else if(plyr==2) { player2_move(board); if(won==1) break; } else break; if (move_verification(board) == false) { printf("It's a draw !\n"); break; } } return 0; }
Fact - Beethoven wrote his first symphony in C
