A few general questions...

[micron]

By the way, if alpha and beta are the same, it's logically inconsistent because if a score is returned that is equal to alpha AND beta then it has failed high AND it has failed low - which is illogical.

And so it is strongly recommended to put this at the top of Search() and QSearch():

Code: Select all

assert&#40; alpha < beta );

[Sven]

When I hear the word "research" does that mean to research the current root node?

Typically you do a "test search" sometime called a scout search to determine if a move is as good as the one you currently consider best. It does not have to be just the root move, it is done recursively at just about any node.

if the search fails low, you don't care and you can move on because you have "proved" that it sucks.

If the search fails high, it means that the move is BETTER than you expected and you must search it again but with a larger window. You could use infiinte here since you don't really know how good it is. Generally the score returned can be viewed as a lower bound so you can start with alpha set to that score, but beta could be anything but you might want to just search it -inf +inf until it's all debugged before getting too clever.

Let say there are 12 root moves... and we get a fail high on root move #4. So we start over our search again at move #4 resting all its children to their 1st move with the adjusted window.....correct?

Yes. Only move 4 is searched again with an adjusted window.

I think it is necessary to point out that the original question was posed in the context of PVS, not of aspiration windows as one might think. In PVS, a move [not only at the root node] that was searched with a null window but failed high is re-searched with a different (wider) window (i.e. the hypothesis that all other [root] moves are not better than the first move was refuted).

But independent from PVS (and especially without PVS, or only in that re-search mentioned above being part of PVS), you may see a root move failing high when using an aspiration window, and there you start over at the root node with a different (wider) aspiration window. Despite PVS, the latter does usually only apply at the root node.

Sven

[hgm]

But independent from PVS (and especially without PVS, or only in that re-search mentioned above being part of PVS), you may see a root move failing high when using an aspiration window, and there you start over at the root node with a different (wider) aspiration window. Despite PVS, the latter does usually only apply at the root node.

Why would you do that? If all moves you previously searched already failed low compared to a value somewhere inside your aspiration window, they will still fail low in exactly the same way when you increase beta.

Only when all moves fail low compared to your aspiration window, you would have to restart a search of all moves with a lower alpha. Because any of them could be the best.

[Sven]

But independent from PVS (and especially without PVS, or only in that re-search mentioned above being part of PVS), you may see a root move failing high when using an aspiration window, and there you start over at the root node with a different (wider) aspiration window. Despite PVS, the latter does usually only apply at the root node.

Why would you do that? If all moves you previously searched already failed low compared to a value somewhere inside your aspiration window, they will still fail low in exactly the same way when you increase beta.

Only when all moves fail low compared to your aspiration window, you would have to restart a search of all moves with a lower alpha. Because any of them could be the best.

It is correct what you say. But we were talking about failing high while you are talking about failing low. Please note also that I did not limit my statement to the PVS algorithm, I was referring to using aspiration windows in general.

Sven

[hgm]

Yes, so? Weren't you saying that one should re-search earlier (root) moves that did not fail high when a later move does fails high, in that case?

[Sven]

Yes, so? Weren't you saying that one should re-search earlier (root) moves that did not fail high when a later move does fails high, in that case?

I am not giving an advice that is somehow contrary to common practice over years. I am summarizing what everyone (perhaps except you ) has done in the past. I understand what you mean but up to now this was simply not the standard, so I wonder why you behave as if everything else than your version were fully abnormal. For instance, look at Crafty or Stockfish, they are doing it the way I mentioned. Look also into Bruce Moreland pages, CPW, or other literature. On the other hand, I could not find any strong open-source engine that uses aspiration windows the way you describe it.

Furthermore, the whole point is moot due to TT hits guiding you through the re-search of the first root moves in most cases.

And what about search instability? You re-search just the one root move that caused the fail-high, but now you get back a lower score, now which is your new best move? And how do you correctly maintain the root move list when jumping right into the middle of it in order to start the re-search?

Sven

[hgm]

I am not giving an advice that is somehow contrary to common practice over years. I am summarizing what everyone (perhaps except you ) has done in the past.

Well, that is fine, as long as we agree that it makes no sense. Remember I was _asking_ why you would do that. But in stead of answering it right away, you started claiming we were not talking about the same thing...

I understand what you mean but up to now this was simply not the standard, so I wonder why you behave as if everything else than your version were fully abnormal.

For one, none of my engines uses aspiration. I thought that technique had kind of become obsolete with PVS, where the null-window can be considered the ultimate aspiration. However, I think that everything that contradicts elementary logic had better be considered fully abnormal... At least enough for me to _inquire_ about the reason. That you equate things that I don't understand straight away as implying they must be "fully abnormal" is your own interpretation, and you cannot blame me for that. Now if you don't know the reason, but assume there is one because others do this, you can simply say so.

For instance, look at Crafty or Stockfish, they are doing it the way I mentioned. Look also into Bruce Moreland pages, CPW, or other literature. On the other hand, I could not find any strong open-source engine that uses aspiration windows the way you describe it.

Furthermore, the whole point is moot due to TT hits guiding you through the re-search of the first root moves in most cases.

Well, that remains to be seen. Some engines, for instance, use sub-tree node counts for move sorting in the next iteration. Getting a hash hit that reduces the node count to 1 would be very detrimental for that. So you would have to take special provisions again to avoid that. So it might not be very costly in terms of search time, but it could still be a lot of unnecessary extra work codewise.

And what about search instability? You re-search just the one root move that caused the fail-high, but now you get back a lower score, now which is your new best move?

Well, the one that was best before, of course. Like always. Exact scores are supposed to be more reliable than bounds, so when you get a score that contradicts the earlier fail high, you believe the exact score. And if it is lower than bestScore, there is no PV / alpha update, and it is still a fail low compared to the original window. I don't see how you could even imagine this would be problematic.

And how do you correctly maintain the root move list when jumping right into the middle of it in order to start the re-search?

I have no idea what you are talking about. How come, "jump in the middle"? You already were in the middle. Since when is searching the next move 'jumping in the middle'? You do it every move.

Re-search is for the move that failed. Not for the node that contained one move that failed. That was the entire point from the beginning.

[Don]

For one, none of my engines uses aspiration. I thought that technique had kind of become obsolete with PVS, where the null-window can be considered the ultimate aspiration.

There is still a small gain using aspiration at the root of the search. I used to think that PVS could replace aspiration completely too but we decided to try it anyway, leaving no stone un-turned in the quest for 1 or 2 more ELO.

Note that you cannot just run a couple of position to prove it helps, as any aspiration looks good in the best cases (or even in MOST cases, even if it's bad on average.) The way we test stuff like this it to run thousands of games and look at the ELO (and average depth) and in this case there was a small but unambiguous gain for using aspiration at the root.

To be honest, I hate it. PVS is clean and simple, aspiration is more complicated and has unpleasant side-effects but such is the way of high performance chess.

In Komodo's implementation I just set alpha and beta, and if the root search comes back failed, I search again from scratch with a new windows. I don't know if that is standard or not or who else does it but I would assume the other programs do it since it works.

[Sven]

I am not giving an advice that is somehow contrary to common practice over years. I am summarizing what everyone (perhaps except you ) has done in the past.

Well, that is fine, as long as we agree that it makes no sense. Remember I was _asking_ why you would do that. But in stead of answering it right away, you started claiming we were not talking about the same thing...

In my probably poor understanding of English, asking "why would you do that" as in the given context seems to imply saying "that makes no sense". Since you even confirmed that with your first sentence above I see that my understanding was not too bad ... And no, we don't agree on that, of course

I understand what you mean but up to now this was simply not the standard, so I wonder why you behave as if everything else than your version were fully abnormal.

For one, none of my engines uses aspiration. I thought that technique had kind of become obsolete with PVS, where the null-window can be considered the ultimate aspiration. However, I think that everything that contradicts elementary logic had better be considered fully abnormal... At least enough for me to _inquire_ about the reason. That you equate things that I don't understand straight away as implying they must be "fully abnormal" is your own interpretation, and you cannot blame me for that. Now if you don't know the reason, but assume there is one because others do this, you can simply say so.

You can't deny that your reaction on my remark creates a strong impression that you believed the contents of my remark to be somewhat "abnormal". Again, you are now confirming this view with your last paragraph (see bottom of this post).

Aspiration window has not become obsolete, you can easily see that when following some chess programming threads. Also take a look at Stockfish, I already mentioned it.

And yes, indeed I know a reason why people are using the "traditional" approach: it is simple, while solutions like the one you are proposing tend to create new trouble. And believe it or not: most probably you can't judge about that unless you have implemented aspiration windows in your own engine.

For instance, look at Crafty or Stockfish, they are doing it the way I mentioned. Look also into Bruce Moreland pages, CPW, or other literature. On the other hand, I could not find any strong open-source engine that uses aspiration windows the way you describe it.

Furthermore, the whole point is moot due to TT hits guiding you through the re-search of the first root moves in most cases.

Well, that remains to be seen. Some engines, for instance, use sub-tree node counts for move sorting in the next iteration. Getting a hash hit that reduces the node count to 1 would be very detrimental for that. So you would have to take special provisions again to avoid that. So it might not be very costly in terms of search time, but it could still be a lot of unnecessary extra work codewise.

Yes, the hash hit will reduce the subtree node count to 1, but only for the re-search of nodes that have already been searched with a lower beta in the same iteration. So there will be nothing detrimental, and no need to take any special provisions.

And what about search instability? You re-search just the one root move that caused the fail-high, but now you get back a lower score, now which is your new best move?

Well, the one that was best before, of course. Like always. Exact scores are supposed to be more reliable than bounds, so when you get a score that contradicts the earlier fail high, you believe the exact score. And if it is lower than bestScore, there is no PV / alpha update, and it is still a fail low compared to the original window. I don't see how you could even imagine this would be problematic.

You need to keep track of the second-best move in order to do so. And furthermore, you need to think about the semantics of the whole search at the root node. The way you see it means that you increase "beta" locally just for one move (and possibly all subsequent root moves), and you do this within the body of the root move loop. But at the root node level the search was started with a different (tighter) alpha-beta window, so you get into unnecessary trouble on semantical level: what does it mean to get back a value at root that is >= the original beta but < the new beta?

Of course it is possible to solve all that, even to get around all those issues I mentioned. But it will mess up your code, believe me.

And how do you correctly maintain the root move list when jumping right into the middle of it in order to start the re-search?

I have no idea what you are talking about. How come, "jump in the middle"? You already were in the middle. Since when is searching the next move 'jumping in the middle'? You do it every move.

The normal thing at each node is that you leave the node prematurely (cut off all remaining subtrees) whenever the best score is >= beta, and return to the calling context, which is usually the parent node but for the root is the iterative deepening context. What you want to do is actually not leaving the root node. I agree that "jumping in the middle" is not the appropriate term but it is similar to that if you think of your approach as if you would re-search the root node but skip the first root moves.

Re-search is for the move that failed. Not for the node that contained one move that failed. That was the entire point from the beginning.

No, that was exactly what I wanted to point out it was not. It is only in your theory that re-search does not involve the whole root node. And here is the point where you have confirmed that you see my initial remark as completely wrong, while it is only the current standard which I described and your theory may be some kind of improvement but involves a couple of unclear issues and tends to create additional code complexity.

Sven

[Evert]

Seems to me that there is a bit of confusion caused by two different ways to do the root search: either you call your normal search function, which returns both a score and a best move, or you play each move in the root function and then call your normal recursive search function.
In the first case, obviously you research all moves after a fail high/low, because you call the search function again with a modified alpha/beta window. In the second case you could indeed only research a move that failed high as long as you already have an exact score from an earlier move.

I've always done the latter myself.