Sliding-path for incremental move generation

[stegemma]

I'm testing this new way to compute incremental moves, in Satana. It seems enough good but still i need some work, to make it better than non-incremental generator. The idea is simple:

- i save source/destination square as 64 bit values
- i save the sliding-path needed to reach dst square, in any single move
- i save the sliding direction too (for me is just some bit in move's flags that i already save for other purposes)
- after have done a move, i test the executed move against any move of both colors, to know if they're still valid

The first attempt was to simply copying the valid moves to the new moves array then i've switched to two distinct arrays: one for the moves and one for the moves pointers. I don't copy the whole move but only add the pointer to the move pointers array when i find a valid move.

Choosing for valid moves requires some test. If the executed move ends to the src square of testing move, that move is invalid (the piece has been captured or is the moved piece itself). If the dst square is on the sliding path, the move could be invalid or the moved piece has been captured by the testing move. If the src move was on the sliding-path, the move itself is valid and could becomes a non-capture, then it should be extended through the sliding-direction saved in the move. There are other cases, to handle special moves and so on. After have validated all the moves, i compute from scratch those of the moved piece. I should save some virtual move, to handle move extension when a piece "captures" one friend piece that moves away (the moves becomes valid and should be extended) or a pawn "captures" an empty square reached by the moved piece. Castling and en-passant should be handled separately.

Non sliding pieces still have sliding-path in the form of two bits: src+dst square. This let the algorithm works well even for this cases, just they don't need to extend moves, when the moved piece starts from dst square.

One side-effect is that i always have all the moves of both colors ready to be executed or just tested for evaluation function and any other needing, as testing for checks. Handling a moves pointers array instead of moves could speed-up sorting of moves, i should test for this.

[hgm]

I am not sure what your goal is here. If you have to loop through all moves to check them individually for which are still valid, there doesn't seem any speed advantage in it. The whole attraction of doing things incrementally is that you won't have to spend any time on everything that already existed, and continues to exist, and only spend time on things that alter.

[stegemma]

I am not sure what your goal is here. If you have to loop through all moves to check them individually for which are still valid, there doesn't seem any speed advantage in it. The whole attraction of doing things incrementally is that you won't have to spend any time on everything that already existed, and continues to exist, and only spend time on things that alter.

The idea was that saving moves is the slower part (in my engine) and maybe saving only a pointer instead of 3/4 64 bit values could be better. I should complete all the kind of moves and use some trick, to speed-up further but, for now, it seems not slower than generating moves from scratch, just because testing for legality becomes easier with this method. In case of a move that open a ray on its own king, leaving him in check, it could be faster than the from-scratch generation. Another point is that i still have to add hashing of any move and this could be faster, do to the way i generate moves.

Incremental move generation has always been interesting to me, i would like to have it working almost at the same speed of the from-scratch one, to be happy

[hgm]

Well, I am also very much interested in incremental move generation. In particular for my engine HaChu, where I want to implement these large Shogi variants that us 2 x 96 pieces on a 19x19 board. There generating all moves from scratch in every node would be quite expensive, while a single move affects only a very small fraction of the existing moves.

But of course making and searchin a move will always be far more expensive than generating it from scratch. So the only cases where you can save significant effort is in cut-nodes or leaf nodes, where you only search very few moves. You then can save a lot on not generating the moves you don't want to search. It is really the process of generating moves just to conclude that they were not interesting enough to search (e.g. because they are non-captures, not checks, or futile captures) that wastes so much time.

So I am looking for incremental methods that efficiently produce the non-futile captures and checks. So keep around a set of capture moves, pre-sorted by victim value. And then add or remove incrementally from the sets for each victim. During this adding of new moves it can also keep track incrementally of the highest attacked victim (i.e. if attacks were created on a more valuable piece than the current MVV). This makes it possible to run through the piece list from the MVV down until you reach the futile victims.

[Henk]

When my move generator gets to the remaining moves it generates all moves again and removes from them the moves that were passed like captures, promotions and killers.

I don't have a procedure to recognize non-captures.

I need to generate all moves otherwise I can not sort them.

[stegemma]

A lot depends on how the engine is structured, of course. In the last version of Satana, both with and without incremental generator, i don't use a piece array anymore.

I don't know if generating a single move or validating one would be the same, as speed. When the engine generates a move, it should computes the new position (sliding bits or adding an index and so on) then test for destination square and finally saves or not the move. In incremental approach, it should compare sliding-path of an existing move with the source/destination squares of the previous move then save or not a pointer. The number of moves to generate or to test seems to be almost equal. Of course with bitboard or magic-birboard this could be different, but i don't use it.

Any move already have the information to know the piece it captures, so it would be very fast to find the best move to play and then validate it only if we play it, to achieve a good speed-up on leaves, as you say.

[hgm]

Perhaps I don't fully understand your design, but it still sounds like you have a list of moves, and then have to loop through all of them to figure out if there is a move to play. (And in the large majority of nodes there would be no such move, as almost all nodes are leaves.)

I would like to eliminate such looping wherever I can. E.g. keep a word for every victim, which flags attacks from each of the possible directions. And if that word would be non-zero (meaning there are attacks on that piece), set a corresponding flag in a piece-set word. So that the Search() loop over moves would consist of extracting the bit corresponding to the next-valuable attacked opponent, fetch the corresponding set of attack directions, (if the victim was non-futile) extract those one by one, to look in a table indexed by square and direction what the distance to the closest piece in that direction is (which then must be the attacker).

Incrementally generating new moves, or deleting old moves, would then go accompanied by setting or clearing the flags in the direction set of the corresponding victim, and, update the corresponding flag in the piece-set word accordingly.

[stegemma]

Really when i loop through the moves i get that the most of them are playable, because the previous move has changed only a little of them. In my engine, i creates all the moves, even on leaf nodes, this is why i get the same results, from both approach. Using the move list, maybe i could avoid the full validation on leaves and only keep captures... but, for now, i don't have quiescence.

I know you're idea of keeping flags with direction of attacked pieces. I'm exploring various solutions fior incremental move generation, for sample, even a way to keep moves inside any single square... but still i've not found one really interesting, but the one i'm trying.

When i were young, i've think about a move generation where moves were defined geometrically, in the classical line formula: y = ax + b and so on... i was studying at school that formulas and they appears interesting maybe today they can applyed in GPU or using SIMD but l'et's go with this simple sliding-paths, for now.

[hgm]

One of the advantages of generating moves incrementally is that you also can keep track of mobility incrementally. You know the number of extra moves sliders get when you unblock them, because you have to find the new piece their elongated move attacks anyway. And generate the moves of the moved piece from its new position.

[stegemma]

One of the advantages of generating moves incrementally is that you also can keep track of mobility incrementally. You know the number of extra moves sliders get when you unblock them, because you have to find the new piece their elongated move attacks anyway. And generate the moves of the moved piece from its new position.

Maybe another good thing (that works better against humans) is to know where the last move point to. When an human not very strong attack somewhere, our attention, as human player, would be on the last move of our opponent, we ask ourself "what he/she's doing with that move?". This could be used to give the software some kind of attention to the squares involved in the last move: squares of extended slice-paths and squares reached by the last moved piece, when we compute new moves from scratch. i would try this, if it's not too many heavy.