I am trying to create AI in my connect four game using the minimax algorithm, but I'm having trouble getting it to work. I believe I'm very close, but am still unable to get it correct. Could anyone please assist me in any errors? I realize my code is not great, as I am not very efficient with Javascript yet, which is why I wanted to try this out. If I am totally off track, could someone please inform me of a better approach? Thanks in advance.
EDIT: I have replaced my code below with my updated code. It now "works" as far as giving me AI moves, but the problem is that they are not "intelligent" moves. I've looked at numerous minimax definitions and I feel that I've implemented it correctly. Even when I go to about a depth of 7, a 5 year old could beat it. Any help would be appreciated.
function getBestMove(currBoard,depth,who) {
var opp;
//Get opponent for next piece
if(who == 'a') {
opp = 'p';
} else {
opp = 'a';
}
var tBoard = new Array(rows);
for(var i=0; i<tBoard.length; i++) {
tBoard[i] = new Array(cols);
}
var moves = new Array(aiOpenCols.length);
//Drop each piece and use minimax function until depth == 0
for(var i=0; i<aiOpenCols.length; i++) {
for(var j=0; j<rows; j++) {
for(var k=0; k<cols; k++) {
tBoard[j][k] = currBoard[j][k];
}
}
tBoard = dropPiece(aiOpenCols[i],who,tBoard);
moves[i] = minimax(tBoard,(+depth - 1),opp,aiOpenCols[i]);
}
var bestAlpha = -100000; //Large negative
//Use random column if no moves are "good"
var bestMove = Math.floor(Math.random() * aiOpenCols.length);
bestMove = +aiOpenCols[bestMove];
//Get largest value from moves for best move
for(var i=0; i<aiOpenCols.length; i++) {
if(+moves[i] > bestAlpha) {
bestAlpha = moves[i];
bestMove = aiOpenCols[i];
}
}
bestMove++; //Offset by 1 due to actual drop function
return bestMove;
}
function minimax(currBoard,depth,who,col) {
//Drop current piece, called from getBestMove function
currBoard = dropPiece(col,who,currBoard);
//When depth == 0 return heuristic/eval of board
if(+depth == 0) {
var ev = evalMove(currBoard);
return ev;
}
var alpha = -100000; //Large negative
var opp;
//Get opponent for next piece
if(who == 'a') {
opp = 'p';
} else {
opp = 'a';
}
//Loop through all available moves
for(var i=0; i<aiOpenCols.length; i++) {
var tBoard = new Array(rows);
for(var i=0; i<tBoard.length; i++) {
tBoard[i] = new Array(cols);
}
for(var j=0; j<rows; j++) {
for(var k=0; k<cols; k++) {
tBoard[j][k] = currBoard[j][k];
}
}
//Continue recursive minimax until depth == 0
var next = minimax(tBoard,(+depth - 1),opp,aiOpenCols[i]);
//Alpha = max(alpha, -minimax()) for negamax
alpha = Math.max(alpha, (0 - +next));
}
return alpha;
}
function evalMove(currBoard) {
//heuristic function
//AI = # of 4 streaks + # of 3 streaks + # of 2 streaks - # of 3 streaks opp - # of 2 streaks opp
var fours = checkFours(currBoard,'b') * 1000;
var threes = checkThrees(currBoard,'b') * 100;
var twos = checkTwos(currBoard,'b') * 10;
var oppThrees = checkThrees(currBoard,'r') * 100;
var oppTwos = checkTwos(currBoard,'r') * 10;
var scores = fours + threes + twos - oppThrees - oppTwos;
//If opponent wins, return large negative
var oppFours = checkFours(currBoard,'r');
if(+oppFours > 0) {
return -100000;
} else {
return scores;
}
}
function dropPiece(col,who,currBoard) {
for(var i=0; i<currBoard.length; i++) {
if(currBoard[i][col] != 'w') {
//Make sure column isn't full
if(i != 0) {
if(who == 'p') {
currBoard[i-1][col] = 'r';
} else {
currBoard[i-1][col] = 'b';
}
break;
}
}
//If column is empty, place in first row
if(i == (currBoard.length - 1)) {
if(who == 'p') {
currBoard[i][col] = 'r';
} else {
currBoard[i][col] = 'b';
}
}
}
return currBoard;
}