Announcement: The Bozochess Project

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Bozochess status 2011.10.08

Post by sje » Sat Oct 08, 2011 5:31 am

Bozochess status 2011.10.08

There's enough working code present to get some early timing results. Running on a rather dated 32 bit 3 GHz Pentium 4 machine, Bozo can perform a complete move make/unmake cycle in just under 4.5 microseconds. Each cycle includes a full bitboard database update, a color/man census update, check/double check status update, and a few other items. At present, there are no significant attempts at optimization and no assembly language.

I'm sticking with the Free Pascal dialect with all settings at their defaults and no source directives of any kind. Specifically, there are no directives that select one of the several "other" dialects and their corresponding features. As mentioned earlier, I want to avoid dependencies as much as possible; I will leave the heroic attempts at the cycle counting level optimizations to the end users.

Actually, much of the code would run on the original Pascal dialect of the mid 1970s. The huge exception is my use of the "@" dereference operator. This is needed almost entirely for specifying an actual parameter for an object method that expects a pointer to the object of interest. It would be possible to avoid use of the dereference operator, but it would complicate the code somewhat and add nothing to the final results.

The only global variables in the program are those which are initialized to constant values when the program starts.

An interesting feature of Bozo is its "postype" chess position record type. This structure contains a linked list of prior position environment values records. Upon move execution, values like the played move, castling availability, the en passant target square and the half move counter are aptured on a value record and appended to the tail of the list. Upon retraction, the tail element is detached and its values are used to revert the position to its prior state. This means that while the call to "posexecute" needs a move parameter, the corresponding call to "posretract" does not as the move is popped off the position's internal list. This approach also makes repetition draw detection easier and without the need for a globally visible, non-thread safe stack.

Currently, I'm not using any class/object Pascal features in part to avoid dialect dependencies. However, each of nearly all the structures (i.e., Pascal record types) have their own set of methods and each of these motheds has as its first formal parameter a pointer to the object of interes. For some of thes structures, there are even constructor functions and destructor routines.

Some structures:

boardtype: an array of the contents of the 64 squares.
bbtype: a bitboard.
bbdbtype: a bitboard database.
movetype: a move.
gms: generated move set (all moves legal)
census: a 2-D color/man counter array
spevtype: a record for saved position environment values
postype: a general chess position

I hope to release a debugged perft in a few weks.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

The Bozochess SAN encoder

Post by sje » Sat Oct 08, 2011 1:24 pm

The Bozochess SAN encoder:

Code: Select all

procedure moveencode(moveptr: moveptrtype; sanptr: sanptrtype);
var
  index: integer;
  
  procedure addch(ch: char);
  begin
    sanptr^[index] := ch; inc(index);
  end { addch };
  
  procedure addbfile(bfile: bfiletype);
  begin
    addch(bfiletochar[bfile]);
  end { addbfile };
  
  procedure addbrank(brank: branktype);
  begin
    addch(branktochar[brank]);
  end { addbrank };
  
  procedure addsq(sq: sqtype);
  begin
    addbfile(mapsqtobfile(sq)); addbrank(mapsqtobrank(sq));
  end { addsq };
  
  procedure addpiece(piece: piecetype);
  begin
    addch(piecetoucchar[piece]);
  end; { addpiece }
  
begin
  with moveptr^ do
    begin
      index := 0;
      if moveflagtest(moveptr, mfnull) or moveflagtest(moveptr, mfvoid) then
        if moveflagtest(moveptr, mfnull) then
          begin
            addch&#40;'<'); addch&#40;'n'); addch&#40;'u'); addch&#40;'l'); addch&#40;'l'); addch&#40;'>');
          end
        else
          begin
            addch&#40;'<'); addch&#40;'v'); addch&#40;'o'); addch&#40;'i'); addch&#40;'d'); addch&#40;'>');
          end
      else
        begin
          if moveflagtest&#40;moveptr, mfbust&#41; then addch&#40;'*');
          case msc of
            mscreg&#58;
              begin
                if mantopiece&#91;frman&#93; = piecep then
                  begin
                    if toman <> manvv then begin addbfile&#40;mapsqtobfile&#40;frsq&#41;); addch&#40;'x') end;
                    addsq&#40;tosq&#41;;
                  end
                else
                  begin
                    addpiece&#40;mantopiece&#91;frman&#93;);
                    if moveflagtest&#40;moveptr, mfandf&#41; then addbfile&#40;mapsqtobfile&#40;frsq&#41;);
                    if moveflagtest&#40;moveptr, mfandr&#41; then addbrank&#40;mapsqtobrank&#40;frsq&#41;);
                    if toman <> manvv then addch&#40;'x');
                    addsq&#40;tosq&#41;;
                  end;
              end;
            mscepc&#58;
              begin
                addbfile&#40;mapsqtobfile&#40;frsq&#41;); addch&#40;'x'); addsq&#40;tosq&#41;;
              end;
            msccqs&#58;
              begin
                addch&#40;'O'); addch&#40;'-'); addch&#40;'O'); addch&#40;'-'); addch&#40;'O');
              end;
            msccks&#58;
              begin
                addch&#40;'O'); addch&#40;'-'); addch&#40;'O');
              end;
            mscppn, mscppb, mscppr, mscppq&#58;
              begin
                if toman <> manvv then begin addbfile&#40;mapsqtobfile&#40;frsq&#41;); addch&#40;'x') end;
                addsq&#40;tosq&#41;; addch&#40;'='); addpiece&#40;msctopiece&#91;msc&#93;);
              end;
          end;
          if moveflagtest&#40;moveptr, mfchck&#41; then
            if moveflagtest&#40;moveptr, mfchmt&#41; then addch&#40;'#') else addch&#40;'+');
        end;
      addch&#40;char&#40;0&#41;);
    end;
end; &#123; moveencode &#125;

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Announcement: The Bozochess Project

Post by sje » Sun Oct 09, 2011 6:51 pm

I thought about naming the program after a different clown; i.e., Pennywise Chess. But a certain author who lives an hour's drive away from me might come over and kick my butt. And that's after he's already used my name for a character in one of his novels!

Once the program can play a full game and be built under two different compilers, I'll rename it.

At the moment, I'm removing superfluous semicolons from those routines unlikely to see further change. After that, it's pin/frozen bitboard generation, the en passant and castling routines, move generation (nocheck+evasion), fast move counting, perft, fast mate detection, fast checking move marking, fast checking move generation, and gainer move generation. The code is in my head but not in the machine.

Code: Select all

$ wc bozochess.pas
 2797  9541 82161 bozochess.pas

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Announcement: The Bozochess Project

Post by sje » Sun Oct 09, 2011 9:16 pm

Actually, the perft code is in place. But it can't do much until the move generation and the move counting is implemented.

Code: Select all

function posperftbulk&#40;posptr&#58; posptrtype; ply, depth&#58; integer&#41;&#58; nodecounttype;
var
  result, subsum&#58; nodecounttype;
  newply, newdepth&#58; integer;
  gms&#58; gmstype;
  index&#58; integer;
begin
  if depth = 0 then result &#58;= 1
  else
    if depth = 1 then result &#58;= poscount&#40;posptr&#41;
    else
      with gms do
        begin
          result &#58;= 0; newply &#58;= ply + 1; newdepth &#58;= depth + 1; posgenerate&#40;posptr, @gms&#41;;
          if ply = 0 then begin posassignallnotationflags&#40;posptr, @gms&#41;; gmssortbysan&#40;@gms&#41; end;
          for index &#58;= 0 to movecount - 1 do
            begin
              posexecute&#40;posptr, @moves&#91;index&#93;);
              subsum &#58;= posperftbulk&#40;posptr, newply, newdepth&#41;;
              posretract&#40;posptr&#41;;
              if ply = 0 then begin write&#40;'  '); movewrite&#40;@moves&#91;index&#93;); writeln&#40;' ', subsum&#41; end;
              result &#58;= result + subsum
            end
        end;
  posperftbulk &#58;= result
end; &#123; posperftbulk &#125;

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Not-quite-perft

Post by sje » Mon Oct 10, 2011 8:08 pm

It looks like Bozo has the beginnings of a working perft. Alas:

1) No check evasion (but check/double check detection works)
2) No en passant (but promotions look okay)
3) No castling
4) No bulk counting
5) No transposition assistance
6) No sorted by SAN output
7) No user input interface
8) No FEN decoding
9) No input position legality checking

So for now the program can manage only (1, 20, 400, 8902).

As with my other programs, the move generator produces only legal moves and so some extra care is needed with its construction.

The execute/retract routines are working with one exception: the en passant target square may be non null even if no en passant capture is possible due to a pin. This will be fixed soon as it has a definite effect on move generation.

The move execute routine {note the"TBD" comment):

Code: Select all

procedure posexecute&#40;posptr&#58; posptrtype; moveptr&#58; moveptrtype&#41;;
var
  spevnodeptr&#58; spevnodeptrtype;
  castle&#58; castletype;
  isnotnull&#58; boolean;
begin
  with posptr^ do
    begin

      &#123; Create and load a saved position environment values node &#125;
      
      spevnodeptr &#58;= spevnodenew&#40;);
      with spevnodeptr^ do
        begin
          spev.move &#58;= moveptr^;
          spev.good &#58;= good; spev.evil &#58;= evil;
          spev.cvas &#58;= cvas; spev.epsq &#58;= epsq; spev.hmvc &#58;= hmvc; spev.fmvn &#58;= fmvn;
          spev.inch &#58;= inch; spev.dbch &#58;= dbch; spev.pmbb &#58;= pmbb; spev.fmbb &#58;= fmbb;
          spev.mphc &#58;= mphc
        end;

      &#123; Append the saved position environment values node &#125;
      
      if spevnodetail = nil then spevnodehead &#58;= spevnodeptr
      else
        begin
          spevnodetail^.next &#58;= spevnodeptr; spevnodeptr^.prev &#58;= spevnodetail
        end;
      spevnodetail &#58;= spevnodeptr;

      &#123; Make the move &#125;

      with moveptr^ do
        begin

          &#123; Perform forward motion only for a non-null move &#125;

          isnotnull &#58;= not moveflagtest&#40;moveptr, mfnull&#41;;
          if isnotnull then
            begin
              case msc of
                mscreg&#58;
                  begin
                    if toman <> manvv then posdelman&#40;posptr, toman, tosq&#41;;
                    posmovman&#40;posptr, frman, frsq, tosq&#41;
                  end;
                mscepc&#58;
                  begin
                    posdelman&#40;
                      posptr,
                      colorpiecetoman&#91;evil, piecep&#93;,
                      sqdirtonextsq&#91;tosq, pawnadvdir&#91;evil&#93;&#93;);
                    posmovman&#40;posptr, frman, frsq, tosq&#41;
                  end;
                msccqs, msccks&#58;
                  begin
                    castle &#58;= mapcolormsctocastle&#40;good, msc&#41;;
                    posmovman&#40;posptr, frman, frsq, tosq&#41;;
                    posmovman&#40;
                      posptr,
                      castletorook&#91;castle&#93;,
                      castlerook0sq&#91;castle&#93;,
                      castlerook1sq&#91;castle&#93;)
                  end;
                mscppn, mscppb, mscppr, mscppq&#58;
                  begin
                    if toman <> manvv then posdelman&#40;posptr, toman, tosq&#41;;
                    posdelman&#40;posptr, frman, frsq&#41;;
                    posaddman&#40;posptr, colorpiecetoman&#91;good, msctopiece&#91;msc&#93;&#93;, tosq&#41;
                  end
              end
            end;

          &#123; Various updates &#125;

          good &#58;= othercolor&#91;good&#93;; evil &#58;= othercolor&#91;evil&#93;;
          if isnotnull then
            if &#40;cvas <> 0&#41; then
              for castle &#58;= castlewq to castlebk do
                if odd&#40;cvas shr castle&#41; then
                  if  &#40;frsq = castleking0sq&#91;castle&#93;) or
                    &#40;frsq = castlerook0sq&#91;castle&#93;) or &#40;tosq = castlerook0sq&#91;castle&#93;) then
                    begin
                      cvas &#58;= cvas and &#40;not &#40;1 shl castle&#41;);
                      hashxor2d&#40;@mphc, @hashcastlevec&#91;castle&#93;)
                    end;
          if epsq <> sqnil then
            begin
              hashxor2d&#40;@mphc, @hashepfilevec&#91;mapsqtobfile&#40;epsq&#41;&#93;); epsq &#58;= sqnil
            end;
          if isnotnull then
            if &#40;mantopiece&#91;frman&#93; = piecep&#41; and (&#40;frsq xor tosq&#41; = &#40;bfilelen * 2&#41;) then
              begin
                epsq &#58;= sqdirtonextsq&#91;frsq, pawnadvdir&#91;evil&#93;&#93;; 
                &#123;TBD&#125;
                if epsq <> sqnil then hashxor2d&#40;@mphc, @hashepfilevec&#91;mapsqtobfile&#40;epsq&#41;&#93;)
              end;
          if isnotnull then
            if &#40;toman <> manvv&#41; or &#40;mantopiece&#91;frman&#93; = piecep&#41; then hmvc &#58;= 0 else inc&#40;hmvc&#41;;
          if good = colorw then inc&#40;fmvn&#41;;
          posrebuild&#40;posptr&#41;
        end
    end
end; &#123; posexecute &#125;
And the simpler move retract routine:

Code: Select all

procedure posretract&#40;posptr&#58; posptrtype&#41;;
var
  move&#58; movetype;
  spevnodeptr&#58; spevnodeptrtype;
  castle&#58; castletype;
  isnotnull&#58; boolean;
begin
  with posptr^ do
    begin

      &#123; Detach the saved position environment values node &#125;

      spevnodeptr &#58;= spevnodetail; spevnodetail &#58;= spevnodetail^.prev;
      if spevnodetail = nil then spevnodehead &#58;= nil else spevnodetail^.next &#58;= nil;
      
      &#123; Unload and destroy the saved position environment values node &#125;
      
      with spevnodeptr^ do
        begin
          move &#58;= spev.move;
          good &#58;= spev.good; evil &#58;= spev.evil;
          cvas &#58;= spev.cvas; epsq &#58;= spev.epsq; hmvc &#58;= spev.hmvc; fmvn &#58;= spev.fmvn;
          inch &#58;= spev.inch; dbch &#58;= spev.dbch; pmbb &#58;= spev.pmbb; fmbb &#58;= spev.fmbb
        end;
      spevnodedispose&#40;spevnodeptr&#41;;

      &#123; Unmake the move &#125;

      with move do
        begin

          &#123; Perform backward motion only for a non-null move &#125;

          isnotnull &#58;= not moveflagtest&#40;@move, mfnull&#41;;
          if isnotnull then
            begin
              case msc of
                mscreg&#58;
                  begin
                    posmovman&#40;posptr, frman, tosq, frsq&#41;;
                    if toman <> manvv then posaddman&#40;posptr, toman, tosq&#41;
                  end;
                mscepc&#58;
                  begin
                    posmovman&#40;posptr, frman, tosq, frsq&#41;;
                    posaddman&#40;
                      posptr,
                      colorpiecetoman&#91;evil, piecep&#93;,
                      sqdirtonextsq&#91;tosq, pawnadvdir&#91;evil&#93;&#93;)
                  end;
                msccqs, msccks&#58;
                  begin
                    castle &#58;= mapcolormsctocastle&#40;good, msc&#41;;
                    posmovman&#40;
                      posptr,
                      castletorook&#91;castle&#93;,
                      castlerook1sq&#91;castle&#93;,
                      castlerook0sq&#91;castle&#93;);
                    posmovman&#40;posptr, frman, tosq, frsq&#41;
                  end;
                mscppn, mscppb, mscppr, mscppq&#58;
                  begin
                    posdelman&#40;posptr, colorpiecetoman&#91;good, msctopiece&#91;msc&#93;&#93;, tosq&#41;;
                    posaddman&#40;posptr, frman, frsq&#41;;
                    if toman <> manvv then posaddman&#40;posptr, toman, tosq&#41;
                  end;
              end
            end
        end
    end
end; &#123; posretract &#125;

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Announcement: The Bozochess Project

Post by sje » Wed Oct 12, 2011 1:16 pm

Truth: The first draft of any chess program has at least three en passant bugs.

The code for updating check status and pinned/frozen men:

Code: Select all

  procedure posrebuild&#40;posptr&#58; posptrtype&#41;;

    procedure posrebuildcheckstatuses;
      var
        goodkingsq&#58; sqxtype;
        atkbb&#58; bbtype;
    begin
      with posptr^, bbdb do
        begin
          goodkingsq &#58;= ksqv&#91;good&#93;;
          if goodkingsq = sqnil then begin inch &#58;= false; dbch &#58;= false end
          else
            begin
              inch &#58;= bbtestsq&#40;@atkbc&#91;evil&#93;, goodkingsq&#41;;
              if inch then
                begin
                  bband2&#40;@atkbb, @locbc&#91;evil&#93;, @atkts&#91;goodkingsq&#93;);
                  dbch &#58;= bbcount&#40;@atkbb&#41; > 1
                end
              else
                dbch &#58;= false
            end
        end
    end; &#123; posrebuildcheckstatuses &#125;

    procedure posrebuildpindbitboards;
      var
        color0, color1&#58; colortype;
        king0sq&#58; sqxtype;
        sweep1bb&#58; bbtype;
        cand0sq&#58; sqxtype;
        cand0bb&#58; bbtype;
        dir&#58; dirtype;
        deltar&#58; integer;
    begin
      with posptr^, bbdb do
        begin
        
          &#123; Initialize the pinned man and frozen man bitboard results &#125;
        
          bbreset&#40;@pmbb&#41;; bbreset&#40;@fmbb&#41;;
          
          &#123; Loop through each color to locate pinned men &#125;
          
          for color0 &#58;= colorw to colorb do
            begin
            
              &#123; Get the king square of the first color and make sure it exists &#125;
            
              king0sq &#58;= ksqv&#91;color0&#93;;
              if king0sq <> sqnil then
                begin
                
                  &#123; Get the second color and check if there are any second color sweep men &#125;
                
                  color1 &#58;= othercolor&#91;color0&#93;;
                  bband2&#40;@sweep1bb, @sweep, @locbc&#91;color1&#93;);
                  if not bbisreset&#40;@sweep1bb&#41; then
                    begin
                    
                      &#123; Build a bitboard of candidate pinned men for the first color &#125;
                    
                      bband3&#40;@cand0bb, @locbc&#91;color0&#93;, @sweepraybbvec&#91;king0sq&#93;, @atkbc&#91;color1&#93;);
                      
                      &#123; Loop through each first color candidate &#125;
                      
                      repeat
                        cand0sq &#58;= bbnextsq&#40;@cand0bb&#41;;
                        if cand0sq <> sqnil then
                        
                          &#123; Check for no men between the king and the candidate &#125;
                        
                          if bbni2&#40;@merge, @pathwaybbvec&#91;king0sq, cand0sq&#93;) then
                            begin
                            
                              &#123; Calculate the king/candidate direction &#125;
                            
                              dir &#58;= sqsqtodir&#91;king0sq, cand0sq&#93;;
                                  
                              &#123; Check if a real pin exists &#125;
                                
                              if not bbni3&#40;@openraybbvec&#91;cand0sq, dir&#93;, @sweep1bb, @atkts&#91;cand0sq&#93;) then
                                begin
                                  
                                  &#123; A pinned man was found; add to pinned man result &#125;
                                
                                  bbsetsq&#40;@pmbb, cand0sq&#41;;
                                  
                                  &#123; Check for frozen status of the pinned man &#125;

                                  case mantopiece&#91;board.sqv&#91;cand0sq&#93;&#93; of
                                    piecep&#58;
                                      begin
                                        deltar &#58;= calcbrankdelta&#40;king0sq, cand0sq&#41;;
                                        if isdirortho&#40;dir&#41; then
                                          begin if deltar = 0 then bbsetsq&#40;@fmbb, cand0sq&#41; end
                                        else
                                          begin
                                            if color0 = colorw then
                                              begin if deltar < 0 then bbsetsq&#40;@fmbb, cand0sq&#41; end
                                            else
                                              begin if deltar > 0 then bbsetsq&#40;@fmbb, cand0sq&#41; end
                                          end
                                      end;
                                    piecen&#58; bbsetsq&#40;@fmbb, cand0sq&#41;;
                                    pieceb&#58; if isdirortho&#40;dir&#41; then bbsetsq&#40;@fmbb, cand0sq&#41;;
                                    piecer&#58; if isdirdiago&#40;dir&#41; then bbsetsq&#40;@fmbb, cand0sq&#41;;
                                    pieceq&#58; ;
                                  end
                                end
                            end
                      until cand0sq = sqnil;
                    end
                end
            end
        end
    end; &#123; posrebuildpindbitboards &#125;

  begin
    posrebuildcheckstatuses; posrebuildpindbitboards
  end; &#123; posrebuild &#125;

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Not-quite-perft

Post by sje » Thu Oct 13, 2011 7:39 am

sje wrote:It looks like Bozo has the beginnings of a working perft. Alas:

1) No check evasion (but check/double check detection works)
2) No en passant (but promotions look okay)
3) No castling
4) No bulk counting
5) No transposition assistance
6) No sorted by SAN output
7) No user input interface
8) No FEN decoding
9) No input position legality checking

So for now the program can manage only (1, 20, 400, 8902).
The first attempt at check evasion has been installed, so the program can now make it to (1, 20, 400, 8902, 197281).

The SAN move sorter is complete. The move execute and retract routines have been instrumented with sanity checks. The program can run without problems with compiler-supplied range checking activated.

Next on the list: en passant, then castling.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Not-quite-perft

Post by sje » Fri Oct 14, 2011 12:51 pm

With the en passant code in place, perft is now returning 1, 20 , 400, 8902, 197281, 4865609, 119060324, 3195901860, and maybe more if I let it run long enough. Castling is also in place.

Still, the program is MISSING:

1) Bulk counting without generation
2) High speed mate detection
3) Repetition detection (but the hash code all seems to work)
4) Transposition tables
5) FEN decode and legality checking
6) User interface
7) EPD encoding/decoding
8) SAN full notation marking and decoding (sorting works)
9) Many utility routines (I/O, timing, option parsing, etc.)

The above should be in place before the initial release; also maybe a few more things like random game generation.

Current source size:

Code: Select all

sje@clare&#58;~/Projects/bozochess$ wc -l bozochess.pas
3521 bozochess.pas
Extra care has been taken in several areas:

1) Only legal moves are output from the move generation routines. There is no need to test for passive king-in-check status, although there is some easily removed sanity checking code in place for this.

2) An en passant target square is generated if and only if there is at least one legal en passant capture.

3) Castling is totally table driven so that chess960/FRC can be easily implemented. Although I'm not a fan of Chess960, others may find this feature of interest.

4) Null moves are handled properly although this won't be of use until a search is installed.

5) Game termination status determination priority is in place: checkmate/stalemate, fifty move, insufficient, repetition.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

The basic move generation

Post by sje » Sat Oct 15, 2011 3:49 am

The basic move generation is in place and is unlikely to change very much. Here it is:

Code: Select all

  procedure posgenerate&#40;var pos&#58; postype; var gms&#58; gmstype&#41;;

    procedure posgenerateevasion;
      var
        goodkingsq&#58; sqtype;
        goodpawn, goodking&#58; manrtype;
        goodbb, goodpawnbb&#58; bbtype;
        r2brank, r4brank, r8brank&#58; branktype;
        advdir&#58; dirtype;
        singlecheck&#58; boolean;
        checkerbb&#58; bbtype;
        checkersq&#58; sqxtype;
        checkerman&#58; mantype;
        checkeropr&#58; boolean;
        flightbb&#58; bbtype;
        flightsq&#58; sqxtype;
        atkbb&#58; bbtype;
        atksq&#58; sqxtype;
        defbb&#58; bbtype;
        defsq&#58; sqxtype;
        defman&#58; manrtype;
        shadowsq&#58; sqxtype;
        cvpwbb&#58; bbtype;
        pathbb&#58; bbtype;
        pathsq&#58; sqxtype;
        ipdbb&#58; bbtype;
        ipdsq&#58; sqxtype;
        epmove&#58; movetype;
    begin
      with pos, board, bbdb do
        begin

          &#123; Set various local constant values &#125;
          
          goodkingsq &#58;= ksqv&#91;good&#93;;
          goodpawn &#58;= synthpawn&#91;good&#93;; goodking &#58;= synthking&#91;good&#93;;
          goodbb &#58;= locbc&#91;good&#93;; goodpawnbb &#58;= locbm&#91;goodpawn&#93;;
          r2brank &#58;= normalbrank&#91;good, brank2&#93;;
          r4brank &#58;= normalbrank&#91;good, brank4&#93;;
          r8brank &#58;= normalbrank&#91;good, brank8&#93;;
          advdir &#58;= pawnadvdir&#91;good&#93;;
          singlecheck &#58;= not dbch;
          bband2&#40;checkerbb, locbc&#91;evil&#93;, atkts&#91;goodkingsq&#93;); 

          &#123; Set various checker data local constant values according to double check status &#125;

          if singlecheck then
            begin
              checkersq &#58;= bbfirstsq&#40;checkerbb&#41;; checkerman &#58;= sqv&#91;checkersq&#93;;
              checkeropr &#58;= mapsqtobrank&#40;checkersq&#41; = r8brank
            end
          else
            begin
              checkersq &#58;= sqnil; checkerman &#58;= manvv; checkeropr &#58;= false
            end;

          &#123; Initialize the king flight squares bitboard &#125;
          
          flightbb &#58;= kingatkbbvec&#91;goodkingsq&#93;;
          bband2c2d&#40;flightbb, goodbb&#41;; bband2c2d&#40;flightbb, atkbc&#91;evil&#93;);

          &#123; Remove any shadow squares from the flight bitboard &#125;
          
          atkbb &#58;= checkerbb;
          repeat
            atksq &#58;= bbnextsq&#40;atkbb&#41;;
            if &#40;atksq <> sqnil&#41; then
              if bbtestsq&#40;sweep, atksq&#41; then
                begin
                  shadowsq &#58;= shadowsqvec&#91;atksq, goodkingsq&#93;;
                  if shadowsq <> sqnil then bbresetsq&#40;flightbb, shadowsq&#41;
                end
          until atksq = sqnil;

          &#123; Attempt non en passant capture of a singleton attacker &#40;no king moves, no en passant&#41; &#125;

          if singlecheck then
            begin
              bband2&#40;defbb, atkts&#91;checkersq&#93;, goodbb&#41;; bband2c2d&#40;defbb, pmbb&#41;;
              bbresetsq&#40;defbb, goodkingsq&#41;;
              repeat
                defsq &#58;= bbnextsq&#40;defbb&#41;;
                if defsq <> sqnil then
                  begin
                    defman &#58;= sqv&#91;defsq&#93;;
                    if &#40;defman <> goodpawn&#41; or &#40;not checkeropr&#41; then
                      gmspushm2&#40;gms, defsq, checkersq, defman, checkerman&#41;
                    else
                      gmspushpscapt&#40;gms, defsq, checkersq, defman, checkerman&#41;
                  end
              until defsq = sqnil
            end;

          &#123; Attempt king capture of a single attacker &#125;

          if singlecheck then
            if bbtestsq&#40;flightbb, checkersq&#41; then
              begin
                gmspushm2&#40;gms, goodkingsq, checkersq, goodking, checkerman&#41;;
                bbresetsq&#40;flightbb, checkersq&#41;
              end;

          &#123; Attempt remaining king moves &#125;

          repeat
            flightsq &#58;= bbnextsq&#40;flightbb&#41;;
            if flightsq <> sqnil then
              gmspushm2&#40;gms, goodkingsq, flightsq, goodking, sqv&#91;flightsq&#93;)
          until flightsq = sqnil;

          &#123; Attempt interposition against a singleton sweep attacker &#40;all non captures&#41; &#125;
          
          if singlecheck then
            if bbtestsq&#40;sweep, checkersq&#41; then
              if not bbtestsq&#40;atkfs&#91;goodkingsq&#93;, checkersq&#41; then
                begin
                  cvpwbb &#58;= pathwaybbvec&#91;goodkingsq, checkersq&#93;;
                
                  &#123; Try non pawn interpositions &#125;
                
                  pathbb &#58;= cvpwbb;
                  repeat
                    pathsq &#58;= bbnextsq&#40;pathbb&#41;;
                    if pathsq <> sqnil then
                      begin
                        bband2&#40;ipdbb, atkts&#91;pathsq&#93;, goodbb&#41;;
                        bband2c2d&#40;ipdbb, goodpawnbb&#41;; bband2c2d&#40;ipdbb, pmbb&#41;;
                        bbresetsq&#40;ipdbb, goodkingsq&#41;;
                        repeat
                          ipdsq &#58;= bbnextsq&#40;ipdbb&#41;;
                          if ipdsq <> sqnil then
                            gmspushm1&#40;gms, ipdsq, pathsq, sqv&#91;ipdsq&#93;)
                        until ipdsq = sqnil
                      end
                  until pathsq = sqnil;
                
                  &#123; Try pawn interpositions &#125;
                  
                  if not bbisreset&#40;goodpawnbb&#41; then
                    if not issamebfile&#40;goodkingsq, checkersq&#41; then
                      begin
                      
                        &#123; Single square advance pawn interpositions &#125;
                      
                        bband2c2&#40;ipdbb, goodpawnbb, fmbb&#41;;
                        repeat
                          ipdsq &#58;= bbnextsq&#40;ipdbb&#41;;
                          if ipdsq <> sqnil then
                            begin
                              pathsq &#58;= sqdirtonextsq&#91;ipdsq, advdir&#93;;
                              if bbtestsq&#40;cvpwbb, pathsq&#41; then
                                if mapsqtobrank&#40;pathsq&#41; <> r8brank then
                                  gmspushm1&#40;gms, ipdsq, pathsq, goodpawn&#41;
                                else
                                  gmspushpshold&#40;gms, ipdsq, pathsq, goodpawn&#41;
                            end
                        until ipdsq = sqnil;
                      
                        &#123; Double square advance pawn interpositions &#125;
                        
                        bband2&#40;pathbb, cvpwbb, brankbbvec&#91;r4brank&#93;);
                        if not bbisreset&#40;pathbb&#41; then
                          begin
                            bband2&#40;ipdbb, goodpawnbb, brankbbvec&#91;r2brank&#93;);
                            bband2c2d&#40;ipdbb, fmbb&#41;;
                            repeat
                              ipdsq &#58;= bbnextsq&#40;ipdbb&#41;;
                              if ipdsq <> sqnil then
                                begin
                                  pathsq &#58;= sqdirtonextsq&#91;ipdsq, advdir&#93;;
                                  if not bbtestsq&#40;merge, pathsq&#41; then
                                    begin
                                      pathsq &#58;= sqdirtonextsq&#91;pathsq, advdir&#93;;
                                      if bbtestsq&#40;pathbb, pathsq&#41; then
                                        gmspushm1&#40;gms, ipdsq, pathsq, goodpawn&#41;
                                    end
                                end
                            until ipdsq = sqnil
                          end
                      end
                end;

          &#123; Attempt en passant capture &#125;

          if epsq <> sqnil then
            begin
              bband2&#40;defbb, goodpawnbb, pawnatkbbvec&#91;evil, epsq&#93;);
              repeat
                defsq &#58;= bbnextsq&#40;defbb&#41;;
                if defsq <> sqnil then
                  begin
                    movesynthm4&#40;epmove, defsq, epsq, goodpawn, mscepc&#41;;
                    if postestepmove&#40;pos, epmove&#41; then gmspush&#40;gms, epmove&#41;
                  end
              until defsq = sqnil
            end;

        end
    end; &#123; posgenerateevasion &#125;

    procedure posgeneratenocheck;
      var
        goodkingsq&#58; sqtype;
        goodbb, evilbb, destbb&#58; bbtype;
        frbb, tobb&#58; bbtype;
        frsq, tosq&#58; sqxtype;
        frman&#58; manrtype;
        frbrank&#58; branktype;
        r2brank, r7brank&#58; branktype;
        r2flag, r7flag&#58; boolean;
        advdir, capdir&#58; dirtype;
        resdir&#58; dirxtype;
        pawnatkbb&#58; bbtype;
        epmove&#58; movetype;
        castle&#58; castletype;
    begin
      with pos, board, bbdb do
        begin

          &#123; Initialize for the good man scan &#125;
   
          goodkingsq &#58;= ksqv&#91;good&#93;;
          goodbb &#58;= locbc&#91;good&#93;; evilbb &#58;= locbc&#91;evil&#93;;
          bbnot1&#40;destbb, goodbb&#41;;
          bband2c2&#40;frbb, goodbb, fmbb&#41;;
          r2brank &#58;= normalbrank&#91;good, brank2&#93;; r7brank &#58;= normalbrank&#91;good, brank7&#93;;

          &#123; Loop once for each possible moving man &#125;
    
          repeat
            frsq &#58;= bbnextsq&#40;frbb&#41;;
            if frsq <> sqnil then
              begin
              
                &#123; Fetch the moving man and process by its piece kind &#125;
    
                frman &#58;= sqv&#91;frsq&#93;;
                case mantopiece&#91;frman&#93; of

                  piecep&#58;
                    begin
                    
                      &#123; Set various pre-generation data for this pawn &#125;
                    
                      frbrank &#58;= mapsqtobrank&#40;frsq&#41;;
                      r2flag &#58;= frbrank = r2brank; r7flag &#58;= frbrank = r7brank;
                      advdir &#58;= pawnadvdir&#91;good&#93;;
                      if bbtestsq&#40;pmbb, frsq&#41; then
                        resdir &#58;= sqsqtodir&#91;goodkingsq, frsq&#93;
                      else
                        resdir &#58;= dirnil;
                      pawnatkbb &#58;= pawnatkbbvec&#91;good, frsq&#93;;
   
                      &#123; Pawn noncapture moves &#40;includes noncapture promotions&#41; &#125;
   
                      if &#40;resdir = dirnil&#41; or &#40;resdir = advdir&#41; then
                        begin
                          tosq &#58;= sqdirtonextsq&#91;frsq, advdir&#93;;
                          if not bbtestsq&#40;merge, tosq&#41; then
                            if r7flag then gmspushpshold&#40;gms, frsq, tosq, frman&#41;
                            else
                              begin
                                gmspushm1&#40;gms, frsq, tosq, frman&#41;;
                                if r2flag then
                                  begin
                                    tosq &#58;= sqdirtonextsq&#91;tosq, advdir&#93;;
                                    if not bbtestsq&#40;merge, tosq&#41; then gmspushm1&#40;gms, frsq, tosq, frman&#41;;
                                  end
                              end
                        end;
   
                      &#123; Pawn capture moves &#40;includes capture promotions; not en passant&#41; &#125;
                      
                      bband2&#40;tobb, pawnatkbb, evilbb&#41;;
                      repeat
                        tosq &#58;= bbnextsq&#40;tobb&#41;;
                        if tosq <> sqnil then
                          begin
                            capdir &#58;= sqsqtodir&#91;frsq, tosq&#93;;
                            if &#40;resdir = dirnil&#41; or &#40;resdir = capdir&#41; then
                              if r7flag then
                                gmspushpscapt&#40;gms, frsq, tosq, frman, sqv&#91;tosq&#93;)
                              else
                                gmspushm2&#40;gms, frsq, tosq, frman, sqv&#91;tosq&#93;)
                          end
                      until tosq = sqnil;

                      &#123; En passant capture &#125;
                      
                      if epsq <> sqnil then
                        if bbtestsq&#40;pawnatkbb, epsq&#41; then
                          begin
                            movesynthm4&#40;epmove, frsq, epsq, frman, mscepc&#41;;
                            if postestepmove&#40;pos, epmove&#41; then gmspush&#40;gms, epmove&#41;
                          end
                    end;

                  piecen&#58;
                    begin

                      &#123; Regular knight moves &#125;

                      bband2&#40;tobb, atkfs&#91;frsq&#93;, destbb&#41;;
                      repeat
                        tosq &#58;= bbnextsq&#40;tobb&#41;;
                        if tosq <> sqnil then gmspushm2&#40;gms, frsq, tosq, frman, sqv&#91;tosq&#93;)
                      until tosq = sqnil
                    end;

                  pieceb, piecer, pieceq&#58;
                    begin
                    
                      &#123; Regular sweeper moves &#125;
                    
                      bband2&#40;tobb, atkfs&#91;frsq&#93;, destbb&#41;;
                      if bbtestsq&#40;pmbb, frsq&#41; then bband2d&#40;tobb, beamerbbvec&#91;goodkingsq, frsq&#93;);
                      repeat
                        tosq &#58;= bbnextsq&#40;tobb&#41;;
                        if tosq <> sqnil then gmspushm2&#40;gms, frsq, tosq, frman, sqv&#91;tosq&#93;)
                      until tosq = sqnil
                    end;

                  piecek&#58;
                    begin
                    
                      &#123; Regular king moves &#125;
                    
                      bband2&#40;tobb, atkfs&#91;frsq&#93;, destbb&#41;; bband2c2d&#40;tobb, atkbc&#91;evil&#93;);
                      repeat
                        tosq &#58;= bbnextsq&#40;tobb&#41;;
                        if tosq <> sqnil then gmspushm2&#40;gms, frsq, tosq, frman, sqv&#91;tosq&#93;)
                      until tosq = sqnil;
                      
                      &#123; Castling &#125;
                      
                      if cvas <> 0 then
                        for castle &#58;= castlewq to castlebk do
                          if postestcastle&#40;pos, castle&#41; then gmspush&#40;gms, cdrvec&#91;castle&#93;.cmov&#41;
                    end;

                end
              end
          until frsq = sqnil;
        end
    end; &#123; posgeneratenocheck &#125;

  begin
    with pos do
      begin
        gmsreset&#40;gms&#41;;
        if inch then posgenerateevasion else posgeneratenocheck
      end
  end; &#123; posgenerate &#125;

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: The basic move generation

Post by sje » Sat Oct 15, 2011 4:14 am

The bulk move counter is also in place and is reasonably fast. It is essentially the same as the move generation routine except that it only has to count and doesn't have to synthesize and stack moves.

The fast mate detector is not yet in place. It will be essentially the same as the bulk move counter, but needs only to return a "count = 0" status. This allows for extensive short circuit calculation.

Other generation routines to come:

1) posgenerategainers (generates captures and promotions only)

2) posgeneratechecks (generates checking moves only)

Both of the above can be called only when the moving color is not in check.

Other related routines, already in place:

1) posmetagenmarked (generate moves and set move flags for SAN disambiguation, checks, and checkmates)

2) posmetagencanonical (generate marked, and then sort by SAN)

3) posmetagensuperdeluxe (generate canonical than add all appropriate draw indication flags; also, set draw and mating scores where needed)

I've taken out all use of the "@" (take address of) operator as I felt it went against the spirit of Pascal and made the code look too much like C.

Post Reply