Hi all. first of all let me apologize in advance for this rather noob question,i am a java beginner,but very facinated with AI programming and programming in general. I am developing my own connect 4 android app, and i am using a standart MiniMax algorithm with Alpha-Beta for the search. But the problem is that in depth >9 the search just takes too much time. so,searching for a easy to implement anhancement for my Alpha-Beta i came across the “Killer Move” Heuristic which i pretty much got the idea of it. But i need some help to implement it in my code.
This is my MiniMax function, the “Best” Object holds a move(int) and also a score for that move (also an int).
And i know that i need to catch the move that causes a cut-off (when alpha>=beta) and use it as a killer move,but i just can’t figure out how to do it exactly. do i need to make it for each ply? where exactly should i initialize the killerMove variable inside this function?
please Don’t think i am lazy, i DID searched the net and couldn’t find code examples for this,only theoretical background. and i really would like to implement it in my code and learn another thing and increase my experience.Even if i can somehow manage to do it by myself, it is important to me that i am doing it right.
Any help would be appreciated! thanks below is my Minimax function
public Best chooseMove(boolean side,int[]board,int alpha,int beta,int depth,int maxDepth){
Best myBest = new Best();
Best reply;
int num;
if(Board.checkGameOver(board)||depth==maxDepth){
myBest.setScore(returnPositionScore(board));
return myBest;
}
if(side){
myBest.setScore(alpha);
num = numberOfEngine;
}
else{
myBest.setScore(beta);
num = numberOfOpponent;
}
ArrayList<Integer> availableMoves = new ArrayList<Integer>(searchAvailableMoves(board));
for(Integer move:availableMoves){
board[move.intValue()] = num; //Make the move
reply = chooseMove(!side,board,alpha,beta,depth+1,maxDepth); //Recursive call with the new board position
board[move.intValue()] = 0; //Undo the move
if(side&&reply.getScore()>myBest.getScore()){
myBest.setMove(move);
myBest.setScore(reply.getScore());
alpha = reply.getScore();
}
else if(!side&&reply.getScore()<myBest.getScore()){
myBest.setMove(move);
myBest.setScore(reply.getScore());
beta = reply.getScore();
}
if(alpha>=beta){
return myBest;
}
}
return myBest;
}