"Automated Discovery of Search Extensions"

[BB+]

Another from the 2009 ACG: http://www.springerlink.com/content/k17t541703627435
[You can probably find some of these papers on the respective authors' websites].

Automated Discovery of Search-Extension Features
Pálmi Skowronski, Yngvi Björnsson and Mark H. M. Winands
Abstract:
One of the main challenges with selective search extensions is designing effective move categories (features). Usually, it is a manual trial-and-error task, which requires both intuition and expert human knowledge. Automating this task potentially enables the discovery of both more complex and more effective move categories. The current work introduces Gradual Focus, an algorithm for automatically discovering interesting move categories for selective search extensions. The algorithm iteratively creates new more refined move categories by combining features from an atomic feature set. Empirical data is presented for the game Breakthrough showing that Gradual Focus looks at a number of combinations that is two orders of magnitude fewer than a brute-force method does, while preserving adequate precision and recall.

[jwes]

This paper is here - http://www.ru.is/faculty/yngvi/pdf/SkowronskiBW09.pdf

[BB+]

The last sentence of the paper is the ominous: Finally, it would be interesting to explore the method in other game domains, and we have started preliminary work in chess.

One of the main difficulties seems to be that only used half-ply extensions (The features are evaluated using a fixed fractional-ply value of 0.5, chosen somewhat arbitrary although such that it is neither too conservative nor too aggressive). Furthermore, the field of computer chess is more mature than that of Breakthrough (We experiment with it in the game Breakthrough, where there
exists little knowledge of what comprises good moves to extend on), so any application to chess would probably be smaller in magnitude. They get 58% wins in 2400 games (against a control engine) from their best possible configuration of extensions, which is around 50 ELO. The paper itself is more about the efficacy of the "Gradual Focus" method in discerning features rather than per se improving the play of an engine (they discuss how fast GF found the "best" feature set, compared to a more exhaustive method of trying nearly all feature combos).

[Rebel]

One even might wonder if extensions (except maybe for checks) make sense any longer as they might bite the latest concept of LMR.

Another issue: Now that I understand this new LMR concept it's probably fair to say it was first introduced by Rybka and it became the sole reason for its dominance of the last years. But eventually the secret became known and it's now available for every chess programmer. The interesting question remains how the Rybka's secret became known. The most heard opinion is by RE. But it can also be more simple. If we go back to another breakthrough in CC, the discovery of recursive-null-move back in 1995 (or so) it was simply a voluntary leak by the inventor (Frans Morsch) himself. He told Donninger about it who then made it an article in the ICCA journal. Nowadays recursive-null-move is standard. What if Vas in a weak or open moment (unconsciously) gave away the idea? We could stop all discussion then. No cloning.

Speculation: now that the algorithm is in the open we might expect a new race. A new chance is given for the old commercial generation, Fritz, Shredder, Hiarcs. If their evaluation is better than those of Rybka, Stockfish, Ippo* then they might have a chance to take the crown again.

So 3 subjects in 1 post.

Ed

[BB+]

Another issue: Now that I understand this new LMR concept it's probably fair to say it was first introduced by Rybka

You are treading on thin ice with the attribution there. VR himself said (after I questioned him) that SMK told him that he was using almost exactly "modern" LMR already in Shredder 7 [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?pid=42410]. Tord Romstad championed the idea, and Letouzey implemented (with the history counters, which is now deemed unwise) in Fruit. My impression is that "statistical pruning" is a better word to use for what Rybka does (prune if it does well "on average" in testing, w/o really a lot of guidance as to "why" other than testing every idea you can think of, and keeping that which works).

One even might wonder if extensions (except maybe for checks) make sense any longer as they might bite the latest concept of LMR.

There was some exchange I had with Kaufman awhile back on the RF [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?pid=111191] about DeepBlue, and how Rybka compared, and I quoted from Hsu himself as to why DeepBlue didn't use null move: third, it is not clear how to incorporate singular extensions with null move pruning. they did not seem to be that compatible. though Ferret seems to suggest that it is possible. anyway, given that singular extensions are considered far more important in creating deep lines, we keep what we know. Kaufman found this to be a rather poor decision, given the known gains of null-move. My own impression was that the DB team was overly enamoured with "singular extensions", for whatever reason.

[BB+]

I might as well stick in this thread my opinions as to why Rybka was the best (some of this is word-of-mouth, rather than an actual analysis).

R1 (2920 64-bit CCRL on 1cpu). The main advantages over Fruit were bitboards (for 64-bit), slightly tuned eval, more aggressive pruning (much more than the AEL-like razoring/futility of Heinz, where at depth 3 [pre-pre-frontier] you needed to be a queen or so behind to prune), and the material evaluation table.

R1.2 (2998): fix bugs (like overuse of lazy eval due to mixing centipawn/3399 scales), more tuning with both eval and a few search parameters.

R2.3.2a (3068): more aggressive pruning all around (likely search was majorly rewritten), but also more extensions of singular moves, a lot of it learned from WinFinder experience.

R3 (3153): Kaufman's eval (I think R2.3.2a eval was close to Fruit/R1 in scope, but I'd have to check this if someone wants to dispute it), plus a better mix of pruning and singular extensions in the search.

Of course, this is just my opinion, and some cases is nothing more than a guess.

[Rebel]

You are treading on thin ice on the attribution there. VR himself said (after I questioned him) that SMK told him that he was using almost exactly "modern" LMR already in Shredder 7 [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?pid=42410]. Tord Romstad championed the idea, and Letouzey implemented (with the history counters, which is now deemed unwise) in Fruit. My impression is that "statistical pruning" is a better word to use for what Rybka does (prune if it does well "on average" in testing, w/o really a lot of guidance as to "why" other than testing every idea you can think of, and keeping that which works).

Perhaps I should have bold the word new, so: this new LMR concept. The Rybka LMR is a lot more sophisticated than the Shredder 7 even Shredder 8 LMR. Raw LMR gives already but as Rybka showed there was still a lot of potential waiting to be discovered. Perhaps still is....

BTW, I am not surprised by the Shredder / Rybka connection. In fact it strengthens my point. The history-reduction algorithm in Fruit (the forerunner of LMR so to say) was the base and beginning of the Shredder success. When it became known (Fruit sources) Shredder got serious competition. Did you know the original history-reduction algorithm idea isn't SMK? He got the idea from Rudolf Huber (SOS).

Programmers talk with each other, on tournaments in email. All these talks about RE / stolen sources / clones might find their origin in talking programmers

Ed

[mcostalba]

I would like just to thank you BB and Rebel for this contribution.

It is very rare to read about rationales and history and what is behind we commonly use today from two very knowledgeable people and with a clear historical background on chess engines.

Thanks a lot !

P.S: Bob, look at this it doesn't happen so often to read so high quality material in our forums

[Rebel]

There was some exchange I had with Kaufman awhile back on the RF [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?pid=111191] about DeepBlue, and how Rybka compared, and I quoted from Hsu himself as to why DeepBlue didn't use null move: third, it is not clear how to incorporate singular extensions with null move pruning. they did not seem to be that compatible. though Ferret seems to suggest that it is possible. anyway, given that singular extensions are considered far more important in creating deep lines, we keep what we know. Kaufman found this to be a rather poor decision, given the known gains of null-move. My own impression was that the DB team was overly enamoured with "singular extensions", for whatever reason.

Yes, yes, yes, Hsu and extensions, the more juicy the better But he did the job. Those were the days, 1997.

Back to topic, null-move was known for a very long time. Don Beal used null-move already in 1986 but in Q-search only. He explained it to me but I was deaf for it. Hsu, Hyatt and Moreland experimented with null-move. But they all missed that its strength comes from using null-move recursive through the whole tree. And this credit goes to Frans Morsch.

Ed

[Rebel]

I would like just to thank you BB and Rebel for this contribution.

It is very rare to read about rationales and history and what is behind we commonly use today from two very knowledgeable people and with a clear historical background on chess engines.

Thanks a lot !

P.S: Bob, look at this it doesn't happen so often to read so high quality material in our forums

Thanks Marco Just for clarity, you are the SF author? Please forgive my ignorance nowadays, I am catching up lately.

Our Bob of course will comment, he always does. I am not sure if he totally agrees on the historic perspective.

Ed