Problem with bitboard knight attack generator

[Dave_N]

Here is how I handled the fen

Code: Select all

		int rank = 0;
		int file = 0;
		for&#40; int i = 0; i < vecFen&#91;0&#93;.length&#40;); i++ )
		&#123;
			char c = vecFen&#91;0&#93;&#91;i&#93;;

			if&#40; c== '/' )
			&#123;
				rank++;
				file = 0;
				continue;
			&#125;
			if&#40; &#40;c >= '1') && &#40;c <= '8') )
			&#123;
				file += c-'0';
				continue;
			&#125;

			if&#40; isalpha&#40;c&#41; )
			&#123;
				
				switch&#40;c&#41;
				&#123;
				case 'P'&#58;board&#91;file&#93;&#91;7-rank&#93; = wPawn;break;
				case 'N'&#58;board&#91;file&#93;&#91;7-rank&#93; = wKnight;break;
				case 'B'&#58;board&#91;file&#93;&#91;7-rank&#93; = wBishop;break;
				case 'R'&#58;board&#91;file&#93;&#91;7-rank&#93; = wRook;break;
				case 'Q'&#58;board&#91;file&#93;&#91;7-rank&#93; = wQueen;break;
				case 'K'&#58;board&#91;file&#93;&#91;7-rank&#93; = wKing;break;
				case 'p'&#58;board&#91;file&#93;&#91;7-rank&#93; = bPawn;break;
				case 'n'&#58;board&#91;file&#93;&#91;7-rank&#93; = bKnight;break;
				case 'b'&#58;board&#91;file&#93;&#91;7-rank&#93; = bBishop;break;
				case 'r'&#58;board&#91;file&#93;&#91;7-rank&#93; = bRook;break;
				case 'q'&#58;board&#91;file&#93;&#91;7-rank&#93; = bQueen;break;
				case 'k'&#58;board&#91;file&#93;&#91;7-rank&#93; = bKing;break;
				&#125;
				file++;
				continue;
			&#125;
		&#125;

		if&#40; vecFen&#91;1&#93;&#91;0&#93; == 'b' &#41;mov = BLACK;

		if&#40; vecFen&#91;1&#93;&#91;0&#93; == 'w' ) mov = WHITE;

// etc for castling rights, empassant, 50 move counter and move number

basically the fen string is split by white space and stored in a vector of strings (I didn't have much time for optimal programming).
Does using byte aligned structures help ? I often see programs with a variable to pad up the size.

[Sven]

Hi Matthew,

currently I can't answer your question regarding detecting spaces since I have serious trouble understanding your FEN parser code.

For instance, I see that you store information in a "Pieces[]" array. What is its meaning, and where do you store the squares of the pieces? It seems Pieces[] does only count the number of pieces of each type, although I don't understand the shifting loop below the big switch() block. If Pieces[] is your bitboard representation then I think you are handling it incorrectly, there must be some shifting by the square number you detected.

Furthermore, why do you increment "i" depending on values read from the input string within a loop "for (i=0; i<64; i++)" if the index "i" is also used to access the next character from the input string itself? That seems to skip large parts of the FEN string in fact ...

To my view your approach is not straightforward, at least. I would have expected another variable "square" initialized with A8 (that's where an FEN string starts), used to store squares of the pieces being found, incremented whenever a number is read, and decremented by 15 when reading a '/' which means to skip from, say, H8 to A7.

The "square" variable can also, for better readability, be replaced by a combination of rank and file, where rank would start at 7 and file at 0, accordingly. Then you would calculate the square from these two each time you need to store the square of a piece you found.

Whenever I wrote an FEN parser I used to write six separate subroutines matching the six parts of an FEN string, like parseBoardFEN(), parseSideToMoveFEN(), parseCastleRightsFEN() and so on. Each one initializes its state somehow, then reads characters in a loop until either
- a space character is read,
- a null byte (end of string) is detected, or
- an error occurs (which should also trigger not to continue parsing the later parts of the FEN string),
and directly stores its parsing result in corresponding data structures.

Take also care about assumptions on the length of the input string. A somewhat generous limit for the maximum total length of an FEN string for standard chess is 100, something like "8*8 + 7 + 1 + 1 + 4 + 1 + 2 + 1 + 4 + 1 + 4 + 1 + (lazyness buffer)". I would simply use a character pointer to run over the string that was provided, and terminate loops as described above. Null-termination of the input string is a precondition, of course, which you have to guarantee somewhere outside your parser.

Beware of using assert() on wrong input since this crashes your program in the debug version but, more seriously, remains undetected in the release version. You should better quit parsing immediately on any error you detect, and let your program print an error message like "wrong FEN" together with the FEN string and, for the advanced version, perhaps also together with a short hint what exactly was found to be wrong (e.g. illegal character, missing or superfluous data in board FEN, ...).

Sven

[Dave_N]

I agree about error checking, I haven't completely error checked in some areas - fens included - the only place I use to print "bad fen" is if the string is empty or if there aren't enough substrings - I actually add default subtrings for the case of no move number or 50 move number. Thanks for the point about 100 chars being a good maximum number, obviously if the chars in the string are not "PRNBQKprnbqk" then it is a bad Fen too.

[Sven]

I agree about error checking, I haven't completely error checked in some areas - fens included - the only place I use to print "bad fen" is if the string is empty or if there aren't enough substrings - I actually add default subtrings for the case of no move number or 50 move number. Thanks for the point about 100 chars being a good maximum number, obviously if the chars in the string are not "PRNBQKprnbqk" then it is a bad Fen too.

Hi Dave,

Just as a note: I replied to Matthew, not to you.

Sven

[Dave_N]

Yes and I was thanking you for mentioning a numerical fact about FEN's while agreeing about error checking to Mathew, who is probably more optimal than me in C++/C. Maybe that should have been clearer, but I hope you don't mind my comment because I realized you pointed out a problem with my code's error checking functionality.

The best answer, in retrospect, is to check for validity before the call to setboard() or whatever you call your function, because some FEN's can be set by functions that have generated the FEN within the program, for example to hop ahead 10 moves.

just as a note: There is a very nice free C# code on the internet that also shows how to generate and set board structures from FEN strings, I prefer my method.

[Sven]

I agree about error checking, I haven't completely error checked in some areas - fens included - the only place I use to print "bad fen" is if the string is empty or if there aren't enough substrings - I actually add default subtrings for the case of no move number or 50 move number. Thanks for the point about 100 chars being a good maximum number, obviously if the chars in the string are not "PRNBQKprnbqk" then it is a bad Fen too.

Hi Dave,

Just as a note: I replied to Matthew, not to you.

Hi again Dave,

I have now also read you FEN code. What you posted looks correct in general, so my only remark is that, apart from missing error handling which you already noted above, your code may also crash on an illegal FEN string. For instance, providing a substring between two slashes that covers more than 8 files, or providing more than 7 slashes will lead to an out of bounds access to your board array. You should definitely handle that before actually writing into your array, e.g. by exiting from the loop if file > 7 or rank > 7 immediately above your "if (isalpha(c))" check.

Also, instead of the isalpha() plus switch(c) you could add a default case into the switch block that exits the loop.

Reading a slash or the end of the substring with "file" different from 8 would be an error, too, as well as reaching the end of the substring with "rank" different from 7.

Sven

[Dave_N]

Yes it would crash - see the above solution - the error checking needs to be performed during the process that splits by white spaces in the case of my program.

Note: the default case can't hurt too in case of the setfen function being called while parsing PGN variations to check for errors in the loading phase.

Thanks for the points.

[Sven]

Yes it would crash - see the above solution - the error checking needs to be performed during the process that splits by white spaces in the case of my program.

Note: the default case can't hurt too in case of the setfen function being called while parsing PGN variations to check for errors in the loading phase.

Thanks for the points.

I would avoid to do double work. There is one place that can detect all possible kinds of errors in an FEN input string, and that is the FEN parser itself. Just manage to have an error flag and, if you like to give more detailled error messages, an error message string, let your parser have both as output parameters, and quit parsing immediately when the error flag is set. If you also want to keep your board data structure intact in case of an FEN error then write to a copy, and only change your original board if no parsing error occurred (although there is no strict requirement for that).

Sven

[sje]

CookieCat's board decoder (Man Placement Data; the first FEN/EPD token):

Code: Select all

  function BoardDecode(var board: boardtype; str: String): Boolean;
    var
      myresult: Boolean;
      index, limit: Integer;
      ch: Char;
      bfindex, brindex: Integer;
      digit: digittype;

    procedure PutMan(man: mantype);
    begin
      board.rfv[brindex, bfindex] := man;
      Inc(bfindex)
    end; { PutMan }

    procedure PutVacant;
    begin
      PutMan(manvv)
    end; { PutVacant }

    procedure PutVacantSeq;
    begin
      while bfindex < bfilelen do
        PutVacant
    end; &#123; PutVacantSeq &#125;

  begin

    &#123; MPD decoding &#125;

    with board do
      begin
        myresult &#58;= True;
        index &#58;= 0;
        limit &#58;= Length&#40;str&#41;;
        brindex &#58;= Ord&#40;brank8&#41;;
        bfindex &#58;= Ord&#40;bfilea&#41;;

        &#123; Loop once per input character &#125;

        while myresult and &#40;index < limit&#41; do
          begin
            ch &#58;= str&#91;index + 1&#93;;
            Inc&#40;index&#41;;
            if ch = '/' then
              begin
                if brindex = 0 then
                  myresult &#58;= False
                else
                  begin
                    PutVacantSeq;
                    Dec&#40;brindex&#41;;
                    bfindex &#58;= Ord&#40;bfilea&#41;
                  end
              end
            else
              if IsCharDigit&#40;ch&#41; then
                begin
                  if bfindex = bfilelen then
                    myresult &#58;= False
                  else
                    begin
                      digit &#58;= DecodeDigit&#40;ch&#41;;
                      if &#40;digit < 1&#41; or &#40;digit > bfilelen&#41; then
                        myresult &#58;= False
                      else
                        if &#40;digit + bfindex&#41; > bfilelen then
                          myresult &#58;= False
                        else
                          while digit > 0 do
                            begin
                              PutVacant;
                              Dec&#40;digit&#41;
                            end
                    end
                end
              else
                if IsCharMan&#40;ch&#41; then
                  if bfindex = bfilelen then
                    myresult &#58;= False
                  else
                    PutMan&#40;DecodeMan&#40;ch&#41;)
                else
                  myresult &#58;= False
          end;

        &#123; Finalize &#125;

        if myresult then
          if brindex <> 0 then
            myresult &#58;= False
          else
            PutVacantSeq;
        if not myresult then
          BoardReset&#40;board&#41;
      end;
    BoardDecode &#58;= myresult
  end; &#123; BoardDecode &#125;

[Dave_N]

I agree about error checking, I haven't completely error checked in some areas - fens included - the only place I use to print "bad fen" is if the string is empty or if there aren't enough substrings - I actually add default subtrings for the case of no move number or 50 move number. Thanks for the point about 100 chars being a good maximum number, obviously if the chars in the string are not "PRNBQKprnbqk" then it is a bad Fen too.

Hi Dave,

Just as a note: I replied to Matthew, not to you.

Hi again Dave,

I have now also read you FEN code. What you posted looks correct in general, so my only remark is that, apart from missing error handling which you already noted above, your code may also crash on an illegal FEN string. For instance, providing a substring between two slashes that covers more than 8 files, or providing more than 7 slashes will lead to an out of bounds access to your board array. You should definitely handle that before actually writing into your array, e.g. by exiting from the loop if file > 7 or rank > 7 immediately above your "if (isalpha(c))" check.

Also, instead of the isalpha() plus switch(c) you could add a default case into the switch block that exits the loop.

Reading a slash or the end of the substring with "file" different from 8 would be an error, too, as well as reaching the end of the substring with "rank" different from 7.

Sven

Yes I see ... actually I might error check everything to be safer, the fen is used in a trustworthy way until user input, however there is no need to even allow internal errors.