Wie erfahre ich, wann eine FEN-Stelle legal ist?

19

Ich mache ein persönliches Projekt, in dem ich zu einem Zeitpunkt, an dem ich die Position des FEN überprüfen muss, mit einigen grundlegenden Überprüfungen begann, z Dinge.

Aber welche weiteren Überprüfungen sollte ich durchführen, um sicherzustellen, dass ein FEN legal ist?

ajax333221
quelle

Antworten:

18

Hier ist eine gut organisierte Liste, die 99,99% der gemeinsamen Positionen bestätigen sollte:

Tafel:

  • Es gibt genau 8 Spalten
  • Die Summe der leeren Felder und Steine ​​addiert sich zu 8 für jeden Rang (Zeile)
  • Es gibt keine fortlaufenden Nummern für leere Felder

Könige:

  • Überprüfen Sie, ob es genau ein w_king und ein b_king gibt
  • Stellen Sie sicher, dass die Könige 1 Quadrat voneinander entfernt sind

Schecks:

  • Nicht aktive Farbe ist nicht aktiviert
  • Die aktive Farbe wird weniger als dreimal überprüft (eine dreifache Überprüfung ist nicht möglich). im Falle von 2, dass es nie Bauer + (Bauer, Bischof, Ritter), Bischof + Bischof, Ritter + Ritter ist

Bauern:

  • Es gibt nicht mehr als 8 Bauern von jeder Farbe
  • Es gibt keine Bauern im ersten oder letzten Rang (Reihe), da sie sich entweder in einer falschen Startposition befinden oder befördert werden sollten.
  • Bei en passantem Platz; Überprüfen Sie, ob es legal erstellt wurde (z. B. muss es auf dem x3oder x6Rang sein, es muss ein Bauer (von der richtigen Farbe) davor sein und das en passant Quadrat und das dahinter sind leer).
  • Wenn Sie verhindern möchten, dass mehr beförderte Figuren als Bauern fehlen (z. B. extra_pieces = Math.max(0, num_queens-1) + Math.max(0, num_rooks-2)...und dann extra_pieces <= (8-num_pawns)), sollten Sie auch spezielle Berechnungen für Bischöfe durchführen. Wenn Sie zwei (oder mehr) Bischöfe mit derselben quadratischen Farbe haben, können diese nur durch Beförderung von Bauern erstellt werden diese information zu der oben genannten formel irgendwie
  • Es ist möglich, die Bauernformation zu erreichen (zB bei mehreren Bauern in einem einzigen Feld müssen genügend feindliche Figuren fehlen, um diese Formation zu bilden). Hier einige nützliche Regeln:
    1. Es ist nicht möglich, mehr als 6 Bauern in einer einzelnen Datei (Spalte) zu haben (da Bauern in der ersten und letzten Reihe nicht existieren können).
    2. Die Mindestanzahl an fehlenden gegnerischen Stücken, um mehrere Bauern in einem einzigen Feld zu erreichen. 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=15Wenn Sie beispielsweise 5 Bauern in A oder H sehen, müssen dem anderen Spieler mindestens 10 Figuren aus seinen 15 eroberbaren Stücken fehlen
    3. Wenn es weiße Bauern in a2 und a3 gibt, kann es legal keinen in b2 geben, und diese Idee kann weiter ausgebaut werden, um mehr Möglichkeiten abzudecken

Rochade:

  • Wenn der König oder die Türme nicht in ihrer Ausgangsposition sind; Die Rochierfähigkeit für diese Seite ist verloren (im Falle eines Königs sind beide verloren).

Bischöfe:

  • Suchen Sie nach Bischöfen in der ersten und letzten Reihe (Reihe), die von Bauern gefangen sind, die sich nicht bewegt haben, zum Beispiel:
    1. ein Bischof (jede Farbe), der hinter 3 Bauern gefangen ist
    2. ein Bischof, der hinter 2 nicht-feindlichen Bauern gefangen ist (nicht von feindlichen Bauern, weil wir diese Position erreichen können, indem wir Bauern unterbewegen, aber wenn wir die Anzahl der Bauern überprüfen und extra_piecesfeststellen, ob dieser Fall möglich ist oder nicht)

Nicht-Springer:

  • (Vermeiden Sie dies, wenn Sie Fisher's Chess960 validieren möchten.) Befinden sich nicht springende feindliche Teile zwischen dem König und dem Turm und gibt es immer noch einige Bauern, die sich nicht bewegen; Überprüfen Sie, ob diese feindlichen Teile dort legal eingedrungen sind. Fragen Sie sich auch: Musste sich der König oder Turm bewegen, um diese Position zu erreichen? (Wenn ja, müssen wir sicherstellen, dass die Fähigkeiten der Rochade dies widerspiegeln.)
  • Wenn sich alle 8 Bauern noch in der Startposition befinden, dürfen nicht alle Nicht-Springer ihren ursprünglichen Rang verlassen haben (auch Nicht-Springer-Feindfiguren können möglicherweise nicht legal eingetreten sein), es gibt andere ähnliche Ideen, etwa wenn das weiße h - Bauer einmal bewegt, die Türme sollten noch in der Bauernformation gefangen sein usw.

Halb- / Ganzzuguhren:

  • Im Fall eines en passant Quadrat, die Hälfte bewegt Uhr muss gleich 0
  • HalfMoves <= ((FullMoves-1)*2)+(if BlackToMove 1 else 0)hängt die +1 oder +0 von der Seite ab, die bewegt werden soll
  • Die HalfMoves müssen x >= 0und die FullMoves seinx >= 1

Andere:

  • Stellen Sie sicher, dass der FEN alle Teile enthält, die benötigt werden (z. B. aktive Farbe, Rochierfähigkeit, en passant Quadrat usw.).

Hinweis: Es ist nicht erforderlich, die Option "Spieler sollten nicht mehr als 16 Steine ​​haben" zu überprüfen, da die Punkte "nicht mehr als 8 Bauern" + "zusätzliche beförderte Steine ​​verhindern" + "Genau ein König" diesen Punkt bereits abdecken sollten

Hinweis 2: Diese Regeln dienen zur Validierung von Positionen, die sich aus der Startposition des normalen Schachs ergeben. Einige der Regeln machen Positionen aus Chess960 ungültig (Ausnahme: Start ab Arrangement Nr. 518) und generierte Rätsel.

ajax333221
quelle
1
Sie können auch die Bauernstruktur überprüfen, z. B. könnten weiße Bauern niemals auf a2, a3 und b2 stehen. Es gibt keine Möglichkeit, dass ein Bauer sowohl auf a3 als auch auf b2 steht.
Akavall
Soll das heißen, dass FEN-Positionen nur von der Anfangsposition aus erreichbar sein sollten? Was ist, wenn ich Rätselpositionen durch eine FEN darstellen lassen möchte? Manchmal werden sie auf eine Weise erstellt, die in einem tatsächlichen Spiel nicht zu erreichen ist ...
tbischel
@tbischel Ich mache diese Regeln aus der normalen Schachperspektive (nicht für Chess960 oder andere generierte Positionen gedacht), danke ich könnte dies irgendwo deutlicher machen
ajax333221
Selbst für normales Schach möchten Sie möglicherweise nicht alle diese Prüfungen durchführen. Am Ende haben Sie ein Programm, das keine illegale Position als FEN darstellen kann. In der Praxis kommt es jedoch vor, dass illegale Züge manchmal erst nach dem Spiel bemerkt werden. Sollte es unmöglich sein, Diagramme aus solchen Spielen usw. anzuzeigen?
RemcoGerlich
1
@ ajax333221: Diese Seite gibt rechtliche Spiele , in denen wissen mehr als 5 Bauern auf das bekommt aDatei.
9
\s*([rnbqkpRNBQKP1-8]+\/){7}([rnbqkpRNBQKP1-8]+)\s[bw-]\s(([a-hkqA-HKQ]{1,4})|(-))\s(([a-h][36])|(-))\s\d+\s\d+\s*

Hier ist ein regulärer Ausdruck, mit dem ich sicherstellen möchte, dass eine FEN-Zeichenfolge tatsächlich gültig ist. Es werden keine Tests für eine legale / illegale Position durchgeführt, aber es ist ein guter Ausgangspunkt.

Andrew
quelle
Ich denke, die aktive Farbe ist ein Muss (Sie erlauben es -) und halbe / volle Uhren sind manchmal optional, denke ich. Auch ich habe den a-hTeil über die /^\s*([rnbqkpRNBQKP1-8]+\/){7}([rnbqkpRNBQKP1-8]+)\s[bw]\s(-|K?Q?k?q?)\s(-|[a-h][36])/
Rochierfähigkeit
Ich habe gerade bemerkt, dass wir den Test "Keine Bauern in Beförderungsrängen" mit etwas beginnen können, wie([rnbqkRNBQK1-8]+\/)([rnbqkpRNBQKP1-8]+\/){6}([rnbqkRNBQK1-8]+) ....
ajax333221
Auch für die Uhren kann dies gut sein, (0|[1-9][0-9]*)\s([1-9][0-9]*)da Züge keine führenden Nullen haben und ein vollständiger Zug nicht mit 0 beginnen kann (Code-Gutschrift)
ajax333221
4

Für die anderen gibt es eine einfache Funktion in der Stockfish-Engine, die einen FEN-String validiert.

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);
}
Thiago Pires
quelle
1
Es sieht so aus, als ob die gesamte eigentliche Validierung in durchgeführt wurde position.is_okay(). Der Code hier führt nur ein paar grundlegende Überprüfungen durch, um sicherzustellen, dass er korrekt formatiert ist und dass es sich lohnt, die echte Validierung durchzuführen (dh nicht offensichtlich illegal).
Undergroundmonorail
3

Hier ist ein einfacher Backtracking-Algorithmus, vorausgesetzt, Sie verfügen über eine Funktion, mit der Sie in jedem Board-Status (auch als Position bezeichnet) Reverse Legal Moves überprüfen können:

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
ldog
quelle
1

Nichts in der FEN-Spezifikation besagt, dass die dargestellte Position vom ursprünglichen Array aus erreichbar sein muss. Es ist ein ungelöstes Problem zu beweisen, dass eine bestimmte Position über das ursprüngliche Array erreichbar ist.

In einer gültigen FEN-Zeichenfolge muss die Anzahl der halben Züge mit dem en-passanten Zielquadrat übereinstimmen. Wenn ein Zielquadrat vorhanden ist, muss die Anzahl der halben Züge Null sein. Die Anzahl der halben Züge muss auch mit der vollen Zugnummer übereinstimmen. ZB ist eine halbe Zugzahl von zehn nicht mit einer vollen Zugzahl von drei kompatibel.

ChessNotation
quelle
1

Ich komme zu spät zur Party.

Es ist nicht möglich, zu 100% zu validieren, ob eine Position legal ist, aber warum sollte die Validierung von Bedeutung sein? Wir können Schach spielen, ob sich die Position zufällig von der Startposition ableitet oder nicht (sogenanntes „Game Array“). Es könnte eine sehr interessante Position zu analysieren sein, aber es kommt einfach vor, dass es illegal ist.

Also würde ich nur überprüfen:

  • Gibt es genau 1 König von jeder Seite?
  • Gibt es keine Bauern auf dem ersten oder achten Rang?
  • Ist die Seite zu bewegen, die nicht bereits Scheck gibt?

Wenn das drei JA sind, können wir nach diesem Diagramm vorwärts Schach spielen. Und selbst diese kurze Liste von Zuständen könnten wir lockern können.

Laska
quelle