reuse of generated moves?

[Casper W. Berg]

The fact that many of the legal moves on one side of the board are the same between turns has made me wonder if it could payoff to keep track of which ones could be reused and thereby save some computation time.

I figure it might be dependant on the engine, e.g. if you use rotated bitboards or a more primitive data structure.
I keep track of all threatened squares in my own program, and I reuse that information in situations where the threats haven't changed for the player who didn't make the last move, i.e. the pieces haven't moved. This gave me a significant speedup!

I imagine something like ruling out files and diagonals (including the kings' to avoid checking problems) for reuse for each move made on the board. That combined with keeping track of each piece's legal moves could make up such an algorithm, but the question is if the bookkeeping is worth it...

Does anyone have any experiences with something like that?

[Dann Corbit]

How is your idea different from an eval hash (commonly used by many strong programs)?

I am not sure I understand it clearly.

[H.G.Muller]

Long ago I tried to design a move generator that kept multiply linked lists of moves around, that were differentially updated. The idea was that this made it easy to retrieve all moves that went to a particular square, or over a particular square.

It never really paid off. The updating of the listst was a lot of work, since a single move can change a lot in the tables, creating new moves that pass over the evacuated square, blocking moves on the destination, and of course redefining all the moves of the moving piece. And on taking the move back you would have to undo all that, which is just as much work. (Or make a complete copy of all lists before changing them, which was even more work.)

Very often most of the work was done in vain: In the new position, the first move that was tried could give a cutoff. Of course the lists are taken deeper into the tree of the single move that causes the cutoff, but by the time it is used deeper in the tree it is changed so much that we might as well have generated it from scratch. The problem is that most moves in a particular position are due to pieces that have many moves, and if you move those pieces most of those many moves change...

So at the moment I see more in the approach of selective move generation: In stead of first generating all moves, and then sorting them in the order you want to search them, generate them in the order that you want to search them, so you can search each move immediately as it is generated, without having wasted time on the generation of others if one of your early moves produces a beta cutoff.

For instance, if you would sort according to MVV/LVA, you could start generating captures of the King (which you don't search at all), and next captures of the Queen, and generate them with the Least-Valuable Attacker first by running through your piece list low to high. After the captures you could generate non-captures, starting with the highest piece, just in case it is under threat. Of course you can learn from the moves that have already been tried, if one of the available captures (say BxR) was refuted by PxQ, you might deduce that there is a threat against your Queen, and that it is has higher priority to try a non-capture to save the Queen than to try RxR or BxN.

All this only applies in 'frontier nodes', that you search for the first time. On later iterations the moves have already been generated and you can sort (or pick) them in the order of the score they received on the privious iterations. You could also make it depend on the window: if you are likely to be in an alpha node the move sorting is irrelevant and you will need to search them all. So you might go for the slightly cheaper mode of move generation piece by piece in that case.

[Casper W. Berg]

How is your idea different from an eval hash (commonly used by many strong programs)?

I am not sure I understand it clearly.

My idea is not about the evaluation it is about generating the legal moves.
A high percentage of the legal moves in a position don't change from turn to turn on average, so my idea is to save some generating work.

Long ago I tried to design a move generator that kept multiply linked lists of moves around, that were differentially updated. The idea was that this made it easy to retrieve all moves that went to a particular square, or over a particular square.

Well, my idea is also rather to keep a list of the moves FROM the squares, i.e. a particular piece. For instance knights will in many cases have the same legal moves

So at the moment I see more in the approach of selective move generation

I have also thought about implementing that, thanks for reminding me!
Then of course, the other idea should just be used for internal nodes.


[/quote]

[Casper W. Berg]

It could be something like this in pseudo code:

function do_move(move m){
make_move(m)
set_non_reusable_files_and_diagonals(m)
}

function generate_moves(board){
for each piece p
if(is_reusable(p)) list.add(get_moves_from_list(p))
else generate_moves(p)
return list
}

[Volker Böhm]

Hi,

I implemented an incremental move generator in Spike, but it was slower than the lazy one.
The problem with the incremental move generator is that you have to update all moves. The lazy move generator often only generates one or few moves.

Greetings Volker

[H.G.Muller]

Well, my idea is also rather to keep a list of the moves FROM the squares, i.e. a particular piece. For instance knights will in many cases have the same legal moves

The point is that moves from a square are very trivial to generate. Especially for a Knight, you just have to look in 8 places if the square is on the board, and if it does not contain your own piece (and perhaps you did not even care about that, if you are also interested in pseudo-captures for a SEE). The latter tests can be combined in a board representation with a 'guard band' of immobile pieces around the edge.

Stepping through an existing list easily causes more overhead (e.g. in a linked list you have to follow the pointers) than what you save. You probably have to check anyway what is in the target square now, even if the move existed 2 ply ago you could have blocked it then by moving into the square with another piece, you could have created a move that was previousy blocked by taking the blocking piece away, or what used to be a piece of yourself can now be an enemy piece because of a capture on the previous ply.

For sliding pieces it is worse, because their distant moves can be blocked by friendly or enemy pieces. If you only keep the listst sorted by FROM square, you have no quick check as to which moves you block. You would have to go through the list starting from the piece position, and check if the list is stil valid to the end of the ray, and if it is, if it should be extended there. But this is exactly the same as what you would do in 'lazy' move generation.

If you also sort them by TO square, you have a quick access to any blocked moves, and can follow the FROM lists ftom where you entered them (at the blocked/unblocked square), extending or clearing them.

Your idea of doing it only to ranks, files or diagonals where there was activity might buy you something, although in the 2 intervening plies 4 ranks and 4 files might be 'polluted', so you still would hav to do about half the work. Direct pointers into the lists that were affected (from the TO squares) would be more selective, but creates the overhead of updating those pointers. It proved a very sticky problem...

[Casper W. Berg]

Your idea of doing it only to ranks, files or diagonals where there was activity might buy you something, although in the 2 intervening plies 4 ranks and 4 files might be 'polluted', so you still would hav to do about half the work. Direct pointers into the lists that were affected (from the TO squares) would be more selective, but creates the overhead of updating those pointers. It proved a very sticky problem...

Yes, I have also thought about this. I would discard all 'polluted' lists so that you only reuse moves from those pieces which are exactly the same.
Then the will be no need of iteration through the lists, you can just append all to the list of legal moves.

Trying to select some out would surely cost more than generating from scratch as you point out. If you only update 4 ranks and files (in the worst case, there might be a lot of overlaps), this is only 8 booleans to update, which is quite cheap compared to the possible gain as I see it.
But still, keeping track of all those lists is somewhat expensive, so I think it's very hard to predict if there is something to gain.

Of course, this is also dependant on how fast your move generation is.

[H.G.Muller]

Well, move generation per se can be about as fast as they come. For most moves (when previous moves with the same piece in the same direction have already been generated, i.e. in the inner loop of your move generator) it is simply adding a step vector to a square number, and testing the color of the piece you will find on that square (assuming off-board sqares are occupied by pieces that both sides recognize as their own). In assembler that would be only two elementary operations, plus two branch instructions to make a loop and break out of it. Now and then you have to switch to another direction, and then it takes a little longer.

But most of the effort probably goes into doing something with the move you just generated. You might want to copy FROM and TO squares to a newly created element on your move stack, for later sorting. And probably some staus bits with it, to tell if it is a pawn promotion, an e.p. capture or a castling, plus perhaps the piece that moved and what was captured). I guess you would have to do that also if the move comes from a list that you kept from a previous ply, because you probably don't want to confuse the previous owner of the list (who still might be using it) by changing anything in it (it might have to be sorted differently).

Perhaps if you would put only pointers on your move stack that point to elements in the listst that contain the full description of the move... But then you would need an extra pointer de-reference every time you wanted to access any of that information. Alas, nothing is for free...

[Casper W. Berg]

The strongest programs use the advantage of bitboards to generate moves, whereby all moves for each type of piece is generated with 64-bit operations. I'm am not sure if the fact that many legal moves in a position are the same between two plies, can be used in this respect (?)

But many engines, like my own, are not based on bitboards.
I use a static pool of pointers to the moves indexet by from- and to-squares, piece-type, and color like you mention last, HGM.
I like to keep it like that for a while, because I finally haven't seen any bugs in the move generator for a great number of games

The right place to start the discussion is perhaps: how many percent of the time that your engine is using, is used for generating moves?

[Volker Annuss]

Hello Casper,

for my bitboard engine I already thought about
for some piece types and for every start square store one bitboard of reachable squares and a list of moves to all these squares. If the bitboard of reachable squares stored is identical to those in the current position, generate the moves by a single memcpy, else generate them the normal way and store them.

The right place to start the discussion is perhaps: how many percent of the time that your engine is using, is used for generating moves?

That's the point. Move generation takes between 10% and 15% of the total time only (if I remember correctly. I did not profile my code for a long time), so I did not test the idea until now. I have no Idea, what hit rate one can achieve for which piece type and how much time (if any) can be saved.

One day I will try it, but until then there are many other interesting ideas to test (but most of them fail).

Greetings
Volker

[smcracraft]

The fact that many of the legal moves on one side of the board are the same between turns has made me wonder if it could payoff to keep track of which ones could be reused and thereby save some computation time.

I figure it might be dependant on the engine, e.g. if you use rotated bitboards or a more primitive data structure.
I keep track of all threatened squares in my own program, and I reuse that information in situations where the threats haven't changed for the player who didn't make the last move, i.e. the pieces haven't moved. This gave me a significant speedup!

I imagine something like ruling out files and diagonals (including the kings' to avoid checking problems) for reuse for each move made on the board. That combined with keeping track of each piece's legal moves could make up such an algorithm, but the question is if the bookkeeping is worth it...

Does anyone have any experiences with something like that?

It sounds like you want to implement something like I heard about which is a set of rules that determine for any given board position after the last move which pieces (for both sides) have to have their moves and/or attack maps updated.

The point being that you run these rules, determine the affected pieces,
delete their moves and entries from the move list and attack maps
and then regenerate both for just those pieces.

This seemed to me like a good idea when I first heard of it. I don't
recall if it was Slate/Atkin in Chess 4.x or Frey/Slate in Chess 0.5
or whatever, but it seemed decent.

I know of no published papers that compares the cost of such
(re) generation with a standard move generator searching through
the piecelist and regenerating the move list and attack maps fresh
each time.

Some choose instead to just generate a few moves at a time and
see if a cutoff can be achieved before more moves need to be
generated.

Again, I know of no studies comparing incremental update/downdate
of movelists/attackmaps with non-incremental with simply partially
generating moves in a fragmented series with searches inbetween.

Part of the issue is the complexity of doing the comparison, choosing
how to compare, since the search would be involved in the last of
the three above.

Stuart