iterative deepeniing and branching factor

[jwes]

It occured to me that the lower the branching factor, the higner the relative cost of iterative deepening, e.g, with a branching factor of 2, the number of nodes for plies 1 to n-1 is nearly equal to the nodes for ply n, while for a branching factor of 6, the number of nodes for plies 1 to n-1 is about 1/5 the nodes for ply n.

[jswaff]

It occured to me that the lower the branching factor, the higner the relative cost of iterative deepening, e.g, with a branching factor of 2, the number of nodes for plies 1 to n-1 is nearly equal to the nodes for ply n, while for a branching factor of 6, the number of nodes for plies 1 to n-1 is about 1/5 the nodes for ply n.

I think I see where you're going, but it's only because you *did* the searches for plies 1 to n-1 that you can even do the ply n search in so few nodes. Otherwise, you'd have no pv/hash/history information to guide the ply n search.

--
James

[wgarvin]

I think sometimes you can skip the first N-2 iterations anyways. If you play your best move and then the opponent responds with the predicted move, then all of the searches for the first N-2 iterations should be satisfied almost instantly by the hashtable.

I remember reading something about this in a thread which I can't find anymore (was it on the old forum, and lost in the transition?)

It might be this thread, "Root Move Ordering" from early April this year. I was just reading it a week ago, too =(

[hgm]

This is a general property of ID, also when you use it in internal nodes: if there is no PV change (meaning in the root that you predicted the opponent's move correctly), only the last iteration has to be done, as if you did not do ID at all.

This is fully automatic, and doesn't have to be programmed explicitly: the early iterations simple are satisfied by hash hits, without search. (It makes time management tricky, though, especially in combination with pondering, as you can get the first N-1 iterations in near-zero time, optimistically starting the Nth iteration, which then takes forever...)

If the branching ratio is too low, the conventional solution is deepening in larger steps, e.g. two ply at the time.

[jwes]

If the branching ratio is too low, the conventional solution is deepening in larger steps, e.g. two ply at the time.

Do you know of programs that do this?

[mjlef]

If the branching ratio is too low, the conventional solution is deepening in larger steps, e.g. two ply at the time.

Do you know of programs that do this?

Most Checkers programs do, since the branching factor is very low in Checkers.

[hgm]

I have never looked how other programs worked even once. I understood from others that it is usually done in internal nodes. (IID)

In a perfectly ordered tree the size of sub-trees sprouting from alpha or beta nodes grwos very unevenly with depth: If the old tree had all-nodes as leaves, the number of leaves is multiplied by ~40 in the next ply, but when they are cut-nodes it stays the same. By extending in steps of 2 you always skip the 'useless' deepenings.

In addition is is usually more reliable to compare evaluations with the same side to move.

In PV nodes (such as the root...) the math is slightly different, though. But the amount of deepening per iteration should be simply seen as a parameter that can be optimized. Especially in searches working with fractional plies, there is no reason tho take in for granted that 1 is the optimum.

[bob]

If the branching ratio is too low, the conventional solution is deepening in larger steps, e.g. two ply at the time.

Do you know of programs that do this?

It isn't a new idea. "BeBe" went by twosies in the middle 80's as one example. I have encountered others that did so. One reason was to eliminate the odd/even ply flip-flopping of the best move when on odd ply searches the program gets one extra move compared to the opponent, while in the even-ply searches both get the same number of moves.

I've tried it but personally chose to not use it. The problem is that there are plenty of positions where you can do an N ply search, but not an N+1 ply search, given a time constraint. Which means that in such cases, you will have to be happy with a depth N-1 search, since the N+1 can't be completed in time. Going by onesies eliminates this.

[Tord Romstad]

It isn't a new idea. "BeBe" went by twosies in the middle 80's as one example. I have encountered others that did so. One reason was to eliminate the odd/even ply flip-flopping of the best move when on odd ply searches the program gets one extra move compared to the opponent, while in the even-ply searches both get the same number of moves.

In my opinion, such problems are an indication of a missing or badly tuned side-to-move bonus in the evaluation function.

I've tried it but personally chose to not use it. The problem is that there are plenty of positions where you can do an N ply search, but not an N+1 ply search, given a time constraint. Which means that in such cases, you will have to be happy with a depth N-1 search, since the N+1 can't be completed in time. Going by onesies eliminates this.

True: For time managment reasons, one ply is probably a better increment than two plies. But I don't see any a priori reason to believe that an increment of exactly one ply is optimal - it is possible that a value of slightly above or below one ply would work better. It might also depend on the phase of the game, and on other considerations. For instance, at the end of an iteration, if you have some time left, but probably not quite enough to finish another iteration with a full ply more, it makes some sense to only increase the depth by only half a ply for the next iteration.

I have personally never tried anything else than exactly one ply per iteration, but I think it might be worth some experiments.

Tord

[bob]

It isn't a new idea. "BeBe" went by twosies in the middle 80's as one example. I have encountered others that did so. One reason was to eliminate the odd/even ply flip-flopping of the best move when on odd ply searches the program gets one extra move compared to the opponent, while in the even-ply searches both get the same number of moves.

In my opinion, such problems are an indication of a missing or badly tuned side-to-move bonus in the evaluation function.

I've never had a side to move bonus, except for pawn endings where the side to move determines whether a pawn is catchable, or whether a pawn is unstoppable due to opposition. But for normal positions, I don't do it because I know of no reliable way to do so. And with the depths we see today, and the extensions/reductions in use, it ends up being apples-to-oranges anyway...

I've tried it but personally chose to not use it. The problem is that there are plenty of positions where you can do an N ply search, but not an N+1 ply search, given a time constraint. Which means that in such cases, you will have to be happy with a depth N-1 search, since the N+1 can't be completed in time. Going by onesies eliminates this.

True: For time managment reasons, one ply is probably a better increment than two plies. But I don't see any a priori reason to believe that an increment of exactly one ply is optimal - it is possible that a value of slightly above or below one ply would work better. It might also depend on the phase of the game, and on other considerations. For instance, at the end of an iteration, if you have some time left, but probably not quite enough to finish another iteration with a full ply more, it makes some sense to only increase the depth by only half a ply for the next iteration.

I have personally never tried anything else than exactly one ply per iteration, but I think it might be worth some experiments.

Tord

In Crafty it is trivial. Several years ago I tried several options, including 1/2 and 3/4 of a ply. In some cases it works better (those positions where iteration N+1 somehow blows up and takes way longer than expected). But in more cases, it was worse...