koedem wrote: ↑Sun Dec 19, 2021 9:11 pm
petero2 wrote: ↑Sat Dec 18, 2021 9:08 pm
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.
