Fast reverse move generation

[koedem]

Is there a known highly efficient algorithm for reverse move generation in near full boards? Possibly even an open source implementation? (might be mentioned on this forum but search seems to struggle for me right now)
On near full boards there are tricky things to consider, for instance one can't uncapture into an impossible material balance or one can't uncapture into a pawn structure that's impossible, e.g. doubled pawns against 16 opposition pieces. Of course there may be some highly nontrivial reasons why some unmoved positions may be reachable or not, however, if it is only very few of them as strange edge cases, that would be acceptable in my scenario. But there would be loads of ways to uncapture into "statically" impossible scenarios, I would like to avoid those. Wouldn't be too difficult to hack it together in a very slow way, but it seems tedious, prone to bugs and especially, slow to run. So is there work out there by some smart people who did it better than I could?

[petero2]

I recently added a reverse move generator to texel: https://github.com/peterosterlund2/texe ... 9a13dbea40

It can even be accessed from the command line using the "texelutil" program. For example:

[fen]Q1Nb1r1q/RRq4P/RQB1nq1Q/n1B5/k2rN1r1/6N1/Kb1Q1p2/7B b - - 0 1[/fen]

Code: Select all

$ texelutil revmoves "Q1Nb1r1q/RRq4P/RQB1nq1Q/n1B5/k2rN1r1/6N1/Kb1Q1p2/7B b - - 0 1"
d5c6 captP: - castle: - ep: -
d5c6 captP: Q castle: - ep: -
d5c6 captP: R castle: - ep: -
d5c6 captP: B castle: - ep: -
d5c6 captP: N castle: - ep: -
d5c6 captP: P castle: - ep: -
d7c6 captP: Q castle: - ep: -
d7c6 captP: R castle: - ep: -
d7c6 captP: B castle: - ep: -
d7c6 captP: N castle: - ep: -
d7c6 captP: P castle: - ep: -
e8c6 captP: Q castle: - ep: -
e8c6 captP: R castle: - ep: -
e8c6 captP: B castle: - ep: -
e8c6 captP: N castle: - ep: -
e8c6 captP: P castle: - ep: -

I don't know if it is fast/accurate enough for your needs though. When calling RevMoveGen::genMoves() more than once, you should make sure to reuse the vector object to avoid dynamic memory allocations.

[dangi12012]

I recently added a reverse move generator to texel: https://github.com/peterosterlund2/texe ... 9a13dbea40

It can even be accessed from the command line using the "texelutil" program. For example:

[fen]Q1Nb1r1q/RRq4P/RQB1nq1Q/n1B5/k2rN1r1/6N1/Kb1Q1p2/7B b - - 0 1[/fen]

Code: Select all

$ texelutil revmoves "Q1Nb1r1q/RRq4P/RQB1nq1Q/n1B5/k2rN1r1/6N1/Kb1Q1p2/7B b - - 0 1"
d5c6 captP: - castle: - ep: -
d5c6 captP: Q castle: - ep: -
d5c6 captP: R castle: - ep: -
d5c6 captP: B castle: - ep: -
d5c6 captP: N castle: - ep: -
d5c6 captP: P castle: - ep: -
d7c6 captP: Q castle: - ep: -
d7c6 captP: R castle: - ep: -
d7c6 captP: B castle: - ep: -
d7c6 captP: N castle: - ep: -
d7c6 captP: P castle: - ep: -
e8c6 captP: Q castle: - ep: -
e8c6 captP: R castle: - ep: -
e8c6 captP: B castle: - ep: -
e8c6 captP: N castle: - ep: -
e8c6 captP: P castle: - ep: -

I don't know if it is fast/accurate enough for your needs though. When calling RevMoveGen::genMoves() more than once, you should make sure to reuse the vector object to avoid dynamic memory allocations.

Can you post Megamoves/s for your movegen? So just time/nodes. Maybe even for kiwipete position?
Reverse movegen would be an interesting task to use to solve 8 man TB - for since the current implementation is not the fastest.

[dangi12012]

Now that I think of it..
What is reverse perft for the starting position?
Do the pawns ever move?
Is it just the knights jumping around?
No new piece can spawn since its already 32 pieces?

Questions over questions.

[koedem]

I recently added a reverse move generator to texel: https://github.com/peterosterlund2/texe ... 9a13dbea40

Thanks, that looks like what I was looking for. So it does look at impossible piece configurations as I'd hoped. (in fact I might even exclude promoted pieces, at least more than one promoted piece)
As I understand it, it does not consider the slightly more advanced but still relatively basic question of un-pawn captures? So reasoning of the like of "You can't have a doubled pawn if the opponent has 16 pieces", or slightly more complicated, you can't have a doubled pawn with neighbours on either side, (read, d2 e2 e4 f2) if the opponent has 15 pieces still. (so if the opponent has 14 pieces you can't un-capture e4xd5 there, only c4xd5)
Do you think that would be complicated to add / slow down move generation a lot? I think those would be the main scenarios that I would like to avoid, what happens at 14 pieces or less I don't care about as much. But I don't know enough about surely existing smart representations of pawn structures that make this easy or not.

Also, just out of curiosity, what are you using it for?
I was wondering about shortest lines to reach some positions e.g. from the starting position, so there possibly with a reverse move generator one could meet in the middle, i.e. to find a depth 13 position I could generate all depth -6 positions from that target position, then do a depth 7 forward search trying to find any of them.

[petero2]

I recently added a reverse move generator to texel: https://github.com/peterosterlund2/texe ... 9a13dbea40

Thanks, that looks like what I was looking for. So it does look at impossible piece configurations as I'd hoped. (in fact I might even exclude promoted pieces, at least more than one promoted piece)
As I understand it, it does not consider the slightly more advanced but still relatively basic question of un-pawn captures? So reasoning of the like of "You can't have a doubled pawn if the opponent has 16 pieces", or slightly more complicated, you can't have a doubled pawn with neighbours on either side, (read, d2 e2 e4 f2) if the opponent has 15 pieces still. (so if the opponent has 14 pieces you can't un-capture e4xd5 there, only c4xd5)
Do you think that would be complicated to add / slow down move generation a lot? I think those would be the main scenarios that I would like to avoid, what happens at 14 pieces or less I don't care about as much. But I don't know enough about surely existing smart representations of pawn structures that make this easy or not.

I already have code to do that type of analysis (and more advanced things too, see ProofGame::distLowerBound()) but it is not part of the RevMoveGen class since it was not needed for my use case. In my case I do much more advanced analysis (but only for captures) to try to detect illegal positions. This analysis can take several seconds in some cases though.

Also, just out of curiosity, what are you using it for?

It is a part of the code I developed to determine if a chess position is legal, i.e. if it can be reached from the starting position by playing a sequence of legal moves. See also this thread.

I was wondering about shortest lines to reach some positions e.g. from the starting position, so there possibly with a reverse move generator one could meet in the middle, i.e. to find a depth 13 position I could generate all depth -6 positions from that target position, then do a depth 7 forward search trying to find any of them.

If you just want to find the answer for some position you could try the "texelutil proofgame" function. For example:

Code: Select all

$ texelutil proofgame "r1bqk2r/2ppbppp/p1n2n2/1p2p3/4P3/1B3N2/PPPP1PPP/RNBQR1K1 b kq - 5 7"
min cost: 13 queue: 0 nodes: 0 time: 8.299e-06
Q:0 R:0 Bd:0 Bl:0 N:0 P:0 sP:0
q:0 r:0 bd:0 bl:0 n:0 p:0 sp:0
13 -w 1:1 queue: 879 nodes: 66 time: 0.00433577
e4 b5 Bc4 e5 Nf3 a6 O-O Be7 Re1 Nc6 Bd5 Nf6 Bb3
nodes: 66 time: 0.00729203

The proofgame code uses A* search with a heuristic function based on solving an assignment problem obtained by a relaxation that assumes piece movements do not interfere with each other.

I guess that this A* method is more efficient than a meet in the middle algorithm.

[koedem]

The proofgame code uses A* search with a heuristic function based on solving an assignment problem obtained by a relaxation that assumes piece movements do not interfere with each other.

I guess that this A* method is more efficient than a meet in the middle algorithm.

Interesting, does this then also allow pawn captures from any position? Since that would be the one time piece movement interference would be actively helpful.
For most positions that A* method should indeed be much better, though I was wondering in particular about unique proof games of a certain length, like you might have them in a puzzle. So that might make it harder for the A* search to find that one very narrow path. To give a specific example, a classical puzzle is to reach this position in 8 half moves: rnbqkbnr/pp3ppp/2p1p3/8/4P3/8/PPPP1PPP/RNBQK1NR w KQ - 0 5
For the A* search it would be trivial to reach it in 6 half moves, however doing it in 8 requires some cleverness (which naturally is the whole point of this puzzle). So I am not sure how well one could even modify that search to achieve this? And then how well it would run. (might still be much faster to be fair) Also to point this out, I would want to use this to verify that uniqueness. So I don't just care about finding a solution but also proving there's no other solution with e.g. the same depth.

Meanwhile, for this of course the meet in the middle algorithm works just as well as for any other position. (which is to say, very slowly and requiring a lot of memory, but it works (for this small position it's actually quite fast, but if it was a 14 ply game instead, then the effort would be much larger))

[petero2]

The proofgame code uses A* search with a heuristic function based on solving an assignment problem obtained by a relaxation that assumes piece movements do not interfere with each other.

I guess that this A* method is more efficient than a meet in the middle algorithm.

Interesting, does this then also allow pawn captures from any position? Since that would be the one time piece movement interference would be actively helpful.

The heuristic function knows the rules for all piece types and solves shortest paths problems to determine how many moves it takes for a piece to get from one square to another. So it knows a pawn cannot go from a2 to c3 for example.

The "no interference" property can be explained with the following position:
[fen]rnbqkbnr/pppppp1p/6p1/R7/P7/8/1PPPPPPP/1NBQKBNR w Kkq - 0 1[/fen]


The algorithm knows that a pawn can go from a2 to a4 in one move and that a rook can go from a1 to a5 in one move, so it concludes that at least two white moves are needed. The fact that the pawn interferes with with the rook so that the rook actually needs 4 moves to reach a5 is ignored by the heuristic function. When the heuristic function underestimates the true distance to the goal, it means more search nodes are needed to find a solution.

For most positions that A* method should indeed be much better, though I was wondering in particular about unique proof games of a certain length, like you might have them in a puzzle. So that might make it harder for the A* search to find that one very narrow path. To give a specific example, a classical puzzle is to reach this position in 8 half moves: rnbqkbnr/pp3ppp/2p1p3/8/4P3/8/PPPP1PPP/RNBQK1NR w KQ - 0 5
For the A* search it would be trivial to reach it in 6 half moves, however doing it in 8 requires some cleverness (which naturally is the whole point of this puzzle).

My program gets this right kind of by accident because it also considers castling rights. Therefore it rejects the solution "e4 e6 Bb5 c6 Bxc6 dxc6" because black did not manage to lose his castling rights.

So I am not sure how well one could even modify that search to achieve this? And then how well it would run. (might still be much faster to be fair) Also to point this out, I would want to use this to verify that uniqueness. So I don't just care about finding a solution but also proving there's no other solution with e.g. the same depth.

My program remembers all positions it has visited, so I think something like this could work:

• If a node has length(path) + heuristic(pos) > desired solution length, throw the node away.
• If a solution is found but it is too short, ignore it and continue searching.
• For each visited position, also consider the number of moves it took to reach the position, i.e. the full move counter is included when determining if two positions are equal.
• For each visited position, also remember how many times it has been reached. (i.e. through transpositions)
• If a solution of the right length is found, remember its path. If any node in the path has been visited more than once, stop as the solution is not unique. Otherwise, continue searching.
• If another solution is found, stop as the solution is not unique.
• If any node in the solution path is visited again, stop as the solution is not unique.

There might be some complications I have not thought about though.

Meanwhile, for this of course the meet in the middle algorithm works just as well as for any other position. (which is to say, very slowly and requiring a lot of memory, but it works (for this small position it's actually quite fast, but if it was a 14 ply game instead, then the effort would be much larger))

A* also requires a lot of memory and typically fails for difficult problems because it runs out of memory.

[koedem]

Thanks for the detailed response, a lot of food for thought there, will have to think about it.
I'm thinking there might be some value in trying A* for a puzzle first and then have the possibly more robust meet-in-the-middle as a fallback if the first does not yield a result in reasonable time, or runs out of memory or something. I should definitely try to implement the A* and see how it does for the kind of problems I'm looking at.
On a completely different note, since you're probably seeing this post, did you see my DM a while back asking about Texel's SMP algorithm?

[petero2]

On a completely different note, since you're probably seeing this post, did you see my DM a while back asking about Texel's SMP algorithm?

I don't have any more documentation about Texel's SMP algorithm than in the thread you already found:

https://www.talkchess.com/forum3/viewto ... 40#p728817

I still use the same SMP/cluster algorithm in Texel.