Slow Searchers?

[Michael Neish]

I haven't posted here for a long time, but have been lurking on and off over the years.

Just wondering ... is there anyone out there who is still implementing a slow, knowledgeable search paradigm in his or her program? I mean an expensive, but supposedly smarter evaluation coupled with aggressive pruning and extensions based on the evaluation.

It just appears to me (correct me if I'm wrong, but please do so politely ) that everyone, or at least everyone obvious, is doing basically the same thing with relatively minor refinements. To be brief: the best programs are fast, dumb searchers, but they compensate for their dumbness by being prodigious calculators. Evaluations are shallow and search extensions/reductions are crude, often statistically based.

This has surely been debated ad nauseum over the years, and my understanding (correct me if I'm wrong again, but I'd hate to be wrong twice in a row ) that fast searching won the argument quite a while ago in terms of raw playing strength.

But what has fast-searching got to do with AI? Aren't today's best programs just calculators, implementing a set of simple rules, albeit very fast and effectively? Wouldn't we learn more about AI, maybe even Chess, if we shifted our attention to other possibilities?

I'm being deliberately vague, since I know that prior attempts of this kind haven't managed to produce very strong programs (not to mention that my own ignorance lets me down at this point!). Now that hardware has moved on so much, maybe now is the time for a fresh look?

Opinions please.

Thanks.

Mike.

[Steve Maughan]

I don't think the best programs have a "dumb" evaluation. I think they are actually quite sophisticated. A 1 ply search with quiescent resolution is probably 1800 ELO, which is the strength of a reasonable club player i.e. not dumb.

Steve

[lucasart]

I haven't posted here for a long time, but have been lurking on and off over the years.

Just wondering ... is there anyone out there who is still implementing a slow, knowledgeable search paradigm in his or her program? I mean an expensive, but supposedly smarter evaluation coupled with aggressive pruning and extensions based on the evaluation.

It just appears to me (correct me if I'm wrong, but please do so politely ) that everyone, or at least everyone obvious, is doing basically the same thing with relatively minor refinements. To be brief: the best programs are fast, dumb searchers, but they compensate for their dumbness by being prodigious calculators. Evaluations are shallow and search extensions/reductions are crude, often statistically based.

This has surely been debated ad nauseum over the years, and my understanding (correct me if I'm wrong again, but I'd hate to be wrong twice in a row ) that fast searching won the argument quite a while ago in terms of raw playing strength.

But what has fast-searching got to do with AI? Aren't today's best programs just calculators, implementing a set of simple rules, albeit very fast and effectively? Wouldn't we learn more about AI, maybe even Chess, if we shifted our attention to other possibilities?

I'm being deliberately vague, since I know that prior attempts of this kind haven't managed to produce very strong programs (not to mention that my own ignorance lets me down at this point!). Now that hardware has moved on so much, maybe now is the time for a fresh look?

Opinions please.

Thanks.

Mike.

Every now and then, someone (obviously clueless) comes here, and tries to lecture a field of expert on how computer chess should be done. This is a typical manifestation of the Dunning-Kruger effect.

I'm not even going to argue on the "points" made above, because they are far to vague and simplistic to even be considered.

The "argument" is always the same: we should replace brute force search by knowledgeable eval, which is a completely void argument that shows zero understanding of the subject. My answer is this: DO IT YOURSELF, and THEN you will understand.

We can discuss this ad nauseam, but it is pointless, because you will never learn anything except by experimenting yourself.

[Ferdy]

I haven't posted here for a long time, but have been lurking on and off over the years.

Just wondering ... is there anyone out there who is still implementing a slow, knowledgeable search paradigm in his or her program? I mean an expensive, but supposedly smarter evaluation coupled with aggressive pruning and extensions based on the evaluation.
[...]

I believe most programmers are still into it, but are very wise also, they attempt to add knowledge but verify it thru actual game tests.
Also popular is removal of existing certain eval feature that does not help strength anymore . Acceptance/rejection of test results are guided by statistics.

[hgm]

I think that engines like The Baron are still pursuing the slow searcher approach. Dumb static evaluations might have won the day for now, but this might just be a 'metastable' local optimum. It can actually be easily understood why such a local optimum does exist:

Knowledge in the static evaluation almost always goes at the expense of raw speed. So knowledge that in principle is useful, and could buy you an Elo point or two when measured under conditions of the same number of nodes nodes per move, might be detrimental when evaluated at the same time per move. Because they slow down the nps by 2-3%, which will cost approximately 2-3 Elo, less than they were worth.

How many Elo you lose per % slowdown might actually be dependent on TC: it seems that strength increase of engines per extra ply saturates a bit as you make them think deeper. So the same % slowdown hurts you more at fast TC than at slow TC. And of course everyone nowadays evaluates their changes at ultra-fast TC. Where % slowdown translates into Elo loss even more than at slow TC.

So there is a stong incentive to eliminate in-principle-beneficial evaluation knowledge that does not pay off in terms of knowledge/slowdown. But the same slowdown that causes 3% less nps in a fast searcher, would only cause 1% slowdown in a slow searcher that already takes 3 times longer to evaluate. So if the knowledge would bring a 2-Elo improvement on a same-nodes basis, it would cause a net loss of 1 Elo in the fast searcher, but a net gain of 1 Elo in the slow searcher. In other words, it can be expected that there is a 'knowledge threshold', an below it removing any knowledge of the little that was leftover is beneficial, while above it, it would be hurtful, and in fact adding more knowledge would be beneficial. Evolutionary development with minimal changes would drive the low and fast searchers in different directions, away from each other.

The situation is very comparable to the one in biology, where bacteria are 'fast breeders', and have eleminated almost all cell structure and organization because the slowdown in growth it would cause to maintain it would not make it pay off. While there are also eukariotic beings with much larger and versatile cells, with highly organized structure and much more robust. But alas, they grow much more slowly than the bacteria. Yet we are not bacteria...

[Michael Neish]

I haven't posted here for a long time, but have been lurking on and off over the years.

Just wondering ... is there anyone out there who is still implementing a slow, knowledgeable search paradigm in his or her program? I mean an expensive, but supposedly smarter evaluation coupled with aggressive pruning and extensions based on the evaluation.

It just appears to me (correct me if I'm wrong, but please do so politely ) that everyone, or at least everyone obvious, is doing basically the same thing with relatively minor refinements. To be brief: the best programs are fast, dumb searchers, but they compensate for their dumbness by being prodigious calculators. Evaluations are shallow and search extensions/reductions are crude, often statistically based.

This has surely been debated ad nauseum over the years, and my understanding (correct me if I'm wrong again, but I'd hate to be wrong twice in a row ) that fast searching won the argument quite a while ago in terms of raw playing strength.

But what has fast-searching got to do with AI? Aren't today's best programs just calculators, implementing a set of simple rules, albeit very fast and effectively? Wouldn't we learn more about AI, maybe even Chess, if we shifted our attention to other possibilities?

I'm being deliberately vague, since I know that prior attempts of this kind haven't managed to produce very strong programs (not to mention that my own ignorance lets me down at this point!). Now that hardware has moved on so much, maybe now is the time for a fresh look?

Opinions please.

Thanks.

Mike.

Every now and then, someone (obviously clueless) comes here, and tries to lecture a field of expert on how computer chess should be done. This is a typical manifestation of the Dunning-Kruger effect.

I'm not even going to argue on the "points" made above, because they are far to vague and simplistic to even be considered.

The "argument" is always the same: we should replace brute force search by knowledgeable eval, which is a completely void argument that shows zero understanding of the subject. My answer is this: DO IT YOURSELF, and THEN you will understand.

We can discuss this ad nauseam, but it is pointless, because you will never learn anything except by experimenting yourself.

I don't believe that my post deserved the arrogant reply that you have posted.

You are no one and nothing to judge just how clueless I am about Chess or Chess programming. However, it is clear from your reply that you are clueless about how to interact reasonably with another human being. I'd suggest more time away from your computer and more time trying to be sociable. It would do you a lot of good.

I was not attempting to lecture anyone on how to program a Chess computer. I was making a few suggestions to get some reasonable debate under way on the subject, which of course I am free to do, since this is an open forum. Some people have the luxury of being to try things out for themselves (i.e. time), and most don't, because they have other more important issues in their lives.

To the others, thanks for your time. I may repost after reading your replies more carefully.

[jdart]

I agree. The eval function is the largest single time consumer in my program, and always has been.

But search is important because static evaluation of threats and tactical opportunities is not really possible w/o search. You can do a sort of halfway job of it but to get deep tactics in general you need deep search.

There are a few programs that take a different and more purely knowledge-based approach. This one for example: http://www.vanheusden.com/pos/ - but it is not very strong.

--Jon

[Uri Blass]

I do not think that you can describe pos as a knowledge based program.

pos is an extremely weak program and every serious chess program has more knowledge than pos.

Here is a game of pos from your link against a crippled version of gnu chess.


[pgn][Event "Pos versus GNU Chess"]
[Site "?"]
[Date "2008.03.25"]
[Round "1"]
[White "Pos"]
[Black "GNU Chess"]
[Result "1-0"]
[ECO "A00"]
[Opening "Polish (Sokolsky-Orangutan) Opening"]
[Variation "Bugayev Attack, 1...e5 2.Bb2 f6 3.a3"]
[TimeControl "7200+30"]
[Termination "normal"]
[PlyCount "71"]
[WhiteType "human"]
[BlackType "human"]

1. h3 e5 2. c3 Nc6 3. Qc2 Nf6 4. f3 Bc5 5. Qd3 d6 6. h4 h5 7. e3 a5 8. Be2
Ke7 9. Rh2 g6 10. g3 Bf5 11. b4 Bxd3 12. Bxd3 axb4 13. Bc4 Nd7 14. Ke2 f6
15. Rh3 b6 16. Bd5 Ndb8 17. Be4 Kf7 18. Kd3 d5 19. Bb2 bxc3 20. Bxc3 Rh6
21. Kc2 dxe4 22. fxe4 Qh8 23. a4 Nd7 24. d3 Bxe3 25. Ra2 Bxg1 26. Ra3 Rf8
27. Rh1 Be3 28. Rh2 Ke6 29. Kb3 Na7 30. Kc4 Qg7 31. Raa2 Rh7 32. Bb4 Rf7
33. Kc3 g5 34. Kb2 Bg1 35. d4 Bxh2 36. d5# 1-0

[/pgn]

A fast searcher may rely on search to find that 11.b4 is losing the queen.
knowledge based program may use static evaluation to find that 11.b4 is losing the queen but usually I can expect them to do search to see clearly more complicated tactics even if they search smaller trees.

It seems that pos does not use search and does not use a serious evaluation.
Good evaluation could tell it without search to play e4 or d4 or Nf3 in the opening and not 1.h3 2.c3 3.Qc2 4.f3 5.Qd3 and it seems that pos does not have a simple positional knowledge that all the serious fast searchers have.

[Michael Neish]

I agree. The eval function is the largest single time consumer in my program, and always has been.

But search is important because static evaluation of threats and tactical opportunities is not really possible w/o search. You can do a sort of halfway job of it but to get deep tactics in general you need deep search.

There are a few programs that take a different and more purely knowledge-based approach. This one for example: http://www.vanheusden.com/pos/ - but it is not very strong.

--Jon

My intimation (not even an idea) was that Eval() may be made sharp enough to recognise when a deeper search may be necessary or not. Of course it is the job of Quiesce() or an SEE to take into account any simple capture sequences so that an evaluation is meaningful, but I wonder whether a smarter Eval() could be called at the leaves before Quiesce() that may (more cheaply and accurately) decide whether to stand pat or not, or whether to investigate certain capture sequences, or some other simple tactics.

There would have to be a pay-off in doing this. The slower Eval() would obviously have to result in fewer nodes searched in Quiesce() to make it worthwhile.

But this must have been tried, surely, as well as calling a smart Eval() at every node to guide the search more intelligently, the idea being that although NPS would be bogged down significantly, this would be compensated by a reduction in total nodes searched.

This is the concept that I'm working on at the moment, as well as jumping in and out of search directly from Eval(). But on the few minutes a day that I have for programming it will be months before I'll have anything to report, even if it's just "it's complete crap".

Thanks to H.G. (don't know your first name, although we've had a few discussions in the past) for recommending TheBaron. I was hoping it would be open source to take a peek at the code. Do you know of any open source engines, even if they are painfully weak?

Cheers.

[jdart]

It is probably worth a try.

I also forgot to mention Steven Edwards' program Symbolic (http://chessprogramming.wikispaces.com/Symbolic). I do not know much about the internals (it is not open source) but it appears to have a search significantly different from other programs and (as I understand it) also more knowledge-based. It is a reasonably strong engine.

--Jon