Как закодировать шахматное патовое правило?

Question

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

Answer 1

Ваш генератор движения будет одного из двух разных дизайнов;

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

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

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

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

Answer 2

Вот код с открытым исходным кодом со всеми правилами для классической игры в шахматы: 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. Из свойств модельного класса:

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

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

public boolean onCellClick(int row, int column) {
    if (row == -1 && conquest != null) {
        checkType = 0;
        conquest.changeFigure(column);
        return true;
    } else if (selected != null) {
        if (possibleMovements != null) {
            for (int[] move : possibleMovements) {
                if (move[0] == row && 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;
}

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

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 && ((GenericPiece) piece).getMovesCount() == 1) {
        Piece king = board.getSelected(piece.getTeam(),
                piece.getRow(), piece.getColumn() + 1);
        if (king != null && king.getFigure() == Piece.KING && ((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 && king.getFigure() == Piece.KING && ((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 && (piece.getRow() == 0 || piece.getRow() == board.getRows() - 1)) {
        conquest = (GenericPiece) piece;
        checkType = CONQUEST;
    }
}

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