IID

[Daniel Shawul]

Wher should Internal Iterative Deepening be used.
I do it at any node where i don't have a hash move..
I know this eats more nodes than doing it only at PV nodes,
But using the first method allows a better move ordering which seems to
compensate the loss for my case. What is your experience?

[Peter Fendrich]

Wher should Internal Iterative Deepening be used.
I do it at any node where i don't have a hash move..
I know this eats more nodes than doing it only at PV nodes,
But using the first method allows a better move ordering which seems to
compensate the loss for my case. What is your experience?

I think it highly depends on the type of search you are doing and what type of extension/reductions you have.
I'm using PVS and this is how IID fits into Terra:
- When I don't have a hashmove
- When alpha != beta-1 (In PVS this has a meaning!)
The idea is to use IID as a last thing for PV-nodes to get a good move to search first when I have no hashmove.

It is qustionable if it really paid off and in Alaric I don't even use IID. It conflicts with other things in the search.
/Peter

[Tord Romstad]

I think it highly depends on the type of search you are doing and what type of extension/reductions you have.
I'm using PVS and this is how IID fits into Terra:
- When I don't have a hashmove
- When alpha != beta-1 (In PVS this has a meaning!)
The idea is to use IID as a last thing for PV-nodes to get a good move to search first when I have no hashmove.

In my experience, IID really pays off, in PVS as well as MTD. I have even found IID to be effective when beta-alpha>1, if done sufficiently far from the leaves and only at nodes where I have good reason to expect a fail high (for instance because the static eval is bigger than beta).

Tuning IID well requires some work, though. Some experimentation is needed to find out how close to the leaves IID should be allowed, and how big the reduction factor should be. It might also be a good idea to avoid IID in positions where there is an apparently obviously winning capture.

Here is the (very simple) code I use in Glaurung at the moment:

Code: Select all

  if(!pvmove && ((beta-alpha > 1 && depth > 3*PLY) ||
       (depth > 6*PLY && ss->eval > alpha - P_VALUE))) {
    value = search(alpha, beta, depth-2*PLY, 0, 0);
    ABORT_TEST();
    pvmove = SearchStack[Ply].pv[Ply];
  }


Tord

[Daniel Shawul]

In my experience, IID really pays off, in PVS as well as MTD. I have even found IID to be effective when beta-alpha>1, if done sufficiently far from the leaves and only at nodes where I have good reason to expect a fail high (for instance because the static eval is bigger than beta).

why not exclude ALL nodes also? because at these nodes move ordering
doesn't matter. I also do not make IID after null move, because i store
the move that caused the null move fail low and use it later during move ordering(when there is no hash table move).
doing IID at every node seems to decrease my branching factor especially in endgames.

i haven't tried delaying IID until winning and equal captures are tried,but i
doubt if it can do me any good. Not restraing it seems to improve my move ordering so much .

think it highly depends on the type of search you are doing and what type of extension/reductions you have.

what effect do extesnions have on IID? they make trees of some moves larger but i don't see how this can affect IID.
daniel

[Peter Fendrich]

I also do not make IID after null move, because i store the move that caused the null move fail low and use it later during move ordering(when there is no hash table move).

I don't understand this. For me it is handled by the ordinary hash table. Suppose that we made a nullmove. We store the childs FH move in hashtable. The nullmove is now FL. Next time this is the hashmove that is tried first.
No need to store it in some other way, is it?

doing IID at every node seems to decrease my branching factor especially in endgames.

It should decrease your branching factor but does the program really search fewer nodes? The extra IID nodes are almost balancing this up in Terra.

what effect do extesnions have on IID?

None, your'e right. I wasn't thinking. I have however experimented with alternatives to IID and in that process I found candidates to both extensions and reductions. I will eventually discuss this method but I want to try it out in my own program first!
/Peter

[Daniel Shawul]

I don't understand this. For me it is handled by the ordinary hash table. Suppose that we made a nullmove. We store the childs FH move in hashtable. The nullmove is now FL. Next time this is the hashmove that is tried first.
No need to store it in some other way, is it?

what i mean is move ordering after null move is not that important because any good move (killers for example) can refute it easily if it indeed is refutable. The reason why i store the threat move (move that caused the null move to fail low) is because i do botvinnik markoff extensions. This threat move can be used as an additional killer move.
So when the search have no idea about the position(no hash table move), trying this killer moves may be better than doing a reduced depth search.

It should decrease your branching factor but does the program really search fewer nodes? The extra IID nodes are almost balancing this up in Terra

The search time for a given depth decreses noticeably. why should i care about nodes searched? i think this may not be a good idea for blitz games
where less depth is reached. Making the reduction larger (i currently reduce by 2), may work better but i haven't tried it.

daniel

[Peter Fendrich]

The reason why i store the threat move (move that caused the null move to fail low) is because i do botvinnik markoff extensions.

Ok, I do the same.

The search time for a given depth decreses noticeably. why should i care about nodes searched?

When talking about move ordering it is the same thing. I think it is a very fast way to evaluate if the move ordering really is improved.

i think this may not be a good idea for blitz games
where less depth is reached. Making the reduction larger (i currently reduce by 2), may work better but i haven't tried it.

I doubt it but maybe I'm doing something wrong because IID is more or less break even in Terra except for very simple positions. In total, no big deal.
/Peter

[Dann Corbit]

{snip}
I doubt it but maybe I'm doing something wrong because IID is more or less break even in Terra except for very simple positions. In total, no big deal.
/Peter

IID has exactly one benefit: Greatly improved move ordering. So, if you have only 80% fail high before IID, you will see a ridiculous improvement with adding IID for every search. But if you have 92% move ordering before IID, you will see very little change. I have seen this in some programs.

[Richard Pijl]

I've made a little test. Baron with no IID vs Baron with recursive IID including some tricks I will explain:

Baron has a built in benchmarking command, that will do a fixed ply search on 10 position. For convenience I've taken these ten positions to make the comparison. On average the search will take 0.5, 1.5, 5, 15 and 45 seconds per position. I'm listing the number of nodes searched.

Code: Select all

    No IID                      IID              Saving
   1073998                   1067600         0.5%
   3476214                   3322037         4.4%
  11174134                  10746308         3.8%
  35143077                  32445096         7.6%
 109395491                  97190097        11.2%


As you can see a more than 11% decrease in number of nodes in an on average 45 second search. And savings are rising on longer searches (as can be expected) so on tournament time control this should be really significant.

I'm doing IID everywhere where I do not have a hashmove and remaining depth is at least 2 ply. So also in nullwindow searches.
This picture has improved a bit after taking over Tord's recommendation above to only do IID in nullmove window searches if evaluation returns a value > alpha-pawnvalue. I use a reduced evaluation function for that purpose, which hardly takes time to execute.
Another trick has been posted by Ed Schroeder some time ago (also on his site). If you have a lot of depth left, don't reduce by two ply, but by dividing depth by 2. So my IID depth is the minimum of Depth/2 and Depth-2.

Richard.

[Daniel Shawul]

When talking about move ordering it is the same thing. I think it is a very fast way to evaluate if the move ordering really is improved.

you are right. i was not measuring nodes for a fixed depth. Richard's test
is the right setup.

Another trick has been posted by Ed Schroeder some time ago (also on his site). If you have a lot of depth left, don't reduce by two ply, but by dividing depth by 2. So my IID depth is the minimum of Depth/2 and Depth-2.

i have tried depth/2 after i read the paper, but i found it to be not better than depth - 2. May be this is a parameter that eveyone has to tune.
best
daniel

[Zach Wegner]

I don't understand this. For me it is handled by the ordinary hash table. Suppose that we made a nullmove. We store the childs FH move in hashtable. The nullmove is now FL. Next time this is the hashmove that is tried first.
No need to store it in some other way, is it?

No, it is not the same position. One is after a null-move, the other is after a real move. Or I thoroughly misunderstood you

Regards,
Zach

[Peter Fendrich]

No, it is not the same position. One is after a null-move, the other is after a real move. Or I thoroughly misunderstood you

Regards,
Zach

Actually I misunderstood Daniel from the beginning, so if you misunderstood me you probably go it right in the end...
He meant the move from the Botv.-Markarov threat detection that of course be used for move ordering in different positions while I was thinking of the next time the same Nullmove move was refuted by a move.
Sometimes (but not htis time) I've got some really interesting ideas by merely misunderstanding others - it seems to be good for the creative process!
/Peter