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

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

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

Post by tomitank » Mon Jul 24, 2017 10:12 am

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

User avatar
hgm
Posts: 26128
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

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

Post by hgm » Mon Jul 24, 2017 10:30 am

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.

tomitank
Posts: 258
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

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

Post by tomitank » Mon Jul 24, 2017 11:44 am

Even if you are in check and Score is not greater than alpha?

User avatar
hgm
Posts: 26128
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

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

Post by hgm » Mon Jul 24, 2017 12:49 pm

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.

tomitank
Posts: 258
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

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

Post by tomitank » Mon Jul 24, 2017 1:37 pm

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% 

User avatar
hgm
Posts: 26128
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

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

Post by hgm » Mon Jul 24, 2017 3:04 pm

That is not a significant difference.

zenpawn
Posts: 336
Joined: Sat Aug 06, 2016 6:31 pm
Location: United States

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

Post by zenpawn » Mon Jul 24, 2017 3:19 pm

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.

User avatar
hgm
Posts: 26128
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

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

Post by hgm » Mon Jul 24, 2017 3:37 pm

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.

tomitank
Posts: 258
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

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

Post by tomitank » Mon Jul 24, 2017 8:52 pm

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% 

op12no2
Posts: 389
Joined: Tue Feb 04, 2014 11:25 am
Location: Wales
Full name: Colin Jenkins
Contact:

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

Post by op12no2 » Mon Jul 24, 2017 9:07 pm

Hi Tamás, Is the tomitankChess javascript source anywhere public? It would be fun to set up a tourney with Lozza.

Post Reply