Hard pruning history

[BB+]

Michael Sherwin indicates that he may have spoken about the idea of "hard pruning" in Romi prior to its appearance in Toga. I searched through all the CCC posts of 2005 and those of 2006 up to March 8 (when Dann Corbit's archive ends, conveniently the same as when the Toga II 1.2 appeared), and found only about a dozen posts from him in February 2006, none of which mention any pruning. There are some posts about pruning, but I don't see any responses by him. However, the messages are not the easiest to sort out in their current form (one per file).

As I said in the first post, I simply remembered that Toga used this, and made no claim that it was the first to do it. In any event, many ideas are discovered multiple times.

The pruning thread started with Frank Phillips on Feb 27 2006 (message #489978) saying "I kept hearing about history pruning during CCT8, which is new to me." Tord made the web-blurb http://www.glaurungchess.com/lmr.html . VR commented: For me, the terms "pruning" and "reducing" are interchangeable. I'd guess most CC programmers agree with this - for example, we have null move pruning --- though this is most of what the dispute between LMR and LMP is here, and both Ballicora and Hyatt found fault with VR's semantics.

It seems that Miguel Ballicora (message #490051) was the first to mention LMP per se, and indeed perhaps even 5 years before 2006 he tried it, and he gives credit to Bob Hyatt.

Code: Select all

From: Miguel A. Ballicora
Message Number: 490051
Date: February 27, 2006 at 11:51:09

I was away from CC 3 years and I was wondering what this technique was. Thanks for the explanation, it was pretty clear.
Unfortunately, I tried this ~5 years ago in several ways and it did not work . It was not my idea, it was Bob Hyatt's here at CCC. I still have in my code this ancient lines (nodecount is moves searched):

                #if 0
                /* BH's suggestion, modified */
                if (nodecount == 15 && depth == 1) {
                        break;
                }
                #endif

                #if 0
                /* BH's suggestion */
                if (nodecount == 15 && depth == 2) {
                        depth--;
                }
                #endif

                #if 0
                /* BH's suggestion, modified */
                if (nodecount == 15 && prun_cand ) {
                        break;
                }
                #endif
Considering that after moves 15 the order in my case is determined by history heuristics, one the options literally was history pruning, and I tried reductions too. The tree decreased but my engine (gaviota) played terrible. Maybe I should give it a try again. As you can see, the implementation was too raw.

Miguel

Tord commented on this, and then VR went so far as to call this "Shannon B-type" as it were.

That's one difference. The really big difference was the "if (nodecount == 15) break;". That's Shannon B-type search!

Vas

Note the "nodecount == 15" and particularly the "break", where the latter makes this LMP rather than LMR.

[hyatt]

For the record, it was not "my idea". As I previously mentioned, Bruce Moreland caused me to test the LMR / LMP type ideas in Crafty. But at the time, it was _purely_ "L" as in "Late" with no regard to other dynamic considerations (checks, etc). As far as the LMP idea goes, It was simply a common idea in the 60's and 70's until Slate/Atkin went back to brute-force. Back then, everyone used the term "plausible move generator" which was a mythical "black box" that somehow generated moves in some sort of "plausible" order. That is, you would somehow generate moves that a reasonable player might actually choose, before you generated moves that nobody would play. Obviously, easier said than implemented...

I'm experimenting with the "L" stuff once again, working to find ways to better order the moves, without slowing the program down. But testing is slow. You can tweak the ordering, and incur more cost. But with better ordering, you can reduce or prune more, gaining speed back. It takes some time to determine if there is a "sweet spot" for a particular ordering idea, since testing the reduction/pruning values produces a combinatorial explosion of test cases.

[thorstenczub]

)

Chess Champion Mark V by Mark Taylor+David Levy from 1981 Championship winner in travemuende was B-Strategy on a 6502 with 1 or 2 mhz.

successor program called Cyrus68000 was later sold in CXG Sphinx40/50 and had to play against
Richard Langs Mephisto Roma .

While Mark V was very good at that time, the Sphinx40/50 (Cyrus68000) had no chance against Richard Langs asymmetric search ideas.

i wonder how we have to call Thomas Nitsches 3 stage search into this context.

Thomas Nitsches search of Mephisto III had 3 stages:

MEPHISTO 3 unterteilt den Entscheidungsbaum in 3 Abschnitte

* Utopische Züge (gut, falls der Gegner nichts tut):

Eine Stellung kommt in einer Tiefe von etwa 1-3 vor. Der Beginn einer Kombination. Fast jeder irgendwie erfolgversprechende Zug wird selektiert, auch wenn die Wahrscheinlichkeit des Erfolges recht gering ist. Der Mensch nennt manche dieser Züge Opfer.

* Optimistische Züge (gut, falls der Gegner nur die zweitbeste Antwort hat):

Die Kombination hat eine Tiefe von 4-8 erreicht. Nur noch Züge mit einer Trefferwahrscheinlichkeit von größer als 30% werden selektiert. I.A. sind dies Züge, bei denen hohe Figuren angegriffen werden, Schach gedroht wird, etc. Diese Züge sollen aber selbst nichts opfern.

* Realistische Züge (gut, falls der Gegner den besten Gegenzug wählt):

Die Stellung kommt in einer Tiefe größer als 8 vor. Nur noch klare Abwicklungen werden untersucht. D.h. das Programm greift nicht mehr auf Verdacht an, sondern verfolgt Züge mit hoher Trefferrate. Etwa eine angegriffene Figur in Sicherheit bringen, d.h. realisieren, daß die Figur auch wirklich sicher ist und nicht etwa gefesselt oder überlastet ist.

utopic moves, optimistic moves, realistic moves.

it was so much pruning in these ideas, that mephisto III played a move with only 1-2 NPS.
and it worked !! At these days, the novag and fidelity and mephisto and saitek machines
did arround 400-1500 NPS.

Nitsche+Henne were even capable to win a championship title (in Glasgow) with this search idea.

[ernest]

Nitsche+Henne were even capable to win a championship title (in Glasgow) with this search idea.

Yes, amazing!!!!!!!!!!!!

[mcostalba]

I don't understand how something "obvious" as search only a subset of a node's moves at low depths or search with different depths the node moves could be called an idea and even dispute who was the first !

Null search that's an "idea" but hard pruning and LMR are really obvious to me: their difficult is in the implemetation and in particular in fine tuning them because although underlying idea is trivial, make them to work is not.

[mjlef]

When Richard Lang's programs were king there was speculation they worked via a tapered qsearch. The reported depth was correct, but the qsearch included moves other an checks and captures, and that part fot he search was tapered. I am not sure if anyone dissassembled it or if Richard ever revealed much about it. This could be considered hard pruning.

[thorstenczub]

as far as i understand it, he wrote his engine in machine code, used SEE (static exchange evaluator) and an asymmetric search (plies 1-3-5-7-9... only few best moves, plies 2-4-6-8-... almost ALL moves have been considered). This made his program look very deep.
but on the other hand created a very solid (and some say boring) playing style. Reason was that his program did not ALWAYS found the best moves in ply 1-3-5... while it saw all threads against him .

when null move was established, this asymmetric search was outsearched by symmetric null move programs such as fritz/frans morsch and nimzo/chrilly donninger.
suddenly nullmove was a big thing in all programs.


IMO also colossus chess by martin bryant was very early with nullmove.

But IMO Thomas Nitsche and Elmar Henne had nullmove and SEE in Mephisto III too in 1983.
AND extreme forward pruning (in a 3 stages search [utopic/optimistic/realistic search stage]).
when normal dedicated chess computers made 400-1500 NPS in 1984, Mephisto III 8 bit only did 1-3 NPS and the 68000 version did 4-10 NPS.

the forward pruning was so effective, that although only doing 1-3 NPS, Mephisto III was capable to win 1984 in Glasgow against the fast searchers.

here the commercial 8 bit MMI module (32KB ROM, 4 KB RAM, 8 mhz CPU) :


We never got any other commercial chess program that made so few NPS.
IMO Mephisto III realized in the so called MMI module for H+G was a clear A.I.
aproach.
a commercial A.I. module.

the 1-3 NPS came very close to the amount of positions a human beeing is capable to compute.
its a pity those ideas did not make it onto the PC level.
the idea to see the whole search tree printed out on a single piece of paper,
and beeing able to understand why the program did which move, is IMO a big
advantage. if you have a program that is doing millions of NPS, you have almost no
idea what the program is doing in the search process.
with Mephisto III one could replay all nodes !
And understand the mistakes in the programs search.



btw:
chris whittington also used tapered forward pruning.



in 1984 the fast searchers outplayed the selective programs.
Novag constellation / superconstellation and several Ulf Rathsmann clones
sold by novag and mephisto and Conchess were very good in tactics, generated many NPS
made it difficult for the selective programs.

in 1985 Hegener+Glaser changed horses. they "fired" Thomas Nitsche and Elmar Henne and took Richard Lang and his 16bit 68000 machines.

he would dominate for long time.

but later ed schroeder and frans morsch from netherlands gave richard a tough fight.
while ed schröder had a positional program, that was later also very good in tactics, but selective,
frans morsch concentrated on search and preprocessing ideas.
I was at the championship 1986 in cologne when Ed Schröder appeared with his Rebel
and nearly won the championship...

[thorstenczub]

in those days you could test the asymmetry in richard langs programs with test positions.
e.g. karpov-topalov
rqr3k1/3Qbp2/p1n1p1p1/1pp5/2P2P2/2N3P1/PP3PB1/R3R1K1 w - - 0 1

Hardware in those days was 400 mhz ... maybe AMD K6-2/3 with 400 mhz or Pentium II with 400 mhz.

Code: Select all

Fritz7.0.0.8                                            00:00 
Hiarcs8                                                  00:05
CSTal2.03                                             01:29
Shredder6 Paderborn                         19:30
Genius3                                    not in 30:00
Genius4                                    not in 30:00
Genius 6.5                                not in 30:00

As you can see, genius 3 or 4 or even 6.5 could not solve 1.Rxe6 within 30 minutes. others could.

Now take the position ONE move shifted, take back Rc8 :

rq3rk1/3Qbp2/p1n1p1p1/1pp5/2P2P2/2N3P1/PP3PB1/R3R1K1 w - -

here first has to be moved Rc8 and then Rxe6, so Rxe6 is to be found with
the 2-4-6-8... search.

Suddenly Genius can find it, as the main lines show...

printout of Genius6.5 pc-programs main-lines:

Code: Select all

00:00 5-17  990           -0.84  Tc8 cxb5 Ta7 Dd3 Sd4 a4 Lf6 Tad1 Db6
00:05 6-18 1116903   -0.84  Tc8 cxb5 Ta7 Dd3 Sd4 a4 Lf6 Tad1 Db6
00:36 7-19  6213488  -1.15  Tc8 Txe6 Ta7 Txg6+fxg6 De6+ Kg7 Lxc6 Lf6 cxb5 Th8 Td1
02:05 8-20  22337693  -1.15  Tc8 Txe6 Ta7 Txg6+fxg6 De6+ Kg7 Lxc6 Lf6 cxb5 Th8 Td1
07:29 9-21  77904531  -1.15  Tc8 Txe6 Ta7 Txg6+fxg6 De6+ Kg7 Lxc6 Lf6 cxb5 Th8

Chess System Tal pruned the opposite way then Genius.
it pruned the opponent plies heavier than the own plies !

so CSTAL often did not consider to take back the sacs it was planning.

[BB+]

I don't understand how something "obvious" as search only a subset of a node's moves at low depths or search with different depths the node moves could be called an idea and even dispute who was the first !

For a chess player, I agree it is obvious. But from someone whose background is computer science and game-tree search, perhaps it is not. Which group has (historically) been more active in the development of computer chess?

[tom]

in those days you could test the asymmetry in richard langs programs with test positions.
e.g. karpov-topalov
rqr3k1/3Qbp2/p1n1p1p1/1pp5/2P2P2/2N3P1/PP3PB1/R3R1K1 w - - 0 1

It would be interesting to understand if any of these "old" asymmetric algorithms would work in the frameworks in use today (nullmove, lmr etc.)

Could it be another area to "mine"?