Page 1 of 3

IID (skipped when in check and Score greater than alpha)

Posted: Mon Jul 24, 2017 10:12 am
by tomitank
Hi.

Is there a measurable difference? Which is the best?

1.

Code: Select all

if (IS_PV && !inCheck && boardPly != 0 && Depth >= 4 && hashMove == NOMOVE) {
	AlphaBeta(alpha, beta, Depth-2, false, inCheck);
	hashMove = ProbeHashMove();
}
2.

Code: Select all

if (IS_PV && boardPly != 0 && Depth >= 4 && hashMove == NOMOVE) {
	AlphaBeta(alpha, beta, Depth-2, false, inCheck);
	hashMove = ProbeHashMove();
}
3.

Code: Select all

if (IS_PV && !inCheck && boardPly != 0 && Depth >= 4 && hashMove == NOMOVE) {
	Score = AlphaBeta(alpha, beta, Depth-2, false, inCheck);
	if (Score > alpha) hashMove = ProbeHashMove();
}
4.

Code: Select all

if (IS_PV && boardPly != 0 && Depth >= 4 && hashMove == NOMOVE) {
	Score = AlphaBeta(alpha, beta, Depth-2, false, inCheck);
	if (Score > alpha) hashMove = ProbeHashMove();
}
Currently i tested, but it can take a long time.

Thanks, Tamas

Re: IID (skipped when in check and Score greater than alpha)

Posted: Mon Jul 24, 2017 10:30 am
by hgm
For my engines IID has always proved useful in any node (even all-nodes, because you can never be sure they are all-nodes). But that was of course with an efficient implementation, not with a crappy recursive call to redo the same node, so that it does a lot of work in duplicate, and then throws all of it away except for the hash move.

Re: IID (skipped when in check and Score greater than alpha)

Posted: Mon Jul 24, 2017 11:44 am
by tomitank
Even if you are in check and Score is not greater than alpha?

Re: IID (skipped when in check and Score greater than alpha)

Posted: Mon Jul 24, 2017 12:49 pm
by hgm
Well, I did not test that specifically, but why not? Checks are often given to delay losses. I could have a pin, fork or skewer that I can cash on to get above beta, but I have to resolve the check first, in a correct way. The check will hardly have lowerd the opponent's score, so if we are below alpha after it, the opponent would have been above beta before it. And yet he stooped to searching checks, rather than comfortably leaning back with a null move. So apparently he is under threat, and likely many non-checks he tried first already failed low. Normal move ordering (killers, history) usually doesn't work well when in check, so the chances I will find the proper refutation by static means is not very large, if the check wasn't a pointless sacrifice. Searching checks is expensive, because they get exteded, so even if they occur rarely in the tree, treating them efficiently might have a measurable impact.

Re: IID (skipped when in check and Score greater than alpha)

Posted: Mon Jul 24, 2017 1:37 pm
by tomitank
Very small difference

tomitankChess - PV node, not in check
tomitankChessV4 - PV node

Code: Select all

Rank Name              Elo    +    - games score oppo. draws 
   1 tomitankChess       2   16   16   300   51%    -2   42% 
   2 tomitankChessV4    -2   16   16   300   50%     2   42% 

Re: IID (skipped when in check and Score greater than alpha)

Posted: Mon Jul 24, 2017 3:04 pm
by hgm
That is not a significant difference.

Re: IID (skipped when in check and Score greater than alpha)

Posted: Mon Jul 24, 2017 3:19 pm
by zenpawn
hgm wrote:For my engines IID has always proved useful in any node (even all-nodes, because you can never be sure they are all-nodes). But that was of course with an efficient implementation, not with a crappy recursive call to redo the same node, so that it does a lot of work in duplicate, and then throws all of it away except for the hash move.
Could you please elaborate on the non-crappy way? :) Thanks.

Re: IID (skipped when in check and Score greater than alpha)

Posted: Mon Jul 24, 2017 3:37 pm
by hgm
Just loop over depth after move generation, so that you can continue to use the same move list, and benefit from any sorting that has been applied to it at lower depth. My search routines typically looks like this:

Code: Select all

Search(depth)
{
  inCheck = CheckTest();
  depth += inCheck; // check extension
  GenerateMoves();
  for&#40;iterDepth=startDepth; iterDepth <= depth; iterDepth++) &#123;
    for&#40;ALL_MOVES&#41; &#123;
      MakeMove&#40;);
      score = -Search&#40;iterDepth-1&#41;;
      UnMake&#40;);
      ...
    &#125;
    SortBestToFront&#40;);
  &#125;
&#125;
The startDepth controls whether IID is actually done, and is set based on whether there was a hash hit, and what the draft of the probed result was.

If you would have to redo move generation, check testing etc. in every iteration from scratch, it can easily become not worth it.

Re: IID (skipped when in check and Score greater than alpha)

Posted: Mon Jul 24, 2017 8:52 pm
by tomitank
tomitankChess - PV node, not in check
tomitankChessV4 - PV node, Score > alpha

Code: Select all

Rank Name              Elo    +    - games score oppo. draws 
   1 tomitankChess       0   14   14   400   50%     0   39% 
   2 tomitankChessV4     0   14   14   400   50%     0   39% 

Re: IID (skipped when in check and Score greater than alpha)

Posted: Mon Jul 24, 2017 9:07 pm
by op12no2
Hi Tamás, Is the tomitankChess javascript source anywhere public? It would be fun to set up a tourney with Lozza.