Time assignment to children

[lauriet]

Well Mathew,
Why not write the code and play it against Crafty for instance.
Practice trumps theory every time.

P.S.
You gotta love reading Bobs views as he usually says something like....
"well so and so tried this back in 1983 and found this.
A wise tribal elder.

[matthewlai]

Well Mathew,
Why not write the code and play it against Crafty for instance.
Practice trumps theory every time.

P.S.
You gotta love reading Bobs views as he usually says something like....
"well so and so tried this back in 1983 and found this.
A wise tribal elder.

It is being written as we speak. It takes a while because it's a pretty fundamental change to search, and I have to think about how all the old techniques should be implemented without the concept of depth.

There are also no examples to follow online (unlike everything else in computer chess), and that's pretty exciting .

[kbhearn]

Depth is still of great importance as it covers up the weaknesses of the evaluation function (some of which are not remotely easily repairable).

Let's take an imaginary tree with two interesting root moves, white to move.

Interesting root move 1 pushes a pawn and closes the position and leads to a very bushy tree where almost no moves are obviously uninteresting compared to the others, just lots of long slow maneuvres. White has a passed pawn but it is unsupported and ultimately doomed after which black will be better. Your engine considers the position as slightly better for white due to this pawn but will need depth to start to realise it has to make concessions to delay its loss.

Interesting root move 2 opens the position and leads to a very narrow forcing exchange of material into a stable drawn position.

Now given equal time for move 1 and move 2 while move 2 is busy exploring shuffling pieces around in the drawn position and getting nowhere (which fair enough, it is something to be explored to be sure it really is drawn), move 1 has not even made it through to a sufficient depth to be sure its static evaluation of the position was reasonable since you're busy time-splitting amongst the very bushy tree and none of the moves make it very deep. This is what LMR tackles very well by making sure at least 1 line gets to the depth to start going 'uh oh, i can't hold that pawn' which will have a ripple effect of exploding the tree for move 1 as it tries to find a way to hold an advantage. But this is a good explosion because it's found a critical problem with its original pv which will in turn lead to switching to move 2 and taking the draw eventually.

[matthewlai]

Depth is still of great importance as it covers up the weaknesses of the evaluation function (some of which are not remotely easily repairable).

Let's take an imaginary tree with two interesting root moves, white to move.

Interesting root move 1 pushes a pawn and closes the position and leads to a very bushy tree where almost no moves are obviously uninteresting compared to the others, just lots of long slow maneuvres. White has a passed pawn but it is unsupported and ultimately doomed after which black will be better. Your engine considers the position as slightly better for white due to this pawn but will need depth to start to realise it has to make concessions to delay its loss.

Interesting root move 2 opens the position and leads to a very narrow forcing exchange of material into a stable drawn position.

Now given equal time for move 1 and move 2 while move 2 is busy exploring shuffling pieces around in the drawn position and getting nowhere (which fair enough, it is something to be explored to be sure it really is drawn), move 1 has not even made it through to a sufficient depth to be sure its static evaluation of the position was reasonable since you're busy time-splitting amongst the very bushy tree and none of the moves make it very deep. This is what LMR tackles very well by making sure at least 1 line gets to the depth to start going 'uh oh, i can't hold that pawn' which will have a ripple effect of exploding the tree for move 1 as it tries to find a way to hold an advantage. But this is a good explosion because it's found a critical problem with its original pv which will in turn lead to switching to move 2 and taking the draw eventually.

That's an interesting point.

It essentially boils down to, when we have a position where all the moves look equally interesting, should we split up the time evenly, or should we pick one move and dive in deep. From a probabilistic perspective, I think it makes more sense to divide equally. That's the equivalent of looking at all moves with probability (of being in the PV) higher than a certain threshold.

Obviously the case you described is one where going deeper is better. However, in a parallel universe, with a very similar position, it may turn out that one of the equally-interesting-looking moves actually turn out to be very interesting in 2 plies - and we don't see it because we arbitrarily decided to go deep on another move instead. I have a feeling this is more common, but I don't have anything to support that belief.

In any case, even if we want to make sure we go deep on at least one node, it still doesn't require the concept of depth. We can do that with node budgets equally well, by arbitrarily picking one node to give it a large portion of the budget.

[bob]

I don't follow your question? I treat 'em all the same until the q-search, where there almost all of the time is spent on them.

Well, it's a followup question from our discussion earlier. Captures lead to simplifications. In a depth-limited search, less time is spent on simplifying moves. They are treated the same depth-wise, not time-wise or node-wise.

That depends. With LMR one won't spend "much more time on B, because as you step through the moves, you ramp up the reductions.

And that's what I meant when I originally said I believe the power of LMR is in the side effect of shaping the search to be more like what I proposed.

But if our goal is to achieve what I proposed, there are simpler and more theoretically sound ways than LMR (for example, using node-limited search).

LMR doesn't make sense. That has been well established. It just works because it happens to be right more often than it happens to be wrong. It's a very crude technique. It's something that doesn't work in theory but works in practice.

We have a position with 35 legal moves. 5 of them are hash moves, SEE winning captures, and killers. 5 of them are SEE losing captures or losing non-captures. We still have 25 moves left. These 25 moves are ordered pretty much randomly. How does it make any sense that we start reducing and ramp up the reduction halfway through those 25 moves?

First they are not ordered randomly. IE the history heuristic for starters. But the main key is that most everyone uses PVS. Which means you search one move or you search all moves. Once you have searched more than one, the probability of this being an ALL node increases rapidly. and if that is the case, reducing effort has no risk at all, except when move ordering breaks down and a very late move suddenly fails high unexpectedly. But since this is rare, the idea of LMR is quite sound. You can prove that for perfectly ordered trees it is just as correct as pure alpha/beta when compared to minimax. So you toss an unfair coin, and most of the time you win. But you will lose some here and there. That's LMR in a nutshell.

So to me, LMR is quite natural and sensible. Most people, given a task to do the same thing N times will find that the last instance of the task is done more quickly and more sloppily than the first. Watch someone paint on house trim for a while, and you'll see what I mean.

[wgarvin]

I have provided justification for spending equal time on each branch (vs equal depth). What are the justifications for equal depth?

1. Scores from equal depths are more likely to be directly comparable.
2. The cost of searching to depth X+1 instead of X, usually exceeds the savings from searching to depth X-1 instead of X. So to be able to search one ply deeper on some subtree in the same amount of time (or nodes), you end up having to reduce several (or many) other subtrees.

Some experiments have shown that engines seem to gain a relatively fixed amount of strength from each ply they can go deeper. So it seems to me that the tradeoff in 2. (where you shorten several subtrees in order to lengthen just one of them) would be a bad tradeoff, and searching them all to the same nominal depth makes the most sense unless you have other information about the interestingness of those lines of play, in which case you should be extending or reducing them anyway, to take advantage of it. Cue LMR.

We are ignoring "uninteresting" moves for now because that's an orthogonal issue and unrelated to the topic being discussed.

...

My hypothesis is that the power of LMR is really in its side effect of making time sharing more "fair" between narrow and wide nodes.

The "uninteresting" moves might be orthogonal to your idea about how to allocate time in the search, but I don't think you can ignore them when talking about why LMR seems to work so well.
As I argued already, I think it works so well because the "wide" nodes are full of crappy moves and LMR mostly reduces those.

I think LMR's benefits have nothing to do with making the time distribution "more fair", and everything to do with not spending huge amounts of time searching subtrees for crappy moves.

[wgarvin]

Depth is still of great importance as it covers up the weaknesses of the evaluation function (some of which are not remotely easily repairable).

Let's take an imaginary tree with two interesting root moves, white to move.

Interesting root move 1 pushes a pawn and closes the position and leads to a very bushy tree where almost no moves are obviously uninteresting compared to the others, just lots of long slow maneuvres. White has a passed pawn but it is unsupported and ultimately doomed after which black will be better. Your engine considers the position as slightly better for white due to this pawn but will need depth to start to realise it has to make concessions to delay its loss.

Interesting root move 2 opens the position and leads to a very narrow forcing exchange of material into a stable drawn position.

Now given equal time for move 1 and move 2 while move 2 is busy exploring shuffling pieces around in the drawn position and getting nowhere (which fair enough, it is something to be explored to be sure it really is drawn), move 1 has not even made it through to a sufficient depth to be sure its static evaluation of the position was reasonable since you're busy time-splitting amongst the very bushy tree and none of the moves make it very deep. This is what LMR tackles very well by making sure at least 1 line gets to the depth to start going 'uh oh, i can't hold that pawn' which will have a ripple effect of exploding the tree for move 1 as it tries to find a way to hold an advantage. But this is a good explosion because it's found a critical problem with its original pv which will in turn lead to switching to move 2 and taking the draw eventually.

That's an interesting point.

It essentially boils down to, when we have a position where all the moves look equally interesting, should we split up the time evenly, or should we pick one move and dive in deep. From a probabilistic perspective, I think it makes more sense to divide equally. That's the equivalent of looking at all moves with probability (of being in the PV) higher than a certain threshold.

Why decide before you have searched them?

If you do it the traditional way and just search each subtree to some nominal depth, one may take more nodes/time than the other. Assuming you took whatever opportunities you could see to reduce effort on "uninteresting" lines, why would that be a bad outcome?

If you insist on allocating your search effort before you know the cost of reaching depth X in each subtree, the result is going to be that some subtrees may be searched deeper than X and others shallower than X. But not for any specific reason (such as singular moves in the PV, or whatever), but just because of the general branchiness of the subtree.

If one node has 3 interesting moves, and another has 9, why should we search them to the same depth?

Let's say we have an extreme case where 1 node has 1 possible move, and the other node has 200 possible moves. If we assume the best move is equally likely to be the first node as the second node, does it make sense to spend almost no time on the first node?

It depends. If the subtree of the first is much smaller than the subtree of the second, then it would make sense...


But anyway, it sounds like an interesting experiment. Its rather different than the "typical" search style of most engines so it might be worth trying just to see what happens. Perhaps I am missing something important about the idea.

[Rein Halbersma]

This is a very high level philosophical idea about shaping the search tree.

I'm have been working on this also. What I try to do is a 3 step algorithm to expand the tree:

Step 1. Back-propagate the probability densities from the leaves (or dropout moves in my case) to the root.
1.a. For this you need to estimate/calculate the probability density function of the max of several gaussians.
1.b. At the same time you can calculate the odds that each move is the best in its own node.

Step 2. Forward-propagate the "PV likelihood" from the root towards the dropout moves using these odds.

Step 3. Select the leaf or dropout move with the highest values found in step 2 and expand those nodes. I expect you can safely expand a whole bunch of them in parallel, to avoid repeating step 1 and 2 too often.

(Then repeat from 1 until you run out of time or until the probability that the 1st root move is best exceeds a certain threshold.)

This scheme (especially the back-propagation of probalities) sounds a lot like some sort of Monte Carlo tree search. Was this a source of inspiration for you?

I figure that many of the well-known algorithms (iterative deepening, singular extensions, LMR, splitpoint selection, easy move, conspiracy search) can be seen as crude-but-fast approximations of this generic algorithm.

Monte Carlo tree search converges to the minimax search result, see e.g. this review paper.

[matthewlai]

First they are not ordered randomly. IE the history heuristic for starters.

And like you said before, history heuristic is basically random noise.

But the main key is that most everyone uses PVS. Which means you search one move or you search all moves. Once you have searched more than one, the probability of this being an ALL node increases rapidly. and if that is the case, reducing effort has no risk at all, except when move ordering breaks down and a very late move suddenly fails high unexpectedly. But since this is rare, the idea of LMR is quite sound. You can prove that for perfectly ordered trees it is just as correct as pure alpha/beta when compared to minimax. So you toss an unfair coin, and most of the time you win. But you will lose some here and there. That's LMR in a nutshell.

It doesn't change the fact that in PVS, once we run out of known good moves (hash move, killers, etc), we know very little about the rest of the moves. The 6th move and the 20th move have about the same (low) probability of failing high. Why do we search the 6th deeper than the 20th? If we want to reduce, wouldn't it make sense to reduce all these moves equally?

So to me, LMR is quite natural and sensible. Most people, given a task to do the same thing N times will find that the last instance of the task is done more quickly and more sloppily than the first. Watch someone paint on house trim for a while, and you'll see what I mean.

Yes, that's more human. But humans are bad at chess. Why are we emulating humans?

[matthewlai]

1. Scores from equal depths are more likely to be directly comparable.

That is true and it's not specific to this search method. With LMR and null-move, we are comparing scores from very different depths all the time, too. When comparing deeper scores with shallower scores, deeper scores should be scaled toward zero (to account for snowballing effect), but that's very difficult to get right.

2. The cost of searching to depth X+1 instead of X, usually exceeds the savings from searching to depth X-1 instead of X. So to be able to search one ply deeper on some subtree in the same amount of time (or nodes), you end up having to reduce several (or many) other subtrees.

Cost of search is not comparable between different subtrees. The extra cost of going X+1 vs X in a simple subtree can easily be less than the cost of going X vs X-1 in a complex subtree.

In the end, the number of leaf nodes explored will be the more or less the same (assuming constant NPS). It's only a question of where to put those leaf nodes.

Some experiments have shown that engines seem to gain a relatively fixed amount of strength from each ply they can go deeper. So it seems to me that the tradeoff in 2. (where you shorten several subtrees in order to lengthen just one of them) would be a bad tradeoff, and searching them all to the same nominal depth makes the most sense unless you have other information about the interestingness of those lines of play, in which case you should be extending or reducing them anyway, to take advantage of it. Cue LMR.

Yes, but that's comparing depths of the same (whole) tree, not depths of different subtrees.

The "uninteresting" moves might be orthogonal to your idea about how to allocate time in the search, but I don't think you can ignore them when talking about why LMR seems to work so well.
As I argued already, I think it works so well because the "wide" nodes are full of crappy moves and LMR mostly reduces those.

The problem with LMR is it reduces some of those crappy moves more than others, with no good reason. It would make more sense to reduce them all the same amount. Perhaps an amount based on how wide the node is? Cue my approach .

I think LMR's benefits have nothing to do with making the time distribution "more fair", and everything to do with not spending huge amounts of time searching subtrees for crappy moves.

I guess no one can really prove that one way or another. I'll just have to write up my approach and see what happens.