Where is bug?

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Sven
Posts: 3969
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Where is bug?

Post by Sven » Mon Apr 30, 2018 10:59 am

tomitank wrote:And here is my ASP:

Code: Select all

		search :

		for &#40;currDepth = 1; currDepth <= maxSearchDepth; currDepth++)
		&#123;
			if &#40;countMove == 1 && currDepth > 5 && bestMove&#41; break;

			for &#40;var margin = &#40;currDepth >= 4 ? 10 &#58; INFINITE&#41;; ; margin *= 2&#41; &#123;

				alpha = Math.max&#40;Score - margin, -INFINITE&#41;;
				beta  = Math.min&#40;Score + margin,  INFINITE&#41;;

				Score = AlphaBeta&#40;alpha, beta, currDepth, true, inCheck&#41;;

				if &#40;timeStop == 1&#41; break search; // time out

				if &#40;Score > alpha && Score < beta&#41; break;
			&#125;
		&#125;
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
Posts: 258
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Re: Where is bug?

Post by tomitank » Mon Apr 30, 2018 12:03 pm

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
Posts: 1870
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Where is bug?

Post by Ras » Mon Apr 30, 2018 1:00 pm

Sven wrote:- 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
Posts: 258
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Re: Where is bug?

Post by tomitank » Mon Apr 30, 2018 6:40 pm

I found the issue.

As I wrote, it's the right way:

Code: Select all

         if &#40;Score > BestScore&#41; &#123;

            BestScore = Score;

            if &#40;boardPly == 0 && &#40;LegalMove == 1 || Score > alpha&#41;) &#123;
               UpdatePv&#40;currentMove, Score, depth, alpha, beta&#41;;
            &#125;

            if &#40;Score > alpha&#41; &#123;

            	BestMove = currentMove;

               if &#40;Score >= beta&#41; &#123;
                  // history, killers
                  return Score;
               &#125;
               alpha = Score;
            &#125;
         &#125;
      &#125; 
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 &#40;boardPly == 0 && &#40;LegalMove == 1 || Score > alpha&#41;) &#123;
               UpdatePv&#40;currentMove, Score, depth, alpha, beta&#41;;
            &#125;
Am I correct?

Sven
Posts: 3969
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Where is bug?

Post by Sven » Mon Apr 30, 2018 8:56 pm

Ras wrote:
Sven wrote:- 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
Posts: 3969
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Where is bug?

Post by Sven » Mon Apr 30, 2018 9:07 pm

tomitank wrote:I found the issue.

As I wrote, it's the right way:

Code: Select all

         if &#40;Score > BestScore&#41; &#123;

            BestScore = Score;

            if &#40;boardPly == 0 && &#40;LegalMove == 1 || Score > alpha&#41;) &#123;
               UpdatePv&#40;currentMove, Score, depth, alpha, beta&#41;;
            &#125;

            if &#40;Score > alpha&#41; &#123;

            	BestMove = currentMove;

               if &#40;Score >= beta&#41; &#123;
                  // history, killers
                  return Score;
               &#125;
               alpha = Score;
            &#125;
         &#125;
      &#125; 
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 &#40;boardPly == 0 && &#40;LegalMove == 1 || Score > alpha&#41;) &#123;
               UpdatePv&#40;currentMove, Score, depth, alpha, beta&#41;;
            &#125;
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
Posts: 1870
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Where is bug?

Post by Ras » Mon Apr 30, 2018 9:29 pm

Sven wrote: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
Posts: 3969
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Where is bug?

Post by Sven » Mon Apr 30, 2018 9:43 pm

Ras wrote:
Sven wrote: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
Posts: 1870
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Where is bug?

Post by Ras » Mon Apr 30, 2018 11:23 pm

Sven wrote: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.

Post Reply