Incremental update

[stegemma]

[...]
Think about this. You update attacks after a move at ply=1, then you update again after ply=3, then again after ply=5, and so on until ply=31. How much of the ply=1 stuff did you repeatedly undo as you went deeper? Then you only use the final product. Which (for me, anyway) was cheaper than the incremental stuff.[...]

That's sounds wrong to me because with a branch factor > 1, the number of nodes in last ply are a lot greater than the sum of nodes on previous plies; this means that the incremental work done before the last ply is just a fraction of the work needed on the last one. The problem IMHO is to compare the overall cost of the incremental updates between the cost of other strategy in the last ply. For sample, in my (old) incremental move generator the cost of the structure needed to make it works were so high that generating all the moves from scratch is now faster but the reason wasn't the fact that I used that generator on ply 1+ ply 2 + plus 3...

[hgm]

Think about this. ...

Well, apparently this is a wrong way to think about it, as it leads to a faulty conclusion.

What is wrong with the much more direct appproach of just counting the number of MakeMoves versus the number of leafs and internal nodes of the tree, and using total_work = work_per_case * number_of_cases? That clearly shows that the trade-off between doing things in the MakeMove (i.e. incrementally) as opposed to the leaves or internal nodes (from scratch) is independent of depth, as the ratio MokeMoves/node is independent of depth, and just depends on branching factor.

[bob]

[...]
Think about this. You update attacks after a move at ply=1, then you update again after ply=3, then again after ply=5, and so on until ply=31. How much of the ply=1 stuff did you repeatedly undo as you went deeper? Then you only use the final product. Which (for me, anyway) was cheaper than the incremental stuff.[...]

That's sounds wrong to me because with a branch factor > 1, the number of nodes in last ply are a lot greater than the sum of nodes on previous plies; this means that the incremental work done before the last ply is just a fraction of the work needed on the last one. The problem IMHO is to compare the overall cost of the incremental updates between the cost of other strategy in the last ply. For sample, in my (old) incremental move generator the cost of the structure needed to make it works were so high that generating all the moves from scratch is now faster but the reason wasn't the fact that I used that generator on ply 1+ ply 2 + plus 3...

I simply measured the cost by experiment. Computing updated attacks is not exactly a cheap operation. When you move any piece, you potentially uncover a square that lets other pieces (for both sides) attack through it. And you cover another square that blocks pieces for both sides. Rotated and magic bit boards was cheaper when I ran the test.

And then when you make/update, the last one is always wasted since you must eventually reach a node where you don't search anything and just stand pat.

YMMV, but early Crafty was an incremental attack update program just like chess 4.x. I think Summer of 1995 was the end of that approach when I wrote the rotated code that was much faster.

[bob]

Think about this. ...

Well, apparently this is a wrong way to think about it, as it leads to a faulty conclusion.

What is wrong with the much more direct appproach of just counting the number of MakeMoves versus the number of leafs and internal nodes of the tree, and using total_work = work_per_case * number_of_cases? That clearly shows that the trade-off between doing things in the MakeMove (i.e. incrementally) as opposed to the leaves or internal nodes (from scratch) is independent of depth, as the ratio MokeMoves/node is independent of depth, and just depends on branching factor.

The way I thought about it was with gettimeofday().

Crafty versions prior to 6.0 did an incremental attacks update. 6.0 threw that out by using rotated bit boards and generating on the fly as needed...

[stegemma]

[...]
Crafty versions prior to 6.0 did an incremental attacks update. 6.0 threw that out by using rotated bit boards and generating on the fly as needed...

...so now you only need to implement a "rotated bitboard incremental attacks update"

[bob]

[...]
Crafty versions prior to 6.0 did an incremental attacks update. 6.0 threw that out by using rotated bit boards and generating on the fly as needed...

...so now you only need to implement a "rotated bitboard incremental attacks update"

I initially did. Joel Rivat and I tested this (he had an engine "ChessGuru" that played on ICC all the time. We both concluded with independent tests and independent programs, that direct attack calculation was faster than incremental attack updates...

At least for our codes..

[hgm]

And then when you make/update, the last one is always wasted since you must eventually reach a node where you don't search anything and just stand pat.

But in a good implementation, you would of course skip the update in that case. There is liitle point in comparing speeds if the implementation sucks.

[bob]

And then when you make/update, the last one is always wasted since you must eventually reach a node where you don't search anything and just stand pat.

But in a good implementation, you would of course skip the update in that case. There is liitle point in comparing speeds if the implementation sucks.

How would you know? You are trying a capture at ply=N. How do you know there will be no good captures at ply=N+1 and therefore you can avoid the incremental update stuff? How do you know whether or not your search will try a checking move at ply=N+1? Seems to me you have to get there before you know you are going to get there.

[hgm]

How do you know there will be no good captures at ply=N+1 and therefore you can avoid the incremental update stuff?

This is not difficult/expensive at all. Captures you have at ply N+1 must already be in the old attack map, or must be discovered slider moves, which are in the old attack map as enemy slider attacks to the from-square. The latter are rare: in typical chess positions most moves will not discover any sliders at all. Existing attacks in the old attack map can have disappeared, because the attacker was captured with the last move, but these are easily filtered out.

[hgm]

How do you know there will be no good captures at ply=N+1 and therefore you can avoid the incremental update stuff?

This is not difficult/expensive at all. Captures you have at ply N+1 must already be in the old attack map, or must be discovered slider moves, which are in the old attack map as enemy slider attacks to the from-square. The latter are rare: in typical chess positions most moves will not discover any sliders at all. Existing attacks in the old attack map can have disappeared, because the attacker was captured with the last move, but these are easily filtered out.