Some thoughts on QS

[Rebel]

It's not like the other guys other than chessbase were innocent either. Ed had his own arbitration trick. Rebel only would report games to be lost when score was above 5.0, yet it would stop the game being a rook down and that it evaluated then as 4.5, so it would be part of the 'aborted games' or seen as a draw rather than carry a 1-0 or 0-1.

Connect your brain to some anti-virus software.

Ah you don't like it.

Well i got a phone call back then from Jan Louwman who at 36 machines had been testing Diep.

"Diep won nothing against Rebel".

Ed, we speak of a game or 150, time control 40 in 2 back then and Diep had, according to Rebel's GUI won 0 games, which is what Jan told me through the phone very upset

When i checked out Diep's logs i saw a different truth though on what had been played

Checking Rebel closer then the naked truth became obvious.

You guys all had your methods to increase score. After all, the human operator interpreting the score is most important. Jan thought it was games that were removed by Rebel because of 2 times the exact same game and had not given those games attention of course. He just read up the score that Rebel GUI displayed

Diep probably lost on time or Jan must have been some kind time control setup mistake. Anyway, where was the big public scandal? Or was Jan the only one to notice?

The tragic of conspiracy theorists is that they won't believed if they discover a real conspiracy. Again, connect that software.

[marcelk]

In the 90s i was the big promotor of course of not using preprocessor engines. Bob joined me in that. With that we were initially the only ones.

The only ones in promoting or in doing? Correct me if I'm wrong, but I believe preeval.c was functional in Crafty in one form or another from 1996 until about two years ago when it was finally removed.

And although I usually don't care zip what people in the 1990s were doing, I remember that my program has never done any pre-processing (I have a mail of Dec 8 1994 where I explain that to you :-) ). I'm sure there are plenty of others from that era, 'Arthur' comes to mind.

[Don]

In the 90s i was the big promotor of course of not using preprocessor engines. Bob joined me in that. With that we were initially the only ones.

The only ones in promoting or in doing? Correct me if I'm wrong, but I believe preeval.c was functional in Crafty in one form or another from 1996 until about two years ago when it was finally removed.

And although I usually don't care zip what people in the 1990s were doing, I remember that my program has never done any pre-processing (I have a mail of Dec 8 1994 where I explain that to you ). I'm sure there are plenty of others from that era, 'Arthur' comes to mind.

I stopped using pre-processor long ago too. I think my last pre-processor program won the International Computer Chess Championship in 1993, but it was already an old program by then - probably finished in 1992.

[Gerd Isenberg]

Hi Don,

Over the years I've had quite a few conversations with Richard. Here's what I know (and I'm sure he wouldn't mind me sharing).

• CG doesn't have a Q Search as Ed rightly said
  I know from playing with the engines its search is extremely asymetrical i.e it searches broadly on opponents moves and narrow on its own moves
  It doesn't use null move (or didn't back in 2000)
  It keeps an incremental attack table for each square
  It uses evaluation terms at each node to prune (in lieu of null move)

Yes, all of that. I have seen part of his documentation, the Ossi papers as I have called them. They were wrongly (as I later found out) mailed to me instead of Richard's home address, a package of 200 A4 pages. Ossi wrote very instructive an detailed eval terms with clarifying diagrams that went into some form of PST structure initialized before the search started. Hundreds of patterns and pawn structures. Hence CG had a fast eval driven by a kind of sophisticated PST based system.

On my question, how do you do your selective search he answered, by just throwing away all the bad moves.

As Don said, I think there are probably gems in CG that would benefit the current crop of engines. Richard basically had to figure all of this stuff out for himself. He also had to grapple with limited hardware. It's quite amazing really.

Absolutely. Someone should ask if he still has the Ossi papers and if he is willing to scan them.

Wow!

See also this interview from Mike Watters' side, where Lang confirms he never used qsearch ...
Richard Lang - Question & Answer Interview given to a German magazine in 2003
http://www.chesscomputeruk.com/Richard_Lang_Q_A.pdf

[Don]

On my question, how do you do your selective search he answered, by just throwing away all the bad moves.

I asked Richard Lang the same question - and he said that he didn't understand what the big deal was and he just said that it was progressive, he throws away more and more moves as the search gets towards the leaf. I then asked him what happens if none of the moves reaches alpha and he said, "well you HAVE to search them." I didn't find any of this very helpful - for example how the moves were selective and some critical details would be needed to really understand what was going on.

[Gerd Isenberg]

Richard basically had to figure all of this stuff out for himself

At least he had absorbed Dan and Kathe Spracklen's book about Sargon which provided a complete Z80 Assembly listing, also containing the static swapoff routine ...
and saw several ways to improve, not only in speed, but also in better algorithms and ways of obtaining a score for chess positions...

[Rebel]

On my question, how do you do your selective search he answered, by just throwing away all the bad moves.

I asked Richard Lang the same question - and he said that he didn't understand what the big deal was and he just said that it was progressive, he throws away more and more moves as the search gets towards the leaf. I then asked him what happens if none of the moves reaches alpha and he said, "well you HAVE to search them." I didn't find any of this very helpful - for example how the moves were selective and some critical details would be needed to really understand what was going on.

The unsolicited questions, the ones you really don't want to answer, are always the hardest

[hgm]

Code: Select all

#define QSdepth 10 /* optimize empirically */

Search(alpha, beta, eval, evalCut, depth) 
{ 
  startDepth = (depth == QSdepth ? 0 : depth); // IID only in horizon nodes
  for(d = startDepth; d <= depth; d++) { // IID 
    bestScore = (depth > QSdepth ? -INF : eval); // depth 0-10 is all QS, so stand pat 
    if(bestScore >= beta) return bestScore; 

    for( ALL_MOVES ) { 
      if(depth<=QSdepth && !MoveIsCapture(move)) continue; // only captures in QS 

      MakeMove(move); 
      newEval = Eval();
      victimValue = newEval - eval;
      if(depth <= QSdepth && (victimValue <= value[mover] || !Attacked(TOSQUARE(move)))) {
        if(victimValue > evalCut) { // previous ply was unjustly extended / searched
          if(d == 0) score = +INF; // force beta cutoff if last two ply were a gain
          else {
            d--; depth--; evalCut = +INF; // take away extension and prevent this from happening again
            score = -Search(-beta, -alpha, newEval, victimValue, d);
          }
        } else // extend, but set us up to fail low if this happens to opponent on next d=0 ply
        score = -Search(-beta, -alpha, newEval, victimValue, d); 
      } else {
        if(d == 0) score = -INF; // non-obvious gains fail low without search at d=0 (pruned)
        else // and at other depths they eat one depth unit
        score = -Search(-beta, -alpha, newEval, +INF, d-1); 
      }
      UnMake(); 

      ... 
    } 
  } 
} 

I have a less cryptic formulation of the IIDing QS, by getting rid of the rather obscure and possibly very complex function IsObviousGain(). This is replaced by tests after MakeMove(). This is a more general approach, and is not assuming any complex infra-structure in the engine that can decide whether pieces are protected or not. (This can be quite hard to figure out when a move can explode neighboring pieces; even an attack map could then give wrong information, because a listed protector could get lost in the explosion, while on the other hand a square listed as unprotected could become protected because you blew up a neighbor that was blocking a slider attacker.)

In the current scheme it is not needed to know whether something is protected, (i.e. capturable by the side not to move after your move), only whether something is attacked by the stm. And even then it can be allowed to err in the direction of reporting pieces unprotected that in fact are protected in a non-obvious way (e.g. by exploding something on a neighboring square). This only means you will miss an early pruning of such bad captures, but eventually it will be discovered on the following ply that a recapture was possible, and abort the search there with a beta cutoff. (Which is the same as when a too-valuable 'hostage' would be executed on a different square).

With MMV sorting it should always be discovered on the first move whether it has a more valuable victim on what was captured on the previous ply. So there is no searching of moves in the sub-tree that will be pruned in this delayed way.

[diep]

In the 90s i was the big promotor of course of not using preprocessor engines. Bob joined me in that. With that we were initially the only ones.

The only ones in promoting or in doing? Correct me if I'm wrong, but I believe preeval.c was functional in Crafty in one form or another from 1996 until about two years ago when it was finally removed.

And although I usually don't care zip what people in the 1990s were doing, I remember that my program has never done any pre-processing (I have a mail of Dec 8 1994 where I explain that to you ). I'm sure there are plenty of others from that era, 'Arthur' comes to mind.

Bob helped me in the discussions there. the guys like Don who claim now they no longer were preprocessor since 93, it's nice to mention that in 2012. Would have helped to mention in discussions around 1995-1996.

No support on this terrain from Don back then...

That Bob promoted things he didn't find yet a student for to carry out for him in his own software, that isn't so interesting. It's about the vision to see what's right.

[Don]

In the 90s i was the big promotor of course of not using preprocessor engines. Bob joined me in that. With that we were initially the only ones.

The only ones in promoting or in doing? Correct me if I'm wrong, but I believe preeval.c was functional in Crafty in one form or another from 1996 until about two years ago when it was finally removed.

And although I usually don't care zip what people in the 1990s were doing, I remember that my program has never done any pre-processing (I have a mail of Dec 8 1994 where I explain that to you ). I'm sure there are plenty of others from that era, 'Arthur' comes to mind.

Bob helped me in the discussions there. the guys like Don who claim now they no longer were preprocessor since 93, it's nice to mention that in 2012. Would have helped to mention in discussions around 1995-1996.

No support on this terrain from Don back then...

That Bob promoted things he didn't find yet a student for to carry out for him in his own software, that isn't so interesting. It's about the vision to see what's right.

I never liked the pre-processor, even when I was using it before 1992 and I knew that deeper searching programs would eventually have to give it up. So if we had had the discussion I would have been firmly on your side but we never talked about that.

I even experimented with stuff like building the tables at the terminal depth - N but that has other serious problems. An idea I had long ago and experimented with is adding them to the hash table so that each pawn structure had it's own hash table - but that had a bunch of problems associated with it such as not being able to consider piece interactions, just piece positioning relative to the pawn structure. That also had a serious problem with cache back when I experimented with it although it would now be possible with modern CPU with monster caches. But that method also has the problem that you cannot keep the score incrementally updated - you have to recompute when the pawn structure changes. Mobility can be expressed perfectly if your mobility only considers pawns in the way.