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...bob wrote:[...]
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.[...]
Incremental update
Moderators: hgm, Rebel, chrisw
-
- Posts: 859
- Joined: Mon Aug 10, 2009 10:05 pm
- Location: Italy
- Full name: Stefano Gemma
Re: Incremental update
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com
http://www.linformatica.com
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Incremental update
Well, apparently this is a wrong way to think about it, as it leads to a faulty conclusion.bob wrote:Think about this. ...
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Incremental update
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.stegemma wrote: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...bob wrote:[...]
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.[...]
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Incremental update
The way I thought about it was with gettimeofday().hgm wrote:Well, apparently this is a wrong way to think about it, as it leads to a faulty conclusion.bob wrote:Think about this. ...
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.
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...
-
- Posts: 859
- Joined: Mon Aug 10, 2009 10:05 pm
- Location: Italy
- Full name: Stefano Gemma
Re: Incremental update
...so now you only need to implement a "rotated bitboard incremental attacks update"bob wrote:[...]
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...
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com
http://www.linformatica.com
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Incremental 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...stegemma wrote:...so now you only need to implement a "rotated bitboard incremental attacks update"bob wrote:[...]
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...
At least for our codes..
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Incremental update
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 wrote: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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Incremental update
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 wrote: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 wrote: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.
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Incremental update
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.bob wrote:How do you know there will be no good captures at ply=N+1 and therefore you can avoid the incremental update stuff?
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Incremental update
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.bob wrote:How do you know there will be no good captures at ply=N+1 and therefore you can avoid the incremental update stuff?