У меня проблемы с реализацией алгоритма MiniMax для моей шахматной игры.Кажется, что большинство его частей работает, но они либо не делают хороших ходов, либо что-то не так с их оценкой (счетом на основе активных фигур обоих игроков).Например, если я установлю проверку (например, помощник дурака), ай делает что-то случайное, а не убивает короля.Я действительно не могу определить, что я делаю неправильно.
Класс, который оценивает плату, StandardBoardEvaluator, кажется, работает после некоторого тестирования, поэтому проблема, скорее всего, где-то в реализации MiniMax.Игра составлена из класса Board, который имеет и 2D-массив с 8x8 объектами моего собственного класса Square, который сам по себе имеет ссылку на фигуру (которая может быть нулевой, или любую из типичных шахматных фигур).В алгоритме я постоянно делаю новые экземпляры Board как идущие вниз по поисковой тройке, поэтому я сделал эти конструкторы "глубокого клона" в Board и Square, так что, похоже, это не проблема.Например:
public Board(Board originalBoard) {
this.turnIsWhite = originalBoard.getTurnIsWhite();
winner = null;
squares = new Square[8][8];
for (int rank=0; rank<squares.length; rank++) {
for(int file=0; file<squares[rank].length; file++) {
squares[rank][file] = new Square(originalBoard.getSquare(posStringFromFileRank(rank, file)));
}
}
}
И
public Square(Square originalSquare) {
this.pos = new String(originalSquare.getPos());
this.piece = originalSquare.getPiece();
}
У меня есть типичный командный класс MovePiece для движущихся фигур.Он использует другой класс, MoveCheck, чтобы проверить, является ли команда перемещения допустимой.MovePiece возвращает логическое значение, представляющее, является ли перемещение допустимым.Оба эти класса были тщательно протестированы и работают, поэтому я не думаю, что проблема в этих классах.
Вот алгоритм:
public class MiniMax implements MoveStrategy{
BoardEveluator bV;
MoveGenerator mGen;
int depth;
public MiniMax(int depth){
bV = new StandardBoardEvaluator();
mGen = new MoveGenerator();
this.depth = depth;
}
@Override
public MovePiece execute(Board board) {
MovePiece bestMove = null;
int lowestValue = Integer.MAX_VALUE;
int highestValue = Integer.MIN_VALUE;
int currentValue = 0;
String color = (board.getTurnIsWhite() ? "white" : "black");
System.out.println(color + " is evaluation best move with MiniMax depth " + depth);
List<MovePiece> allPossibleMoves = mGen.getLegalMoves(board, board.getTurnIsWhite());
for (MovePiece mp : allPossibleMoves){
Board tempBoard = new Board(board);
mp.setBoard(tempBoard);
if (mp.execute()){
currentValue = tempBoard.getTurnIsWhite() ? min(tempBoard, depth -1) : max(tempBoard, depth -1);
if (board.getTurnIsWhite() && currentValue >= highestValue){
highestValue = currentValue;
bestMove = mp;
}
else if (!board.getTurnIsWhite() && currentValue <= lowestValue){
lowestValue = currentValue;
bestMove = mp;
}
mp.unexecute();
}
}
return bestMove;
}
int min (Board board, int depth){
if (depth == 0 || board.getWinner() != null){
return bV.eveluate(board);
}
int lowestValue = Integer.MAX_VALUE;
List<MovePiece> legalMoves = mGen.getLegalMoves(board, board.getTurnIsWhite());
for (MovePiece mp : legalMoves){
Board tempBoard = new Board(board);
mp.setBoard(tempBoard);
if (mp.execute()){
int currentValue = max(tempBoard, depth - 1);
if (currentValue <= lowestValue){
lowestValue = currentValue;
}
mp.unexecute();
}
}
return lowestValue;
}
int max (Board board, int depth){
if (depth == 0 || board.getWinner() != null){
return bV.eveluate(board);
}
int highestValue = Integer.MIN_VALUE;
List<MovePiece> legalMoves = mGen.getLegalMoves(board, board.getTurnIsWhite());
for (MovePiece mp : legalMoves){
Board tempBoard = new Board(board);
mp.setBoard(tempBoard);
if (mp.execute()){
int currentValue = min(tempBoard, depth - 1);
if (currentValue >= highestValue){
highestValue = currentValue;
}
mp.unexecute();
}
}
return highestValue;
}
И класс оценщика
public class StandardBoardEvaluator implements BoardEveluator {
private int scorePlayer(Board board, boolean isWhite){
return pieceValue(board, isWhite) + mobolity(isWhite, board);
}
private int mobolity(boolean isWhite, Board board){
return (int) (board.getActiveSquares(isWhite).size() * 1.5);
}
private static int pieceValue(Board board, boolean isWhite){
int piceValueScore = 0;
for (Square square : board.getActiveSquares(isWhite)){
piceValueScore += square.getPiece().getPieceValue();
}
return piceValueScore;
}
@Override
public int eveluate(Board board) {
return scorePlayer(board, true) - scorePlayer(board, false);
}
}
Вот класс MovePiece:
private Square from;
private Square to;
private Board board;
private MoveCheck mCheck;
private RulesCheck rCheck;
private boolean done = false;
private Piece killed;
public MovePiece(Board board, String from, String to) {
this.board = board;
this.from = board.getSquare(from);
this.to = board.getSquare(to);
mCheck = new MoveCheck();
}
public MovePiece(Board board, Square from, Square to) {
this.board = board;
this.from = from;
this.to = to;
mCheck = new MoveCheck();
rCheck = new RulesCheck(board);
}
public void setBoard(Board board) {
this.board = board;
}
public Board getBoard() {
return board;
}
public Square getFrom() {
return from;
}
public Square getTo() {
return to;
}
public void setFrom(Square from) {
this.from = from;
}
public void setTo(Square to) {
this.to = to;
}
public void setFrom(String from) {
this.from = board.getSquare(from);
}
public void setTo(String to) {
this.to = board.getSquare(to);
}
@Override
public boolean execute() {
rCheck = new RulesCheck(board);
if (done) {
board.movePiece(from, to);
return true;
}
else if (mCheck.isLegal(board, from, to)){
if (to.getPiece() != null) {
killed = to.getPiece();
rCheck.winCheck(killed);
}
board.setGameOutput("Moved " + from.pieceToString() + " at " + from.getPos() + " - to " + to.getPos() + "(" + to.pieceToString() + ")");
board.movePiece(from, to);
rCheck.checkPromotion(to);
done = true;
return true;
}
return false;
}
@Override
public void unexecute() {
if (to.getPiece().getClass() == Pawn.class)
((Pawn) to.getPiece()).decreaseMoves();
board.movePiece(to, from);
if (killed != null) {
to.setPiece(killed);
}
}
MoveCheckКласс просто проверяет, является ли ход допустимым для фигуры (путь свободен, цель - враг или пуст и т. д.), не думайте, что это актуально для моей проблемы, поскольку код протестирован и работает.
Значение элемента объявляется как int в подклассах (все типы элементов) абстрактного класса Piece.100 очков за пешку, 300 за слона и рыцаря, 500 за ладью, 900 за королеву и 10 000 за короля.
Если кто-нибудь поможет мне разобраться в проблеме, я буду вечно благодарен!Пожалуйста, дайте мне знать, если вам нужно найти какой-то другой код, который я не показывал.