patternMinor
Trying to improve minimax heuristic function for connect four game in JS
Viewed 0 times
minimaxconnecttryingfunctionfourimproveheuristicgamefor
Problem
I have made a connect four game in JS and currently have a functioning minimax algorithm. The problem I'm having is that it is very, very easy to beat, even with a large depth. This is leading me to believe that I need a better heuristic function, but I cannot come up with much better than what I already have. So, I thought I would ask if anyone has any experience, or just a good idea, for a very good heuristic to use. I would also accept improvement ideas on my current heuristic below. Thank you in advance!
EDIT: I'm going to go ahead and post my total minimax in here (3 functions total), because I have added disjoints and made my 4-in-a-row higher, but my AI is still terrible. I know my 2,3 and 4-in-a-rows work because I tested them, but I can't pin-point why I'm still having trouble even at high depths.
```
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 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 0) return 100000;
var threes = checkThrees(currBoard,'b') * 1000;
var twos = checkTwos(currBoard,'b')
EDIT: I'm going to go ahead and post my total minimax in here (3 functions total), because I have added disjoints and made my 4-in-a-row higher, but my AI is still terrible. I know my 2,3 and 4-in-a-rows work because I tested them, but I can't pin-point why I'm still having trouble even at high depths.
```
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 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 0) return 100000;
var threes = checkThrees(currBoard,'b') * 1000;
var twos = checkTwos(currBoard,'b')
Solution
Connect 4 is a solved game - under perfect play, white wins. Victor Allis's thesis contains a winning algorithm for white. The game had been solved a few weeks earlier by James D. Allen. Later on, John Tromp came up with a strategy that will win the game from any position, if possible, and thus solved the game strongly.
Context
StackExchange Computer Science Q#13453, answer score: 7
Revisions (0)
No revisions yet.