Best search algorithms for ancient hardware

[lkaufman]

Given what we now know about how to write strong programs, which search algorithms would work well in the hardware of the mid 1980s, the dedicated chess machines running at speed around 3 or 4 MHz? Basically, hardware that could generally search to a depth of five plies full width plus check extensions and capture search. Would we use all the same techniques of today's programs or would we want to use only certain ones? Obviously I exclude any techniques that require more than say six plies to utilize in today's programs.

[Aleks Peshkov]

Best algorithms for what?
Better style and stronger play against human?
Maximum strength for correspondence game analysis?
Better performance against ancient state of the art machines?
Better performance against modern mobile phone powered chess programs?

[lucasart]

Given what we now know about how to write strong programs, which search algorithms would work well in the hardware of the mid 1980s, the dedicated chess machines running at speed around 3 or 4 MHz? Basically, hardware that could generally search to a depth of five plies full width plus check extensions and capture search. Would we use all the same techniques of today's programs or would we want to use only certain ones? Obviously I exclude any techniques that require more than say six plies to utilize in today's programs.

And why wouldn't we use these techniques on low NPS machines ?

All the advanced techniques (LMR, IID, Razoring etc.) that only apply to a sufficient depth can stil be in the program. They will just be used rarely, so perhaps the threshold depth may be reviewed, but removing them is probably not a good idea.

What would be important is the memor footprint on those machines, as well as the usage of 64 bit computations. I dont think the C language had a type like unsigned int 64 in those days (and even if it did, it would have been an emulated and horribly slow one, since machines <= 80286 are 16 bit!).

The best way is to try. The only engine that would be suited as I see it is Fruit because:
1. It is written in C (C++ disqualifies as the language changes all the time, and didn't exist in those days anyway).
2. It doesn't have a large memory footprint, and it doesn't use bitboards.

So if you can get hold of an ancient machine then try. It's the only way you'll ever know. The rest is just pointless discussions and speculations.

[lkaufman]

I meant how to achieve best rating on the computer rating lists. Maybe I should modify the question to ask whether one would change anything in today's program if one ran on a modern computer that was forced to move in a tiny fraction of a second that would make it equal (in terms of nodes searched) to what the old 4 MHz hardware could search in a minute per move or so.
It is not obvious that algorithms which apply to say a five ply search at the end of a twenty ply search are necessarily appropriate for a total search of five plies. That is really the point of the question.

[diep]

I meant how to achieve best rating on the computer rating lists. Maybe I should modify the question to ask whether one would change anything in today's program if one ran on a modern computer that was forced to move in a tiny fraction of a second that would make it equal (in terms of nodes searched) to what the old 4 MHz hardware could search in a minute per move or so.
It is not obvious that algorithms which apply to say a five ply search at the end of a twenty ply search are necessarily appropriate for a total search of five plies. That is really the point of the question.

Todays strongest programs search very bugfree and correct.

Back then the struggle was to not blunder away pieces. As my first incarnation back in 1993-1994 also achieved 4, later on 5 ply i am very aware of what searching 5 ply is.

IID won't work, first 10 iterations it will never work.
LMR won't work (prunes too little).

Also todays Rybka's wouldn't work at any of those machines, as they require a fast L1 and L2 cache of enormeous size, in fact bigger than the RAM back then. So just to calculate material, which gets out of a giant table using a megabyte of RAM is impossible.

Bitboards same problem.

You have 8 and 16 bits processors.

Some things i do in diep's evaluation also would be way way too slow on processors back then.

Rebel simply would kill every single program of today at this hardware, because it would get 11 ply using superselectivity versus todays software maybe 3 ply (forward pruning not counted).

Also the forward prunings methods very popular now in todays software, especially rybka type:

if( eval >= beta + 1 pawn ) then return;

That would hopelessly fail at hardware back then. Suppose you miss all those tactics last plies. This form of forward pruning is a positional form of forward pruning, you'd not want to miss all that.

Genius and Rebel pick up all that tactics.

I did do an experiment with superselectivity similar to how forward pruning worked back then. That's tactical 600 elo stronger for Diep.

So instead of 10 ply it got suddenly 14 ply nearly.

Simply +4 ply WITHOUT missing much tactics that all of todays software misses at those plydepths.

However it was 150 elopoints weaker effectively at a time control of 3 minutes a move @ 1.x Ghz K7, start of this century (2001).

Let's not forget that a 10Mhz XT back then @ 3 minutes a move is still 30 Mhz minutes per move.

Todays time controls are a lot faster.

So based upon some experiments i did do there a year or 9 ago, i know that the superselectivity from those days is completely kick butt tactical and initially that's what you want to see. Only above those 10 plies it gets more relaxed.

Nowadays software achieves that 10+ ply easily at which point suddenly everything mentionned will work. IID, LMR (provided your eval is tuned well - which in diep's case is doubtful).

The selectivity you need at 10Mhz XT, or better cpu's would've been back then the hardware that Genius ran on, it's still a lot more selective than anything we use today; basically because it positionally plays a lot weaker.

So objectively it just is too dubious to use today.

Of course with todays knowledge i, and i don't doubt others, also figured out other superselectivity algorithms, that have never been used back then.

They simply didn't know how to do it.

Another issue is you want to get a high nps, as long as you don't get that 10 ply. Getting 1 ply deeper initially is completely deadly against opponents.

So your program needs to be assembler for sure to have any impact. Forget compilers, you lose 100% nearly if someone outsearches you 1 ply there.

Another question is: how well would your software work, with some adaptation, at a 512 processor transputer that Zugzwang had back then.

It was 512 processors * 1Mhz.

Zugzwang achieved the total nps of roughly 200 nps there. So that's all 512 processors added up.

Pretty little in short.

One would expect of course more like a 100k nps at such a box, at which point it is a deadly machine. SMP still was in the pioneering age back then.

Please don't underestimate how advanced selective Rebel was in its start 90s incarnation. It is why it won that world title, completely based upon search and reasonable eval.

As for the elorating what you would achieve with todays evaluation functions, that is of course a lot higher than back then.

The quality of the evals today is so much better.

Testing was a lot tougher back then. Nowadays that is all full automatic. It wasn't back then full automatic. A few professional companies had some sort of automatic testing; for example the report from Hong Kong by Jan Louwman, where he saw how things had been automated there by a few handy technicians.

So if you backport todays software with super selectivity from back then, in assembler code of course written by Frans Morsch and Eric van Rietpaap, you would still win probably at that 10Ghz 680x0 processor all tournaments including the world champs 1995, hands down.

1997 is more tricky but maybe you'd win that as well at such 10Mhz motorola box, in endgames, provided opponents would reach that,
you'd have a problem as the time control there was something like 30 moves in 1 hour, then 60 moves in 1 hour; so going back to 1 minute an hour after move 30. In short you would require a completely won position by move 30. Yet todays evaluation functions would handsdown manage that, as of course most games they'd play such crap moves you would win that.

1999, forget it, as they get 17 ply then suddenly at quad socket machines,
an aggregated 500Mhz * 4 = 2Ghz * 3 minutes = 6Ghz minute pro move,
that's factor 500+ faster, so forget it, too big of a difference.

Please realize that limitations as hardware, if you give that to todays programmers, and then writing things in low level assembler, that's completely fulltime work.

Vincent

[diep]

I meant how to achieve best rating on the computer rating lists. Maybe I should modify the question to ask whether one would change anything in today's program if one ran on a modern computer that was forced to move in a tiny fraction of a second that would make it equal (in terms of nodes searched) to what the old 4 MHz hardware could search in a minute per move or so.
It is not obvious that algorithms which apply to say a five ply search at the end of a twenty ply search are necessarily appropriate for a total search of five plies. That is really the point of the question.

1 minute a move is not fair. It was 3 minutes a move back then.
Without that 3 minutes a move forget it. You would require a superior RISC processor from back then where genius ran on. Dont forget it had the fastest hardware from the dedicated computers back then. Frans Morsch complained loud about this, even 2 decades later.

The XT machines @ 4.77Mhz or with turbo button @ 10Mhz, they would be a lot slower than a 10Mhz RISC processor from back then, as out of order didn't work yet. That arrived at the completely superior pentium processor, at which point the RISC processors are history from performance viewpoint for computerchess.

That time control really matters, factor 3 to get another ply and a little would be completely crucial.

[lkaufman]

"Rebel simply would kill every single program of today at this hardware, because it would get 11 ply using superselectivity versus todays software maybe 3 ply (forward pruning not counted)."

Thanks for your answer. I'm not familiar with the "superselectivity" of Rebel. If it's not confidential, could you explain a bit about how that worked?

[Aleks Peshkov]

Rumors said Rybka was tuned using super fast time control self play.
I bet most current active programs are tuned for super fast time controls also.

So the current search algorithms of the top engines should be near the best without special modifications.

[lkaufman]

Good point, but I think that the search algorithms of current programs are tuned at levels that would allow 8 or 9 plies full width typically, quite a bit more than the five plies in the question. Eval changes are tested at shorter levels generally than search changes.

[mhalstern]

Back in the 486 (100 mhz I believe) days, dos based Mchess Pro was the king. What was so special about M-Chess? What made it tick?