Kaskapa
Reputation: 41
Heuristics and IDA* for an F2L solver not working and I don't know why
I have generated a simple heuristics database for an F2L solver for a Rubik's cube. I represent the state in a way that I need 2 heuristic databases. One is for the pair corner and the other is for the 5 edges(4 corner edges and 1 corresponding pair edge).
I have generated the heuristics for a max depth of 6 for testing purposes. The corner heuristic database contains 24 lines (which is expected) and the edge database contains around 200k lines of states (which is less than expected, but for testing purposes fine enough, I calculated it to be around 3 million). Here is an example of the corner database:
"((0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 3, 2), (0, 0, 0))": 0,
"((0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (2, 3, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0))": 1,
"((0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 3, 2))": 1,
"((0, 0, 0), (0, 0, 0), (3, 0, 2), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0))": 1,
"((0, 0, 0), (0, 0, 0), (2, 3, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0))": 1,
"((0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 2, 3), (0, 0, 0), (0, 0, 0), (0, 0, 0))": 1,
"((0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (3, 2, 0))": 1,
Here is an example of the edge database:
"((0, 4), (0, 0), (0, 3), (0, 2), (0, 0), (0, 1), (3, 2), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0))": 1,
"((0, 4), (0, 1), (2, 3), (0, 2), (0, 0), (0, 0), (0, 0), (0, 3), (0, 0), (0, 0), (0, 0), (0, 0))": 1,
"((0, 1), (0, 2), (0, 4), (0, 3), (0, 0), (0, 0), (3, 2), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0))": 1,
"((0, 4), (0, 1), (0, 3), (0, 2), (0, 0), (0, 0), (3, 2), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0))": 1,
"((0, 4), (0, 1), (0, 3), (0, 0), (0, 0), (0, 0), (0, 2), (0, 0), (3, 2), (0, 0), (0, 0), (0, 0))": 1,
"((0, 0), (0, 1), (0, 3), (0, 2), (4, 0), (0, 0), (3, 2), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0))": 1,
"((0, 4), (0, 0), (0, 3), (0, 2), (0, 1), (0, 0), (3, 2), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0))": 1,
"((0, 4), (0, 1), (0, 0), (0, 2), (0, 0), (0, 0), (3, 0), (0, 0), (0, 0), (0, 0), (2, 3), (0, 0))": 1,
I use JSON to save the database.
The order how the edges and corners are in the tuple show the location of each edge and corner on the cube, and the order the colors are correspond to their orientation.
The issue I have is that when I run my python IDA* script it works just fine for solutions that require one move to solve, but as soon as the depth gets bigger than 2 it just runs and never stops.
Here is the code that I already have:
from random import choice
from rubiks_cube import Cube
import json
import copy
ACTIONS = ["L", "R", "U", "D", "F", "B", "L'", "R'", "U'", "D'", "F'", "B'", "L2", "R2", "U2", "D2", "F2", "B2"]
class IDA_star(object):
def __init__(self, heuristicEdge, heuristicCorner, max_depth = 20):
self.max_depth = max_depth
self.threshold = max_depth
self.min_threshold = None
self.heuristicEdge = heuristicEdge
self.heuristicCorner = heuristicCorner
self.moves = []
def run(self, cube):
while True:
status = self.search(cube, 1)
if status: return self.moves
self.moves = []
self.threshold = self.min_threshold
return []
def search(self, cube, g_score):
cube_copy = copy.deepcopy(cube)
edge_state = get_edge_state(cube_copy)
corner_state = get_corner_state(cube_copy)
if is_goal_state(corner_state, edge_state):
return True
elif len(self.moves) >= self.threshold:
return False
min_val = float('inf')
best_action = None
for a in ACTIONS:
cube_copy.do_moves(a)
edge_state = get_edge_state(cube_copy)
corner_state = get_corner_state(cube_copy)
if is_goal_state(corner_state, edge_state):
self.moves.append(a)
return True
h_score_edge = self.heuristicEdge[str(edge_state)] if str(edge_state) in self.heuristicEdge else self.max_depth
h_score_corner = self.heuristicCorner[str(corner_state)] if str(corner_state) in self.heuristicCorner else self.max_depth
h_score = h_score_edge + h_score_corner
f_score = g_score + h_score
if f_score < min_val:
min_val = f_score
best_action = [(cube_copy, a)]
elif f_score == min_val:
if best_action is None:
best_action = [(cube_copy, a)]
else:
best_action.append((cube_copy, a))
if best_action is not None:
if self.min_threshold is None or min_val < self.min_threshold:
self.min_threshold = min_val
next_action = choice(best_action)
self.moves.append(next_action[1])
status = self.search(next_action[0], g_score + min_val)
if status: return status
return False
goal_corner_state = ((0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 3, 2), (0, 0, 0))
goal_edge_state = ((0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (2, 3), (0, 0), (0, 0), (0, 2), (0, 3), (0, 1), (0, 4))
def is_goal_state(corner_state, edge_state):
return corner_state == goal_corner_state and edge_state == goal_edge_state
def get_corner_and_edge_state(cube):
return get_corner_state(cube), get_edge_state(cube)
def get_edge_state(cube):
edges = cube.get_edges()
state = [[0, 0] for _ in range(12)]
for i, edge in enumerate(edges):
if set(edge) in [{0, 2}, {0, 3}, {2, 3}, {0, 4}, {0, 1}]:
state[i] = list(edge)
return tuple(tuple(edge) for edge in state)
def get_corner_state(cube):
corners = cube.get_corners()
state = [[0,0,0] for _ in range(8)]
for i, corner in enumerate(corners):
if set(corner) == {0, 2, 3}:
state[i] = list(corner) # Preserve the order of colors
break
return tuple(tuple(corner) for corner in state) # Make it hashable
MAX_MOVES = 5
HEURISTIC_FILE_EDGE = '/heuristic_f2l_one_pair_edge.json'
HEURISTIC_FILE_CORNER = '/heuristic_f2l_one_pair_safe.json'
with open(HEURISTIC_FILE_EDGE, 'r') as f:
heuristicEdge = json.load(f)
with open(HEURISTIC_FILE_CORNER, 'r') as f:
heuristicCorner = json.load(f)
cube = Cube(0)
cube.do_algorithm("z2 L' U' L")
solver = IDA_star(heuristicEdge, heuristicCorner)
moves = solver.run(Cube(0))
print(moves)
Upvotes: 0
Views: 24