🔒 Locked

ANOTHER minimax(negamax) question...

Started by core-nuts Dec 11, 2005 at 2:30 PM 4 replies 1.8k views

Original Post

Dec 11, 2005 at 2:30 PM

Hi, as you can see I've posted a couple of questions recently trying to get down the basics of the minimax algorithm. I decided to go with negamax and I THOUGHT I had it figured out and working...but I'm running into a couple problems using it with my connect 4 game. I was just hoping someone could maybe look at my code and let me know if anything seems wrong. I haven't yet implemented a function to 'evaluate' the strength of each move...I'm just trying to get the program to see moves that will result in a win. What I have works, if it is my turn and there is 3 in a row and a winning move, it will tell me that. However, if it is my turn and the oppenent has a winning move that I can block it doesn't tell me that. By examining the algorithm, it seems like it should tell me that. The recursion should stop when it finds the winning move and send that down. So the way I see it, for the oppenents move, there should be 6 moves that will result in his winning and return a winning value, but there should be the one move that won't because that move will have blocked his winning move. So it will send back 6 9999 values, which become negative...and the other value will be smaller than that, which becomes bigger when it is sent back negative...so it seems like it SHOULD detect that and recommend that move. However it isn't, which leads me to believe that I have messed up somewhere or that I have an error. I just can't seem to figure it out. Anyways, heres my code...if anyone takes a look I would be more than grateful.


int negaMax(int board[][BOARD_HEIGHT], int depth, int player) {
    MOVE moveList[7] = {0};
    int bestValue = -WIN;
    int value, numMoves;
    
    // used to keep track of which player's turn it is
    switch(player) {
        case 1: player = 2; break;
        case 2: player = 1; break;
        default: break;
    }
    
    // check for win
    if(scanBoard(board))
        return WIN;
    
    // if reached searched depth, evaluate board
    if(depth <= 0){
        return evaluate(board);
    }
    numMoves = possibleMoves(board, moveList, player);
    if(numMoves == 0) 
        return 0;
    
    for(int i = 0; i < numMoves; i++) {
        doMove(board, moveList);
        value = -negaMax(board, depth-1, player);
        undoMove(board, moveList);
        if(value > bestValue) 
            bestValue = value;
    }
    return bestValue;
}

int getMove(int board[][BOARD_HEIGHT], int player) {
    MOVE moveList[7] = {0};
    int numMoves, returnValue, maxValue = -9999, returnMove = 0;
    // put a list of possible moves into moveList array
    numMoves = possibleMoves(board, moveList, player);
    // for each of the possible moves, run negamax and get 'score' for each
    for(int i = 0; i < numMoves; i++) {
        doMove(board, moveList);
        returnValue = negaMax(board, 5, player);
        cout << returnValue << endl;
        undoMove(board, moveList);
        if(returnValue > maxValue){
            maxValue = returnValue;
            returnMove = moveList.x;
        }
    }
    
    return returnMove+1;
}

alvaro

Dec 11, 2005 at 3:33 PM

There are several things that are wrong with your code.

You should check in every node if the game is over, not only when you run out of depth.

The call to evaluate() doesn't know which side is playing. Generally you will want to return positive values if the player to move is winning, but for that you need to know who the player to move is.

It would be better if you could post the whole program (I hope it's not too big), so we can try it ourselves to see what the problems are.

core-nuts

Dec 11, 2005 at 4:32 PM

Thanks for the reply. I will post all the code. But I will warn you that I quickly put the rest of the code together, mainly to test my AI...so its a little sloppy and probly not the most efficient.

Also, I believe that my program checks for a win with every node...that is why I am a bit confused. The scanBoard(board) should return true if it has detected any 4 pieces in a row...

And I haven't yet implemented the evaluate() function yet...I know it will need to act accordingly to which player it is, I figured I would worry about that when I got there. I am just trying to get the most basic functions, which in this case is just to detect when either you can make a winning move, or how to block the oppenents winning move. It tells you which move to do to make your own winning move, just not to block the opponents...though it seems it should...

Anyways, thanks so much and heres the whole code.

// Connect 4 - prelim#include <iostream>#include <string>using namespace std;const int       WIN = 9999;const intEMPTY           = 0,PLAYER_1        = 1, PLAYER_2        = 2;const intBOARD_WIDTH     = 7,BOARD_HEIGHT    = 6;enum {player_1 = 1, player_2 = 2} player;// used to store the position of the pieces, instead of making the board a 1dimenion arraytypedef struct {    int x;    int y;    int player;} MOVE;void initBoard(int board[][BOARD_HEIGHT]);void print(int board[][BOARD_HEIGHT]);bool addPiece(int player, int col, int board[][BOARD_HEIGHT]);void switchPlayer();bool scanBoard(int board[][BOARD_HEIGHT]);// print out possible movesint possibleMoves(int board[][BOARD_HEIGHT], MOVE moveList[8], int player);void doMove(int board[][BOARD_HEIGHT], MOVE theMove);void undoMove(int board[][BOARD_HEIGHT], MOVE theMove);int getMove(int board[][BOARD_HEIGHT], int player);int negaMax(int board[][BOARD_HEIGHT], int depth, int player);int evaluate(int board[][BOARD_HEIGHT]);int main() {    int gameBoard[BOARD_WIDTH][BOARD_HEIGHT];    bool gameOver = false;    int input;    MOVE moveList[8] = {0};        initBoard(gameBoard);    player = player_1;        while(!gameOver) {        if(player == player_1) {            cout << "It is player 1's turn.\n\n";        }        if(player == player_2)            cout << "It is player 2's turn.\n\n";                    cout << " 1    2    3    4    5    6    7   " << endl             << "----------------------------------" << endl;        print(gameBoard);        cout << endl << "Which column would you like to add the piece to?(1-7): ";        cin >> input;                        if(!addPiece(player, input, gameBoard))             cout << "Cannot add anymore pieces there!!\n" << endl;        else {            if(scanBoard(gameBoard)) {                system("cls");                gameOver = true;                print(gameBoard);                cout << "Game Over! Player " << player << " wins!!!\n\n";                system("pause");            }            else                system("cls");                switchPlayer();                cout << getMove(gameBoard, player);        }    }        return 0; }void print(int board[][BOARD_HEIGHT]) {    for(int i = 0; i < BOARD_HEIGHT; i++) {        for(int j = 0; j < BOARD_WIDTH; j++) {            if(board[j] == 0) cout << "   | ";            else                cout << " " << board[j] << " | ";        }        cout << endl;    }}void initBoard(int board[][BOARD_HEIGHT]) {    // set the game board to empty    for(int i = 0; i < BOARD_HEIGHT; i++) {        for(int j = 0; j < BOARD_WIDTH; j++) {            board[j] = EMPTY;        }    }}bool addPiece(int player, int col, int board[][BOARD_HEIGHT]) {    // loop through the column to find the first open slot, starting at the bottom    for(int i = BOARD_HEIGHT - 1; i >= 0; i--) {        // if empty spot is found, put the players piece there        if(board[col-1] == EMPTY) {            board[col-1] = player;            return true;        }    }    // if no empty spot is found, the function will return false    return false;}void switchPlayer() {    switch(player) {        case player_1:            player = player_2;            break;        case player_2:            player = player_1;            break;        default: break;    }}bool scanBoard(int board[][BOARD_HEIGHT]) {    for(int i = 0; i < BOARD_HEIGHT; i++) {         for(int j = 0; j < BOARD_WIDTH; j++) {                        if(board[j] != 0) { // only scan if space has a piece in it                                // scan for vertical line                if(i < 4) {                    if(board[j] == PLAYER_1 && board[j][i+1] == PLAYER_1 &&                         board[j][i+2] == PLAYER_1 && board[j][i+3] == PLAYER_1)                        return true;                    if(board[j] == PLAYER_2 && board[j][i+1] == PLAYER_2 &&                         board[j][i+2] == PLAYER_2 && board[j][i+3] == PLAYER_2)                        return true;                }                                    // scan for horizontal line                if(j < 4) {                    if(board[j] == PLAYER_1 && board[j+1] == PLAYER_1 &&                       board[j+2] == PLAYER_1 && board[j+3] == PLAYER_1)                        return true;                    if(board[j] == PLAYER_2 && board[j+1] == PLAYER_2 &&                       board[j+2] == PLAYER_2 && board[j+3] == PLAYER_2)                        return true;                }                                // scan for horizontal - down and right                if(i < 4 && j < 4) {                    if(board[j] == PLAYER_1 && board[j+1][i+1] == PLAYER_1 &&                       board[j+2][i+2] == PLAYER_1 && board[j+3][i+3] == PLAYER_1)                        return true;                    if(board[j] == PLAYER_2 && board[j+1][i+1] == PLAYER_2 &&                       board[j+2][i+2] == PLAYER_2 && board[j+3][i+3] == PLAYER_2)                        return true;                }                                // scan for horizontal - down and left                if(i < 4 && j > 2) {                    if(board[j] == PLAYER_1 && board[j-1][i+1] == PLAYER_1 &&                       board[j-2][i+2] == PLAYER_1 && board[j-3][i+3] == PLAYER_1)                        return true;                    if(board[j] == PLAYER_2 && board[j-1][i+1] == PLAYER_2 &&                       board[j-2][i+2] == PLAYER_2 && board[j-3][i+3] == PLAYER_2)                        return true;                }// end if            }// end if        }// end for    }    return false;}int possibleMoves(int board[][BOARD_HEIGHT], MOVE moveList[7], int player) {    int moveIndex = 0;    int moves = 0;    for(int i = 0; i < BOARD_WIDTH; i++){         for(int j = BOARD_HEIGHT-1; j >= 0; j--) {            if(board[j] == EMPTY) {                moveList[moveIndex].x = i;                moveList[moveIndex].y = j;                moveList[moveIndex].player = player;                j = -1; // exit loop                moveIndex++;                moves++;            } //end if        } // end for    } // end for    return moves;}int getMove(int board[][BOARD_HEIGHT], int player) {    MOVE moveList[7] = {0};    int numMoves, returnValue, maxValue = -9999, returnMove = 0;    // put a list of possible moves into moveList array    numMoves = possibleMoves(board, moveList, player);    // for each of the possible moves, run negamax and get 'score' for each    for(int i = 0; i < numMoves; i++) {        doMove(board, moveList);        returnValue = negaMax(board, 5, player);        cout << returnValue << endl;        undoMove(board, moveList);        if(returnValue > maxValue){            maxValue = returnValue;            returnMove = moveList.x;        }    }        return returnMove+1;}int negaMax(int board[][BOARD_HEIGHT], int depth, int player) {    MOVE moveList[7] = {0};    int bestValue = -WIN;    int value, numMoves;        // used to keep track of which player's turn it is    switch(player) {        case 1: player = 2; break;        case 2: player = 1; break;        default: break;    }        // check for win    if(scanBoard(board))        return WIN;        // if reached searched depth, evaluate board    if(depth <= 0){        return evaluate(board);    }    numMoves = possibleMoves(board, moveList, player);    if(numMoves == 0)         return 0;        for(int i = 0; i < numMoves; i++) {        doMove(board, moveList);        value = -negaMax(board, depth-1, player);        undoMove(board, moveList);        if(value > bestValue)             bestValue = value;    }    return bestValue;}void doMove(int board[][BOARD_HEIGHT], MOVE theMove){    board[theMove.x][theMove.y] = theMove.player;}void undoMove(int board[][BOARD_HEIGHT], MOVE theMove){    board[theMove.x][theMove.y] = 0;}    int evaluate(int board[][BOARD_HEIGHT]) {    return 1; // temporary}

alvaro

Dec 11, 2005 at 5:55 PM

I am sorry I missed your call to scanBoard. However, it looks to me like you should return -WIN in that case, since you are looking at it from the point of view of the side to move, which just lost the game.

I'll try to compile and run your code later (sorry, this computer doesn't have a working compiler).

core-nuts

Dec 11, 2005 at 9:55 PM

Hey, I really appreciate you trying to help me out. This place always surprises me with how willing people are to help others out.

Anyways, it seems like I have something wrong with my logic...I'm trying to work through it, but I still can't seem to get it right. If you are able to figure it out or just offer some advice - man, that would be awesome.

Thanks again!

core-nuts

Dec 11, 2005 at 10:10 PM

HAHA! I think I figured it out.

You were right about how I should be returning -WIN instead of WIN. However, I also needed to return a negative negaMax when I called it first in the getMove function.

so my call now looks like this:

returnValue = -negaMax(board, 4, player);

It appears to be working properly now, and I just needed to work on my evaluate function and see if it all will come together.

But like I said, if you have any suggestions or anything, I am always open for feedback.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.