Same code?

[sje]

From Chess 0.5:

Code: Select all

PROCEDURE CUTATK                       (* CUT ATTACKS THROUGH SQUARE *)
  (A:TS);                              (* SQUARE *)

VAR 
  INRS : RS;                           (* ATTACKING PIECES *)
  INTS : TS;                           (* ATTACKING PIECE SQUARE *)
  IMRS : RS;                           (* SCRATCH *)
  INTD : TD;                           (* STEP SIZE *)
  INTM : TM;                           (* ATTACKING PIECE SIDE *)
  INTL : TL;                           (* NO LONGER ATTACKED SQUARE *)
  INTT : TT;                           (* NO LONGER ATTACKED SQUARE *)

BEGIN
  CPYRS(INRS,ATKTO[A]);                (* ALL PIECES ATTACKING SQUARE *)
  WHILE NXTTS(INRS,INTS) DO
    IF XSPB[MBORD[INTS]] THEN          (* IF SWEEP PIECE *)
    BEGIN
      INTD := XLLD[XTSL[A]-XTSL[INTS]];
                                       (* STEP SIZE ON 10X12 BOARD *)
      INTM := XTPM[MBORD[INTS]];       (* SIDE OF ATTACKING PIECE *)
      INTL := XTSL[A]+INTD;            (* FIRST SQUARE BEYOND PIECE *)
      INTT := XTLS[INTL];              (* FIRST SQUARE BEYOND PIECE ON
                                          8X8 BOARD *)
      WHILE INTT > AT DO               (* WHILE ON BOARD *)
      BEGIN
        CLRRS(ATKFR[INTS],INTT);       (* CLEAR ATTACK MAP *)
        CLRRS(ATKTO[INTT],INTS);
        ANDRS(IMRS,ATKTO[INTT],TMLOC[INTM]);
                                       (* OTHER ATTACKS ON SQUARE BY
                                          SAME SIDE *)
        IF NULRS(IMRS) THEN            (* IF NO ATTACKS BY THAT SIDE *)
          CLRRS(ALATK[INTM],INTT);     (* CLEAR ATTACKS BY SIDE *)
        IF MBORD[INTT] = MT THEN
        BEGIN
          INTL := INTL+INTD;           (* STEP BEYOND SQUARE *)
          INTT := XTLS[INTL];
        END
        ELSE
          INTT := AT;                  (* STOP SCAN *)
      END;
    END;
END;  (* CUTATK *)

From the new CIL Toolkit:

Code: Select all

(defun cut-attacks (my-sq my-bbdb)
  "Cut the attacks through a square in a bitboard database."
  (let*
    (
      (loc-merge-bb        (bbdb-loc-merge-bb my-bbdb))
      (loc-sweep-bb        (bbdb-loc-sweep-bb my-bbdb))
      (loc-color-bb-vec    (bbdb-loc-color-bb-vec my-bbdb))
      (atk-by-color-bb-vec (bbdb-atk-by-color-bb-vec my-bbdb))
      (atk-fr-sq-bb-vec    (bbdb-atk-fr-sq-bb-vec my-bbdb))
      (atk-to-sq-bb-vec    (bbdb-atk-to-sq-bb-vec my-bbdb))
      (atkr-bb             (clone-bb (svref atk-to-sq-bb-vec my-sq)))
    )
    (loop-bb (atkr-bb atkr-sq)
      (when (sq-set? loc-sweep-bb atkr-sq)
        (let*
          (
            (atkr-color      (calc-occ-color-bbdb atkr-sq my-bbdb))
            (atkr-loc-bb     (svref loc-color-bb-vec atkr-color))
            (atk-by-color-bb (svref atk-by-color-bb-vec atkr-color))
            (atk-fr-sq-bb    (svref atk-fr-sq-bb-vec atkr-sq))
            (dir             (aref intersquare-dir-vec atkr-sq my-sq))
            (extn-sqs        (aref open-ray-sqs-vec my-sq dir))
          )
          (when extn-sqs
            (do ((extn-sq (pop extn-sqs))) ((not extn-sq))
              (reset-sq atk-fr-sq-bb extn-sq)
              (reset-sq (svref atk-to-sq-bb-vec extn-sq) atkr-sq)
              (when (bb-ni2? atkr-loc-bb (svref atk-to-sq-bb-vec extn-sq))
                (reset-sq atk-by-color-bb extn-sq))
              (if (or (null? extn-sqs) (sq-set? loc-merge-bb extn-sq))
                (setf extn-sq nil)
                (setf extn-sq (pop extn-sqs))))))))))

[Carey]

I don't understand Lisp, so I can't judge that part. (Last time I tried to read Lisp was Bill Gosper's bignum math stuff probably 10 years ago.)

I am quite familar with Chess 0.5 though, if you are having trouble understanding Larry Atkin's coding style and obscure variable naming.

I have a C version of the same routine, if that might be more easily read.

A couple years ago I grafted Chess 0.5's database stuff into my program just to see what kind of performance I got. Can't remember exactly, but the penalty was significant.

The 4 key bitboard routines (AddAtk, CutAtk, DelAtk, PrpAtk) are a little slow compared to the rotated stuff or even the modern methods.

You might be able to combine them and keep the full attack database and still get reasonable performance, but I haven't looked into doing that.

Code: Select all

void cutatk                            /* cut attacks through square */
  (Sqr64_t a)                               /* square */

{
  BitBoard_t inrs;                             /* attacking pieces */
  Sqr64_t ints;                             /* attacking piece square */
  BitBoard_t imrs;                             /* scratch */
  td intd;                             /* step size */
  tm intm;                             /* attacking piece side */
  tl intl;                             /* no longer attacked square */
  tt intt;                             /* no longer attacked square */


  inrs=atkto[a];                /* all pieces attacking square */
  while (nxtts(&inrs,&ints))             /* Extract a bit */
    if (IsSweep[mbord[ints ]])           /* if sweep piece */
    {
      intd = xlld[MapTo120[a]-MapTo120[ints]-(azl)];
                                       /* step size on 10x12 board */
      intm = ColorOfPiece[mbord[ints ]];       /* side of attacking piece */
      intl = MapTo120[a ]+intd;            /* first square beyond piece */
      intt = MapTo64[intl];              /* first square beyond piece on
                                          8x8 board */
      while (intt > -1)                /* while on board */
      {
        atkfr[ints] &= ~SqrToBit[intt];      /* clear attack map */
        atkto[intt] &= ~SqrToBit[ints];
        imrs = atkto[intt] & tmloc[intm];
                                       /* other attacks on square by
                                          same side */
        if (imrs==0ULL)               /* if no attacks by that side */
          alatk[intm] &= ~SqrToBit[intt];     /* clear attacks by side */
        if (mbord[intt ] == NoPiece)
        {
          intl = intl+intd;            /* step beyond square */
          intt = MapTo64[intl];
        }
        else
          intt = -1;                   /* stop scan */
      }
    }
}     /* cutatk */

[sje]

Basic differences:

Chess 0.5 is written in early Pascal circa 1977, the new CIL is written in Common Lisp and was coded this month.

Chess 0.5 is intended for instructional purposes, CIL is for research and production versions.

Chess 0.5 relies extensively on global variables and its routines have minimal formal parameter lists. CIL has no global variables (but plenty of global constants) and so its routines rely entirely on formal parameters for dynamic behavior; each routine can be tested interactively.

Chess 0.5 was not written to be thread safe. CIL is thread safe.

Chess 0.5 has an 8x8 board combined with a 10x12 board used for edge detection. A position in CIL has an 8x8 board and uses pre-calculated square lists. Note how the Chess 0.5 CUTATK routine needs to do step calculation and edge detection; and that doesn't help much speed-wise.

However, note that both routines do "the same thing" when "the same thing" is interpreted at a sufficiently high level of abstraction. Does this mean that CIL stole from Chess 0.5? No, it means that both have incorporated the same idea from earlier sources.

[Carey]

Basic differences:

Chess 0.5 is written in early Pascal circa 1977, the new CIL is written in Common Lisp and was coded this month.

Chess 0.5 is intended for instructional purposes, CIL is for research and production versions.

Right, and right.

Chess 0.5 relies extensively on global variables and its routines have minimal formal parameter lists. CIL has no global variables (but plenty of global constants) and so its routines rely entirely on formal parameters for dynamic behavior; each routine can be tested interactively.

Chess 0.5's compiler wasn't too efficient when it came to local vars, parameters, etc. So globals were easier. Plus, the asm Chess 4.5 was used as a guide, so the structures are very similar.

Incidentally, the compiler they used was Wirth's actual Pascal compiler.

Chess 0.5 was not written to be thread safe. CIL is thread safe.

Threads??? They had threads way back then...

Chess 0.5 has an 8x8 board combined with a 10x12 board used for edge detection. A position in CIL has an 8x8 board and uses pre-calculated square lists.

Note how the Chess 0.5 CUTATK routine needs to do step calculation and edge detection; and that doesn't help much speed-wise.

Right, that was the part I was talking about causing such a performance penalty.

You might be able to speed that part up with some more modern methods, but I haven't actually checked into that.

Realistically though, unless you really need the database, there's not much point wasting time even creating & maintaing it.

However, note that both routines do "the same thing" when "the same thing" is interpreted at a sufficiently high level of abstraction.

Does this mean that CIL stole from Chess 0.5? No, it means that both have incorporated the same idea from earlier sources.

I never siad nor suggested you 'stole' from Chess 0.5

Be kind of hard to steal from public domain, anyway. Larry Atkin specificly wrote it to be used and expanded upon. There were at least two tournament programs that were based heavily upon Chess 0.5 (And one commercial chess 'tool kit' was very heavily influenced by it. Not a clone, but it didn't take much effort to see its history.)

I figured you used it as a guide or something.

And since you posed with a subject of "Same code?" I assumed you were actually wanting feedback of some sort.

Either comments about how close your code was to the Pascal code, or you were unsure about some detail of how Chess 0.5 did things.

Since I am familar with Chess 0.5, I responded in case you had questions about that old code and Atkin's odd style.

If you don't want comments, then you probably shouldn't post a message like that with a subject like that.

No, it means that both have incorporated the same idea from earlier sources.

Since I like computer history more than computer present, what 'earlier sources' are you refering to?

I don't know of any earlier chess program that maintained a bitboard attack database like Chess 4.x did. (And hence chess 0.5)

I suppose Chess 3.6 came close, but it was recreated from scratch rather than being maintained and updated. And the source has been lost. And I don't think anybody has a copy of Atkin's thesis which fully describes it.

[sje]

Actually, I was using the original ETH Zurich Pascal compiler back in 1976 on a CDC 6500. I even had a source copy on 132 column line printer paper; can't find it now but maybe it's online somewhere.

I wrote my first bitboard program back in 1987 and it played in numerous USCF tournaments. It had two parallel versions of bitboard database implementations; one in ANSI C and the other in Motorola 68020 assembly language. Both were quite fast, as is the bitboard database management in Symbolic. I could say that the CIL has the fastest bitboard database in Lisp, but then again it's probably the only one in Lisp.

My ideas for bitboard management came not from any source code (I hadn't seen any), but from the Chess 4.x chapter in _Chess Skill in Man and Machine_.

My main point in posting the code was to show how two rather different implementations can arise from the same basic idea.

[Carey]

Actually, I was using the original ETH Zurich Pascal compiler back in 1976 on a CDC 6500. I even had a source copy on 132 column line printer paper; can't find it now but maybe it's online somewhere.

It wasn't as of a couple years ago.

Maybe that's changed since then.

I wrote my first bitboard program back in 1987 and it played in numerous USCF tournaments. It had two parallel versions of bitboard database implementations; one in ANSI C and the other in Motorola 68020 assembly language. Both were quite fast, as is the bitboard database management in Symbolic. I could say that the CIL has the fastest bitboard database in Lisp, but then again it's probably the only one in Lisp.

The code itself may be 'fast', but that wasn't what I was meaning.

I was meaning maintaining the database itself is slow and most of the info will never be used.

It just takes too much effort to update & downdate the database for what little it actually gets used. Especially considering modern bitboard methods that can generate the info much more easily as you need it.

But most people don't do that kind of database for a reason.

It would be nice if that kind of database could be maintained more efficiently, but I'm not sure that can be done.

My ideas for bitboard management came not from any source code (I hadn't seen any), but from the Chess 4.x chapter in _Chess Skill in Man and Machine_.

Chess 0.5 was meant as an example program to go along with the book. So people could actually see and understand all that bitboard stuff etc.

The source for Chess v4.6 is now available, if you are curious.

It's a little hard to read though. Well, maybe not for you... Slate came up with a bucn of macros to make things look somewhat like LISP.

Atkin said he was never really fond of it and would have been happier if they had just used regular assembler & macros.

My main point in posting the code was to show how two rather different implementations can arise from the same basic idea.

Well, you didn't say or suggest that, so nobody knew....

[sje]

The early Zurich Pascal compiler source was actually a better Pascal tutorial than Wirth's User Manual and Report. My copy was probably the first bootstrapped version and had an appalling number of unneeded CDC dependencies dealing with 60 bit words, 18 bit addresses, and 6 bit characters. (Binary output dependencies were understandable, of course.)

Surprisingly, it also had several goto statements. There was a goto target near the end of the code for an unexpected input EOF as the parser could not gracefully recover from such. The register allocation was also peppered with gotos and labels. The compiler had a single pass and very little optimization was available. All of the usual library routines had hard coded handlers in the compiler to take care of type checking and variable argument counts.

----

It's not particularly useful to discuss bitboard database utility without defining the exact contents of a bitboard database. In Symbolic and the CIL Toolkit, the BBDB includes:

all-men-merged-bb
all-sweeper-men-merged-bb
men-by-color-bb[2]
men-by-kind[12]
attacks-from-color-bb[2]
attacks-from-square-bb[64]
attacks-to-square-bb[64]

plus:

pinned-men-by-color-bb[2]
frozen-men-by-color-bb[2]

I have found all of these useful and worth maintaining.

[sje]

Here's the attack propagator routine pro-attacks, the dual of cut-attacks:

Code: Select all

(defun pro-attacks (my-sq my-bbdb)
  "Propagate the attacks through a square in a bitboard database."
  (let*
    (
      (loc-merge-bb        (bbdb-loc-merge-bb my-bbdb))
      (loc-sweep-bb        (bbdb-loc-sweep-bb my-bbdb))
      (atk-by-color-bb-vec (bbdb-atk-by-color-bb-vec my-bbdb))
      (atk-fr-sq-bb-vec    (bbdb-atk-fr-sq-bb-vec my-bbdb))
      (atk-to-sq-bb-vec    (bbdb-atk-to-sq-bb-vec my-bbdb))
      (atkr-bb             (clone-bb (svref atk-to-sq-bb-vec my-sq)))
    )
    (loop-bb (atkr-bb atkr-sq)
      (when (sq-set? loc-sweep-bb atkr-sq)
        (let*
          (
            (atkr-color      (calc-occ-color-bbdb atkr-sq my-bbdb))
            (atk-by-color-bb (svref atk-by-color-bb-vec atkr-color))
            (atk-fr-sq-bb    (svref atk-fr-sq-bb-vec atkr-sq))
            (extn-sqs        (fetch-beyond-sqs atkr-sq my-sq))
          )
          (when extn-sqs
            (do ((extn-sq (pop extn-sqs))) ((not extn-sq))
              (set-sq atk-fr-sq-bb extn-sq)
              (set-sq (svref atk-to-sq-bb-vec extn-sq) atkr-sq)
              (set-sq atk-by-color-bb extn-sq)
              (if (or (null? extn-sqs) (sq-set? loc-merge-bb extn-sq))
                (setf extn-sq nil)
                (setf extn-sq (pop extn-sqs))))))))))

Note that like cut-attacks (and the other main bitboard database routines), the pro-attacks routine does not reference any piece boards.

[sje]

The add-attacks and del-attacks routines:

Code: Select all

(defun merge-attack-ray-bb (my-bb my-sq my-dir my-bbdb)
  "Merge an attack bitboard from a square along a ray in the bitboard database."
  (let ((scan-sqs (aref open-ray-sqs-vec my-sq my-dir)))
    (when scan-sqs
      (do ((scan-sq (first scan-sqs)) (loc-merge-bb (bbdb-loc-merge-bb my-bbdb))) ((not scan-sq))
        (set-sq my-bb scan-sq)
        (if (or (null? scan-sqs) (sq-set? loc-merge-bb scan-sq))
          (setf scan-sq nil)
          (setf scan-sq (pop scan-sqs)))))))

(defun add-attacks (my-sq my-man my-bbdb)
  "Add the attacks of a man on a square in a bitboard database."
  (let*
    (
      (color            (svref mc-man-to-color-vec my-man))
      (piece            (svref mc-man-to-piece-vec my-man))
      (atk-to-sq-bb-vec (bbdb-atk-to-sq-bb-vec my-bbdb))
      (atk-by-color-bb  (svref (bbdb-atk-by-color-bb-vec my-bbdb) color))
      (atkr-bb           nil)
    )
    (cond
      ((= piece piece-pawn)
        (setf atkr-bb (clone-bb (aref pawn-attack-bb-vec color my-sq))))
      ((= piece piece-knight)
        (setf atkr-bb (clone-bb (svref crook-attack-bb-vec my-sq))))
      ((= piece piece-bishop)
        (setf atkr-bb (mk-bb))
        (dodiagodirs (dir)
          (merge-attack-ray-bb atkr-bb my-sq dir my-bbdb)))
      ((= piece piece-rook)
        (setf atkr-bb (mk-bb))
        (doorthodirs (dir)
          (merge-attack-ray-bb atkr-bb my-sq dir my-bbdb)))
      ((= piece piece-queen)
        (setf atkr-bb (mk-bb))
        (dosweepdirs (dir)
          (merge-attack-ray-bb atkr-bb my-sq dir my-bbdb)))
      ((= piece piece-king)
        (setf atkr-bb (clone-bb (svref king-attack-bb-vec my-sq))))
      (t
        (error "cond fault: add-attacks")))
    (copy-bb (svref (bbdb-atk-fr-sq-bb-vec my-bbdb) my-sq) atkr-bb)
    (loop-bb (atkr-bb atkr-sq)
      (set-sq (svref atk-to-sq-bb-vec atkr-sq) my-sq)
      (set-sq atk-by-color-bb atkr-sq))))

(defun del-attacks (my-sq my-man my-bbdb)
  "Delete the attacks from a man on a square in a bitboard database."
  (let*
    (
      (atk-fr-sq-bb-vec (bbdb-atk-fr-sq-bb-vec my-bbdb))
      (atk-to-sq-bb-vec (bbdb-atk-to-sq-bb-vec my-bbdb))
      (atkr-bb          (clone-bb (svref atk-fr-sq-bb-vec my-sq)))
      (atkr-color       (svref mc-man-to-color-vec my-man))
      (atkr-loc-bb      (svref (bbdb-loc-color-bb-vec my-bbdb) atkr-color))
      (atk-by-color-bb  (svref (bbdb-atk-by-color-bb-vec my-bbdb) atkr-color))
    )
    (reset-bb (svref atk-fr-sq-bb-vec my-sq))
    (loop-bb (atkr-bb atkr-sq)
      (reset-sq (svref atk-to-sq-bb-vec atkr-sq) my-sq)
      (when (bb-ni2? atkr-loc-bb (svref atk-to-sq-bb-vec atkr-sq))
        (reset-sq atk-by-color-bb atkr-sq)))))

[sje]

For those who are interested in the source for Chess 0.5, see:

http://www.moorecad.com/standardpascal/misc.html

I haven't tried it myself, but it looks like the edited version will compile under gpc (GNU Pascal Compiler).

Note: not only is the program pre-SAN, it's also pre-algebraic, so you get to use English Descriptive Notation in all its glory.