Как узнать, когда позиция FEN является законной?

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

Но какие еще проверки я должен сделать, чтобы полностью убедиться, что FEN легален?

Вот хорошо организованный список, который должен подтвердить 99,99% + общих позиций:

Совет:

• Есть ровно 8 кол
• Сумма пустых квадратов и кусочков добавляется к 8 для каждого ранга (строки)
• Для пустых квадратов нет последовательных чисел

Kings:

• Посмотрите, есть ли ровно один w_king и один b_king
• Убедитесь, что короли отделены друг от друга на 1 квадрат

Проверки:

• Неактивный цвет не проверяется
• Активный цвет проверяется менее 3 раз (тройная проверка невозможна); в случае 2 это никогда не пешка + (пешка, слон, рыцарь), слон + слон, рыцарь + рыцарь

Пешки:

• В каждом цвете не более 8 пешек
• В первом или последнем ранге (ряду) нет пешек, поскольку они либо находятся в неправильной стартовой позиции, либо должны были повыситься.
• В случае проходной площади; посмотрите, было ли оно создано по закону (например, оно должно быть в ранге x3или x6, перед ним должна быть пешка (правильного цвета), а квадрат en passant и тот, что позади него, пусты)
• Предотвратите, чтобы больше продвигаемых фигур, чем отсутствующих пешек (например, extra_pieces = Math.max(0, num_queens-1) + Math.max(0, num_rooks-2)...и затем extra_pieces <= (8-num_pawns)), также вы должны делать специальные вычисления для слонов. Если у вас есть два (или более) слона одного и того же квадратного цвета, они могут быть созданы только с помощью продвижения пешки, и вы должны включить эта информация в формуле выше как-то
• Формирование пешки возможно достичь (например, в случае нескольких пешек на одном колье, должно быть достаточно вражеских фигур, чтобы сделать это формирование), вот несколько полезных правил:
  1. невозможно иметь более 6 пешек в одном файле (столбце) (поскольку пешки не могут существовать в первом и последнем разрядах)
  2. минимальное количество недостающих фигур противника для достижения нескольких пешек на одном колье 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, например, если вы видите 5 пешек в A или H, другой игрок должен пропустить не менее 10 фигур из своих 15 захваченных фигур
  3. если в a2 и a3 есть белые пешки, то в b2 их не может быть по закону, и эту идею можно расширить, чтобы охватить больше возможностей

Рокировка:

• Если король или ладьи не находятся в исходном положении; способность рокировки для этой стороны теряется (в случае короля оба теряются)

Епископы:

• Ищите слонов в первом и последнем рядах (рядах), захваченных пешками, которые не сдвинулись, например:
  1. слон (любого цвета) в ловушке за 3 пешками
  2. епископ, пойманный в ловушку за двумя не вражескими пешками (не пешками противника, потому что мы можем достичь этой позиции, недооценивая пешек, однако, если мы проверим количество пешек и extra_piecesсможем определить, возможен ли этот случай или нет)

Non-прыгуны:

• (Избегайте этого, если вы хотите проверить шахматы Фишера960). Если между королем и ладьей есть вражеские фигуры, не являющиеся перемычками, и все еще остаются пешки без движения; проверьте, могли ли эти вражеские фигуры попасть туда на законных основаниях. Кроме того, спросите себя: нужен ли король или ладья, чтобы двигаться, чтобы создать эту позицию? (если да, мы должны убедиться, что способности рокировки отражают это)
• Если все 8 пешек все еще находятся в исходной позиции, все непрыгунчики не должны были оставить свой начальный ранг (также вражеские фигуры непрыгнаных не могли бы войти легально), есть и другие похожие идеи, например, если белый h пешка перемещается один раз, ладьи все еще должны быть в ловушке внутри пешечной группировки и т. д.

Часы наполовину / полный ход:

• В случае квадрата en passant часы половинного хода должны быть равны 0
• HalfMoves <= ((FullMoves-1)*2)+(if BlackToMove 1 else 0), +1 или +0 зависит от стороны, чтобы двигаться
• HalfMoves должны быть x >= 0и FullMovesx >= 1

Другой:

• Убедитесь, что FEN содержит все необходимые детали (например, активный цвет, способность к рокировке, квадрат прохода и т. Д.)

Примечание: нет необходимости делать проверку «игрокам не должно быть больше 16 фигур», потому что очки «не более 8 пешек» + «предотвращать дополнительные продвинутые фигуры» + «точно один король» уже должен покрывать эту точку

Примечание 2: эти правила предназначены для проверки позиций, возникающих из начальной позиции обычных шахмат, некоторые из правил аннулируют некоторые позиции из Chess960 (исключение, если они начинаются с договоренности № 518) и генерируют головоломки, поэтому избегайте их, чтобы получить функциональный валидатор.

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

Вот регулярное выражение, которое я использую, чтобы убедиться, что строка FEN действительно допустима. Это не делает никакого теста на легальную / нелегальную позицию, но это хорошая отправная точка.

Для остальных есть простая функция в движке Stockfish, которая проверяет строку 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);
}

Вот простой алгоритм возврата, при условии, что у вас есть функция, которая может проверять обратные законные ходы в каждом состоянии доски (также известное как позиция):

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

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

В допустимой строке FEN счетчик половинных перемещений должен совпадать с целевым квадратом en passant; если целевой квадрат присутствует, то счетчик половины хода должен быть равен нулю. счетчик половинных ходов также должен соответствовать полному номеру ходов; например, половина хода десять несовместима с полным числом хода три.

Приходить на вечеринку поздно.

Невозможно на 100% подтвердить, является ли позиция законной, но почему проверка должна иметь значение? Мы можем играть в шахматы независимо от того, происходит ли позиция из начальной позиции (так называемый «игровой массив»). Может быть очень интересная позиция для анализа, но бывает, что это незаконно.

Так что я бы проверил просто:

• Есть ли ровно по одному королю с каждой стороны?
• Нет ли пешек в первом или восьмом ряду?
• Сторона, которая движется, уже не дает чек?

Если это три ДА, то мы можем сыграть в шахматы нападающими с этой диаграммы. И даже этот короткий список условий мы могли бы ослабить.