Comment savoir quand un poste FEN est légal?

Je fais un projet personnel, où à un moment donné, je dois valider la position FEN, j'ai commencé par quelques vérifications de base, telles que vérifier s'il y a des rois et m'assurer qu'il n'y a pas de lignes ou de colonnes supplémentaires, et ce genre de des choses.

Mais que dois-je faire d'autre pour m'assurer complètement qu'un FEN est légal?

Voici une liste bien organisée qui devrait valider 99,99% + des positions communes:

Planche:

• Il y a exactement 8 cols
• La somme des carrés et des pièces vides s'ajoute à 8 pour chaque rang (ligne)
• Il n'y a pas de numéros consécutifs pour les cases vides

Rois:

• Voir s'il y a exactement un w_king et un b_king
• Assurez-vous que les rois sont séparés d'un carré

Contrôles:

• La couleur non active n'est pas cochée
• La couleur active est vérifiée moins de 3 fois (une triple vérification est impossible); dans le cas de 2 qu'il n'est jamais pion + (pion, évêque, chevalier), évêque + évêque, chevalier + chevalier

Pions:

• Il n'y a pas plus de 8 pions de chaque couleur
• Il n'y a pas de pions au premier ou au dernier rang (rangée) car ils sont soit dans une mauvaise position de départ, soit ils auraient dû être promus.
• En cas de carré en passant; voir s'il a été légalement créé (par exemple, il doit être sur le rang x3ou x6, il doit y avoir un pion (de la bonne couleur) devant lui, et le carré en passant et celui derrière lui sont vides)
• Empêchez d'avoir plus de pièces promues que de pions manquants (par exemple extra_pieces = Math.max(0, num_queens-1) + Math.max(0, num_rooks-2)..., puis extra_pieces <= (8-num_pawns)), vous devez également faire des calculs spéciaux pour les évêques.Si vous avez deux (ou plus) évêques de la même couleur carrée, ceux-ci ne peuvent être créés que par la promotion de pions et vous devez inclure ces informations à la formule ci-dessus en quelque sorte
• La formation de pions est possible à atteindre (par exemple en cas de plusieurs pions dans un même col, il doit y avoir suffisamment de pièces ennemies manquantes pour faire cette formation), voici quelques règles utiles:
  1. il est impossible d'avoir plus de 6 pions dans un seul fichier (colonne) (car les pions ne peuvent pas exister dans les premier et dernier rangs)
  2. le nombre minimum de pièces manquantes ennemies pour atteindre un pion multiple dans une seule colonne B to G 2=1, 3=2, 4=4, 5=6, 6=9 ___ A and H 2=1, 3=3, 4=6, 5=10, 6=15, par exemple, si vous voyez 5 pions en A ou H, l'autre joueur doit manquer au moins 10 pièces de ses 15 pièces capturables
  3. s'il y a des pions blancs en a2 et a3, il ne peut pas légalement en avoir un en b2, et cette idée peut être développée pour couvrir plus de possibilités

Roque:

• Si le roi ou les tours ne sont pas dans leur position de départ; la capacité de roque de ce côté est perdue (dans le cas du roi, les deux sont perdus)

Évêques:

• Recherchez les évêques dans les premier et dernier rangs (rangées) piégés par des pions qui n'ont pas bougé, par exemple:
  1. un évêque (de n'importe quelle couleur) pris au piège derrière 3 pions
  2. un évêque piégé derrière 2 pions non ennemis (pas par des pions ennemis parce que nous pouvons atteindre cette position en sous-promouvant les pions, cependant si nous vérifions le nombre de pions et extra_piecesnous pourrions déterminer si ce cas est possible ou non)

Non-sauteurs:

• (Évitez ceci si vous voulez valider les échecs de Fisher960) S'il y a des pièces ennemies non sauteuses entre le roi et la tour et qu'il y a encore des pions sans bouger; Vérifiez si ces pièces ennemies auraient pu légalement y pénétrer. Demandez-vous également: le roi ou la tour devait-il se déplacer pour générer cette position? (si oui, nous devons nous assurer que les capacités de roque reflètent cela)
• Si les 8 pions sont toujours dans la position de départ, tous les non-cavaliers ne doivent pas avoir quitté leur rang initial (les pièces ennemies non-cavalières ne peuvent pas non plus avoir pu entrer légalement), il existe d'autres idées similaires, comme si le h blanc -le pion a bougé une fois, les tours doivent toujours être piégées à l'intérieur de la formation de pion, etc.

Horloges à demi / mouvement complet:

• Dans le cas d'un carré passant, l'horloge de demi-mouvement doit être égale à 0
• HalfMoves <= ((FullMoves-1)*2)+(if BlackToMove 1 else 0), le +1 ou +0 dépend du côté à déplacer
• Les HalfMoves doivent être x >= 0et les FullMovesx >= 1

Autre:

• Assurez-vous que le FEN contient toutes les pièces nécessaires (par exemple, couleur active, capacité de roque, carré en passant, etc.)

Remarque: il n'est pas nécessaire de cocher la case « les joueurs ne devraient pas avoir plus de 16 pièces» car les points «pas plus de 8 pions» + «empêcher les pièces supplémentaires promues» + «exactement un roi» devrait déjà couvrir ce point

Remarque 2: ces règles sont destinées à valider les positions résultant de la position de départ des échecs normaux, certaines règles invalideront certaines positions de Chess960 (exception si elles sont lancées à partir de l'arrangement Nº518) et les puzzles générés, évitez-les donc d'obtenir un validateur fonctionnel.

\s*([rnbqkpRNBQKP1-8]+\/){7}([rnbqkpRNBQKP1-8]+)\s[bw-]\s(([a-hkqA-HKQ]{1,4})|(-))\s(([a-h][36])|(-))\s\d+\s\d+\s*

Voici une expression régulière que j'utilise pour garantir qu'une chaîne FEN est réellement valide. Il ne fait aucun test pour une position légale / illégale, mais c'est un bon point de départ.

Pour les autres, il existe une fonction simple dans le moteur Stockfish, qui valide une chaîne FEN.

bool Position::is_valid_fen(const std::string &fen) {
   std::istringstream iss(fen);
   std::string board, side, castleRights, ep;

   if (!iss) return false;

   iss >> board;

   if (!iss) return false;

   iss >> side;

   if (!iss) {
      castleRights = "-";
      ep = "-";
   } else {
      iss >> castleRights;
      if (iss)
         iss >> ep;
      else
         ep = "-";
   }

   // Let's check that all components of the supposed FEN are OK.
   if (side != "w" && side != "b") return false;
   if (castleRights != "-" && castleRights != "K" && castleRights != "Kk"
       && castleRights != "Kkq" && castleRights != "Kq" && castleRights !="KQ"
       && castleRights != "KQk" && castleRights != "KQq" && castleRights != "KQkq"
       && castleRights != "k" && castleRights != "q" && castleRights != "kq"
       && castleRights != "Q" && castleRights != "Qk" && castleRights != "Qq"
       && castleRights != "Qkq")
      return false;
   if (ep != "-") {
      if (ep.length() != 2) return false;
      if (!(ep[0] >= 'a' && ep[0] <= 'h')) return false;
      if (!((side == "w" && ep[1] == '6') || (side == "b" && ep[1] == '3')))
         return false;
   }

   // The tricky part: The board.
   // Seven slashes?
   if (std::count(board.begin(), board.end(), '/') != 7) return false;
   // Only legal characters?
   for (int i = 0; i < board.length(); i++)
      if (!(board[i] == '/' || (board[i] >= '1' && board[i] <= '8')
            || piece_type_is_ok(piece_type_from_char(board[i]))))
         return false;
   // Exactly one king per side?
   if (std::count(board.begin(), board.end(), 'K') != 1) return false;
   if (std::count(board.begin(), board.end(), 'k') != 1) return false;
   // Other piece counts reasonable?
   size_t wp = std::count(board.begin(), board.end(), 'P'),
      bp = std::count(board.begin(), board.end(), 'p'),
      wn = std::count(board.begin(), board.end(), 'N'),
      bn = std::count(board.begin(), board.end(), 'n'),
      wb = std::count(board.begin(), board.end(), 'B'),
      bb = std::count(board.begin(), board.end(), 'b'),
      wr = std::count(board.begin(), board.end(), 'R'),
      br = std::count(board.begin(), board.end(), 'r'),
      wq = std::count(board.begin(), board.end(), 'Q'),
      bq = std::count(board.begin(), board.end(), 'q');
   if (wp > 8 || bp > 8 || wn > 10 || bn > 10 || wb > 10 || bb > 10
       || wr > 10 || br > 10 || wq > 9 || bq > 10
       || wp + wn + wb + wr + wq > 15 || bp + bn + bb + br + bq > 15)
      return false;

   // OK, looks close enough to a legal position. Let's try to parse
   // the FEN and see!
   Position p;
   p.from_fen(board + " " + side + " " + castleRights + " " + ep);
   return p.is_ok(true);
}

Voici un algorithme de retour en arrière simple, à condition que vous ayez une fonction qui puisse vérifier les mouvements légaux inversés à chaque état de la carte (également connu sous le nom de position):

function is_legal_state(state,move)

   //Terminate if a starting state was found. This immediately implies there
   //was a legal game that generated this state, in fact the backtracking
   //can tell you precisely such a game       
   if (state in starting board state)
     return true

   //Apply some move to get to a new state, state is a persistent object
   apply_reverse_move(state,move)

   //Generate all legal "reverse" moves, that is, moves that could have
   //been performed to get to the current state from another position,
   //provided the previous position was valid. You do not have to check the
   //validness of the previous state, you just have to make sure the
   //transitioning move was valid
   legalmoves = enumerate_all_reverse_moves( state )

   for local_move in legalmoves:
     return is_legal_state(state,local_move)

   //Reverse the move that was previously applied so backtracking can
   //work properly 
   reverse_reverse_move(state,move)

   return false

Rien dans la spécification FEN ne dit que la position représentée doit être accessible à partir du tableau initial. Prouver qu'une position donnée est accessible à partir du tableau initial est un problème non résolu.

Dans une chaîne FEN valide, le nombre de demi-coups doit être en accord avec le carré cible en passant; si un carré cible est présent, alors le nombre de demi-coups doit être nul. le compte du demi-coup doit également être en accord avec le numéro de coup complet; Par exemple, un décompte de demi-coups de dix est incompatible avec un nombre total de coups de trois.

Venir à la fête tard.

Il n'est pas possible de valider à 100% si un poste est légal, mais pourquoi la validation est-elle importante? Nous pouvons jouer aux échecs que la position dérive ou non de la position de départ (ce que l'on appelle le «tableau de jeu»). Il pourrait y avoir une position très intéressante à analyser, mais il se trouve que c'est illégal.

Je vérifierais donc simplement:

• Y a-t-il exactement 1 roi de chaque côté?
• N'y a-t-il pas de pions au premier ou au huitième rang?
• Le côté à déplacer ne donne-t-il pas déjà un chèque?

Si c'est trois OUI, nous pouvons jouer aux échecs en avant à partir de ce diagramme. Et même cette courte liste de conditions que nous pourrions être en mesure d'assouplir.