Announcement: The Bozochess Project

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

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

Re: Even closer

Post by sje » Sat Oct 22, 2011 2:56 am

Also, the rg and rgstat routines were connected to the command processor:

Code: Select all

[] rg
5r2/8/2k5/8/8/8/1K6/8 b - - 100 323
FiftyMoves
[] rg
4nk2/8/8/8/4K3/4N3/8/8 b - - 0 174
Insufficent
[] rg
8/3K4/8/8/8/3b3k/8/8 b - - 0 200
Insufficent
[] rg
8/6k1/8/8/8/4K3/8/1b4B1 b - - 0 144
Insufficent
[] rg
3k4/8/8/6K1/8/8/3n4/5N2 b - - 0 151
Insufficent
[] rg
8/8/1K4b1/8/8/8/1k6/8 b - - 0 216
Insufficent
[] rg
2b5/8/3k4/p7/p2r2rp/P6K/4r2P/8 w - - 0 74
Stalemate
[] rg
8/8/3k4/2R1R3/8/8/2K1R3/8 b - - 100 183
FiftyMoves
[] rg
8/5k2/8/8/8/8/8/n3K3 w - - 0 141
Insufficent
[] rg
4k3/8/5b2/8/4K3/8/8/8 b - - 0 225
Insufficent
[] rg
1k6/8/Q1K5/p5P1/p7/P7/8/8 b - - 8 118
Stalemate
[] rg
4N3/8/1P4Qk/8/8/3B4/8/K7 b - - 0 129
Checkmate
[] rgstat 100000
Checkmate 15186
FiftyMoves 19453
Insufficent 56680
Repetition 2576
Stalemate 6105
[] rgstat 100000
Checkmate 15092
FiftyMoves 19402
Insufficent 56764
Repetition 2633
Stalemate 6109

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

Another command: dbbdb

Post by sje » Sat Oct 22, 2011 12:39 pm

Bozo has another command: dbbdb (Display bitboard database). I've included it for those early in their chess programming effort who might want to better see how bitboards work.

Code: Select all

[] sf 2qrr1n1/3b1kp1/2pBpn1p/1p2PP2/p2P4/1BP5/P3Q1PP/4RRK1 w - - 0 1
[] dbbdb
merge     [e1 f1 g1 a2 e2 g2 h2 b3 c3 a4 d4 b5 e5 f5 c6 d6 e6 f6 h6 d7 f7 g7 c8 d8 e8 g8]
sweep     [e1 f1 e2 b3 d6 d7 c8 d8 e8]
locbc[w]  [e1 f1 g1 a2 e2 g2 h2 b3 c3 d4 e5 f5 d6]
locbc[b]  [a4 b5 c6 e6 f6 h6 d7 f7 g7 c8 d8 e8 g8]
locbm[P]  [a2 g2 h2 c3 d4 e5 f5]
locbm[N]  []
locbm[B]  [b3 d6]
locbm[R]  [e1 f1]
locbm[Q]  [e2]
locbm[K]  [g1]
locbm[p]  [a4 b5 c6 e6 h6 g7]
locbm[n]  [f6 g8]
locbm[b]  [d7]
locbm[r]  [d8 e8]
locbm[q]  [c8]
locbm[k]  [f7]
atkbc[w]  [a1 b1 c1 d1 e1 f1 g1 h1 a2 b2 c2 d2 e2 f2 g2 h2 a3 b3 d3 e3 f3 g3 h3 a4 b4 c4 d4 e4 f4 g4 b5 c5 d5 e5 f5 h5 d6 e6 f6 g6 c7 e7 b8 f8]
atkbc[b]  [b3 a4 c4 e4 g4 b5 d5 f5 g5 h5 a6 c6 e6 f6 g6 h6 b7 c7 d7 e7 g7 h7 a8 b8 c8 d8 e8 f8 g8]
atkfs[a1] []
atkfs[b1] []
atkfs[c1] []
atkfs[d1] []
atkfs[e1] [a1 b1 c1 d1 f1 e2]
atkfs[f1] [e1 g1 f2 f3 f4 f5]
atkfs[g1] [f1 h1 f2 g2 h2]
atkfs[h1] []
atkfs[a2] [b3]
atkfs[b2] []
atkfs[c2] []
atkfs[d2] []
atkfs[e2] [d1 e1 f1 a2 b2 c2 d2 f2 g2 d3 e3 f3 c4 e4 g4 b5 e5 h5]
atkfs[f2] []
atkfs[g2] [f3 h3]
atkfs[h2] [g3]
atkfs[a3] []
atkfs[b3] [d1 a2 c2 a4 c4 d5 e6]
atkfs[c3] [b4 d4]
atkfs[d3] []
atkfs[e3] []
atkfs[f3] []
atkfs[g3] []
atkfs[h3] []
atkfs[a4] [b3]
atkfs[b4] []
atkfs[c4] []
atkfs[d4] [c5 e5]
atkfs[e4] []
atkfs[f4] []
atkfs[g4] []
atkfs[h4] []
atkfs[a5] []
atkfs[b5] [a4 c4]
atkfs[c5] []
atkfs[d5] []
atkfs[e5] [d6 f6]
atkfs[f5] [e6 g6]
atkfs[g5] []
atkfs[h5] []
atkfs[a6] []
atkfs[b6] []
atkfs[c6] [b5 d5]
atkfs[d6] [a3 b4 c5 e5 c7 e7 b8 f8]
atkfs[e6] [d5 f5]
atkfs[f6] [e4 g4 d5 h5 d7 h7 e8 g8]
atkfs[g6] []
atkfs[h6] [g5]
atkfs[a7] []
atkfs[b7] []
atkfs[c7] []
atkfs[d7] [c6 e6 c8 e8]
atkfs[e7] []
atkfs[f7] [e6 f6 g6 e7 g7 e8 f8 g8]
atkfs[g7] [f6 h6]
atkfs[h7] []
atkfs[a8] []
atkfs[b8] []
atkfs[c8] [a6 c6 b7 c7 d7 a8 b8 d8]
atkfs[d8] [d7 c8 e8]
atkfs[e8] [e6 e7 d8 f8 g8]
atkfs[f8] []
atkfs[g8] [f6 h6 e7]
atkfs[h8] []
atkts[a1] [e1]
atkts[b1] [e1]
atkts[c1] [e1]
atkts[d1] [e1 e2 b3]
atkts[e1] [f1 e2]
atkts[f1] [e1 g1 e2]
atkts[g1] [f1]
atkts[h1] [g1]
atkts[a2] [e2 b3]
atkts[b2] [e2]
atkts[c2] [e2 b3]
atkts[d2] [e2]
atkts[e2] [e1]
atkts[f2] [f1 g1 e2]
atkts[g2] [g1 e2]
atkts[h2] [g1]
atkts[a3] [d6]
atkts[b3] [a2 a4]
atkts[c3] []
atkts[d3] [e2]
atkts[e3] [e2]
atkts[f3] [f1 e2 g2]
atkts[g3] [h2]
atkts[h3] [g2]
atkts[a4] [b3 b5]
atkts[b4] [c3 d6]
atkts[c4] [e2 b3 b5]
atkts[d4] [c3]
atkts[e4] [e2 f6]
atkts[f4] [f1]
atkts[g4] [e2 f6]
atkts[h4] []
atkts[a5] []
atkts[b5] [e2 c6]
atkts[c5] [d4 d6]
atkts[d5] [b3 c6 e6 f6]
atkts[e5] [e2 d4 d6]
atkts[f5] [f1 e6]
atkts[g5] [h6]
atkts[h5] [e2 f6]
atkts[a6] [c8]
atkts[b6] []
atkts[c6] [d7 c8]
atkts[d6] [e5]
atkts[e6] [b3 f5 d7 f7 e8]
atkts[f6] [e5 f7 g7 g8]
atkts[g6] [f5 f7]
atkts[h6] [g7 g8]
atkts[a7] []
atkts[b7] [c8]
atkts[c7] [d6 c8]
atkts[d7] [f6 c8 d8]
atkts[e7] [d6 f7 e8 g8]
atkts[f7] []
atkts[g7] [f7]
atkts[h7] [f6]
atkts[a8] [c8]
atkts[b8] [d6 c8]
atkts[c8] [d7 d8]
atkts[d8] [c8 e8]
atkts[e8] [f6 d7 f7 d8]
atkts[f8] [d6 f7 e8]
atkts[g8] [f6 f7 e8]
atkts[h8] []
[] exit

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

Two new commands

Post by sje » Sat Oct 22, 2011 8:24 pm

Bozo has two new commands.

The first is "rm" (retract move) that does what you would expect it to do.

The second is "perfttran" which runs a perft calculation with transposition table assistance. At present, the table entry count is 2^20 and each entry has a 64 bit path count and a 64 bit signature. The signature is composed of 56 bits of hash and 8 bits of draft. I have made this code as simple as possible as the primary intent is to provide a teaching program.

Only nine more days until the source release.

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

Re: Two new commands

Post by sje » Sun Oct 23, 2011 4:26 am

With transposition assistance, but with neither assembly language nor inline routines, Bozo can calculate perft(7) = 3,195,901,860 in under a minute. Compare this the 36 hours needed by by old program Spector back in the late 1980s.

The PosPerftTran routine:

Code: Select all

  function PosPerftTran(var pos: postype; mydepth: integer; dflag: boolean): nodecounttype;
    var
      myresult: nodecounttype;
      ply: plytype;
      depth: integer;
      storeptr: mpetstoreptrtype;
      storeindex: mpetindextype;
      sigmask: QWord;

    function PosPerftTranAux: nodecounttype;
      var
        myresult, subsum: nodecounttype;
        p0flag: boolean;
        index: integer;
        gms: gmstype;
        entryindex: mpetindextype;
        entrysig: QWord;
    begin
      if depth = 0 then myresult := 1
      else
        begin
          p0flag := ply = 0;
          if (depth = 1) and (not p0flag) then myresult := PosCount(pos)
          else
            begin
            
              { Probe }
            
              entryindex := pos.mphc and mpetmask; entrysig := (pos.mphc and sigmask) or depth;
              with storeptr^[entryindex] do
                if signature = entrysig then myresult := pathcount
              else
                begin
                
                  { Calculate }
                
                  with gms do
                    begin
                      myresult := 0;
                      if p0flag then PosMetaGenCanonical(pos, gms) else PosGenerate(pos, gms);
                      inc(ply); dec(depth);
                      for index := 0 to movecount - 1 do
                        begin
                          PosExecute(pos, moves[index]); subsum := PosPerftTranAux(); PosRetract(pos);
                          if p0flag and dflag then writeln('  ', MoveEncode(moves[index]), ' ', subsum);
                          myresult := myresult + subsum
                        end;
                      dec(ply); inc(depth)
                    end;
                    
                  { Stash }
                    
                  with storeptr^[entryindex] do
                    begin signature := entrysig; pathcount := myresult end
                end
            end
        end;
      PosPerftTranAux := myresult
    end; { PosPerftTranAux }

  begin
    ply := 0; depth := mydepth; sigmask := plylen - 1; sigmask := not sigmask; new(storeptr);
    for storeindex := 0 to mpetslen - 1 do
      with storeptr^[storeindex] do begin signature := 0; pathcount := 0 end;
    myresult := PosPerftTranAux; dispose(storeptr); PosPerftTran := myresult
  end; { PosPerftTran }

Joerg Oster
Posts: 691
Joined: Fri Mar 10, 2006 3:29 pm
Location: Germany

Re: Two new commands

Post by Joerg Oster » Sun Oct 23, 2011 9:35 am

Hi Steven,

I'm following your project with great interest.
It is amazing how fast you proceed.

I already downloaded FreePascal and can't wait to put my hands on Bozo. :D
Will you provide some kind of documentation/explanation of the source code?

8 days left regards :wink:
Joerg

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

Re: Two new commands

Post by sje » Sun Oct 23, 2011 10:09 am

Joerg Oster wrote:I already downloaded FreePascal and can't wait to put my hands on Bozo. :D
Will you provide some kind of documentation/explanation of the source code?
Thank you for your interest in Bozo.

The initial documentation for Bozo will be very limited and will likely be nothing more than sparse commentary in the program source. This situation will improve, but it will take some time. I will note that there has been considerable effort to ensure consistent, descriptive names for constants, types, variables, and routines; this should help to decipher the program source.

Remember that the major goal of the initial release is to identify and resolve portability issues with compiler and target dependencies; actual chess playing ability will appear in later releases.

For non-English deployments, I have tried to make much of the data output table driven so it will be easy to re-target strings for colors, pieces, and other data to non-English values.

Here is a transcript of Bozo's first calculation of perft(9):

Code: Select all

$ time ./bozochess
BozoChess 2011.10.23   Copyright (C) 2011 by S. J. Edwards
BozoChess ready

[] perfttran 9
PerftTran depth: 9
FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
  Na3 85849641909
  Nc3 109418317145
  Nf3 108393009416
  Nh3 86659653631
  a3 74950758099
  a4 101265301849
  b3 96577095997
  b4 97442160946
  c3 108697368719
  c4 120549219832
  d3 176976245463
  d4 227220482342
  e3 259522947791
  e4 263561543780
  f3 68094899093
  f4 84792070664
  g3 99646370024
  g4 92281289941
  h3 74778417365
  h4 102853440161
Pathcount: 2439530234167
[] exit

BozoChess done

real	290m27.500s
user	281m24.504s
sys	0m3.487s

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

A few more things

Post by sje » Sun Oct 23, 2011 4:56 pm

A few more things have been added:

1) A better board display ("dbmono" command):

Code: Select all

[] dbmono
bRbNbBbQbKbBbNbR
bPbPbPbPbPbPbPbP
  ::  ::  ::  ::
::  ::  ::  ::  
  ::  ::  ::  ::
::  ::  ::  ::  
wPwPwPwPwPwPwPwP
wRwNwBwQwKwBwNwR
2) A better color board display using ANSI color escape sequences which resist posting here ("db" command).

3) User move input sequence parsing, validation, and execution; from one move to as many as will fit on a 255 character command line.

The source procedure/function count is approaching 300 and the line count is nearing 6,000.

Eight days until the source release.

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

Gainer move generation

Post by sje » Mon Oct 24, 2011 12:02 am

I use the term "gainer" to indicate a move that is a capture or a promotion or both. Underpromotions are included. (The opposite of a gainer is a "holder".) So, what some call a "capture search", I call a "gainer search". And if a program has a gainer search, it has to have a gainer move generator.

Here's Bozo's gainer move generator:

Code: Select all

  procedure PosGenerateGainers(var pos: postype; var gms: gmstype);
    var
      goodkingsq: sqtype;
      goodbb, evilbb: bbtype;
      frbb, tobb: bbtype;
      frsq, tosq: sqxtype;
      frman: manrtype;
      r7brank: branktype;
      r7flag: Boolean;
      advdir, capdir: dirtype;
      resdir: dirxtype;
      pawnatkbb: bbtype;
      epmove: movetype;
  begin
    GmsReset(gms);
    with pos, board, bbdb do
      begin

        { Initialize for the good man scan }
 
        goodkingsq := ksqv[good]; goodbb := locbc[good]; evilbb := locbc[evil];
        BbAnd2C2(frbb, goodbb, fmbb);
        r7brank := normalbrank[good, brank7]; advdir := pawnadvdir[good];

        { Loop once for each possible moving man }
  
        repeat
          frsq := BbNextSq(frbb);
          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;
                  
                    r7flag &#58;= MapSqToBrank&#40;frsq&#41; = r7brank;
                    if BbTestSq&#40;pmbb, frsq&#41; then
                      resdir &#58;= compass&#91;goodkingsq, frsq&#93;
                    else
                      resdir &#58;= dirnil;
                    pawnatkbb &#58;= pawnatkbbvec&#91;good, frsq&#93;;
 
                    &#123; Pawn noncapture promotions &#125;
 
                    if &#40;resdir = dirnil&#41; or IsDirxOrtho&#40;resdir&#41; then
                      if r7flag then
                        begin
                          tosq &#58;= advance&#91;frsq, advdir&#93;;
                          if not BbTestSq&#40;merge, tosq&#41; then GmsPushPsHold&#40;gms, frsq, tosq, frman&#41;
                        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;= compass&#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 PosIsEnPassantMoveLegal&#40;pos, epmove&#41; then GmsPush&#40;gms, epmove&#41;
                        end
                  end;

                piecen&#58;
                  begin

                    &#123; Regular knight capturing moves &#125;

                    BbAnd2&#40;tobb, atkfs&#91;frsq&#93;, evilbb&#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 capturing moves &#125;
                  
                    BbAnd2&#40;tobb, atkfs&#91;frsq&#93;, evilbb&#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 capturing moves &#125;
                  
                    BbAnd2&#40;tobb, atkfs&#91;frsq&#93;, evilbb&#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;
                  end;

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


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

Re: Announcement: The Bozochess Project

Post by sje » Tue Oct 25, 2011 3:09 am

Bozo now has some understanding of PGN, but is not yet able to decode game files. Other than that, most of the latest work has gone towards cleaning the source and keeping it consistent and organized.

Seven days until the source release.

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

A few more things

Post by sje » Tue Oct 25, 2011 5:37 pm

1) The interactive command processor command set has been expanded again, but its file accessing commands are not yet complete.

2) The "rgstat" command has a better output format and now includes percentages.

3) The "perfttran" command now accesses its transposition table with a simple "lesser of two" entry replacement scheme; this is a big time saver for deep perft calculations.

4) I've executed yet another search and destroy mission targeting superfluous semicolons in the program source.

5) The PGN tag name set has been increased from the required seven standard tags. However, if a tag name is not already defined in the source, then it will not be recognized when reading a PGN game. But it's easy to add new tag names in the program.

Six more days until the source release. I will be sending out copies via email attachment; those interested should send me a PM, send me an email, or post in this thread.

Sample transcript:

Code: Select all

&#91;&#93; help
Enter a command, or a sequence of one or more SAN chess moves
  Commands&#58;
    db          Display board &#40;ANSI color&#41;
    dbbdb       Display bitboard database
    dbmono      Display board &#40;monochrome&#41;
    dfen        Display FEN
    dm          Display moves
    dp          Display position
    exit        Exit program
    help        Show help
    loadfen     Load FEN from a file
    loadpgn     Load PGN from a file
    new         New game
    noop        No operation
    perftbulk   Run perft to <depth> with bulk counting
    perftfull   Run perft to <depth> with each node visited
    perfttran   Run perft to <depth> with transposition help
    rg          Generate a random game
    rgstat      Generate a report for <n> random game&#40;s&#41;
    rm          Retract move
    savefen     Save FEN to a file
    savepgn     Save PGN to a file
    sfen        Set FEN <MPD> <good> <cavs> <epsq> <hmvc> <fmvn>
    test        Run developer test
&#91;&#93; rgstat 1000
    Checkmate    147  14.700%
   FiftyMoves    193  19.300%
  Insufficent    584  58.400%
   Repetition     33   3.300%
    Stalemate     43   4.300%
 Unterminated      0   0.000%
Total 1000
&#91;&#93; rgstat 10000
    Checkmate   1585  15.850%
   FiftyMoves   1904  19.040%
  Insufficent   5638  56.380%
   Repetition    252   2.520%
    Stalemate    621   6.210%
 Unterminated      0   0.000%
Total 10000
&#91;&#93; rgstat 100000
    Checkmate  15246  15.246%
   FiftyMoves  19392  19.392%
  Insufficent  56700  56.700%
   Repetition   2524   2.524%
    Stalemate   6138   6.138%
 Unterminated      0   0.000%
Total 100000
&#91;&#93; rgstat 1000000
    Checkmate 153127  15.313%
   FiftyMoves 193474  19.347%
  Insufficent 566760  56.676%
   Repetition  25303   2.530%
    Stalemate  61336   6.134%
 Unterminated      0   0.000%
Total 1000000

Post Reply