Alpha Beta Search
- by Becky
I'm making a version of Martian Chess in java with AI and so far I THINK my move searching is semi-working, it seems to work alright for some depths but if I use a depth of 3 it returns a move for the opposite side...now the game is a bit weird because when a piece crosses half of the board, it becomes property of the other player so I think this is part of the problem. I'd be really greatful if someone could look over my code and point out any errors you think are there! (pls note that my evaluation function isn't nearly complete lol)
MoveSearch.java
public class MoveSearch {
private Evaluation evaluate = new Evaluation();
private int blackPlayerScore, whitePlayerScore;
public MoveContent bestMove;
public MoveSearch(int blackScore, int whiteScore) {
blackPlayerScore = blackScore;
whitePlayerScore = whiteScore;
}
private Vector<Position> EvaluateMoves(Board board) {
Vector<Position> positions = new Vector<Position>();
for (int i = 0; i < 32; i++) {
Piece piece = null;
if (!board.chessBoard[i].square.isEmpty()) {
// store the piece
piece = board.chessBoard[i].square.firstElement();
}
// skip empty squares
if (piece == null) {
continue;
}
// skip the other players pieces
if (piece.pieceColour != board.whosMove) {
continue;
}
// generate valid moves for the piece
PieceValidMoves validMoves = new PieceValidMoves(board.chessBoard, i, board.whosMove);
validMoves.generateMoves();
// for each valid move
for (int j = 0; j < piece.validMoves.size(); j++) {
// store it as a position
Position move = new Position();
move.startPosition = i;
move.endPosition = piece.validMoves.elementAt(j);
Piece pieceAttacked = null;
if (!board.chessBoard[move.endPosition].square.isEmpty()) {
// if the end position is not empty, store the attacked piece
pieceAttacked = board.chessBoard[move.endPosition].square.firstElement();
}
// if a piece is attacked
if (pieceAttacked != null) {
// append its value to the move score
move.score += pieceAttacked.pieceValue;
// if the moving pieces value is less than the value of the attacked piece
if (piece.pieceValue < pieceAttacked.pieceValue) {
// score extra points
move.score += pieceAttacked.pieceValue - piece.pieceValue;
}
}
// add the move to the set of positions
positions.add(move);
}
}
return positions;
} // EvaluateMoves()
private int SideToMoveScore(int score, PieceColour colour) {
if (colour == PieceColour.Black){
return -score;
} else {
return score;
}
}
public int AlphaBeta(Board board, int depth, int alpha, int beta) {
//int best = -9999;
// if the depth is 0, return the score of the current board
if (depth <= 0) {
board.printBoard();
System.out.println("Score: " + evaluate.EvaluateBoardScore(board));
System.out.println("");
int boardScore = evaluate.EvaluateBoardScore(board);
return SideToMoveScore(boardScore, board.whosMove);
}
// fill the positions with valid moves
Vector<Position> positions = EvaluateMoves(board);
// if there are no available positions
if (positions.size() == 0) {
// and its blacks move
if (board.whosMove == PieceColour.Black) {
if (blackPlayerScore > whitePlayerScore) {
// and they are winning, return a high number
return 9999;
} else if (whitePlayerScore == blackPlayerScore) {
// if its a draw, lower number
return 500;
} else {
// if they are losing, return a very low number
return -9999;
}
}
if (board.whosMove == PieceColour.White) {
if (whitePlayerScore > blackPlayerScore) {
return 9999;
} else if (blackPlayerScore == whitePlayerScore) {
return 500;
} else {
return -9999;
}
}
}
// for each position
for (int i = 0; i < positions.size(); i++) {
// store the position
Position move = positions.elementAt(i);
// temporarily copy the board
Board temp = board.copyBoard(board);
// make the move
temp.makeMove(move.startPosition, move.endPosition);
for (int x = 0; x < 32; x++) {
if (!temp.chessBoard[x].square.isEmpty()) {
PieceValidMoves validMoves = new PieceValidMoves(temp.chessBoard, x, temp.whosMove);
validMoves.generateMoves();
}
}
// repeat the process recursively, decrementing the depth
int val = -AlphaBeta(temp, depth - 1, -beta, -alpha);
// if the value returned is better than the current best score, replace it
if (val >= beta) {
// beta cut-off
return beta;
}
if (val > alpha) {
alpha = val;
bestMove = new MoveContent(alpha, move.startPosition, move.endPosition);
}
}
// return the best score
return alpha;
} // AlphaBeta()
}
This is the makeMove method
public void makeMove(int startPosition, int endPosition) {
// quick reference to selected piece and attacked piece
Piece selectedPiece = null;
if (!(chessBoard[startPosition].square.isEmpty())) {
selectedPiece = chessBoard[startPosition].square.firstElement();
}
Piece attackedPiece = null;
if (!(chessBoard[endPosition].square.isEmpty())) {
attackedPiece = chessBoard[endPosition].square.firstElement();
}
// if a piece is taken, amend score
if (!(chessBoard[endPosition].square.isEmpty()) && attackedPiece != null) {
if (attackedPiece.pieceColour == PieceColour.White) {
blackScore = blackScore + attackedPiece.pieceValue;
}
if (attackedPiece.pieceColour == PieceColour.Black) {
whiteScore = whiteScore + attackedPiece.pieceValue;
}
}
// actually move the piece
chessBoard[endPosition].square.removeAllElements();
chessBoard[endPosition].addPieceToSquare(selectedPiece);
chessBoard[startPosition].square.removeAllElements();
// changing piece colour based on position
if (endPosition > 15) {
selectedPiece.pieceColour = PieceColour.White;
}
if (endPosition <= 15) {
selectedPiece.pieceColour = PieceColour.Black;
}
//change to other player
if (whosMove == PieceColour.Black) whosMove = PieceColour.White;
else if (whosMove == PieceColour.White) whosMove = PieceColour.Black;
} // makeMove()
