### Help with minimax algorithm

Hi. I'm trying to implement the minimax algorithm described here: http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html . Basically I want a human player to be able to play tic tac toe against a computer, on a board ranging from n=3 to n=10, where the board size is n by n.

I've implemented a large portion of the functionality but for some reason the minimax function is very dumb. It does not seem to be arriving at the best solution despite my efforts to follow the algorithm. I was hoping someone here had a suggestion on what is going wrong.

Here is the code:

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273`` ``````#include #include #include #include // Function declarations void clearScrn(); // Prints a lot of new lines to "clear" screen void drawBoard(char*); // Draw current state of board char boardWin(char*, int); // Evaluate if board is in won state int minimax(char, char*, int); // The source of all frustration in this assignment // Variables int n = 0; int m = 0; int turn = 0; int move = -1; int main(int argc, char** argv){ // Process arguments if(argc < 4 || argc > 4){ std::cout << "Invalid arguments:\n./proj2 \n"; return 1; } if (strlen(argv[1]) >= 2) // Handle max n = 10 n = 10; else n = argv[1][0] - 0x30; // n x n board m = argv[2][0] - 0x30; // m marks in a line to win char turn = *argv[3]; // 'h' for human's turn, 'c' for computer's turn // Set pieces char humanPiece, compPiece; if(turn == 'h'){ // Human goes first humanPiece = 'X'; compPiece = 'O'; } else { humanPiece = 'O'; compPiece = 'X'; } // Create the board char board[n*n]; // Blank all cells for(int i = 0; i < n*n; i++) board[i] = ' '; // Print instructions and blank board std::cout << "Enter a coordinate from 1 to " << n << " in the form: x y\n\n"; drawBoard(board); // Start game loop int movex = 0; int movey = 0; char status; while(true){ if(turn == 'h'){ std::cout << "> "; std::cin >> movex >> movey; move = ((movex-1) * n) + (movey-1); board[move] = humanPiece; turn = 'c'; } else if(turn == 'c'){ clearScrn(); // Clear screen minimax(compPiece, board, move); drawBoard(board); turn = 'h'; } // After making a move, evaluate the board status = boardWin(board, move); if(status != '0') break; } // Print ending game message clearScrn(); drawBoard(board); if ( status == humanPiece) std::cout << "Human player won!\n"; else if (status == compPiece) std::cout << "Computer won!\n"; else std::cout << "Draw!\n"; return 0; } int minimax(char player, char* board, int p){ // First check if board is won char state = boardWin(board, p); if (state == 'X') return 1; if (state == 'O') return -1; if (state == 'D') return 0; // Get a list of all legal moves for player std::vector moves; char temp_board[n*n]; for(int i = 0; i < n*n; i++){ temp_board[i] = board[i]; if(board[i] == ' '){ moves.push_back(i); } } int result; int current; if (player == 'X'){ // MAX result = -99; for(std::vector::iterator it = moves.begin(); it != moves.end(); it++){ temp_board[*it] = 'X'; current = minimax('O', temp_board, *it); if (result < current){ result = current; move = *it; } } board[move] = 'X'; } if (player == 'O'){ // MIN result = 99; for(std::vector::iterator it = moves.begin(); it != moves.end(); it++){ temp_board[*it] = 'O'; current = minimax('X', temp_board, *it); if (result > current){ result = current; move = *it; } } board[move] = 'O'; } return result; } /* boardWin * * Given a board state and the last move p, evaluate if the board is in a won state * Returns X, O if winner; D if drawn; 0 if no winner and not drawn */ char boardWin(char* board, int p){ // Pass -1 for a blank board state if (p < 0) return 0; // Determine pieces to check char piece = board[p]; // First see if there is a vertical win int match = 0; for(int i = p; i-n >= 0; i -= n){ // Look above the position if(board[i] == board[i-n]){ //std::cout << "1) Match at: " << i << " " << i-n << "\n"; match++; } else break; } for(int i = p; i+n < n*n; i += n){ // Look below the position if(board[i] == board[i+n]){ //std::cout << "2) Match at: " << i << " " << i+n << "\n"; match++; } else break; } if (match >= m-1) return piece; // No vertical win, proceed to horizontal check match = 0; // Reset match counter for(int i = p; i > p - (p%n); i--){ // Look to the left if(board[i] == board[i-1]){ //std::cout << "3) Match at: " << i << " " << i-1 << "\n"; match++; } else break; } for(int i = p; i < (p+n) - (p%n) - 1; i++){ // Look to the right if(board[i] == board[i+1]){ //std::cout << "4) Match at: " << i << " " << i+1<< "\n"; match++; } else break; } if (match >= m-1) return piece; // Check for a diagonal win match = 0; for(int i = p; i < (n*n) - n - 1; i += n+1){ // Look south-east if(board[i] == board[i+n+1] && (i+1)%n != 0){ //std::cout << "5) Match at: " << i << " " << i+n+1<< "\n"; match++; } else break; } for(int i = p; i > n; i = (i-n)-1){ if(board[i] == board[i-n-1] && i%n != 0){ // Look north-west //std::cout << "6) Match at: " << i << " " << i-n-1<< "\n"; match++; } else break; } if (match >= m-1) return piece; // Check for other diagonal match = 0; for(int i = p; i < (n*n)-n; i += (n-1)){ // Look south-west if(board[i] == board[i+n-1] && i%n != 0){ //std::cout << "7) Match at: " << i << " " << i+n-1<< "\n"; match++; } else break; } for(int i = p; i > n; i -= (n+1)){ // Look north-east if(board[i] == board[i-n+1] && (i+1)%n != 0){ //std::cout << "8) Match at: " << i << " " << i-n+1<< "\n"; match++; } else break; } if (match >= m-1) return piece; // Check if the board is drawn bool drawn = true; for(int i = 0; i < n*n; i++){ if(board[i] == ' ') drawn = false; } if (drawn) return 'D'; // No match found return '0'; } void drawBoard(char* board){ for(int i=0; i < n; i++){ // Row for(int j=0; j
Topic archived. No new replies allowed.