Cray Blitz source (Carey)

[sje]

I took a look at the source and the first thing I noticed is that the Fortran dialect in use was rather advanced over the one I learned long ago. In the early Fortran specification, an array subscript expression could be only a constant, a variable, or a variable plus or minus a constant. All integers, of course.

By the time of the mid 1970s or so, many Fortran coders were using a source preprocessor like ratfor that allowed for at least the appearance of structured programming. Sadly, I and too many others were still struggling with the goto, the call-entry, the return-from, the computed-goto, and even the assigned goto.

[bob]

I took a look at the source and the first thing I noticed is that the Fortran dialect in use was rather advanced over the one I learned long ago. In the early Fortran specification, an array subscript expression could be only a constant, a variable, or a variable plus or minus a constant. All integers, of course.

By the time of the mid 1970s or so, many Fortran coders were using a source preprocessor like ratfor that allowed for at least the appearance of structured programming. Sadly, I and too many others were still struggling with the goto, the call-entry, the return-from, the computed-goto, and even the assigned goto.

much of CB is fortran-77, which added things like integer a(-10:10) and better control structures like if/then/else to get rid of many of the goto's...

[sje]

From Cray Blitz:

Code: Select all

c    mtype:        0 = normal move
c                  1 = castle king-side
c                  2 = castle queen-side
c                  3 = en passant pawn capture
c                  4 = pawn promotion to knight
c                  5 = pawn promotion to bishop
c                  6 = pawn promotion to rook
c                  7 = pawn promotion to queen

From Symbolic:

Code: Select all

// Chess move special cases

typedef enum
{
  CTMSCNil = -1,
  CTMSCRegularMove,
  CTMSCEnPassant,
  CTMSCCastleKS,
  CTMSCCastleQS,
  CTMSCPromKnight,
  CTMSCPromBishop,
  CTMSCPromRook,
  CTMSCPromQueen
} CTMSC;

#define CTMSCLen (CTMSCPromQueen + 1)

From the new CIL Toolkit:

Code: Select all

;;; Move special cases

(defconstant msc-reg (enum-init) "Regular moves including simple captures")
(defconstant msc-epc (enum-next) "En passant capture move")
(defconstant msc-cks (enum-next) "King side castling")
(defconstant msc-cqs (enum-next) "Queen side castling")
(defconstant msc-ppn (enum-next) "Pawn promotion to a knight")
(defconstant msc-ppb (enum-next) "Pawn promotion to a bishop")
(defconstant msc-ppr (enum-next) "Pawn promotion to a rook")
(defconstant msc-ppq (enum-next) "Pawn promotion to a queen")

(defconstant msc-limit (enum-limit))

The above arrangement is the one I've used since my very first chess program, a z80 assembly junker I wrote so many years ago.

[Rolf]

(Bob says he's been doing computer chess for 40 years. So that would put the start in 68

Please dont let Bob know this that I asked you, but tell me, Bob for one wasnt in chess at the time then, no, because he couldnt even count the normal chess game moves comme il faut?

1 first white move
2 first black move
3 second white move

Isnt it a bit funny? Hehe. I remember the old days... the crusaders were in power...

<g>

[sje]

much of CB is fortran-77, which added things like integer a(-10:10) and better control structures like if/then/else to get rid of many of the goto's...

I took another look at the source and I don't see any recursion in the search. So I suppose that the Fortran in use didn't support recursive calls. Then again, it's certainly possible that a non-recursive search might be preferable when stack space is limited or may be for other reasons.

On the old CDC 6000 series mainframes, the only compiler I know for certain that supported recursion was the Zurich Pascal compiler. A CDC 6000 series machine had eight 18 bit index registers of which six were generally available; the Fortran compiler used these for do loops and little else. The Pascal compiler took three of these and used them to build and maintain traditional stack frames each with a lexical context link. The code produced was fully recursive and (I think) re-entrant as well.

There was also a little used Algol compiler for the 6000 series, but I didn't have much experience with it; perhaps it also supported recursion.

[bob]

much of CB is fortran-77, which added things like integer a(-10:10) and better control structures like if/then/else to get rid of many of the goto's...

I took another look at the source and I don't see any recursion in the search. So I suppose that the Fortran in use didn't support recursive calls. Then again, it's certainly possible that a non-recursive search might be preferable when stack space is limited or may be for other reasons.

On the old CDC 6000 series mainframes, the only compiler I know for certain that supported recursion was the Zurich Pascal compiler. A CDC 6000 series machine had eight 18 bit index registers of which six were generally available; the Fortran compiler used these for do loops and little else. The Pascal compiler took three of these and used them to build and maintain traditional stack frames each with a lexical context link. The code produced was fully recursive and (I think) re-entrant as well.

There was also a little used Algol compiler for the 6000 series, but I didn't have much experience with it; perhaps it also supported recursion.

CB didn't use a negamax-type recursive search as early fortran compilers didn't support recursion. But it eventually became a good thing, because for parallel search, an iterated search is better than a recursive search because it then is simple to split the tree at any point, rather than being limited to splitting at the current ply because of the recursive stack...

[sje]

CB didn't use a negamax-type recursive search as early fortran compilers didn't support recursion. But it eventually became a good thing, because for parallel search, an iterated search is better than a recursive search because it then is simple to split the tree at any point, rather than being limited to splitting at the current ply because of the recursive stack...

I can see where an non-recursive approach allows for some benefits, the best one being an explicit structure for prior local values instead of having such values scattered in prior stack frames. Another advantage is that's is easier to unwind a data structure than it is to do the same to a call history when some exceptional event occurs.

But you chose a recursive approach in Crafty. Do you think that's faster or maybe easier to write and maintain?

[bob]

CB didn't use a negamax-type recursive search as early fortran compilers didn't support recursion. But it eventually became a good thing, because for parallel search, an iterated search is better than a recursive search because it then is simple to split the tree at any point, rather than being limited to splitting at the current ply because of the recursive stack...

I can see where an non-recursive approach allows for some benefits, the best one being an explicit structure for prior local values instead of having such values scattered in prior stack frames. Another advantage is that's is easier to unwind a data structure than it is to do the same to a call history when some exceptional event occurs.

But you chose a recursive approach in Crafty. Do you think that's faster or maybe easier to write and maintain?

It is easier to understand. But it introduces obstacles to a parallel search. Mosf of them can be overcome, but to do a DTS-like search as done in Cray Blitz is nearly impossible in a recursive search. But I have liked the "understandability" of the recursive search and chose to stick with it as a result...

[sje]

It is easier to understand. But it introduces obstacles to a parallel search. Mosf of them can be overcome, but to do a DTS-like search as done in Cray Blitz is nearly impossible in a recursive search. But I have liked the "understandability" of the recursive search and chose to stick with it as a result...

The usual paradigm for Lisp programming is to employ recursion as much as possible, particularly tail recursion which allows for run time speed optimization. This is also the preferred approach of the functional programming purist crowd. The big drawback is that a lengthy iteration handled recursively can fail badly due to stack space limitations.

A non recursive approach has another benefit: profiling is easier when all costs of a particular routine can be assigned to a single invocation rather than dozens of nested instances.

Any decent run time environment will be able to handle the recursion depths encountered in a chess move tree search. But this was not always the case. I recall a heroic programming effort from back in the early 1970s where some determined coder wrote a chess player for the HP 2000 timesharing system. I had much experience with the machine series in use and I know that the Basic interpreter supported only nine levels of subroutine calls, no formal parameters, and no local variables.

[bob]

(Bob says he's been doing computer chess for 40 years. So that would put the start in 68

Please dont let Bob know this that I asked you, but tell me, Bob for one wasnt in chess at the time then, no, because he couldnt even count the normal chess game moves comme il faut?

1 first white move
2 first black move
3 second white move

Isnt it a bit funny? Hehe. I remember the old days... the crusaders were in power...

<g>

As usual, I can't tell what you are trying to say. But my first chess program did play its first chess move in october of 1968 when I was an undergrad student at the University of Southern Mississippi. I started working on it during the Summer. So it really is right at 40 years. I was playing chess 10 years before that...