¿Cómo saber cuándo un puesto de FEN es legal?

Estoy haciendo un proyecto personal, donde en un momento necesito validar la posición de FEN, comencé con algunas verificaciones básicas, como verificar si hay reyes y asegurarme de que no haya filas o columnas adicionales, y ese tipo de cosas.

Pero, ¿qué otros controles debo hacer para asegurarme por completo de que un FEN es legal?

Aquí hay una lista bien organizada que debería validar el 99.99% + de las posiciones comunes:

Tablero:

• Hay exactamente 8 cols
• La suma de los cuadrados vacíos y las piezas se suman a 8 para cada rango (fila)
• No hay números consecutivos para cuadrados vacíos

Reyes:

• Vea si hay exactamente una w_king y una b_king
• Asegúrate de que los reyes estén separados 1 cuadrado

Cheques:

• El color no activo no está bajo control
• El color activo se verifica menos de 3 veces (la triple verificación es imposible); en caso de 2 que nunca es peón + (peón, alfil, caballero), alfil + alfil, caballero + caballero

Peones:

• No hay más de 8 peones de cada color.
• No hay peones en el primer o último rango (fila) ya que están en una posición de inicio incorrecta o deberían haber ascendido.
• En el caso de en passant square; ver si se creó legalmente (por ejemplo, debe estar en el rango x3o x6, debe haber un peón (del color correcto) delante de él, y el cuadrado al paso y el que está detrás está vacío)
• Evite tener más piezas promocionadas que peones faltantes (por ejemplo, extra_pieces = Math.max(0, num_queens-1) + Math.max(0, num_rooks-2)...y luego extra_pieces <= (8-num_pawns)), también debe hacer cálculos especiales para los obispos. Si tiene dos (o más) obispos del mismo color cuadrado, estos solo se pueden crear a través de la promoción de peones y debe incluir esta información a la fórmula anterior de alguna manera
• Es posible alcanzar la formación de peón (por ejemplo, en el caso de varios peones en una sola columna, deben faltar suficientes piezas enemigas para hacer esa formación), aquí hay algunas reglas útiles:
  1. Es imposible tener más de 6 peones en un solo archivo (columna) (porque los peones no pueden existir en el primer y último rango)
  2. el número mínimo de piezas perdidas del enemigo para alcanzar un peón múltiple en una sola columna 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, por ejemplo, si ves 5 peones en A o H, el otro jugador debe faltar al menos 10 piezas de sus 15 piezas capturables
  3. Si hay peones blancos en a2 y a3, legalmente no puede haber uno en b2, y esta idea se puede ampliar aún más para cubrir más posibilidades

Enroque:

• Si el rey o las torres no están en su posición inicial; la habilidad de enroque para ese lado se pierde (en el caso del rey, ambos se pierden)

Obispos:

• Busque obispos en el primer y último rango (filas) atrapados por peones que no se han movido, por ejemplo:
  1. un alfil (de cualquier color) atrapado detrás de 3 peones
  2. un obispo atrapado detrás de 2 peones no enemigos (no por peones enemigos porque podemos alcanzar esa posición por debajo de los peones, sin embargo, si verificamos el número de peones y extra_piecespodríamos determinar si este caso es posible o no)

No puentes:

• (Evita esto si quieres validar el Ajedrez de Fisher960) Si hay piezas enemigas que no saltan entre el rey y la torre y todavía hay algunos peones sin moverse; comprueba si estas piezas enemigas podrían haber entrado legalmente allí. Además, pregúntese: ¿se necesitaba mover el rey o la torre para generar esa posición? (en caso afirmativo, debemos asegurarnos de que las habilidades de enroque reflejen esto)
• Si los 8 peones aún están en la posición inicial, todos los no saltadores no deben haber dejado su rango inicial (también las piezas enemigas no saltadoras no pueden haber entrado legalmente), hay otras ideas similares, como si el blanco h - el peón se movió una vez, las torres aún deben quedar atrapadas dentro de la formación del peón, etc.

Relojes de movimiento medio / completo:

• En el caso de un cuadrado en passant, el reloj de medio movimiento debe ser igual a 0
• HalfMoves <= ((FullMoves-1)*2)+(if BlackToMove 1 else 0), el +1 o +0 depende del lado a mover
• Los HalfMoves deben ser x >= 0y los FullMovesx >= 1

Otro:

• Asegúrese de que el FEN contenga todas las partes necesarias (p. Ej., Color activo, habilidad de enroque, cuadrado al paso, etc.)

Nota: no es necesario hacer que los 'jugadores no deberían tener más de 16 piezas' porque los puntos 'no más de 8 peones' + 'evitan piezas promocionadas adicionales' + el 'exactamente un rey' ya debería cubrir este punto

Nota 2: estas reglas están destinadas a validar las posiciones que surgen de la posición inicial del ajedrez normal, algunas de las reglas invalidarán algunas posiciones de Chess960 (excepción si se inició desde el arreglo Nº518) y generarán rompecabezas para evitar que obtengan un validador funcional.

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

Aquí hay una expresión regular que uso para garantizar que una cadena FEN sea realmente válida. No realiza ninguna prueba para una posición legal / ilegal, pero es un buen punto de partida.

Para los demás, hay una función simple en el motor Stockfish, que valida una cadena 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);
}

Aquí hay un algoritmo de retroceso simple, siempre que tenga una función que pueda verificar movimientos legales inversos en cada estado del tablero (también conocido como posición):

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

No hay nada en la especificación FEN que indique que la posición representada debe ser accesible desde la matriz inicial. Probar que una posición determinada es accesible desde la matriz inicial es un problema sin resolver.

En una cadena FEN válida, el conteo de medio movimiento debe estar de acuerdo con el cuadrado objetivo pasado; si hay un cuadrado objetivo, entonces el conteo de medio movimiento debe ser cero. el conteo de medio movimiento también debe estar de acuerdo con el número de movimiento completo; por ejemplo, un conteo de medio movimiento de diez es incompatible con un número de movimiento completo de tres.

Llegando tarde a la fiesta.

No es posible validar al 100% si un puesto es legal, pero ¿por qué debería importar la validación? Podemos jugar al ajedrez independientemente de si la posición se deriva o no de la posición inicial (el llamado "conjunto de juegos"). Puede haber una posición muy interesante para analizar, pero sucede que es ilegal.

Entonces verificaría solo:

• ¿Hay exactamente 1 rey de cada lado?
• ¿No hay peones en el primer u octavo rango?
• ¿El lado a mover ya no está dando cheque?

Si son tres SÍ, entonces podemos jugar ajedrez hacia adelante desde este diagrama. E incluso esta breve lista de condiciones podríamos aflojar.