iterative deepeniing and branching factor

[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.

...

I know this is an old post, but I just run across it ...

Tony regretted this, as he once told me, but he claimed it would not be simple to fix. In my opinion it was a pretty big mistake that probably prevented him from winning tournaments, as his machine was pretty impressive and seemed to always finish near, but not quite IN first place. In order to compensate he added a feature he called "verify stand pat" in order to make his program take more time! He was in a situation where he tended to finish a 7 ply search really quickly, but couldn't quite make it to the 9 ply search (he always did odd ply.)

I've played around with it and I think you throw away too much information. It does work in checkers though ...

Back them, pre-LMR days, branching factors were about 6 per additional ply. Now with branching factors around 2, much like checkers, it might pay off. It seems with LMR, each additional ply of depth takes about double the previous search time. So if a 10 ply search takes 1 second, an 11 ply takes about 2 seconds more, and the 12 ply 4 more seconds. By skipping the 11 ply search (for example), you would save about 2 out of 7 seconds. So it might pay off if you were pretty darn sure the 12 ply search would search the first move. And if the move ordering is not bad since it misses one of the searches.

If anyone tests this, I would love to hear the results.

I'm pretty sure this is more about information loss than branching factor, although it's tempting to think that with a BF of 2 this might work after all. I think it's clear that your search will not be as efficient, but the question is really if you will save more time avoiding the intermediate depths than you will with less efficient searches.

We don't have to guess, it would be easy to do this experiment. Maybe I will try and then report back to the forum.

Of course taking an existing program and simply doing this test may not be quite fair, because if you were determined to make this work it's likely that you might do some things differently. Tony probably tuned his program to work as well as possible with the skipping strategy.

It has to do with the reductions he's doing and dubious pruning.

when i was experimenting with this in diep around 1999 for first time,
and ran with diep in that manner for a year (also during tournaments like the world champs 1999) then the worst case of ID step 2 was a lot worse
from step 1.

In positions where step 2 is better, you already get such a huge search depth, that it doesn't matter when that eats more nodes.

I see junior do it by the way sometimes that they skip first 12 ply rather
quickly. Not sure based upon what decision they let the engine decide when to take which stepsize.

The thing is, if you search THAT selective, is iteration depth 20 in fact a 10 ply search depth with "odds that you find tactics up to 20 ply" or is it really 20 ply?

Vincent

I even tried a take-off on that idea... So long as there was plenty of time for the next iteration, I did depth = depth + 1; but when time remaining looked insufficient for another iteration, I switched to depth = depth + 1/2; But it never seemed to play better, or even as well, in testing...

It's one of those things that make you think "How can 1 be the correct universal constant and how were we so lucky as to glom onto it from the get-go?" But it does look to be the best there is right now. And for my code it is convincingly the best based on testing.

[bob]

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.

That is not precise enough. Since ply 1 is an ALL node always, ODD depths have bigger trees than even depths, I agree. Odd depths have 40x as many potential nodes, while even depths double the size of the tree since you do add at least one node at a CUT node. All of this assumes uniform depth. In reality, I don't see any trend with odd vs even depths with all the extensions and reductions that we typically, the tree growth seems to be fairly uniform from ply to play, which makes the argument for trying to skip the easy ones (even plies) and only do odd plies not very convincing. BeBe used to do just this, only doing the odd ply searches. And it occasionally, at critical times, got "stuck" due to poor / no move ordering and would walk into a tactical disaster because it couldn't get anything back from 11, after completing 9, where depth 10 would have been enough to let it discover the problem and have time to find a better move.

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.

[Zach Wegner]

It's one of those things that make you think "How can 1 be the correct universal constant and how were we so lucky as to glom onto it from the get-go?" But it does look to be the best there is right now. And for my code it is convincingly the best based on testing.

Makes perfect sense to me. Less than 1 and you start repeating way too much work, since depth 1.5 is equivalent to 1 in most cases. One is the smallest step you can get where you always increase the amount of information you get on each iteration for every node (minus some edge cases with hard forward pruning or if you have an exact score--game end).

An easy way to think of this is comparing depth first (alpha beta) with best first. Iterative deepening is equivalent to expanding every leaf in best first. Now think about recursively expanding every leaf node twice (expand and then expand all children). Too much work since you don't have any information on the nodes in the first expansion. Now try to expand half a move. You end up evaluating all the nodes, when only some fraction (those that have already been extended half a ply) actually being expanded. Then on the next iteration all the _other_ nodes get expanded, when you still have to evaluate each one...

Now, I think it is still possible to get improvement from incrementing more or less than one in very specific places (for just one iteration or so), but in general I highly doubt anything can beat one.