late move pruning vs. reductions

[jdart]

I have noticed that one difference between Fruit and Toga is that Fruit does late-move reductions (searches them with lowered depth) while Toga actually does pruning (does not search the moves at all). Pruning has a fairly dramatic effect on tree size and causes Toga to reach high depths quickly. Toga also solves some tactical problems faster than Fruit. But pruning is more risky and I would be surprised if it did not cause problems in some positions. Any comments on this? Anyone else tried pruning?

[Tord Romstad]

I have noticed that one difference between Fruit and Toga is that Fruit does late-move reductions (searches them with lowered depth) while Toga actually does pruning (does not search the moves at all). Pruning has a fairly dramatic effect on tree size and causes Toga to reach high depths quickly. Toga also solves some tactical problems faster than Fruit. But pruning is more risky and I would be surprised if it did not cause problems in some positions. Any comments on this? Anyone else tried pruning?

If I understand it correctly, I have been doing precisely what you describe for a couple of years now. In the last few plies of the main search, I search all captures, checks and passed pawn pushes, all moves with the piece that was captured by the null move refutation at the current node, and the first few moves. All remaining moves are pruned, unless they have particularly good statistics.

Risky? This depends on your point of view, I think. It is far less precise than a full-width search, but also far more precise than a quiescence search. I regard it as an intermediate phase between the main search and the quiescence search. I don't see any obvious reason why a gradual transition to the quiescence search should be more dangerous or less sound than a sharp limit when depth==0.

This kind of pruning appears to have been popular back in the days before recursive null move pruning became common, but is not quite as wide-spread today. My experience is that it still works quite well.

Tord

[Uri Blass]

I have noticed that one difference between Fruit and Toga is that Fruit does late-move reductions (searches them with lowered depth) while Toga actually does pruning (does not search the moves at all). Pruning has a fairly dramatic effect on tree size and causes Toga to reach high depths quickly. Toga also solves some tactical problems faster than Fruit. But pruning is more risky and I would be surprised if it did not cause problems in some positions. Any comments on this? Anyone else tried pruning?

I do not see why pruning is risky.
We are only talking about pruning when the remaining depth is small so there is no risk that toga will never see something regardless of depth.

I think that not pruning is risky and programs that do not prune take the risk of being outsearched by the opponent.

Movei does pruning based on evaluation and other factors for some years and it seems to me an obvious decision.

Uri

[jdart]

I think that not pruning is risky and programs that do not prune take the risk of being outsearched by the opponent.

I haven't done testing myself but last I checked Toga and Fruit were pretty close in rating lists like CEGT. Both do futility pruning (as does Arasan) but only Toga does late move pruning.

--Jon

[Uri Blass]

I think that not pruning is risky and programs that do not prune take the risk of being outsearched by the opponent.

I haven't done testing myself but last I checked Toga and Fruit were pretty close in rating lists like CEGT. Both do futility pruning (as does Arasan) but only Toga does late move pruning.

--Jon

Toga is clearly stronger than fruit2.1 and if you talk about later fruits then they are not free source code.

Uri

[Dann Corbit]

I think that not pruning is risky and programs that do not prune take the risk of being outsearched by the opponent.

I haven't done testing myself but last I checked Toga and Fruit were pretty close in rating lists like CEGT. Both do futility pruning (as does Arasan) but only Toga does late move pruning.

--Jon

Toga is clearly stronger than fruit2.1 and if you talk about later fruits then they are not free source code.

Uri

Seems about 100 Elo:
From:
http://www.husvankempen.de/nunn/40_40%2 ... liste.html

no Program Elo + - Games Score Av.Op. Draws
...
58 Toga II 1.3.4 egbb 2830 16 16 1129 47.8% 2845 38.9%
...
133 Fruit 2.1 2717 10 10 2912 59.1% 2653 34.1%

From:
http://computerchess.org.uk/ccrl/4040/r ... t_all.html

Rank Name Rating Score Average Opponent Draws Games LOS
...
Toga II 1.3.1 2897 +12 -12 49.3% +2.6 41.7% 2263
...
Fruit 2.1 2798 +37 -36 59.9% -75.0 37.5% 248

[jdart]

Seems about 100 Elo

Ok, I stand corrected. I guess this technique is worth a try. I am still a bit reluctant to trust it - it looks too much like Shannon Type B - but I can't argue with the results.

--Jon

[Dann Corbit]

Seems about 100 Elo

Ok, I stand corrected. I guess this technique is worth a try. I am still a bit reluctant to trust it - it looks too much like Shannon Type B - but I can't argue with the results.

--Jon

If you look at the actual implementations of it, you will see that the successful ones are "quite fiddly" in that they spend a great deal of time figuring out exceptions to the rules.

[diep]

I have noticed that one difference between Fruit and Toga is that Fruit does late-move reductions (searches them with lowered depth) while Toga actually does pruning (does not search the moves at all). Pruning has a fairly dramatic effect on tree size and causes Toga to reach high depths quickly. Toga also solves some tactical problems faster than Fruit. But pruning is more risky and I would be surprised if it did not cause problems in some positions. Any comments on this? Anyone else tried pruning?

If I understand it correctly, I have been doing precisely what you describe for a couple of years now. In the last few plies of the main search, I search all captures, checks and passed pawn pushes, all moves with the piece that was captured by the null move refutation at the current node, and the first few moves. All remaining moves are pruned, unless they have particularly good statistics.

Risky? This depends on your point of view, I think. It is far less precise than a full-width search, but also far more precise than a quiescence search. I regard it as an intermediate phase between the main search and the quiescence search. I don't see any obvious reason why a gradual transition to the quiescence search should be more dangerous or less sound than a sharp limit when depth==0.

This kind of pruning appears to have been popular back in the days before recursive null move pruning became common, but is not quite as wide-spread today. My experience is that it still works quite well.

Tord

I'm under the impression that the evaluation function has a more dramatic say regarding what you should do last few plies in search, than anything else in the program.

In case your evaluation is mainly material based, with near to no other eval parameters such as Glaurung, it is a rather good idea to prune last few plies IMHO.

If on other hand the programs main concerns are also heavy mobility and a lot of positional factors, then from testing 1000 games at slower time controls at around 2 hours in 40 moves (yes that took the system time of around 32 computers a few years ago from Jan Louwman) i could prove very hard that for Diep this approach wasn't working.

Experiment done: 2001
executing tester: Jan Louwman
total machines in action (minimum) : 30
total machines in action (maximum) : 34
average number of machines : 32

The slower machines played time controls of up to 12 hours a game a machine.

opponents: about 10 different programs, world top from those days.

statistical outcome. With 99.9% sureness i could prove that just material based pruning last 3 plies is not working for Diep.

Average searchdepth win of those 3 plies pruning: 2 ply

IMHO most experimetns fail because they test at search depths of < 14 ply. As soon as you get that 12-14 ply without tactical pruning last 3 plies, then the world image changes bigtime.

that is, 12-14 ply without reductions. With reductions that's more like 17-19 ply.

Note that this experiment says NOTHING about reductions (be it history pruning, LMR or what we called back in the 90s reductions in general).

Vincent

[Uri Blass]

I have noticed that one difference between Fruit and Toga is that Fruit does late-move reductions (searches them with lowered depth) while Toga actually does pruning (does not search the moves at all). Pruning has a fairly dramatic effect on tree size and causes Toga to reach high depths quickly. Toga also solves some tactical problems faster than Fruit. But pruning is more risky and I would be surprised if it did not cause problems in some positions. Any comments on this? Anyone else tried pruning?

If I understand it correctly, I have been doing precisely what you describe for a couple of years now. In the last few plies of the main search, I search all captures, checks and passed pawn pushes, all moves with the piece that was captured by the null move refutation at the current node, and the first few moves. All remaining moves are pruned, unless they have particularly good statistics.

Risky? This depends on your point of view, I think. It is far less precise than a full-width search, but also far more precise than a quiescence search. I regard it as an intermediate phase between the main search and the quiescence search. I don't see any obvious reason why a gradual transition to the quiescence search should be more dangerous or less sound than a sharp limit when depth==0.

This kind of pruning appears to have been popular back in the days before recursive null move pruning became common, but is not quite as wide-spread today. My experience is that it still works quite well.

Tord

I'm under the impression that the evaluation function has a more dramatic say regarding what you should do last few plies in search, than anything else in the program.

In case your evaluation is mainly material based, with near to no other eval parameters such as Glaurung, it is a rather good idea to prune last few plies IMHO.

If on other hand the programs main concerns are also heavy mobility and a lot of positional factors, then from testing 1000 games at slower time controls at around 2 hours in 40 moves (yes that took the system time of around 32 computers a few years ago from Jan Louwman) i could prove very hard that for Diep this approach wasn't working.

Experiment done: 2001
executing tester: Jan Louwman
total machines in action (minimum) : 30
total machines in action (maximum) : 34
average number of machines : 32

The slower machines played time controls of up to 12 hours a game a machine.

opponents: about 10 different programs, world top from those days.

statistical outcome. With 99.9% sureness i could prove that just material based pruning last 3 plies is not working for Diep.

Average searchdepth win of those 3 plies pruning: 2 ply

IMHO most experimetns fail because they test at search depths of < 14 ply. As soon as you get that 12-14 ply without tactical pruning last 3 plies, then the world image changes bigtime.

that is, 12-14 ply without reductions. With reductions that's more like 17-19 ply.

Note that this experiment says NOTHING about reductions (be it history pruning, LMR or what we called back in the 90s reductions in general).

Vincent

Tord did not talk about material based pruning.
He described what he did and I think that you did not do the same:

Here are the words of Tord again:

" In the last few plies of the main search, I search all captures, checks and passed pawn pushes, all moves with the piece that was captured by the null move refutation at the current node, and the first few moves. All remaining moves are pruned, unless they have particularly good statistics."

Note that I do not do exactly the same and I do something else but I also prune in the last plies.

Uri