Jak zakodować regułę impasu szachów?

Question

Próbuję napisać grę w szachy i znaleźć, że nie mogę znaleźć rozwiązań, aby znaleźć sytuacji patowej. Próbuję google, ale nie mogę znaleźć niczego. Czy istnieje dobrze znany algorytm lub coś takiego?

Answer 1

Twój generator ruchów będzie jednym z dwóch różnych wzorów;

• albo to sprawdza legalności podczas generowania ruchów
• lub wygenerować wszystkie możliwe ruchy i usunąć te, które są nielegalne później.

Pierwszy z nich jest lepszy, ponieważ nie wymaga przetwarzania końcowego.

Stan patowy jest po prostu taki, w którym nie ma ruchów prawnych, a król strony przenoszącej jest , a nie w czeku. Warunek szacha to taki, w którym nie ma żadnych ruchów prawnych, ale król na ruchomej stronie jest pod kontrolą.

Innymi słowy, jeśli odkryłeś, jak wykryć check i checkmate, masz już wszystko, co niezbędne do wykrycia sytuacji patowej.

Answer 2

Oto kod open source ze wszystkimi zasadami klasycznej gry w szachy: https://github.com/cjortegon/basic-chess

można uruchomić projekt tuż po klonowaniu projekt (Android, iOS, Desktop i Web) lub można użyj głównej logiki, która jest tutaj: https://github.com/cjortegon/basic-chess/tree/master/libgdx/core/src/com/mountainreacher/chess/model

Oparłem swoje rozwiązanie na 3-momentowym algorytmie, pierwszy moment to moment, w którym gracz wybiera kawałek z planszy, a następnie, gdy cel tego utworu został wybrany i ostatecznie gdy utwór osiągnie tę pozycję (biorąc pod uwagę, że jest to gra animowana, jeśli nie, możesz połączyć kroki 2 i 3).

Poniższy kod został zaimplementowany w Javie. Z właściwości klasy model:

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

Pierwsza metoda będzie obsługiwać chwile 1, 2 i specjalną „podboju” chwilę (stosowane zastawić kawałek tylko):

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; 
} 

I następująca metoda zajmie 3rd chwilę (gdy animacja kończy):

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; 
    } 
} 

ten kod obejmuje wszystkie reguły z klasycznych szachów, w tym: regularnych ruchów jednostkowych, roszady, sprawdź, check-mate i podboje pionki.