[PYTHON] Let's write a program to solve the 4x4x4 Rubik's Cube! 3. Implementation
What is this article?
I am currently making a robot that solves the 4x4x4 Rubik's Cube (Rubik's Revenge) and is aiming for a world record. The biggest hurdle in making a robot was to implement an algorithm to solve a 4x4x4 cube in a realistic time and with as few steps as possible. If you look it up, you will find that there are few documents and ancestors about 4x4x4. I am writing this article, hoping that it will be one of such valuable materials. GitHub is here ** The content of this article is not complete. It may contain some inefficiencies. I will add it as needed if it is improved in the future. ** **
↓ Competition 4x4x4 Rubik's Cube and Competition 4x4x4 Rubik's Cube numbered for program production
The whole picture
This collection of articles consists of three articles in total.
What to talk about in this article
In this article, I will talk about how to actually implement the algorithm explained last time, and TIPS at that time. Avoid taking steps to explain the implementation as it would be redundant. I wrote a detailed explanation about the 2x2x2 Rubik's Cube in the article here (the actual code is also included), so please refer to it as well. ..
Indexing
By searching in small phases, the area to be searched has become extremely small. Thanks to that, you will be able to number the possible states of that phase in order. This eliminates the need for costly work such as ** simulating the movement of the puzzle one by one **, and you can do the work equivalent to moving the puzzle just by referring to the array. However, if you think about EP and CP together, for example, it will not fit in the array of about $ 10 ^ 6-10 ^ 7 $ elements, and it will eat up memory very much. Therefore, for example, there is also a phase in which numbers are assigned only to EP and CP, and the state of the puzzle is represented by two numbers.
You can number them in any way, but for the sake of clarity, the permutation numbers (factorials) of the puzzle for EP and CP, the binary and ternary numbers for EO and CO, respectively, and the factorial with duplication for the center. I think it's better to express it in permutations. For factorial numbers, here is easy to understand.
IDA * Search
In the actual search, I think that a search called IDA * search (Iterative Deepening A *) will be used. This is a phrase that has appeared many times in my article, but if I quote from the article here,
In a nutshell, IDA * is "repeat a depth-first search (DFS) with a limited maximum depth, increasing the depth." The mechanism of IDA * is to forget the node once searched. If you forget the node, you can free up memory, right?
In IDA *, if a depth-first search is performed up to a depth of $ N-1 $ and no solution is found, the maximum depth is increased to $ N $ and the search is restarted from the beginning. By doing this,
- The returned result is always the shortest
- Very low memory usage
There is a benefit.
However, for nodes (states) with shallow depth, the same search is repeated many times, so the amount of calculation increases slightly. However, since the state of the puzzle increases as an exponential function with respect to the depth, the increase in the amount of calculation is not so large.
The key to IDA * is to ** estimate the "distance" from the current state to the completion of the phase **. This "distance" is the number of steps to solve in this case. Specifically, if the state of the puzzle is represented by the index $ i $,
Proceed with the search so that Let me explain in detail.
- $ depth $ is the upper limit of the depth (= effort) when searching.
- $ f (i) $ is an estimate of how many solutions will take to go through the state of index $ i $.
- $ g (i) $ is the number of steps taken from the initial state to the state of index $ i $.
- $ h (i) $ is an estimate of the number of steps taken from the state of index $ i $ to the phase completion state.
If you increase $ depth $ from 0 to 1 while satisfying this formula, you will find a solution with a short effort. If the actual number of steps required to complete the phase from the index $ i $ is $ h ^ \ star (i) $, and $ h (i) \ leq h ^ \ star (i) $ is always satisfied. You will find the optimal solution. That is, you will find the solution with the least effort (within that phase). This case is called admissible.
Avoid searching for the same state more than once
It would be inefficient to search for the same state many times. However, if you save the state somewhere, it will consume a huge amount of memory. Therefore, when solving the Rubik's cube, we will implement this by avoiding the case where ** optimizing the procedure results in the same procedure **. Of course, this alone cannot avoid the case where "I went through different steps but the situation is the same". However, it is said that this alone will not have to search for the same state with a high probability (for 3x3, here It is written in 6803 & item_no = 1 & page_id = 13 & block_id = 21).).
In the case of 4x4x4 Rubik's Cube, it is better not to search in the following two cases.
- When turning the same surface continuously
- When turning the same axis, when turning in the order of inner layer-> outer layer (or outer layer-> inner layer: decide which one to use first)
A function that returns an estimate of the number of steps to complete
He said that $ h (i) $ is important for IDA * search. Here, I will briefly talk about the calculation method of $ h (i) $ (although I am researching it myself).
First, pre-calculate how many steps each index will have from the completed state and make a table. In my case I made this a csv. If you actually use this precomputed value, you often have multiple indexes (assuming you have $ n $), so you can retrieve $ n $ from the precomputed table. Using these $ n $ "distances", we must finally output one distance that represents how far the board is from completion.
I will just list what I have tried. Let the distance of $ n $ be $ L = (l_0, l_1, \ dots l_ {n-1}) $. Also assume that $ \ mathrm {sd} (L) $ represents the standard deviation of $ L $.
h(i)=\max(L) h(i)=\sum L h(i)=\max(L)+a\ \mathrm{sd}(L) h(i)=\sqrt{\sum_j l_j^2} - $ t = \ mathrm {pow} \ left (a,-\ left (\ frac {\ max (L)} {b \ \ mathrm {sd} (L)}-c \ right) ^ d \ right) $ H (i) = (1-t) \ max (L) + t \ sqrt {\ sum_j l_j ^ 2} $ as $ Also, $ h (when $ \ mathrm {sd} (L) = 0 $ i) = \ max (L) $
The first is guaranteed to be admissible, but it tends to be computationally expensive as $ h (i) $ is often well below $ h ^ \ star (i) $. The second uses Manhattan distance, but it breaks admissible too much. In a simple example, $ h ^ \ star (i) for $ n $ evaluation items $ (l_0, l_1, \ dots l_ {n-1}) $ that are aligned by turning the same rotation `` `R```. Even though = 1 $, it returns $ h (i) = n $. Breaking admissible not only increases the number of solutions, but also increases the space to search, which tends to increase the amount of calculation. The third formula is based on the hypothesis that $ h ^ \ star (i) $ tends to increase when the variation of ** $ L $ is large. But it didn't work very well. The fourth is the Euclidean distance. It's better than the second one, but there is still the possibility of breaking the admissible. The fifth is the method we are currently using. Adjust the constants $ a, b, c, d $ to make $ 0 <t <1 $. This $ t $ is used to internally divide the maximum value of $ L $ and the Euclidean distance. $ t $ is calculated with the policy of returning a value closer to the Euclidean distance when $ \ mathrm {sd} (L) $ is larger than ** $ \ max (L) $ **. This function $ h (i) $ is arbitrarily called Nyanyan's Function.
Pseudo code
This is a Python-like pseudo code from Program written in Cython.
def phase_search(phase, indexes, depth, h_i): # phase:Phase, indexes:Puzzle state index, depth:The number of steps that can be left, h_i:h in the state of indexes(indexes)
global path
if depth == 0: #If there are 0 steps left, return whether the solution has been reached.
return h_i == 0
twist = successor[phase][0] #twist is a hand to turn
while twist <= successor[phase][-1] : #successor is a candidate for rotation
if skip(twist, path): #Do not turn the same side that you turned with your previous hand
twist = skip_axis[phase][twist] #Advance twist until you can't turn the same side
continue
next_indexes = move(indexes, phase, twist) #Move the puzzle by array reference. Since the definition of indexes differs depending on the phase, take the phase as an argument.
next_h_i = h(indexes, phase) # h(i)return it. h(i)Since the definition is different for each phase, the phase is taken as an argument.
if next_h_i > depth or next_h_i > h_i + 1: #Skip if you're obviously trying to make a detour
twist = skip_axis[phase][twist]
path.append(twist) #Add twist to the steps you have taken so far
if phase_search(phase, next_indexes, depth - 1, next_h_i): #Search for the next move by recursion
return True #Solution found
path.pop() #Remove this procedure from the procedure that has been turned so far
twist = next_twist(twist, phase) #Next move
return False #No solution found
def solver(puzzle): # puzzle:A class object that represents all the states of the puzzle, etc.
global path
solution = [] #Solution
for phase in range(6): #Turn the phase with for
indexes = initialize_indexes(puzzle, phase) #Convert puzzle state to index
h_i = h(indexes, phase)
for depth in range(60): #Turn depth. 60 is appropriate
path = [] #Empty path
if phase_search(phase, indexes, depth, h_i): # IDA*Do a search
for twist in path: #Simulate the puzzle until the end of the phase
puzzle = puzzle.move(twist)
solution.extend(path) #Add the solution of the current phase to the solution
break #I found a solution, so break it and move on to the next phase
return solution #Return the solution
Summary
So far, in three articles I have summarized what I have learned in writing a program to solve a 4x4x4 Rubik's cube. I hope it will be helpful to everyone.
Recommended Posts