Jak się dowiedzieć, kiedy stanowisko FEN jest legalne?

Wykonuję osobisty projekt, w którym w pewnym momencie muszę zweryfikować pozycję FEN, zacząłem od kilku podstawowych kontroli, takich jak sprawdzenie, czy są królowie i upewnienie się, że nie ma żadnych dodatkowych wierszy lub kolumn, i tego rodzaju rzeczy

Ale jakie inne kontrole powinienem zrobić, aby całkowicie upewnić się, że FEN jest legalny?

Oto dobrze zorganizowana lista, która powinna potwierdzić 99,99% + wspólnych stanowisk:

Tablica:

• Jest dokładnie 8 kols
• Suma pustych kwadratów i elementów dodaje się do 8 dla każdej rangi (rzędu)
• Brak kolejnych liczb dla pustych kwadratów

Królowie:

• Sprawdź, czy jest dokładnie jeden w_king i jeden b_king
• Upewnij się, że królowie są oddzieleni od siebie o 1 kwadrat

Czeki:

• Nieaktywny kolor nie jest sprawdzany
• Aktywny kolor jest sprawdzany mniej niż 3 razy (potrójne sprawdzenie jest niemożliwe); w przypadku 2, że nigdy nie jest pionkiem + (pionek, biskup, rycerz), biskup + biskup, rycerz + rycerz

Pionki:

• Nie ma więcej niż 8 pionków z każdego koloru
• Nie ma żadnych pionków w pierwszym lub ostatnim szeregu (rzędzie), ponieważ są one na złej pozycji początkowej lub powinny były awansować.
• W przypadku kwadratu en passant; sprawdzić, czy został legalnie utworzony (np. musi znajdować się na pozycji x3lub w x6rankingu, przed nim musi znajdować się pionek (w odpowiednim kolorze), a kwadrat en passant i ten za nim są puste)
• Zapobiegaj posiadaniu większej liczby promowanych pionów niż brakujących pionków (np. extra_pieces = Math.max(0, num_queens-1) + Math.max(0, num_rooks-2)...Wtedy extra_pieces <= (8-num_pawns)), powinieneś również wykonać specjalne obliczenia dla biskupów. Jeśli masz dwóch (lub więcej) biskupów o tym samym kwadratowym kolorze, można je utworzyć tylko poprzez promocję pionków i powinieneś uwzględnić jakoś tę informację do powyższej formuły
• Formacja pionków jest możliwa do osiągnięcia (np. W przypadku wielu pionków w jednej kolumnie, musi brakować wystarczającej liczby pionków wroga, aby utworzyć formację), oto kilka przydatnych zasad:
  1. niemożliwe jest posiadanie więcej niż 6 pionków w jednym pliku (kolumnie) (ponieważ pionki nie mogą istnieć w pierwszym i ostatnim szeregu)
  2. minimalna liczba brakujących elementów wroga, aby dotrzeć do wielu pionków w jednej kolumnie 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, na przykład, jeśli widzisz 5 pionków w A lub H, drugiemu graczowi musi brakować co najmniej 10 elementów z jego 15 możliwych do zdobycia pionków
  3. jeśli w a2 i a3 są białe pionki, legalnie nie może być jednego w b2, a pomysł ten można rozszerzyć, aby objąć więcej możliwości

Castling:

• Jeśli król lub gawrony nie znajdują się w pozycji wyjściowej; zdolność rażenia tej strony jest utracona (w przypadku króla obie są utracone)

Biskupi:

• Szukaj biskupów w pierwszym i ostatnim szeregu (rzędach) uwięzionych przez pionki, które się nie poruszyły, na przykład:
  1. gońca (dowolnego koloru) uwięzionego za 3 pionkami
  2. biskupa uwięzionego za 2 pionkami nieprzyjacielskimi (nie przez pionki wroga, ponieważ możemy osiągnąć tę pozycję przez obniżenie pionów, jednak jeśli sprawdzimy liczbę pionków i extra_piecesmożemy ustalić, czy ten przypadek jest możliwy, czy nie)

Non-jumpers:

• (Unikaj tego, jeśli chcesz zweryfikować szachy Fishera 960). Jeśli pomiędzy królem a wieżą znajdują się wrogie pionki niebędące skoczkami i nadal istnieją pionki bez ruchu; sprawdź, czy te elementy wroga mogły się tam legalnie dostać. Zadaj też sobie pytanie: czy król lub wieża potrzebowali ruchu, aby wygenerować tę pozycję? (jeśli tak, musimy się upewnić, że umiejętności rycerskie to odzwierciedlają)
• Jeśli wszystkie 8 pionków nadal znajduje się w pozycji wyjściowej, wszyscy nieskoczkowie nie mogą opuścić swojej początkowej rangi (również nieprzyjacielskie pionki, które nie są skoczkami, prawdopodobnie nie mogły wejść legalnie), istnieją inne podobne pomysły, na przykład jeśli białe h -Pawn poruszył się raz, wieże powinny być nadal uwięzione wewnątrz formacji pionków itp.

Zegary o połowie / pełnym ruchu:

• W przypadku kwadratu en passant zegar połowy ruchu musi wynosić 0
• HalfMoves <= ((FullMoves-1)*2)+(if BlackToMove 1 else 0), +1 lub +0 zależą od strony do poruszania się
• HalfMoves musi być x >= 0i FullMovesx >= 1

Inny:

• Upewnij się, że FEN zawiera wszystkie potrzebne części (np. Aktywny kolor, zdolność rzucania, kwadrat en passant itp.)

Uwaga: nie ma potrzeby, aby „gracze nie powinni mieć więcej niż 16 sztuk”, ponieważ punkty „nie więcej niż 8 pionków” + „zapobiegają dodatkowym promowanym pionom” + „dokładnie jeden król” powinien już pokryć ten punkt

Uwaga 2: te zasady mają na celu sprawdzanie poprawności pozycji wynikających z pozycji początkowej normalnych szachów, niektóre reguły unieważniają niektóre pozycje z Chess960 (wyjątek, jeśli rozpoczęto od układu nr 518) i generowane łamigłówki, więc unikaj ich, aby uzyskać funkcjonalny walidator.

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

Oto wyrażenie regularne, którego używam, aby upewnić się, że łańcuch FEN jest rzeczywiście prawidłowy. Nie przeprowadza żadnych testów dotyczących legalnej / nielegalnej pozycji, ale jest to dobry punkt wyjścia.

Dla pozostałych w silniku Sztokfisz jest prosta funkcja, która sprawdza poprawność łańcucha 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);
}

Oto prosty algorytm cofania, pod warunkiem, że masz funkcję, która może sprawdzać cofanie legalnych ruchów w każdym stanie tablicy (znanym również jako pozycja):

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

W specyfikacji FEN nic nie mówi, że reprezentowana pozycja musi być osiągalna z tablicy początkowej. Udowodnienie, że dana pozycja jest osiągalna z tablicy początkowej, jest nierozwiązanym problemem.

W prawidłowym ciągu FEN liczba ruchów w połowie musi być zgodna z en passant docelowym kwadratem; jeśli obecny jest kwadrat docelowy, wówczas połowa ruchu musi wynosić zero. połowa ruchu musi być również zgodna z pełnym numerem ruchu; np. liczba ruchów w połowie wynosząca dziesięć jest niezgodna z pełną liczbą ruchów wynoszącą trzy.

Spóźnienie na imprezę.

Nie można w 100% zweryfikować, czy pozycja jest legalna, ale dlaczego walidacja powinna mieć znaczenie? Możemy grać w szachy niezależnie od tego, czy pozycja pochodzi od pozycji początkowej (tak zwana „tablica gier”). Analiza może być bardzo interesująca, ale zdarza się, że jest to nielegalne.

Więc sprawdziłbym tylko:

• Czy z każdej strony jest dokładnie 1 król?
• Czy nie ma pionków na pierwszym lub ósmym stopniu?
• Czy strona, która się porusza, nie daje już czeku?

Jeśli to trzy TAK, możemy grać w szachy w przód z tego schematu. I nawet ta krótka lista warunków, które możemy rozwiązać.