Alpha Beta Pruning Breaking Minimax
So I implemented a minimax search for my chess based puzzle game. In this case the search determines the AI pieces next move.
The minimax on it's own works fine it returns the expected move but when I implement alpha beta pruning the minimax returns the same two values for each piece every turn. For example an AI Rook currently at (0,0) may receive (1,0) as it's move from the minimax and next time it asks the minimax for it's move it will receive (0,0). This loop happens no matter what I change in the evaluation function.
The game state consists of the user's location, the piece's location and the array of tiles which represents the board itself. I use my own node class (should really be called Pair) here in order to store each Tile with it's respective value given by the evaluation function.
Is there an issue with how I'm implemented my alpha beta pruning? Any advice is greatly appreciated. If more information is needed just ask and I'll provide what I can.
//Here is my call to the minimax
Min(depth, user, piece, new Node((int) (Double.NEGATIVE_INFINITY)), new Node((int) Double.POSITIVE_INFINITY), tiles));
Node Max(int depth, Piece user, Piece piece, Node alpha, Node beta, Tile[][] tiles)
{
if(depth <= 0||gameOver(piece))
{
return new Node(evaluation(user,piece,tiles));
}
LinkedList<Tile> moves = user.getMoves(tiles,1);
for(Tile t:moves)
{
Tile temp= new Tile(user);
tiles= user.changePos(t,tiles);
Node val = Min(depth - 1, user, piece, alpha, beta, tiles);
val.addTile(t);
tiles= user.changePos(temp,tiles);
if(val.getValue()>=beta.getValue())
return beta;
if(val.getValue() >= alpha.getValue())
{
if(alpha.getTile()==null)
alpha = val;
else if(val.getValue()==alpha.getValue()){
if(r.nextInt(2)==1)//adds an element of randomness
alpha=val;
}
else
alpha=val;
}
}
return alpha;
}
Node Min(int depth, Piece user, Piece piece, Node alpha, Node beta, Tile[][] tiles)
{
updateGoal(user);
if(depth <= 0||gameOver(piece))
{
return new Node(evaluation(user,piece,tiles));
}
LinkedList<Tile> moves = piece.getMoves(tiles,1);
for(Tile t:moves)
{
Tile temp= new Tile(piece);
tiles= piece.changePos(t,tiles);
Node val = Max(depth - 1, user, piece, alpha, beta,tiles);
val.addTile(t);
tiles= piece.changePos(temp,tiles);
if(val.getValue() <= alpha.getValue())
return alpha;
if(val.getValue() <= beta.getValue())
{
if(beta.getTile()==null)
beta = val;
else if(val.getValue()==beta.getValue()){
if(r.nextInt(2)==1)
beta=val;
}
else
beta=val;
}
}
return beta;
}
上一篇: beta修剪产生错误的结果