Блог

Я пытаюсь написать шахматную партию и обнаруживаю, что не могу найти решения, чтобы найти патовую ситуацию. Я пытаюсь Google, но ничего не могу найти. Есть ли хорошо известный алгоритм или что-то в этом роде?

Ваш генератор ходов будет иметь одну из двух разных конструкций;

• либо он проверяет законность при генерации ходов
• или вы генерируете все возможные ходы и впоследствии удаляете те, которые являются незаконными.

Первый вариант лучше, поскольку он не требует последующей обработки.

Безвыходное положение — это просто ситуация, когда нет законных ходов и король движущейся стороны не находится под контролем. Условие мата — это условие, при котором нет законных ходов, но король движущейся стороны находится под контролем.

Другими словами, если вы выяснили, как обнаруживать шах и мат, у вас уже есть все необходимое для обнаружения тупика.

Вот открытый исходный код со всеми правилами классической шахматной игры: https://github.com/cjortegon/basic-chess

Вы можете запустить проект сразу после клонирования проекта (Android, iOS, Desktop и Web), или вы можете использовать основную логику, которая находится здесь: https://github.com/cjortegon/basic-chess/tree/master/libgdx/core/src/com/mountainreacher/chess/model

Я основал свое решение на алгоритме из 3 моментов, первый момент — это когда игрок выбирает фигуру с доски, затем, когда выбран пункт назначения этой фигуры, и, наконец, когда фигура достигает этой позиции (учитывая, что это анимированная игра, если нет, вы можете объединить шаг 2 и3).

Следующий код был реализован на Java. Из свойств класса model:

 boolean turn;
GenericPiece selected, conquest;
ClassicBoard board;
List<int[]> possibleMovements;
int checkType;
 

Первый метод будет обрабатывать моменты 1, 2 и специальный момент «завоевания» (применяется только к пешке):

 public boolean onCellClick(int row, int column) {
    if (row == -1 amp;amp; conquest != null) {
        checkType = 0;
        conquest.changeFigure(column);
        return true;
    } else if (selected != null) {
        if (possibleMovements != null) {
            for (int[] move : possibleMovements) {
                if (move[0] == row amp;amp; move[1] == column) {
                    // Move the PieceActor to the desired position
                    if (selected.moveTo(row, column)) {
                        turn = !turn;
                    }
                    break;
                }
            }
        }
        selected = null;
        possibleMovements = null;
        return true;
    } else {
        selected = board.getSelected(turn ? Piece.WHITE_TEAM : Piece.BLACK_TEAM, row, column);
        if (selected != null) {
            possibleMovements = new ArrayList<>();
            possibleMovements.addAll(((GenericPiece) selected).getMoves(board, false));
            // Checking the movements
            board.checkPossibleMovements(selected, possibleMovements);
            if (possibleMovements.size() == 0) {
                possibleMovements = null;
                selected = null;
                return false;
            } else {
                return true;
            }
        }
    }
    return false;
}
 

И следующий метод будет обрабатывать 3-й момент (когда анимация заканчивается):

 public void movedPiece(Piece piece) {
    Gdx.app.log(TAG, "movedPiece("   piece.getType()   ")");

    // Killing the enemy
    Piece killed = board.getSelectedNotInTeam(piece.getTeam(),
            piece.getRow(), piece.getColumn());
    if (killed != null) {
        killed.setAvailable(false);
    }

    // Checking hacks
    GenericPiece[] threat = board.kingIsInDanger();
    if (threat != null) {
        checkType = board.hasAvailableMoves(threat[0].getTeam()) ? CHECK : CHECK_MATE;
    } else {
        checkType = NO_CHECK;
    }

    // Checking castling
    if (piece.getFigure() == Piece.ROOK amp;amp; ((GenericPiece) piece).getMovesCount() == 1) {
        Piece king = board.getSelected(piece.getTeam(),
                piece.getRow(), piece.getColumn()   1);
        if (king != null amp;amp; king.getFigure() == Piece.KING amp;amp; ((GenericPiece) king).getMovesCount() == 0) {
            // Left Rook
            if (board.getSelected(piece.getRow(), piece.getColumn() - 1) == null) {
                king.moveTo(piece.getRow(), piece.getColumn() - 1);
            }
        } else {
            king = board.getSelected(piece.getTeam(),
                    piece.getRow(), piece.getColumn() - 1);
            if (king != null amp;amp; king.getFigure() == Piece.KING amp;amp; ((GenericPiece) king).getMovesCount() == 0) {
                // Right Rook
                if (board.getSelected(piece.getRow(), piece.getColumn()   1) == null) {
                    king.moveTo(piece.getRow(), piece.getColumn()   1);
                }
            }
        }
    }

    // Conquest
    else if (piece.getFigure() == Piece.PAWN amp;amp; (piece.getRow() == 0 || piece.getRow() == board.getRows() - 1)) {
        conquest = (GenericPiece) piece;
        checkType = CONQUEST;
    }
}
 

Этот код охватывает все правила классических шахмат, в том числе: регулярные перемещения фигур, рокировки, шах, мат и завоевания пешек.