Endgame database generator source code

[TAILLE]

Yes, I think you can use an 'iterator' to move sequentially through all the positions, and it should be a little faster than indextoposition().

You are right Ed I would like to experiment the use of an iterator. The point is that I use the indextoposition routine only when I look to all positions sequentially. In all other case I need only the positiontoindex fonction.

it means that you cannot store indicies when you do reverse non-conversion passes -- instead you have to store positions in your resolved queue instead of indicies.
-- Ed

I do not understand what you mean. Can you clarify this point ?
Gérard

[Ed Gilbert]

it means that you cannot store indicies when you do reverse non-conversion passes -- instead you have to store positions in your resolved queue instead of indicies.
-- Ed

I do not understand what you mean. Can you clarify this point ?
Gérard

There are two ways to do non-conversion passes. In the 'forward' method, you iterate over all indicies in the subdivision and try to further resolve each position until you finally make a pass over all the indicies and were not able to resolve any of them further, then you are done. While doing this, on the first few passes you may resolve a large percentage of the positions, but you may have to make very many passes to get all the positions resolved. For positions that have e.g. MTC values 100, you have to make 100 passes. If you visit every position for 100 passes, that takes a long time. There is another way, the 'reverse' method, which works like this: each time you make a pass over the indices, you write to a queue the indicies (or positions) which you resolved on the last pass. On each successive pass, instead of visiting every position, you build a reverse movelist from the positions you resolved on the last pass, and only visit those positions that are predecessors of the resolved positions. These predecessor positions are the only ones that can change (immediately) because of a changed value in the previous pass. After a few non-conversion passes, the percentage of positions that get resolved on each pass relative to the total number of positions in the subdivision is very small, and it is more efficient to only visit predecessors of positions that got resolved on the previous pass than to visiit all of them. I use this method, and when I write a queue of resolved positions, I write the indicies in the queue, not the bitboard of the positions, thus the queue is much smaller. But then on the next pass I need to read the indices from the queue and call indextoposition to get the positions that were resolved. You can't do that if you only have an iterator.

-- Ed

[TAILLE]

There are two ways to do non-conversion passes. In the 'forward' method, you iterate over all indicies in the subdivision and try to further resolve each position until you finally make a pass over all the indicies and were not able to resolve any of them further, then you are done. While doing this, on the first few passes you may resolve a large percentage of the positions, but you may have to make very many passes to get all the positions resolved. For positions that have e.g. MTC values 100, you have to make 100 passes. If you visit every position for 100 passes, that takes a long time. There is another way, the 'reverse' method, which works like this: each time you make a pass over the indices, you write to a queue the indicies (or positions) which you resolved on the last pass. On each successive pass, instead of visiting every position, you build a reverse movelist from the positions you resolved on the last pass, and only visit those positions that are predecessors of the resolved positions. These predecessor positions are the only ones that can change (immediately) because of a changed value in the previous pass. After a few non-conversion passes, the percentage of positions that get resolved on each pass relative to the total number of positions in the subdivision is very small, and it is more efficient to only visit predecessors of positions that got resolved on the previous pass than to visiit all of them. I use this method, and when I write a queue of resolved positions, I write the indicies in the queue, not the bitboard of the positions, thus the queue is much smaller. But then on the next pass I need to read the indices from the queue and call indextoposition to get the positions that were resolved. You can't do that if you only have an iterator.

-- Ed

Yes it is clear now.
My algorithm is somewhat different. As soon as I find a new losing position I immediatly generate the predecessors in order to mark them as winning position (if this position is of course not already resolved). That limit also the number of passes and you can see why I do not generate at the same time the DTC table.
I tried in the past to combined this method with yours but I do not manage to obtain good results.
Anyway I do not see the problem with your approach : in parallell of handling the iterator you keep up to date the index of the position by just incrementing it. Because handling the iterator can be a very fast operation made in cache it seems to me a good idea comparing to use the indextoposition routine.
Gérard