I wonder if people tried the following reduction idea

[Uri Blass]

1)You use 1% of your target time to get exact score for every root move at small depth.

2)After doing it make normal search when you decide about reductions based on evaluation when you reduce more plies from moves that have lower score.

for example you can reduce 1 ply for every move that has evaluation that is at least 1 pawn less than the best move.

Note that the idea can be extended by always doing search to get exact scores before doing a deep search when the exact scores can be used later for pruning.

Note that before implementing 2 you need to test that searching to get exact scores does not make the engine significantly weaker(in theory if only 1% of the time is used to get exact scores the engine should not be more than 2 elo weaker but it can be significantly weaker because the search is different and there may be some non relevant killers or hash moves).

Uri

[Don]

1)You use 1% of your target time to get exact score for every root move at small depth.

2)After doing it make normal search when you decide about reductions based on evaluation when you reduce more plies from moves that have lower score.

for example you can reduce 1 ply for every move that has evaluation that is at least 1 pawn less than the best move.

Note that the idea can be extended by always doing search to get exact scores before doing a deep search when the exact scores can be used later for pruning.

Note that before implementing 2 you need to test that searching to get exact scores does not make the engine significantly weaker(in theory if only 1% of the time is used to get exact scores the engine should not be more than 2 elo weaker but it can be significantly weaker because the search is different and there may be some non relevant killers or hash moves).

Uri

In principle LMR already accomplishes this tapering idea. My own program reduces 1, 2 or 3 ply but not by score as you suggest. I have a lot of conditions on which moves should be considered tactically interesting but beyond that it reduces moves based on their position in the move list - moves near the end of the list (at all depths) get more reductions. I don't push it beyond r=3 and in most cases only a few moves would get reduced by 3.

I have not had any success reducing beyond r=3 and the principle of LMR seems to be to that the more moves you try at a particular node, the more confidence you have that the remaining moves are nonsense.

The score at the root at a pretty shallow depth of course is not that reliable, but nothing would surprise me, LMR itself seems rather dicey to me also, but it works amazingly well in my program.

[Eelco de Groot]

1)You use 1% of your target time to get exact score for every root move at small depth.

2)After doing it make normal search when you decide about reductions based on evaluation when you reduce more plies from moves that have lower score.

for example you can reduce 1 ply for every move that has evaluation that is at least 1 pawn less than the best move.

Note that the idea can be extended by always doing search to get exact scores before doing a deep search when the exact scores can be used later for pruning.

Note that before implementing 2 you need to test that searching to get exact scores does not make the engine significantly weaker(in theory if only 1% of the time is used to get exact scores the engine should not be more than 2 elo weaker but it can be significantly weaker because the search is different and there may be some non relevant killers or hash moves).

Uri

Hello Uri,

I think it is not a bad idea. It probably isn't anywhere new, in a basic form Ed Schröder has described something that is essentially the same, but his exact searches in Rebel are from what Ed described really very short, exact fixed-plydepth searches. At least what I remember right now, I really have not studied the Rebel pages but that is what I remember from some of Ed's posts. Having some exact scores of course helps.

Why don't you try it out in Movei ? It is much more fun to actually do the experiment. And it really is the only way to learn. Besides, what you propose is really easy to implement, you can do experiments in an open source engine easily, if you did not already have a program of your own.

With a proposed 1% of your target time, the exact searches will also be rather short, a bit deeper than in Rebel, -was that a 2 ply exact search?-, but I do not think you have to be so conservative here. I have a hypothesis that, as long as the exact search can use info from the null-window searches, but remains a bit shallower, you profit from internal iterative deepening-like effects that Harm-Geert has often described here; much of the information from null-window searches that can use transposition table look-ups is hopefully already there to be re-used, if you settle for this slightly lower depth.

For the moment I'm assuming that PV-searches do not use TT look-ups (not in PV-nodes, not in Glaurung and Fruit) so the effect of having this transposition table information is limited in "PV-nodes". They are not "real" PV-nodes in your idea because you are searching the non-PV rootmoves. But you need not be too strict here also, these are not the main PV-search for your so far best rootmove so why not use TT look-ups here? Many variations are possible, this I have not tried yet.

It is difficult to say what are the benefits offset against the costs, but I think the idea is viable enough. When you look at the sources for Ancalagon, when they become available, they are not at the moment but I'm sure at some point it will be released, you will find that much of Ancalagon's root_search() revolves around this idea But I must admit I had not really thought through that this really means that I should have an exact score for every rootmove, that I could at least use for things like root-move ordering I have to thank you for pointing that out to me Uri!

At the moment I am using the PV-searches in other moves at the root for other purposes -other than using the exact scores as you proposed Uri-, like trying to avoiding some of the Zugzwang effects of null-move (null-move is not allowed in PV-nodes, at least not in Glaurung and Fruit). I am not 100% sure it is effective but it does not seem to hurt much either.

Testing everything is beyond my hardware capabilities and certainly beyond my programming capabilities. I am just happy by doing things a bit differently in Ancalagon

Regards,
Eelco

[Uri Blass]

I remember trying something similiar in movei and the additional nodes in the additional searches were not the problem.

The problem was that even without counting the nodes in the additional search and without reductions the program needed more nodes to get to the same depth and it seems that the additional nodes simply destroyed the order of moves later.

It is probably possible to prevent this problem but I decided that it is too complicated for me to work about it.

Uri

[Eelco de Groot]

It is difficult to say what are the benefits offset against the costs, but I think the idea is viable enough. When you look at the sources for Ancalagon, when they become available, they are not at the moment but I'm sure at some point it will be released, you will find that much of Ancalagon's root_search() revolves around this idea But I must admit I had not really thought through that this really means that I should have an exact score for every rootmove, that I could at least use for things like root-move ordering I have to thank you for pointing that out to me Uri!

I should modify this a bit, because there is one important difference in Ancalagon's rootmove PV-searches compared to Uri's idea that is that I am using everywhere Joona's aspiration windows, so if the rootmove is bad it should just fall out of the aspiration window. This means that there unfortunately is no exact score, unless I fail high against alpha but on the other hand it also makes the PV-search almost behave like a nullwindow search and that means it should be much quicker than a Multi-PV search with an open, or large, window.

It should be possible to do the searches with different, in practice just lower, aspiration windows but I fear a main problem here is that you should not change your aspiration windows too much, the alpha should not jump around too much. My proposed explanation of this is as follows; any lowering of the window makes a lot of transposition table data obsolete, but a higher window does not always mean a speed-up. At least that is a bit what I understood from some of Vas' comments a long time ago, what I interpreted as that a higher alpha, because your PV-move made a jump upwards in evaluation, should not automatically mean that all other moves should right away be tested against this different higher alpha. But I have no data about this, and I have not tried implementing anything along these lines.

Eelco

[diep]

1)You use 1% of your target time to get exact score for every root move at small depth.

Yes.

In my case Februari 1999 for a exact root scoring of every move (actually it was a parallel bug).

Average overhead: factor 6 in nodes.

That would be a lot more with todays better branching factor that Diep has.

Maybe factor 50?

In a more lossy manner i retried similar thing end 2004/start 2005
(determining a bound) for more efficient pruning.

It had same problem, the bigger the search depth the bigger the problem, as the branching factor is simply worse.

So if you would use just 1% of the system time, it means you're getting 10 ply versus your normal search gets a ply or 20-25.

So you would need to use different hashtables. You will be able to understand that a 10 ply search doesn't compare to 20 ply very well.

Doing statements based upon a 10 ply search on iteration 21 is no good idea.

2)After doing it make normal search when you decide about reductions based on evaluation when you reduce more plies from moves that have lower score.

for example you can reduce 1 ply for every move that has evaluation that is at least 1 pawn less than the best move.

Note that the idea can be extended by always doing search to get exact scores before doing a deep search when the exact scores can be used later for pruning.

Note that before implementing 2 you need to test that searching to get exact scores does not make the engine significantly weaker(in theory if only 1% of the time is used to get exact scores the engine should not be more than 2 elo weaker but it can be significantly weaker because the search is different and there may be some non relevant killers or hash moves).

Uri

In itself you can prove that the reduction idea is pretty sound in this manner, but the overhead is too big.

In the experiment 2004/2005 (which took months) i tried to use a reduced form of search to determine a bound for reduction based upon true scores.

Say for example we want to reduce everything except the best 2 moves. You can prove that there is a bound in nearly every position (99.9999999%, not 100%) such that only 2 or 3 moves are better and just reduce the rest or total ignore them (hard forward pruning).

The idea is similar to what you describe above. The overhead to determine those bounds is too big.

Once your aim is to search every move 18+ ply,
it is very easy to mess up your branching factor.

If you look for example to parsos from Rudolf Huber, arguably worlds best MTD program, you also see it has a HUGE WORST CASE in search depth.

Most moves for example it reaches some huge depth then 1 or 2 moves a game it gets like 13 ply as it misguessed its MTD window.

Everything is about your worst case performance and once you mess with the window that tends to be very bad.

Similarly singular extensions of Diep are extremely expensive at todays search depths. I plan to get rid of them.

Vincent

[diep]

Oh small note on the reductions and actual true scoring of them.

You not only need to do this for the actual principal variation that each move gets from root, but basically to reduce in a sound manner you need to do it for every position.

There is something like multicut which uses a similar idea but then for positoins >= beta.

For reductions we use positions < alfa in this case (actually <= alfa but well...).

Now there is 2 types of moves we don't want to miss:

1) determining which say 2 or 3 moves are the best with a reduced search
idea: what is great with a reduced search might be great in a big
search also.
2) determining which moves help us build up a long term thread towards
the opponent. say a move like Rf8-b8 to build up a mating attack at
whites kingside - remember that move Uri? Such moves are difficult for
reducers as they build up a thread but at the reduced search depth you
don't see it yet and reducing all those lines will cut like 10 ply out of
the total line length which hurts BIGTIME. Hashtables do that cutting job
in a manner that you seemingly search plies deeper with reductions,
yet in reality you're missing everything. To use a dutch saying:
"Dumping the child with the bathing water".

Realize the whole discussion above is just about type 1 moves here.

The reason why you're interested in that right now is because nearly all deep searching engines are using some sort of reduction system, be it LMR type based or the more dubious multicut type reductions (hydra , shredder etc). If you manage to slightly improve your type 1 moves, you already kick the hell out of them - see Rybka 3.0 vs 2.3.2 - yet it doesn't solve type 2 moves.

Type 2 moves are a much bigger worry actually if you want to win games that is based upon ATTACK, rather than passive defense what happens now with the beancounter systems.

Everything is just getting more and more optimized for defense right now.

I believe in Zhukov type warfare. Line up everything wheel to wheel, start shooting at that king position until the barrels of all guns overheat and you just total overwhelm that king position. I believe that Kasparov type style of playing is objectively best.

Also it is better for your health this style of playing IMHO. When i was young and had to win games a tad more based upon defending in accurate manner, just like chess engines are so good at, an IM (i'll try remember who it was) asked me: "how strong is your heart?". As that manner of playing would not very sound.

Yet the current evaluations lack chessknowledge and the search systems all miss type 2 moves too much, which actually at todays search depths you can see as positional moves but also as short term strategic moves.

Nothing is as complicated as setting up a good attack, yet it really looks cool when you carry it out.

Vincent

[Uri Blass]

I think that with a special hash tables(something that I did not try) the idea can be used also for better order of moves.

The point is about cases when the hash move is different between the big hash and the small hash.

An extreme example is when the small hash gives an exact score of mate when the big hash gives a different move and in this case it can be even used for safe pruning but even without exact score of mate it may be better to use the small hash in case of a significant material winning move that is not in the big hash.

[diep]

I think that with a special hash tables(something that I did not try) the idea can be used also for better order of moves.

The point is about cases when the hash move is different between the big hash and the small hash.

An extreme example is when the small hash gives an exact score of mate when the big hash gives a different move and in this case it can be even used for safe pruning but even without exact score of mate it may be better to use the small hash in case of a significant material winning move that is not in the big hash.

Yes mates is important in testsets. I know Kallisto for example used a special mate killer for killertables already since start 90s.

I tested it extensively and concluded it easily could speedup factor 2 for testsets, which was like 150 elopoints handsdown in most testsets.

However when i averaged over another hundreds of positions where there was difficult positions in opening/middlegame but not a 'trick to find',
it was losing nodes.

It is all about what you want to optimize for of course

Vincent