I'm using the wikipedia pseudocode to base against -
function alphabeta(node, depth, α, β, Player)
if depth = 0 or node is a terminal node
return the heuristic value of node
if Player = MaxPlayer
for each child of node
α := max(α, alphabeta(child, depth-1, α, β, not(Player) ))
if β ≤ α
break (* Beta cut-off *)
return α
else
for each child of node
β := min(β, alphabeta(child, depth-1, α, β, not(Player) ))
if β ≤ α
break (* Alpha cut-off *)
return β
and here is my java implementation -
private int alphabeta(Node newNode, int depth, int alpha, int beta, boolean Player) {
Integer[] children;
if(depth == 0 || newNode.allNodesFull()){
return (newNode.blacknodes() - newNode.whitenodes());
}
if(Player == false){
children = newNode.findMovesBlack();
Arrays.sort(children);
for(Integer child: children){
nodesGenerated ++;
alpha = Math.max(alpha, alphabeta(new Node(newNode.move(child), true),
depth - 1, alpha, beta, !Player));
if(beta <= alpha)
break;
}return alpha;
}else{
children = newNode.findMovesWhite();
Arrays.sort(children);
for(Integer child: children){
nodesGenerated ++;
beta = Math.min(beta, alphabeta(new Node(newNode.move(child), false),
depth - 1, alpha, beta, !Player));
if(beta <= alpha)
break;
}return beta;
}
}
after some revisions to my code there is no longer a problem with it returning early, but I do have a problem with alpha and beta never changing
I'll give an explanation of what happens, assume they work
findMovesBlack() and findMovesWhite() both return Integer[] arrays that have the possible positions that either player can move regardless of whos turn it is. For the initial position of Reversi, findMovesBlack() would return [19, 26, 37, 44]
allNodesFull() returns a boolean if findMovesBlack() and findMovesWhite() both have lengths of 0.
blacknodes() and whitenodes() return the amount of black or white nodes respectively.
Node.move(int coordinate) returns a String[] array which contains the new position that has been flipped and placed. trust me, it works correctly.
a Node(String[] gameboard, boolean player-to-move) just sets up a new position with the parameters we've found.
I believe that's all you need to see. I've ironed all the kinks out of the back-end.
The answer was in the implementation of the beta and alpha values. I had to mess with the positions relative to the = sign a lot.