using a neural network as an IDA prune table

[dwalton76]

I tried to use a neural network to estimate how many moves it would take to solve the centers of a scrambled 4x4x4. I figured if I could get this to be accurate enough I could use it as a prune table. I did not have any luck though...I could only get it guess the move count correctly 9% of the time.

I do not know a ton about neural networks though...just read a few books.

Has anyone tried this approach and had any luck with it?

 

[qq280833822]

As you mentioned, only 9% of the output values are correct. However, even if it always return 10 (or 11, 12, depends on the depth distribution of the centers of 4x4x4 cube,) the correctness rate might be more than 9%.

Furthermore, to use it as a pruning table for IDA* algorithm, the network should not return any overestimated value. Otherwise, the IDA* algorithm might loss the optimal solution.

 

[dwalton76]

the network should not return any overestimated value

My thinking is that an optimal solution would not be required so returning an overestimated value would be ok. For instance if one NN could somewhat accurately estimate the number of moves required to solve the centers of a 4x4x4 and another NN could estimate the number of moves required to pair the edges then would it be possible to reduce a 4x4x4 to a 3x3x3 in a single phase IDA* by using these two NN prune tables? The solution would not be optimal but it would be such a huge search space so you might be able to get a shorter solution than is possible today with multiple phases for reduction.

I found a few papers on using NNs for IDA* heuristics...the first one is specifically for solving 3x3x3 cubes
http://ceur-ws.org/Vol-1885/57.pdf

and then these for 24-tile puzzles
https://www.cse.iitk.ac.in/users/cs365/2012/submissions/vinitk/cs365/projects/report.pdf
https://ac.els-cdn.com/S00043702110...t=1520353546_9260aae29c5e461d53bc926326719673

The first one looks interesting, they got some decent result. I haven't red the 24-tile papers yet.