Hi all. first of all let me apologize in advance for this rather noob question and if this is not the right sub-forum please let me know and transfer the post.
I am a java beginner/intermediate,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! 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; reply = chooseMove(!side,board,alpha,beta,depth+1,maxDepth); board[move.intValue()] = 0; 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; }