Heuristic Function takes too long to compute

[TalhaGoktopal]

I tried to implement the cube solver. Everything works but the heuristic function is taking to long to create the heuristic database for a depth of 20. I was only able to generate a database with depth 7. I am doing this project for my A Level Computer Science coursework so I don't have much coding experience. Would you be able to tell me what I'm doing wrong? I would really appreciate it.

`def buildHeuristic(state, actions, maxMoves= None, heuristic=None, Heuristic_Mode = None):
#state - initial state of cube (solved cube)
#actions - list of possible actions
#maxMoves - maximum number of moves that can be carried of to find solution
#heuristic - dictionary holding heuristic values for cube state

#Checks if a heuristic dictionary is given
if heuristic is None:
    heuristic = {state: 0}

#que constains state and current distance
que = [(state, 0)]
visited = set()
visited.add(state)

#Calculates the toatl number of cube states
nodeCount = sum([len(actions) ** (x + 1) for x in range(maxMoves + 1)])

with tqdm(total=nodeCount, desc = 'Heuristic') as progressBar:
    while True:
        if not que:
            break
        currentState, distance = que.pop()
        #Checks if the distance is greater then max moves to prevent excessive exploration
        if distance > maxMoves:
            continue
    
        #Applies all the posssible moves to the current state of the cube
        for m in actions:
            
        #Selects cube based on mode
            if Heuristic_Mode == "2x2":
                cube = miniRubiksCube(miniState = currentState)
            else:
                cube = RubiksCube(state = currentState)
            
            match m:
                case "R":
                    cube.R()
                case "L":
                    cube.L()
                case "U":
                    cube.U()
                case "D":
                    cube.D()
                case "F":
                    cube.F()
                case "B":
                    cube.B()
                case "R'":
                    cube.xR()
                case "L'":
                    cube.xL()
                case "U'":
                    cube.xU()
                case "D'":
                    cube.xD()
                case "F'":
                    cube.xF()
                case "B'":
                    cube.xB()

            #Stores new state as mStr 
            mStr = cube.cubeString()
            #If the new state has not been visited or the new distance if less then the origianl distance for that state
            if mStr not in heuristic or heuristic[mStr] > distance + 1:
                #Sets new distance
                heuristic[mStr] = distance + 1
            #Adds the new state and new distance to the que
            que.append((mStr, distance + 1))
            progressBar.update(1)

return heuristic

cube = RubiksCube()
actions = ["R", "L", "U", "D", "F", "B", "R'", "L'", "U'", "D'", "F'", "B'"]

heuristicDatabase = buildHeuristic(cube.cubeString(), actions, maxMoves = 20, heuristic = None)
#Creates heurisitc databse if it does not exist
with open("3x3Heuristic.json", 'w', encoding='utf-8') as file:
json.dump( heuristicDatabase , file , ensure_ascii = False , indent = 4)`

[bellerb]

So I think you might be doing everything correct. I haven't looked at this code in a bit now but from what I remember I was having a similar issue. The branching factor at 20 is really big causing the search to become slower. To improve it you would need to improve the search function. This could be done a couple ways.

One idea is to make the search function more parallel.

Another could be to train a model to learn the heuristics. This is a more muzero approach to things though and would take time to train.

Hope this helps a bit.

[TalhaGoktopal]

Thank you very much. What exactly do you mean to make the search function more parallel?

[bellerb]

The function that creates the heuristic is in series (has one loop). This could be divided across multiple threads (processes in python work better) to help speed up the computation through a divide an conquer approach.

The heuristic is also built through bfs so maybe a different approach here would be more computationally efficient. This is a bit of a brute force approach to building it.

[bellerb]

You can also just run the build and save the heuristics for later so you don't have to build every time. The heuristic map becomes very big though so loading it becomes a bit of an issue at times depending on your computer. Maybe some sort of compression could be applied to the heuristics to shrink the size of the needed map.

[TalhaGoktopal]

You can also just run the build and save the heuristics for later so you don't have to build every time.

I only need to build the heuristic database once and then use it to run searches once the program is running.

You can also just run the build and save the heuristics for later so you don't have to build every time.

I'll have a look at this and try to implement this.

Do you happen to know of any other code (in python) that can be used to solve a Rubiks Cube. Seeing as I dont have much time I want to create a perfect solution that will work for all inputted cubes (depth of 20) to try and maximize my score. Thanks again for the support.

[bellerb]

The only other way I know of is less computer sciencey and is to just implement the know solve anytime algorithm (white face first method). I don't have code for it but this would work every time just won't be as efficient (amount of actions) at solving as my approach once you have the heuristics.

[TalhaGoktopal]

I see. I will try my best to find an alternative method, as a more computational method would probably be better for my grade. Thanks a lot for the help. Wish you the best.