Where is bug?

[Sven]

And here is my ASP:

Code: Select all

		search :

		for (currDepth = 1; currDepth <= maxSearchDepth; currDepth++)
		{
			if (countMove == 1 && currDepth > 5 && bestMove) break;

			for (var margin = (currDepth >= 4 ? 10 : INFINITE); ; margin *= 2) {

				alpha = Math.max(Score - margin, -INFINITE);
				beta  = Math.min(Score + margin,  INFINITE);

				Score = AlphaBeta(alpha, beta, currDepth, true, inCheck);

				if (timeStop == 1) break search; // time out

				if (Score > alpha && Score < beta) break;
			}
		}

This code does not take into account whether the previous call of AlphaBeta failed low or high, for currDepth >= 4 it always re-searches with a window of [Score - margin .. Score + margin] where margin is 20, 40, 80, ... A better attempt could be to do the following:
- After failing low re-search with a lower alpha and *unchanged* beta
- After failing high re-search with a higher beta and *unchanged* alpha
(SF9 does that, too, search for the comment "In case of failing low/high increase aspiration window" ...)

That might help to avoid toggling up and down between fail-low and fail-high which can be caused by search instability (which itself is caused by TT entries being overwritten in the meantime, and is also a possible explanation for non-reproducability problems).

[tomitank]

I tried this idea, but dont gave me elo, that way i dont use.
SF 9 change beta as well if score above alpha. beta = (alpha + beta) / 2;

I understand what you want, but this is not a 100% guarantee for my problem.

I have three choices: I use only the result of the last completed search, or i use only the move of "exact score", or I live together with the possible hash collisions. The latter is ~10 Elo better.

[Ras]

- After failing low re-search with a lower alpha and *unchanged* beta
- After failing high re-search with a higher beta and *unchanged* alpha

I tried that at root in the iterative deepening loop, but without effect. Not quite sure why it doesn't help.

Maybe because I have a PV anyway and don't stop with hash hits in PV nodes. So when I start with depth N, I already have a PV that is at least N-1 deep. Since PV nodes have highest priority in the move sorting, the search tree will first go to the end of the PV and then search one ply deeper. But doing that, I quickly have an alpha and beta for the rest of the tree so that it doesn't matter whether I start with a full window at root.

Does that make sense?

[tomitank]

I found the issue.

As I wrote, it's the right way:

Code: Select all

         if (Score > BestScore) {

            BestScore = Score;

            if (boardPly == 0 && (LegalMove == 1 || Score > alpha)) {
               UpdatePv(currentMove, Score, depth, alpha, beta);
            }

            if (Score > alpha) {

            	BestMove = currentMove;

               if (Score >= beta) {
                  // history, killers
                  return Score;
               }
               alpha = Score;
            }
         }
      } 

The best moves for hash entry must be above alpha.
Because the first move is from the hash entry (if it's avaliable).
If this step did not improve the alpha, then we have bad move.

If the time is out in the next (aspiration window) iteration and we can only search one step, then we maybe have a bad move:
(LegalMove == 1) is the first move.

Code: Select all

            if (boardPly == 0 && (LegalMove == 1 || Score > alpha)) {
               UpdatePv(currentMove, Score, depth, alpha, beta);
            }

Am I correct?

[Sven]

- After failing low re-search with a lower alpha and *unchanged* beta
- After failing high re-search with a higher beta and *unchanged* alpha

I tried that at root in the iterative deepening loop, but without effect. Not quite sure why it doesn't help.

Maybe because I have a PV anyway and don't stop with hash hits in PV nodes. So when I start with depth N, I already have a PV that is at least N-1 deep. Since PV nodes have highest priority in the move sorting, the search tree will first go to the end of the PV and then search one ply deeper. But doing that, I quickly have an alpha and beta for the rest of the tree so that it doesn't matter whether I start with a full window at root.

Does that make sense?

I don't know how you maintained your aspiration window before trying what I wrote (which I thought were pretty standard) so I can't tell why it doesn't "help" in your case. My suggestion was meant as a change for the OP where I thought it could be an improvement.

Regarding your remark that you "have a PV anyway", I do not get your point. The question was how to adapt the aspiration window after failing high or low. Of course you can always do the re-search with a fully open window but that is not necessary, and there seem to be better ways.

[Sven]

I found the issue.

As I wrote, it's the right way:

Code: Select all

         if (Score > BestScore) {

            BestScore = Score;

            if (boardPly == 0 && (LegalMove == 1 || Score > alpha)) {
               UpdatePv(currentMove, Score, depth, alpha, beta);
            }

            if (Score > alpha) {

            	BestMove = currentMove;

               if (Score >= beta) {
                  // history, killers
                  return Score;
               }
               alpha = Score;
            }
         }
      } 

The best moves for hash entry must be above alpha.
Because the first move is from the hash entry (if it's avaliable).
If this step did not improve the alpha, then we have bad move.

If the time is out in the next (aspiration window) iteration and we can only search one step, then we maybe have a bad move:
(LegalMove == 1) is the first move.

Code: Select all

            if (boardPly == 0 && (LegalMove == 1 || Score > alpha)) {
               UpdatePv(currentMove, Score, depth, alpha, beta);
            }

Am I correct?

What is "BestMove" in your case? If it is the best root move that your engine is going to play then it should only be set at the root node (boardPly == 0). If it is something local to the current node then I do not understand why you need both "BestMove" and the PV (which, in my view, should also be updated everywhere, not just at the root - but I don't know exactly the purpose of the UpdatePv() function).

[Ras]

Regarding your remark that you "have a PV anyway", I do not get your point. The question was how to adapt the aspiration window after failing high or low.

My guess is: if there is a PV of depth N-1, then that will be the first search path on the rim of the tree, only one ply deeper to depth N. Once that is done, the alpha/beta window will be quite narrow anyway, so the root windows doesn't really have a big effect.

[Sven]

Regarding your remark that you "have a PV anyway", I do not get your point. The question was how to adapt the aspiration window after failing high or low.

My guess is: if there is a PV of depth N-1, then that will be the first search path on the rim of the tree, only one ply deeper to depth N. Once that is done, the alpha/beta window will be quite narrow anyway, so the root windows doesn't really have a big effect.

This is only true when not failing high or low. Once your search fails high or low, having had a narrow (but wrong) alpha-beta window resulting from a shallower search becomes irrelevant.

[Ras]

This is only true when not failing high or low.

Hmm I see, if the PV from depth N-1 doesn't wash at depth N anymore, then the expensive re-search can be faster if the window isn't wide open.