Some thoughts on QS

[diep]

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.

In those days the piece square tables tended to be pre-processed and with some creativity you could have a very comprehensive evaluation function that was also very cheap because the values were determined just once, before each search begins. You could take the time to have a very expensive analysis to determine where to put pieces.

Some of my early programs also had such a system - in fact I built a little language so that Larry could express evaluation concepts in a more natural way. This has it's limitations for a deep searching program but it was quite effective for programs that could only search a fraction of the depth today's programs could.

I think that this system is clearly wrong also in the days of Genius(Genius3 is from 1994) and the only reason that it was effective in games is that people did not know to write a good evaluation at that time.

Fritz5 and Fritz5.32 used this system and I believe that they changed it in Fritz6 and got a signficant improvement.

From the ssdf rating list:

97 Fritz 6.0 128MB K6-2 450 MHz 2612 17 -17 1751 48%
108 Fritz 5.32 128MB K6-2 450 MHz 2555 20 -20 1194 48%

From the CEGT 40/4 rating list that may be equivalent to tournament time control at the time of Genius:

666 Fritz 6 2455 13 13 1791 49.1% 2462 31.7%
729 Fritz 5.32 2425 13 13 2006 52.0% 2411 29.7%

Uri, just shut up with this total idiocy you write here.

These guys got engines to work at cpu's with 128 bytes RAM and 2KB rom.
Later on they had 4 kilobyte of RAM and a 1Mhz H8 chip. That chip is a lot slower than a 1 Mhz ARM/MIPS type cpu.

Later CPU's had a 4KB RAM and 64KB ROM and a few Mhz.

You just don't have the system time nor code to get real deep.

It's true things are better now, but that's because we have more RAM and faster cpu's in the first place and we had 30 years more time.

If you are sure you are gonna get 4 ply with a todays engine and 6 plies with what they did do, then i'm not so sure any of todays engine would stand a chance. Besides that todays engines you care about forward prune last 3 plies without picking up tactics, so they would lose everything against Genius, as Genius simply would win tactical every game as todays engines are last few plies tactical 500 elo weaker than what engines back then picked up last few plies.

I would like to see a test of Genius vs any top program that is normalized by node count run at less than say 20,000 nodes. As you say those programs were handicapped by the hardware - they were forced to make compromises we don't have to make. If I had to take a wild guess I would say Komodo would win, but if it turned out the opposite I would not be surprised. Komodo was not designed to do 20k node searches.

Today if I do 20k nodes Komodo searches on average 9.5 ply deep. It has a far superior evaluation to CG so I think it would win - however everything you say is true too - although genius is selective Komodo is more selective. I could see Komodo losing some games for this reason but in general I would expect it to outplay Genius. And tactics dominate little searches.

I wish Richard would package up genius into a UCI compatible engine for PC's without making any other changes so we would not have to speculate, one of the early versions that really dominated computer chess at the time. I would rather that than one of the later versions even if the later CG's are technically stronger. I'm pretty sure our memories will not match the reality and we might be disappointed when comparing to modern programs.

I think it might be possible, if the source code to any dos emulator is available, to wrap this up and make a single executable (without the graphics) with a UCI interface? There should be some attempt to preserve these old programs in some form that is accessible by modern GUI's.

Don

The problem at hardware back then would be that todays software needs 10x more cycles per node than software they produced.

If we would use the same evaluation function they used back then at the hardware they massively sold, then todays search would completely lose, as you won't search 4 nor 5 plies, you'll get 3.

[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.

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.

In those days i had impression you were busy more with search than evaluation. Wasn't there a phd student you took with you to this house, that was supposed to be of help for the evaluation function? What again was his name?

You offered big help in the discussion regarding the elowin a ply at bigger search depths.

[Don]

In those days i had impression you were busy more with search than evaluation. Wasn't there a phd student you took with you to this house, that was supposed to be of help for the evaluation function? What again was his name?

You offered big help in the discussion regarding the elowin a ply at bigger search depths.

I cannot remember his name, but he was a USCF master - there were actually 2 students there who were helping in this way as strong players and you probably remember him as coming with me to the Netherlands for one tournament. There was a also Harald Prokop, who was a German but he is not the one you are thinking about although he came to the tournament in Padderborn (I think it was Padderborn.) If I remember I'll let you know. Tall kid, right?

In those days there were huge debates over "brute force" vs "smarts" and I was pigeon-holed into the brute force camp even though I was more of an advocate of doing things smarter. It was not just evaluation but "selective search" which was part of this school of thought. I tried hard to advocate a balanced approach consider both but the problem was that I was one of the few with big hardware - so it was assumed that I only cared about speed.

Also, the anti-bute-force people tended to be less reasonable and more fanatical which I reacted against - even though I was sympathetic to them.

There are 2 basic observations in computer chess and some people would take one of them and run with it, ignoring the other. The two observations:

1. No matter how deep you go, there is always something the program
won't understand due to a knowledge hole.

2. No matter how much knowledge your program has, there will be horrible
blunders if you do not search deep enough.

Often a little knowledge is worth several ply and the anti-BF folks latched on to that. But the BF camp observed that each extra ply of search solved huge sub-classes of tactics and also improved positional play.

It was one of those abstract discussions where people argue just for the sake of arguing and people argued who probably felt the same way but defined terms differently.

As you see, the very best programs are very strong in BOTH tactics and positional play and are extremely selective with a branching factor of around 2 which compares to 4 or 5 15 years ago. So as I often argued, you have to do both.

[diep]

In those days i had impression you were busy more with search than evaluation. Wasn't there a phd student you took with you to this house, that was supposed to be of help for the evaluation function? What again was his name?

You offered big help in the discussion regarding the elowin a ply at bigger search depths.

I cannot remember his name, but he was a USCF master - there were actually 2 students there who were helping in this way as strong players and you probably remember him as coming with me to the Netherlands for one tournament. There was a also Harald Prokop, who was a German but he is not the one you are thinking about although he came to the tournament in Padderborn (I think it was Padderborn.) If I remember I'll let you know. Tall kid, right?

Yeah i refer to the tal kid that was here at home. Now i'm not so tall of course, just 6 feett. Compare with Richard Pijl in computerchess who is nearly 7 feet; i remember the first time meeting Richard Pijl. Literally everything he had was huge. His mouse was much bigger than everyones mouse, his keyboard was huge.

When you got here end 90s,
my mother had cooked traditional Dutch dish for everyone, yet i wasn't so sure you'd like that (even most dutch don't like it ). In fact normally spoken i don't offer Dutch dish to visitors - as odds is too tiny they like it. Most of the Dutch traditional dish is heavy winterfood - even for Russians that's tough to eat.

The tal kid didn't like it as i feared and we didn't have much backup food.

But the second day when i got a lot of Chinese-Indonesian food, the tal kid made up for what he didn't eat the day before

In those days there were huge debates over "brute force" vs "smarts" and I was pigeon-holed into the brute force camp even though I was more of an advocate of doing things smarter.

What i refer to is the elowin a ply discussion. back then some thought it would lineair scale further. especially the 'deep' experiments of amongst others Ernst A Heinz would 'prove' that; namely by measuring the number of PV flips at higher search depths. How that ever represented elostrength is a mystery to me. It's crap science of course.

Also in those days it was impossible to turn off all types of learning in Fritz GUI (not sure about today either), as after each game it would reset those values and they played thousands of games; so the games were not independant experiments either (understatement) so doing statistics is total impossible with those results as well.

It was not just evaluation but "selective search" which was part of this school of thought. I tried hard to advocate a balanced approach consider both but the problem was that I was one of the few with big hardware - so it was assumed that I only cared about speed.

Also, the anti-bute-force people tended to be less reasonable and more fanatical which I reacted against - even though I was sympathetic to them.

I invented reductions in 1999.

Diep world champs 1999 played with reductions. Now reductions is a pretty trivial thing to invent (to quote GCP), but back then it didn't work.

Also current diep version i still struggle. It gives 2 ply search depth win at 8 cores and it gave 2 ply back then as well - that's very little for the risk you take.

This was the case with many algorithms - letting them break even is not easy and most algorithms in 90s was impossible to let break even as the nps of Diep wasn't enough.

Additional to that, being busy inventing new selective algorithms is big R&D, not seldom more than half a year of research to get something useful out of it.

Then with a simple debug action dudes steal it from you.

There are 2 basic observations in computer chess and some people would take one of them and run with it, ignoring the other. The two observations:

1. No matter how deep you go, there is always something the program
won't understand due to a knowledge hole.

2. No matter how much knowledge your program has, there will be horrible
blunders if you do not search deep enough.

Often a little knowledge is worth several ply and the anti-BF folks latched on to that. But the BF camp observed that each extra ply of search solved huge sub-classes of tactics and also improved positional play.

It was one of those abstract discussions where people argue just for the sake of arguing and people argued who probably felt the same way but defined terms differently.

As you see, the very best programs are very strong in BOTH tactics and positional play and are extremely selective with a branching factor of around 2 which compares to 4 or 5 15 years ago. So as I often argued, you have to do both.

I'm not disagreeing; you cannot have weak spots, but if i see how SF can get 30-40 ply pretty easy, whereas each additional ply hardly gives it elo, then i wonder whether there is any objective compare possible nowadays with search depths; especially if we realize that if you refer to the tactics, that Diep at around 20 ply solves tactical about every position i have, whereas it hardly extends tactics, and SF not seldom needs 39+ plies for deep tactics.

[Don]

I'm not disagreeing; you cannot have weak spots, but if i see how SF can get 30-40 ply pretty easy, whereas each additional ply hardly gives it elo, then i wonder whether there is any objective compare possible nowadays with search depths; especially if we realize that if you refer to the tactics, that Diep at around 20 ply solves tactical about every position i have, whereas it hardly extends tactics, and SF not seldom needs 39+ plies for deep tactics.

It's ok not to get much for a ply if your branching factor is less than 2. That's how modern programs work, they give up a lot in things they might miss, but they get a lot for it in depth and other things they might see but never could before. Most programs of today will not solve problems in the same depth as yesterday, but will solve with much less nodes so it's a very good trade-off.

There is also the issue of whether it really makes sense to be so consistent in depth like old programs did - that's nothing like how humans do it so I think heavy pruning, reductions and aggressive futility is a big win - a program SHOULD look much deeper in some lines than others and only in the past few years has then been the case.

[diep]

I'm not disagreeing; you cannot have weak spots, but if i see how SF can get 30-40 ply pretty easy, whereas each additional ply hardly gives it elo, then i wonder whether there is any objective compare possible nowadays with search depths; especially if we realize that if you refer to the tactics, that Diep at around 20 ply solves tactical about every position i have, whereas it hardly extends tactics, and SF not seldom needs 39+ plies for deep tactics.

It's ok not to get much for a ply if your branching factor is less than 2. That's how modern programs work, they give up a lot in things they might miss, but they get a lot for it in depth and other things they might see but never could before. Most programs of today will not solve problems in the same depth as yesterday, but will solve with much less nodes so it's a very good trade-off.

There is also the issue of whether it really makes sense to be so consistent in depth like old programs did - that's nothing like how humans do it so I think heavy pruning, reductions and aggressive futility is a big win - a program SHOULD look much deeper in some lines than others and only in the past few years has then been the case.

Well the whole point is that what you call 'taking a deeper look' only happens in the mainline. That's what effectively happens. Getting a fail high hardly happens.

It takes 15 plies extra or so to find tactics at those depths, just the mainline gets seen very deep. Diep doesn't suffer too much from this problem - obviously its problem is getting any depth at all

Just seeing mainlines deep - it's a way to play chess, but it makes the game boring.

[hgm]

I still think the 'kamikaze capture' as an elementary tactical motive for refuting counter attacks (and thus putting a stop to unsound plunder raids, as plunder raids basically live from answering attacks with counter attacks) should preferably be included in even the most rudimentary QS.

[d]8/p7/r7/7q/8/1Q6/8/5N2 w
After 1. Ng3 a counter attack 1... Rb6? on Queen is refuted by the SEE-wise bad capture 2. Qxb6!

I was thinking of something like this:

Code: Select all

Search(alpha, beta, evalCut, depth) 
{
    int kamikaze = NONE;
    bestScore = (depth > QSdepth ? -INF : eval);
    if(bestScore >= beta) return bestScore; 

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

      MakeMove&#40;move&#41;; 
      if&#40;depth == 0&#41; &#123;

        if&#40;fromSqr == kamikaze&#41;
          score = -Search&#40;-beta, -alpha, +INF, 0&#41;;
        else if&#40;value&#91;victim&#93; > value&#91;mover&#93; || !Attacked&#40;toSqr&#41;) &#123;

          if&#40;value&#91;victim&#93; >= evalCut&#41; // force beta cutoff if last two ply were no gain to opponent
            if&#40;value&#91;victim&#93; > evalCut&#41;
              score = +INF; // he lost material; caller fails low without recourse
            else
              score = +INF + 1 + toSqr; // kludge to pass aborting threat to caller
          else &#123; // set up abort if he can capture &#40;elsewhere&#41; more than we just did
            score = -Search&#40;-beta, -alpha, value&#91;victim&#93;, 0&#41;;
            if&#40;score < -INF&#41; kamikaze = -INF - 1 - score // recovers toSqr to appoint kamikaze
          &#125;

        &#125; else score = -INF; // effectively skips move that is no obvious gain

      &#125; else &#123; // depth (> 0&#41; with unrestricted searching of captures

        score = -Search&#40;-beta, -alpha, +INF, depth-1&#41;; 

      &#125;
      UnMake&#40;); 

      ... 
    &#125; 
  &#125; 
&#125; 

In the example, even if after 1... Rb6 we are at depth=0, we would now first search 2. Nxh5, setting up an evaluation-based cutoff of 1 Queen, which is indeed (just) realized by 2... Rxb3. But because both captured a Queen, the square b3 responsible for the cutting loss is passed to the caller, elevating Qb3 to kamikaze piece. So 2. Qxb6 now will get unconditionally searched, knowing it is backed up by Queen capture 3. Nxh5.

And indeed 2... axb6 (setting the eval-based cutoff at 1 Queen) will be aborted after discovery of 3. Nxh5 in the daughter node. Now this would elevate Qh5 to kamikaze status, but as there is nothing to capture for that Queen, black is out of options, and 2. Qxb6 will be scored as +1 Rook without further search.

[Rebel]

I invented reductions in 1999.

I used them since 1996 with Rebel 8. You stole them from me Vince?



And BTW, I did not invent reductions, the one who put me on track was Erik van Riet Paap.

[Don]

I'm not disagreeing; you cannot have weak spots, but if i see how SF can get 30-40 ply pretty easy, whereas each additional ply hardly gives it elo, then i wonder whether there is any objective compare possible nowadays with search depths; especially if we realize that if you refer to the tactics, that Diep at around 20 ply solves tactical about every position i have, whereas it hardly extends tactics, and SF not seldom needs 39+ plies for deep tactics.

It's ok not to get much for a ply if your branching factor is less than 2. That's how modern programs work, they give up a lot in things they might miss, but they get a lot for it in depth and other things they might see but never could before. Most programs of today will not solve problems in the same depth as yesterday, but will solve with much less nodes so it's a very good trade-off.

There is also the issue of whether it really makes sense to be so consistent in depth like old programs did - that's nothing like how humans do it so I think heavy pruning, reductions and aggressive futility is a big win - a program SHOULD look much deeper in some lines than others and only in the past few years has then been the case.

Well the whole point is that what you call 'taking a deeper look' only happens in the mainline. That's what effectively happens. Getting a fail high hardly happens.

You are essentially correct, but I think you miss the point that the tradeoff is quite good - you can see even interesting sacrifices very quickly with these aggressive reductions. I can lose 2 ply and still see things much faster than I would without LMR.

I did a test from the opening position and I can search 19 ply in less time than I would be able to search 16 ply with LMR off. That is a difference of 3 ply. The trade-off is good because even though I lose quality, I gain much more than I lose.

It takes 15 plies extra or so to find tactics at those depths, just the mainline gets seen very deep. Diep doesn't suffer too much from this problem - obviously its problem is getting any depth at all

Just seeing mainlines deep - it's a way to play chess, but it makes the game boring.

It's not quite as simple as you make it seem. Yes, we do rally around the PV nodes but the non-pv nodes are not that much different in the attention we give them. We are bit more aggressive about pruning and LMR but we still give them plenty of attention.

I think the main reason this works so well is the carefully constructed rules and extensions to prevent too much loss. For example most programs do not reduce the first move - that has a surprisingly high chance of being best. Most programs do not reduce captures, checks and out of checks, or if they do have careful rules to not take this too far. As you know captures checks and out of check tends to be at the heart of most tactics. Komodo is extremely aggressive at reducing but we also have OTHER rules beyond checks and capture that might prevent a move from being reduced.

Also, don't forget that even though a move is reduced, it could be search to the original depth if something interesting is found.

As you indicate it's possible to defeat this system with a position that has a bunch of tricky quiet moves - that can happen on occasion but it's not that common in chess. But even if there is a couple of them in a line, it will STILL probably solve the position more quickly than a program that does no LMR because LMR can add several ply of search. As I mentioned I get 3 ply even for a 30 second search. With longer searches this only increases.

I'm running off a few games to show you just how important LMR is. Note that the time control is Fischer 6 seconds + 0.1 increment - and LMR gives us 2 additional ply of search and over 100 ELO. The sample is too small to believe the 167 ELO this shows - I think in previous tests it comes out to something well over 100 ELO. I'll give you an update later when I have several hundred games:

Code: Select all

Rank Name             Elo      +      -    games   score   oppo.   draws 
   1 komodo5-Lmr    3167.7   69.3   69.3     124   68.5%  3000.0   37.1% 
   2 komodo5-noLmr  3000.0   69.3   69.3     124   31.5%  3167.7   37.1% 


      TIME       RATIO    log(r)     NODES    log(r)  ave DEPTH    GAMES   PLAYER
 ---------  ----------  --------  --------  --------  ---------  -------   -------------
    0.1954       0.961    -0.039     0.290     0.004    12.5009      124   komodo5-Lmr
    0.2032       1.000     0.000     0.288     0.000    10.5843      124   komodo5-noLmr

[Don]

I invented reductions in 1999.

I used them since 1996 with Rebel 8. You stole them from me Vince?



And BTW, I did not invent reductions, the one who put me on track was Erik van Riet Paap.

I experimented with reductions without knowing anything about them from anyone else. But I was too stupid to stick with it even though I was getting some tantalizing big speedups. This was in the late 80's - and I have no idea whether anyone else had started using them by then but I would be very surprised if not.