Best search algorithms for ancient hardware

[mhull]

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.

This might be simple enough to test. Bochs runs pretty slow, even on fast hardware. I bet it runs almost as slow as an 8086. If you have an old super-constellation or other dedicated unit, run it against a modern program running under Bochs.

[lkaufman]

I'm sure a modern program would beat a SuperConstellation or the likes at comparable speed, partly due to superior eval, and partly because null move is even useful at six ply and it was not yet discovered in the mid 1980s. The question is whether one could do much better than to just use Rybka or Stockfish given such slow processor speeds by picking and choosing from today's ideas. I believe the answer is "yes" but I don't know that anyone has tried to write such a program.

[mhull]

I'm sure a modern program would beat a SuperConstellation or the likes at comparable speed, partly due to superior eval, and partly because null move is even useful at six ply and it was not yet discovered in the mid 1980s. The question is whether one could do much better than to just use Rybka or Stockfish given such slow processor speeds by picking and choosing from today's ideas. I believe the answer is "yes" but I don't know that anyone has tried to write such a program.

I might try to verify this. But my slowest working computer has a 20 Mhz 68030 chip with a late 1980s program. The Bochs effective speed might be slower than that.

I'll have to load Linux or XP on the Bochs image first and go from there.

[diep]

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.

It seems Rybka got tuned without playing too much games.

If you have that massive hardware, you don't need to tune playing games,
which gives far better and superior tuning of course.

Playing games you can do a few local optimizations which test out a bunch of bugs, but soon you'll have to play slower and slower time controls.

Playing games is exponential worse if you really try to tune well.

This is easy to see in the play from engines that got tuned in this manner, like crafty.

Vincent

[diep]

I'm sure a modern program would beat a SuperConstellation or the likes at comparable speed, partly due to superior eval, and partly because null move is even useful at six ply and it was not yet discovered in the mid 1980s. The question is whether one could do much better than to just use Rybka or Stockfish given such slow processor speeds by picking and choosing from today's ideas. I believe the answer is "yes" but I don't know that anyone has tried to write such a program.

If you use search from Rebel 1991 (or was it 1992 that world champs - i wasn't there) world champs and use a modern evaluation function with it, you have a killer program at 3-4Mhz.

It will murder anything up to 3-4Mhz, including deep thought, including deep blue.

Vincent

p.s. it would be easy to port the stockfish evaluation to a 8-16 bits program.

[diep]

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.

No no at 3-4Mhz at a 8 bits processor, rybka when ported would be maybe 10k cycles per node, which gives it like 300 nodes per second or so.

So you'll get maybe 3-4 ply, add another 3.5 ply forward pruned to it.

So 7 maybe in total, maybe 8.

But tactical those last few plies are so so weak, it wouldn't even find simple tactical shots.

It is really tuned for todays hardware.

Vincent

nah when i think about it - 300 nps already is rather optimistic. Maybe 100 nodes per second.

Right now your rybka gets roughly around 20 million nps at a 6-core chippie.
You slow it down a factor 200k or so. That's not very healthy

Vincent

[lkaufman]

I don't know so much about Rebel, but the programs of the mid 1980s were pretty much just full width with check extension and capture search. I'm talking about the Novag Constellation series and the Fidelity Excellence series. The ones that ran at around 4 MHz generally searched five plies full width in tournament (40/2) games. I suppose if they knew about null move then they could have searched six plies most of the time, and null move misses very few tactics. You talk about adding 3.5 plies by forward pruning, but my recollection of Rebel is that it outsearched the FW programs by no more than one ply. Which algorithms are you talking about that added several plies; the forward pruning techniques in modern programs wouldn't add even one ply to a five ply search I think?