A few general questions...

[hgm]

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.

You let the root search return between iterations??? This seems an unconventional organization to me. I thought that by definition the root search is the function that controls the iterations, and that it would only return when time is up (or ponder miss).

[Michel]

You let the root search return between iterations??? This seems an unconventional organization to me.

In GnuChess the root search also returns between iterations. There is a separate procedure "Iterate" which controls iterative deepening, setting aspiration windows, time control etc...

[Don]

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.

You let the root search return between iterations??? This seems an unconventional organization to me. I thought that by definition the root search is the function that controls the iterations, and that it would only return when time is up (or ponder miss).

It's probably semantics. In my program there are these functions:

1. beginSearch
2. rootSearch
3. pvSearch
4. nonPvSearch
5. quiesSearch

beginSearch controls the iterations.

[hgm]

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

Yes, it means it does not make sense to me. And I even specified exactly why. So it asks you to explain what I am overlooking. And so far I haven't heard any of that. "everyone else does it" is not really an argument that counters my objection...

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.

Well, that others use it, doesn't prove it is not obsolete. Some would say mailbox boards became obsolete since the advent of 64-bit computers, and there still are top engines that use that too.

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.

What solution am I proposing? Using plain PVS without aspiration? How is that "creating new trouble"???

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.

So that is all moves searched so far, right? Including moves that increased alpha, including the move that could be second best, and having the lowest move count would be sorted as very last in the next iteration. And you say that is not a problem???

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?

This seems all nonsense. The archetypal root search is

Code: Select all

RootSearch()
{
  GenerateMoves();
  firstMove = TRUE;
  for&#40;depth = 1; depth < maxDepth; depth++) &#123;
    SetAspirationWindow&#40;);
    for&#40;ALL_MOVES&#41; &#123;
      MakeMove&#40;);
      score = -Search&#40;&#40;firstMove ? -alpha-1 &#58; -beta&#41;, -alpha&#41;;
      if&#40;score > alpha&#41; &#123;
        if&#40;!firstMove && score < beta&#41; score = -Search&#40;-beta, -alpha&#41;; // PVS
        if&#40;score >= beta&#41; &#123; // aspiration fail high
          score = -Search&#40;-INF, -alpha&#41;;
        &#125;
      &#125;
      UnMake&#40;);
      if&#40;score > alpha&#41; &#123;
        alpha = score;
        bestMove = move;
        if&#40;score>beta&#41; beta = score+1;
      &#125;
      firstMove = FALSE;
      TakeNodeStats&#40;move&#41;;
    &#125;
    SortMoves&#40;);
  &#125;
&#125;

There is no second-best move or anything, no confusion on what beta is... It is all straightforward and simple.

Code: Select all

The normal thing at [u]each[/u] node is that you leave the node prematurely (cut off all remaining subtrees) whenever the best score is >= beta, 

Of course not. The normal thing is you go to the next iteration (ID or IID).

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.

Well, if I really wanted to argue, I would not even want to return to the root node. Letting Search in the above code return only to be called immediately again for the same position (so it destroyed everything it might have learned about that position, in terms of ordering of its move list), just to change its alpha. It would have been far more efficient to have that node chenge its own alpha when it failed low, also in the PVS implementation in Search (as opposed to SearchRoot).

But that is not what we are discussing here. The implementation of PVS as written above is absolutely standard. The only difference is that with aspiration you might have to re-search twice, because aftr the PVS re-search, it could now also be outside the aspiration window.

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.

No, my "theory" was that it was pointless to re-search moves that failed low with a larger beta, because the will fail low in the same way, as their fail low is controlled by alpha, and not by beta. And so far this has not been contradicted in any way.

[hgm]

You let the root search return between iterations??? This seems an unconventional organization to me.

In GnuChess the root search also returns between iterations. There is a separate procedure "Iterate" which controls iterative deepening, setting aspiration windows, time control etc...

Well, you could make the body of every loop a function, of course. This is not free, however, because it means you lose all local variables of the function that now does the body. So you could work around that by storing the important stuff not in local variables, but in globals. (Or, when it is a recursive function, in a stack of globals you maintain by hand.) So that logically the calling routine merges with the called routine, sharing all variables. And then you could inline the called routine, so that at the assembly level it is not really a separate routine at all...

[Zach Wegner]

This seems all nonsense. The archetypal root search is

Code: Select all

RootSearch()
{
  GenerateMoves();
  firstMove = TRUE;
  for&#40;depth = 1; depth < maxDepth; depth++) &#123;
    SetAspirationWindow&#40;);
    for&#40;ALL_MOVES&#41; &#123;
      MakeMove&#40;);
      score = -Search&#40;&#40;firstMove ? -alpha-1 &#58; -beta&#41;, -alpha&#41;;
      if&#40;score > alpha&#41; &#123;
        if&#40;!firstMove && score < beta&#41; score = -Search&#40;-beta, -alpha&#41;; // PVS
        if&#40;score >= beta&#41; &#123; // aspiration fail high
          score = -Search&#40;-INF, -alpha&#41;;
        &#125;
      &#125;
      UnMake&#40;);
      if&#40;score > alpha&#41; &#123;
        alpha = score;
        bestMove = move;
        if&#40;score>beta&#41; beta = score+1;
      &#125;
      firstMove = FALSE;
      TakeNodeStats&#40;move&#41;;
    &#125;
    SortMoves&#40;);
  &#125;
&#125;

There is no second-best move or anything, no confusion on what beta is... It is all straightforward and simple.

And incorrect, because it does not handle aspiration fail lows.

I agree that the "standard" way of doing aspiration windows (on the root node as opposed to on the root moves) is somewhat illogical, but it's certainly a simple and effective solution. In Rondo, I avoid this by making the first root move get an exact score, so I don't have to wait until the end of the move list to declare a fail low, just lower alpha immediately...

[hgm]

And incorrect, because it does not handle aspiration fail lows.

Well, I'd rather call it incomplete than incorrect. We were discussing the fail highs here. I already mentioned above that you would have to re-search all moves if in the end you have a fail low. If you insist to see that in the pseudo code:

Code: Select all

RootSearch()
{
  GenerateMoves();
  firstMove = TRUE;
  for&#40;depth = 1; depth < maxDepth; ) &#123;
    SetAspirationWindow&#40;);
    bestMove = NULL;
    for&#40;ALL_MOVES&#41; &#123;
      MakeMove&#40;);
      score = -Search&#40;&#40;firstMove ? -alpha-1 &#58; -beta&#41;, -alpha&#41;;
      if&#40;score > alpha&#41; &#123;
        if&#40;!firstMove && score < beta&#41; score = -Search&#40;-beta, -alpha&#41;; // PVS
        if&#40;score >= beta&#41; &#123; // aspiration fail high
          score = -Search&#40;-INF, -alpha&#41;;
        &#125;
      &#125;
      UnMake&#40;);
      if&#40;score > alpha&#41; &#123;
        alpha = score;
        bestMove = move;
        if&#40;score>beta&#41; beta = score+1;
      &#125;
      firstMove = FALSE;
      TakeNodeStats&#40;move&#41;;
    &#125;
    if&#40;bestMove == NULL&#41; &#123; alpha = -INF; continue; &#125;
    SortMoves&#40;);
    depth = NextDepth&#40;depth&#41;;
  &#125;
&#125;

But this whole discussion is going off at a tangent, which leaves my original question still unsanswered. So let me try again:

Do all we agree that a re-search on a move that with window {alpha, beta} gave a score < beta, in general will not produce a different score, when the sre-search uses a window {alpha, beta'}, beta' > beta? (If you are lucky by an immediate hash hit in the daughter node?)

And that when you know in advance that the result of a score will be a fail low, it would be pointless to do that search?

Only if you do not agree with one of these two points would it make sense to contradict me. Otherwise, it would suffice to say: "indeed, it is pointless, but everyone does it like that, so I would not dare to do it differently"...

Another interesting thought: if everyone does it like this, while it makes no sense, it can only be because they are copying each other's implementation...