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;
}
ANOTHER minimax(negamax) question...
December 11, 2005 02: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.
If you want the rainbow, you've gotta put up with the rain - do you know which philosopher said that? Dolly Parton. And people say she's just a big pair of tits.
21,607
December 11, 2005 03: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.
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.
December 11, 2005 04: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.
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}
If you want the rainbow, you've gotta put up with the rain - do you know which philosopher said that? Dolly Parton. And people say she's just a big pair of tits.
21,607
December 11, 2005 05: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).
I'll try to compile and run your code later (sorry, this computer doesn't have a working compiler).
December 11, 2005 09: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!
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!
If you want the rainbow, you've gotta put up with the rain - do you know which philosopher said that? Dolly Parton. And people say she's just a big pair of tits.
December 11, 2005 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:
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.
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.
If you want the rainbow, you've gotta put up with the rain - do you know which philosopher said that? Dolly Parton. And people say she's just a big pair of tits.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
