Announcement: The Bozochess Project

[sje]

Bozo got itself a random game generator to help test its game termination code. Running an unoptimized source on a 32 bit 1.86 GHz Intel Core Solo T1350, the program generates random games at a rate of about 376 Hz (ca. 2.66 ms per game). The results of a 100,000 game run:

Code: Select all

bozochess 2011.10.15   Copyright (C) 2011 by S. J. Edwards
bozochess ready

Checkmate:    15129
FiftyMoves:   19324
Insufficient: 56878
Repetition:   2535
Stalemate:    6134

bozochess done

The above counts are in comfortable agreement with the expected values.

Here's the repetition detection code:

Code: Select all

  function poscountpriors(var pos: postype; limit: integer): integer;
    var
      result: integer;
      count: integer;
      spevnodeptr: spevnodeptrtype;
  begin
    with pos do
      begin
        result := 0; count := 0; spevnodeptr := spevnodetail;
        while &#40;result < limit&#41; and &#40;count < hmvc&#41; and &#40;spevnodeptr <> nil&#41; do
          begin
            if odd&#40;count&#41; then if spevnodeptr^.spev.mphc = mphc then inc&#40;result&#41;;
            inc&#40;count&#41;; spevnodeptr &#58;= spevnodeptr^.prev
          end;
        poscountpriors &#58;= result
      end
  end; &#123; poscountpriors &#125;

  function posisrepeated&#40;var pos&#58; postype&#41;&#58; boolean;
    var
      result&#58; boolean;
  begin
    with pos do
      begin
        if hmvc < 4 then result &#58;= false else result &#58;= poscountpriors&#40;pos, 1&#41; = 1;
        posisrepeated &#58;= result
      end
  end; &#123; posisrepeated &#125;

  function posisrepetitiondraw&#40;var pos&#58; postype&#41;&#58; boolean;
    var
      result&#58; boolean;
  begin
    with pos do
      begin
        if hmvc < 8 then result &#58;= false else result &#58;= poscountpriors&#40;pos, 2&#41; = 2;
        posisrepetitiondraw &#58;= result
      end
  end; &#123; posisrepetitiondraw &#125;

[sje]

Another random game generation benchmark, this time on a 2.66 GHz Xeon 5150:

Code: Select all

gail:bozochess sje$ time ./bozochess
BozoChess 2011.10.15   Copyright (C) 2011 by S. J. Edwards
BozoChess ready

Checkmate:    152404
FiftyMoves:   192181
Insufficient: 569058
Repetition:   25190
Stalemate:    61167

BozoChess done

real	25m9.281s
user	25m8.929s
sys	0m0.317s

That's a million games at about 663 Hz (1.51 ms). This is with no source optimization such as inline declarations or any fancy bit magic. Also, each game is actually played twice: once forward, and once again retracting all the moves to the starting position.

[sje]

On the same machine, node frequencies with perft(6):

Visit each node with full update: 482 KHz
Bulk counting: 7.87 MHz
With transposition help: Not there yet

[sje]

Code: Select all

  procedure BbdbAddMan(var bbdb: bbdbtype; man: manrtype; sq: sqtype);
  begin
    with bbdb do
      begin
        BbSetSq(merge, sq); if mantosweeper[man] then BbSetSq(sweep, sq);
        BbSetSq(locbc[mantocolor[man]], sq); BbSetSq(locbm[man], sq);
        BbdbCutAttacks(bbdb, sq); BbdbAddAttacks(bbdb, sq, man)
      end
  end; { BbdbAddMan }

  procedure BbdbDelMan(var bbdb: bbdbtype; man: manrtype; sq: sqtype);
  begin
    with bbdb do
      begin
        BbResetSq(merge, sq); if mantosweeper[man] then BbResetSq(sweep, sq);
        BbResetSq(locbc[mantocolor[man]], sq); BbResetSq(locbm[man], sq);
        BbdbDelAttacks(bbdb, sq, man); BbdbProAttacks(bbdb, sq)
      end
  end; { BbdbDelMan }

  procedure BbdbMovMan(var bbdb: bbdbtype; man: manrtype; frsq, tosq: sqtype);
    var
      color: colortype;
      sweeper: boolean;
  begin
    with bbdb do
      begin
        color := mantocolor[man]; sweeper := mantosweeper[man];
    
        { Reset the origination square data }
    
        BbResetSq(merge, frsq); if sweeper then BbResetSq(sweep, frsq);
        BbResetSq(locbc[color], frsq); BbResetSq(locbm[man], frsq);
        BbdbDelAttacks(bbdb, frsq, man); BbdbProAttacks(bbdb, frsq);
    
        { Set the destination square data }

        BbSetSq(merge, tosq); if sweeper then BbSetSq(sweep, tosq);
        BbSetSq(locbc[color], tosq); BbSetSq(locbm[man], tosq);
        BbdbCutAttacks(bbdb, tosq); BbdbAddAttacks(bbdb, tosq, man)

      end
  end; { BbdbMovMan }

[sje]

My plan is to release the Bozo Chess source on Halloween (October 31st) just to scare people as to how bad a Pascal coder I am.

The first release won't play chess, or at least not very well. But it will have a big boatload of functionality that will make it fairly easy to add an evaluation routine and a search. Remember that the primary goal of the initial release is to test portability with respect to different compilers and different host types; other goals can wait.

Once the portability issues are resolved, then I'll add some real chess playing routines and even more functionality before the second release. This second release will be called "CookieCat Chess". At that point I hope to achieved my initial goal of providing a free and decent pedagogical resource for Pascal chess programming.

[sje]

Another random game generation benchmark, this time on a 2.66 GHz Xeon 5150:

Code: Select all

Checkmate:    152404
FiftyMoves:   192181
Insufficient: 569058
Repetition:   25190
Stalemate:    61167

That's a million games at about 663 Hz (1.51 ms). This is with no source optimization such as inline declarations or any fancy bit magic. Also, each game is actually played twice: once forward, and once again retracting all the moves to the starting position.

After adding the fast mate detector, the rate increased from 663 Hz to 738 Hz (the period decreased from 1.51 ms to 1.35 ms), a speed increase of about 11%.

I'll guess that inlining the bitboard routines will also give some significant speed improvements. But not all Pascal compiler support inline declarations.

[sje]

I the Old Days (ca. 1976) when I first learned Pascal, I used the ETH Zurich compiler (then the only one available) for my little Punch Card Era projects. At that time, Pascal did not support a string type, nor even ASCII, but instead had these 60 bit words of ten 6 bit characters each. It was a mess. Today, there are several Pascal string flavors available. The downside is that I have to pick the most restrictive implementation for the sake of portability. So I've been playing with this and will use the Borland short string style: a string has a maximum length of 255 and is indexed from 1 to 255 (no NUL terminator). Shorter string lengths can be specified, and I have done this for SAN (seven characters max) and FEN (93 characters max).

A similar constraint occurs with the use of Pascal sets. Some implementations have a small, easily exceeded set size. Others have larger and storage inefficient sizes. Some have the maximum set size adjustable by some method incompatible with other compilers and hosts. In my work here and now, I've decided that I can assume a minimum set length of 16 elements and that there won't be too many set type variables because of storage concerns.

I haven't gotten to file operations yet, but it's likely that any text files will have to have each line limited to 255 characters to coexist with the chosen string size limit.

I tried inlining most of the bitboard functions and got a significant speed-up. But there is not a clear way of doing inlining in a portable fashion, so I'll leave out inlining for now.

I also tried compiling a 64 bit executable instead of the 32 bit default. To my surprise, the 64 bit binary ran slower than the 32 bit version. More work is needed here.

If you're interested in the current state of Pascal and want to get a free compiler, see: http://www.freepascal.org/

[sje]

Bozo has gotten an MPD decoder; an MPD (Man Placement Data) string is the first field of a FEN record. I am trying to catch all possible error conditions with FEN decoding as it would be rather embarrassing to not be able to handle my own standard.

I've added types and routines for two-way linked lists of moves and tokens; these are similar to the two-way lists of saved position environment records already in place.

I've tested compiling and running the same source on different machines types: Intel 32 bit, Intel 64 bit, and PowerPC 32 bit (the last with bigendian words, doublewords, and quadwords). All platforms exhibit the same bit scanning order and all get the same results.

I'm now working on the string tokenizer and that will allow the completion of the FEN decoder. After that, I'll work on the Command Processing Context type and its routines; this will support an interactive command processor now and an external GUI later. With this, I'll no longer have to edit and re-compile for each new test.

The program has no global variables except for those with constant values assigned at initialization time. It may later have a single global variable, a pointer to a dynamically allocated command processing context record that in turn will hold everything needed for doing chess.

The project is still on track for a 2011.10.31 release.

[sje]

Bozochess has passed all perft tests that I've tried. These include the ones at http://chessprogramming.wikispaces.com/Perft+Results

There might still be some generate/execute/retract bugs, but if so then they must be rather subtle. The program also passes all debugging range checks (optionally) inserted by the compiler.

The FEN decoder is almost complete; at present it's missing only some validity checks. It's important to get this code complete and correct because the rest of the program assumes that only totally valid data will appear in a position structure.

The program is on track for the planned October 31st release date. It will be interesting to see how different Pascal compilers handle the source. I plan on including a self test routine that will run at program initialization time, taking a second or so to check basic operation via some perft calls. With this, reviewers can get some quick results without having to make any program changes.

[sje]

Bozo now has a FEN decoder with full validity checking on all fields and also of the resulting position. The decoder calls the position loader and the loader can make one minor adjustment: if the en passant target is superfluous, then it will be silently deleted.

With the addition of the SAN file/rank disambiguation flag marking, the move encode/decode routines are now complete.

The interactive command processor is in place and can handle a dozen different commands, so now I don't have to edit and recompile for every test. Stubs are in place for a UCI command processor and an Xboard command processor.

There are still no global variables except for constant values.

Next: Gainer (capture/promotion) only move generation, fast checking detection, fast check/checkmate marking, checks only move generation, score routines.

There are only ten more days until the source release.

The ICP command set so far:

Code: Select all

    df          Display FEN
    dm          Display moves
    exit        Exit program
    help        Show help
    new         New game
    noop        No operation
    perft       Run perft to <depth> with each node visited
    perftbulk   Run perft to <depth> with bulk counting
    rg          Generate a random game
    rgstat      Generate a report for <n> random game&#40;s&#41;
    sf          Set FEN <MPD> <good> <cavs> <epsq> <hmvc> <fmvn>
    test        Run developer test

The main program:

Code: Select all

program BozoChess;

[5,000+ lines omitted]

begin
  Initialize; DriveIcp; Terminate
end. { BozoChess }

Sample transcript:

Code: Select all

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

[] df
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
[] dm
Na3 Nc3 Nf3 Nh3 a3 a4 b3 b4 c3 c4 d3 d4 e3 e4 f3 f4 g3 g4 h3 h4
[] sf 8/7p/p5pb/4k3/P1pPn3/8/P5PP/1rB2RK1 b - d3 0 28
[] df
8/7p/p5pb/4k3/P1pPn3/8/P5PP/1rB2RK1 b - d3 0 28
[] dm
Kd5 Kd6 Ke6 Kxd4 cxd3
[] perftbulk 7
Perftbulk depth: 7
FEN: 8/7p/p5pb/4k3/P1pPn3/8/P5PP/1rB2RK1 b - d3 0 28
  Kd5 216135695
  Kd6 233877684
  Ke6 228162609
  Kxd4 202248953
  cxd3 188764129
Pathcount: 1069189070
[] exit

BozoChess done