Differential move generation

[H.G.Muller]

I am back on the topic of differential move generation, because I realized that in the end leaf of a tree (by far the most abundant node type...) the side that is to move only sees its move list of the underlying node changed by a move of the opponent. This means that changes in the list only can come about through loss of a piece in the last ply (requires no change of the list, just skip the listed moves for that piece, as you would also do when it is pinned on the King), or to blocking / unblocking of my Sliders. The latter are moderately uncommon events. (e.g. On a capture there are no blockings.) When differentially updating, by far the most costly part is usually to delete and add the moves of the piece that you moved yourself.

So typically, the amount of work in a node where we don't actually do any moves would be very little. Only if we decide that one of the moves already in the list or an unblocked one is interesting enough to try (e.g. it is a good capture or a check), we need to update the lists before actually searching that move. (And alas, undo the changes later.)

In particular when we only do this for our capture generator, the number of new moves due to unblocking will be very small: each unblocked ray gives at most one new capture, while it might give many new non-captures. So I am leaning to a mixed approach, where the captures are generated differentially, (and are organized in an attack table), while the non-captures are generated by oldfashioned ray-scanning over the board.

Has anyone played with such ideas?

[Gerd Isenberg]

Has anyone played with such ideas?

Yes, i did differential update in my former dos-program. It was quite ok, despite i probably oversized the concept with huge make/unmake by updating/copying not only move-lists but also attack-sets, enprise pieces etc. Specially in queen endings it becomes rather inefficient.

I the meantime i prefere cheap make with zero unmake, something like 64-byte xor including 16-bit and/add with one conditional branch if castle rights/ep-state changes.

Code: Select all

node[i+i] = node[i] (+) delta[moveIdx]


It also depends how many cheap leaf-nodes, where 3-fold rep, hash-hit, lazy-eval cuts etc., occur - and whether you check such issues before to prune those moves before make...

Gerd

[Uri Blass]

Has anyone played with such ideas?

Yes, i did differential update in my former dos-program. It was quite ok, despite i probably oversized the concept with huge make/unmake by updating/copying not only move-lists but also attack-sets, enprise pieces etc. Specially in queen endings it becomes rather inefficient.

I the meantime i prefere cheap make with zero unmake, something like 64-byte xor including 16-bit and/add with one conditional branch if castle rights/ep-state changes.

Code: Select all

node[i+i] = node[i] (+) delta[modeIdx]


It also depends how many cheap leaf-nodes, where 3-fold rep, hash-hit, lazy-eval cuts etc., occur - and whether you check such issues before to prune those moves before make...

Gerd

I do not understand your idea of zero unmake.
How can you avoid unmaking moves?

I also do not understand the meaning of your code
nodes[i+1]=nodes[i]+...




Uri

[Gerd Isenberg]

I do not understand your idea of zero unmake.
How can you avoid unmaking moves?

I also do not understand the meaning of your code
nodes[i+1]=nodes[i]+...

Uri

oups there was a typo...

I have a stack of positions. So making move is

Code: Select all

pos[i+1] = pos[i] someXorAndAddOp delta[moveIdx]; // instead of modeIdx


So i have all previous positions at ply-index i,i-1,...0 and there is no need to unmake, since this is a copy/make approach and unmaking is simply decrementing ply. As you can see, the delta array is quite huge since i enumerate all moves in some arbitrary order, of course considering different capture targets. Each node structure is 64-byte, somehow a nibble[64] array, 64-bit hashkey, pawn-hashkeys, castle-rights, ep-state, some piece counters etc..

Gerd

[Pradu]

@Gerd. Wow, copying positions is faster for you than a takeback?

[Gerd Isenberg]

Ok, i modify one cacheline almost with three sse2 xors and one pand/padd. Of course it eats some cachelines on the ply-stack, but i think one cacheline per ply is quite acceptable and has some merits with K8L in mind... and probably also splitting node with multiple threads.

I have a 3 MByte preinitialized delta table which worries a bit more - and i hope during the search the move-indizes don't vary too randomly. But clearly i am careful with other huge lookups...

[H.G.Muller]

Sometimes it is a close call between copying and undoing changes. This is what always killed my differential move generation attempts before: I was also keeping way too much information, every moves in multiple doubly linked lists (by from square and to square and captures/non-capture lists). To delete all moves from all these lists with a Queen from the from-square, and then adding the new moves from the to-square, was a disaster. Especially since you had to undo it afterwards.

(I even considered building special hardware to do it: replace the DRAM chips in my computer for Video Rams, that had special memory cycles that could copy an entire memory page to the video shift register, or back. With that I could have copied (1K-aligned) memory blocks of 1 KB in two memory clocks! Still have the chips somewhere, never built it... )

But if you only keep an administration of slider moves to occupied squares, (captures or own-captures) it becomes quite managable. Even a Queen only has 8 of those, and I can keep them in an array by from-square (since the number of directions emanating from that square is fixed and a modest 4 or 8), and I then link them in only one doubly linked list (hanging from the attack tables by to-square). So if the only thing I have to update and undo is unlinking these 4 or 8 cells and creating 4 or 8 new ones (that are simply discarded on undo), it is very competative. Especially since the unlinking and relinking in the attack tables can be shared by all moves with that same piece.

And the whole thing can be skipped in the horizon nodes since only the other side attempts to moves there.

So that only leaves the blocking and unblocking. Unblocking is very easy, since the sliders to be unblocked are directly found in the attack list for the from square. You just have to scan the ray to the next block, and usually there aren't any rays to scan at all. Also this can be shared by all moves of the same piece.

Blocking is nasty, because moves to empty squares are not kept, so there is no way to know which sliders move over an empty to-square. So you would have to do a 0x88-style attack test to the to-square, from all sliders of each side. (So typically 10.) This might spoil the whole thing (although undo is comparatively trivial). But what still attracts me in the scheme, is that blocking does not occur at all on captures. So in QS it might be very attractive.

Especially in nodes where in the end no captures are done. After only deleting the moves of my captured piece and adding the unblocked moves, all captures are basically listed. Per target square, so MVV/LVA is easy.