Hey Ben, this is some sweet stuff! I'm taking Genetic Programming in college right now and want to make my term project a solver. Your stuff is definitely inspiring. Would love to be able to talk to u personally if you're available!
Really nice work, thank you for sharing :D! I've just found your project and your articles, and they will be VERY useful in the undergrad project I'm working on, which aims to implement korf's algorithm. I might be a little bit lost though. I started reading about permutations and groups, and have a general comprehension about it. My problem now consists on understanding the main difference between mapping all the cubies faces like you described in the article as the 3rd way of representing the cube (if I got it right) and the fourth way, where we map each cubie position and orientation. I didn't quite understand how to map the orientation of a dislocated cubie, and without mapping those I get a problem where the two representations don't match when it comes to the parity (when I break the permutations down in transpositions, in the 3th way, i don't always get an even number of transpositions like I do when I do the same process with the permutations of the 4th representation). If you have any tips or further reading recommendations I'll be forever in debt :D And thanks again for sharing
Hi Davi, glad you found the article and video helpful. Regarding the orientations, my Medium article links to an older version of the program, version 2.2.0. The newest version, 4.0.0, stores the orientations and positions a bit differently (in a more "standard" way, for lack of a better word). For what it's worth, I now use the 4th structure in both the algorithms I've implemented, Korf's and Thistlethwaite's. The 3rd structure was useful for a tree-based Thistlethwaite solver, but I've since optimized that code quite a bit with pattern databases. As such, the 4th structure--storing orientations and positions--is by far superior. Here's the code that shows the data structure in action: github.com/benbotto/rubiks-cube-cracker/blob/4.0.0/Model/RubiksCubeIndexModel.h and github.com/benbotto/rubiks-cube-cracker/blob/4.0.0/Model/RubiksCubeIndexModel.cpp Also, if you haven't already found it out there, Jaap Scherphuis's Puzzle Page has a ton of great information about the cube: www.jaapsch.net/puzzles/index.htm Let me know if you have questions, or if my response missed the ball. Happy to help.
hello sir pleas i would like to do the same project please can you tell me how you found the pattern datta base and which heuristic you used and how it works
This looks very nice! I would like to try it out. Unfortunately, I don't have the proper setup to compile the code. It would be nice if the github releases would include the EXE binary so more people can try it out without the need to setup the environment to compile. Ben, can you please add the binary to the github release?
Hello @minglw. Thanks for the feedback. I haven't had time to work on this project in a while, and it's been years since I compiled it on Windows (or, really, since I've done any development in Windows whatsoever). I speculate that the included Docker image could be built under WSL2 these days, and then used to compile and run a Linux binary. At any rate, if you feel inclined to contribute instructions for building under Windows, or to add executables to the releases, I'd be happy to accept a pull request.
Hi Ben. I'm currently working on a school project related to algorithms applied to the rubiks cube. One of the things that I'm trying to understand is the way Kociemba's algorithm works, and how it has achieved/found the number of 20 moves on average to solve any scramble. While searching for this information, I've found that Kociemba works similarly to Korf's algorithm. From what I understand, the whole deal is finding a way to utilize the brute computational force in a way that is able to find a solution but without having to go through all the possible configurations and eliminate some stuff that you are searching for. To do this, the algorithm works separately in certain phases/sub-problems which involve setting different G groups with restricted ways of twisting the cube faces. (Correct me if I am wrong or something is off. ) My question is, what does the algorithm gain by moving the cube from one group to another, I mean, why does the algorithm find it easier to reach a solution by solving the cube into different states using the moves restricted in each group, and how does this help to find the number of 20 moves. Thanks for the video btw, it was helpful.
Hi Wast, I haven't implemented Kociemba's algorithm, but it works in the same manner as Thistlethwaite's. There are a few questions in your comment, the first of which is what is gained by moving the cube from one group to another. The short answer is that the branching factor in each successive group is reduced, making it computationally easier to solve. There are 18 possible twists that can be applied to a cube, so using a brute force breadth-first search to solve an arbitrarily scrambled cube has a branching factor of 18. (It's actually smaller than 18 because some combinations of twists are redundant or commutative.) That's a huge branching factor. It would take millions of years to solve a cube. As such, the strategy employed by Thistlethwaite's/Kociemba's is to move from one group to a new group that can be solved using fewer twists, thereby reducing the branching factor. For example, if all 12 edge pieces are oriented, then it is impossible to disorient the edges without quarter turns of the front and back faces. Put differently, in this group the cube is solvable without using quarter turns of the front and back faces. The branching factor is therefore reduced by 4. Each successive group is solvable with a smaller subset of twists. The second question is how moving through the groups is used to show an upper bounds on the number of moves required to solve a cube. To prove an upper bounds, the first step is to mathematically figure out how many possible states are in a group. That involves a rather intimate understanding of the Rubik's Cube, and some group theory. For the sake of an example, I'll continuing on the example of orienting edges. There are 2^11=2048 possible ways the edges can be oriented: each edge can be in one of two states, oriented or disoriented, but 11 edges dictate the orientation of the 12th (i.e. it's not possible to disorient only one edge piece). Next, the cube is searched recursively until all of these 2048 states are reached, and the number of moves required to reach each state is recorded. That process continues from group to group. Adding up the maximum number of moves required to move from each group to the next is then the worst case scenario, specifically the maximum number of moves required to solve the cube using the particular algorithm. More detail is available in my code, linked in the description. This in particular may be helpful: github.com/benbotto/rubiks-cube-cracker#quick-solver
Here's an idea: What if the algorithm started in the solved state and tried to get to the current state, then just reversed the moves taken to get there? Would that be less work?
That's how the pattern databases are generated--starting from the solved state and finding every permutation of a subset of the cubies. Answering your question more directly, moving from the solved state to an arbitrary scrambled state would be very difficult.
Hi, I just compiled and ran your magnificent program! thanks a lot for sharing! I haven't tested it yet (It's initializing the Database), but, is there a way to set up an initial state of the cube manually? I guess it can be done modifying the source code, Is there a place where I can look for to do that? Thanks in advance! Cheers!
I read your medium article about this and this video summarizes your project nicely. Thank you for all these implementation details. They are very neccessary to think through, especially in this complex task. Funny, how one additional cube layer makes the problem so difficult, computationally. The 2x2 cube can be easily solved with simple BFS in seconds. No tricks needed. 4x4, 5x5, ... won't be solvable at all, if you want it to be an optimal solution. Even with best hardware, am I right?
Hi everluck. Thanks for the nice words. It is stunning how quickly the computational complexity grows by simply adding a layer. 4x4, to my knowledge, has not been solved optimally. I won't go so far as to say that it can't be solved optimally on modern hardware: with an enormous amount of disk space and memory, and that's an emphatic "enormous", Korf's approach might be feasible. But that kind of hardware is well out of my reach =) A non-optimal 4x4 or 5x5 solver wouldn't be much harder than the 3x3, though.
Hey Ben, awesome work you're doing here. I'm currently trying to implement Thistletwhaite's algorithm but I'm not sure what heuristic I should use for each step. Instead of using pattern databases could I just use something as simple as # of unsolved edges / corners for a given group? Thanks!
You might be able to. With A*, the nice thing is that any heuristic can be used so long as it always provides an underestimate for the number of moves required to get from one state to another. The distance between groups is short enough with Thistlethwaite's algorithm that it can even be implemented without any heuristics, i.e. just with a decision tree, which is what I did in my first implementation. At any rate, I think it's worth it to implement pattern databases for Thistlethwaite's algorithm. Each group is small enough that a database of every possible permutation of that group can be created in a small amount of time and stored in less than 1MB on disk/in memory. Those databases then act as a perfect heuristic--that is, they always give the exact number of moves required to get from one group to the next. With perfect heuristics, the time to solve a cube is effectively instant. Have you looked at the Thistlethwaite pattern databases in my code (github.com/benbotto/rubiks-cube-cracker/tree/4.0.0/Model/PatternDatabase/Thistlethwaite)?
@@BenBotto Thanks for the response! Yeah I noticed that your Thistletwaite's algorithm implementation in version 2.2.0 only uses IDDFS and I'm just trying to do the same for now to keep things simple and implement pattern databases once I can get this working. By decision trees, is this just a series of individual IDDFS that are used to get from one group to another? I noticed an abnormally high memory usage (~2GB of ram used after the first IDDFS and ran out of memory at depth 6), is this because I am using an inefficient programming language such as Java and my data structure is not optimized? Thank you so much again for your help!
@@Ilikerotmghacks Yes, that essentially what I meant by decision trees. 2G of memory sounds too high for IDDFS regardless of the language, but I suppose it depends on your implementation. With IDDFS, the space complexity is generally O(d), where d is the depth of the tree. So at depth 6, only 6 nodes should be stored, which shouldn't occupy anywhere near 2GB.
Hi, I'm currently implementing Thistlewaithe's algorithm using only IDDFS, it works well when the last goal has a solution under depth 15, but if it's over it searches for hours not finding any solution, should I work on optimizing the searcher or find a way to limit goal 4 under 15
How good is to creatr a project of cube solve for 1 year coder .. Give me some advice.. I am learning cpp c ... That's all i am focusing on... What more language do i need to learn to make this projects..
It's a great project for a first-year programmer: interesting algorithms, data structures, storage and memory constraints, math, plenty of room for design patterns... In my opinion, C++ and C are perfect for this sort of project because they are fast and efficient, plus they are both fun languages.
Hi! I'm also trying to implement a solver and I'm using a very similar approach. my cube is represented as a 48 uint8_t array like yours. I'm having trouble understanding how to generate the lookup tables for Thistlethwaite's algorithm. I read your article about generating indices from a permutation, but I still don't understand the logic of the actual tables. The way to do it is to BFS backwards (from a solved state) using the group's allowed moves, and then ranking the permutations based on the moves so that closer to the solved state equals a lower rank (index)? if I index the permutations based on edge orientation for example, like in G0->G1 (even though its really quickly so a lookup table is not needed. but just for example) how do I know which moves led to this state then? or is it just there to tell the IDDS that the permutation exists and how close it is to the solution, but not how to get to the solution? Regardless, I wanted to say thank you for explaining in great detail everything about your project. you helped me more than you realise and I really appreciate it so thank you!
Hi NULL. For the Thistlethwaite algorithm I didn't actually use lookup tables. Using lookup tables would speed the algorithm up quite a bit, but it only takes about a minute to solve a cube using that algorithm. I used lookup tables for the Korf algorithm, which is markedly more complex and computationally expensive. Anyway, a lookup table is just a hash table of permutation ranks to number of moves. I.e. it's just a huge array of numbers, where each index is a permutation rank and each element is an estimated number of moves to solve the cube from that state. The tables don't store the moves required to get to the various states. (Storing moves would require _a ton_ of space.) From any state, the lookup tables provide a lower-bounds estimate (an underestimate) of the number of moves required to solve the cube. That estimate can be used with an A* search. In a nutshell, the estimates give the search algorithm an idea of whether a twist is moving closer to or farther away from the solved state, and allows for pruning moves that are moving away from the solution rather than toward it. Regarding generating the tables, I did use BFS for the smaller tables. BFS, however, takes a lot of RAM, so for the larger tables I used a custom IDDFS algorithm. I used non-recursive implementations of both algorithms which performed better than my original recursive versions. Lastly, I speculate that the permutations in each group of the Thisthlethwaite algorithm could be iterated through in their entirety and stored in reasonably-sized pattern databases. Again, that's just speculation, but if it is the case then the pattern databases would give be perfect--each element would contain the exact number of moves to get to the next group. As such, IDA* would be able to solve any scramble effectively instantaneously. If you implement Thisthethwaite's algorithm working with pattern databases, I would love to see it! Hopefully that helps, and good luck on your project! It's a fun one.
As an afterthought, I thought I would point this out in case it's not clear: With the Thisthethwaite algorithm, having estimates of the number of moves required to solve the cube isn't helpful. You would need estimates of the number of moves to get from one group to the next, e.g. from G0->G1. Starting in G0, making one twist might move the cube farther away from the solved state but at the same time closer to G1 (because Thisthlethwaite is non-optimal). So you can't simply start at the solved state and iterate through moves using BFS to generate the databases.
@@BenBotto Thanks for clarifying. I was way off. My thought was that since G4 contains all the other groups, I can just use that as a "base" to iterate from as long as I only use the allowed moves of said group. Obviously, I realise now that it doesn't work like that. What would you do instead? G0->G1 for example, there are many permutations where G1 would be satisfied. My thought was to generate an ID based on the permutation AND the orientation of the edges, but it still doesn't solve the issue since there are many positions where all the edges are solved, so there's still no "base" case.
@@null06f I can think of a few ways of tackling this, but here's the way I would probably go about creating a pattern database for G0->G1. In G1, only the edge orientations matter. In other words, if all of the edges are oriented then the cube is in group G1, regardless of the positions of the edges. There are 12 edges, and the orientation of 11 of the edges dictate the orientation of the 12th, due to edge parity. Each edge can be in one of two orientations. So, there are 2^11=2048 possible permutations of the edge orientations. I would use IDDFS to generate the database. BFS can be used, but using IDDFS will simplify things, and the efficiency gained by using BFS isn't worth the added complexity in my opinion. I can go into details on that if you want, or you can trust me on it. Assuming IDDFS, the algorithm is loosely as follows. Initialize the database as 2048 unsigned bytes, each set to 0x0F. (Let 0x0F mean infinity.) Start at the solved state and iterate over depths 1...n until all 2048 permutations have been found. Each time a new edge orientation permutation is encountered If the permutation has been visited at an earlier depth { prune the branch } else { If the permutation satisfies G1 { store the depth as the nearest G1 in a variable write 0 to the database for the permutation } Else { write to the database the distance from the permutation to the nearest G1 permutation (distance = depth - nearestG1Depth), but only if this distance is shorter than the current entry in the database for the permutation. (Remember that these entries are initialized to infinity.) } } The end result would be a database with exact distances from each state to G1.
@@BenBotto Managed to get a working table after a few trials and errors, just wanted to say thanks again for going above and beyond and explaining everything. it was a huge help just wanted to point something out in case anyone else is going to use this info: the only solved (solved means G1 is contended) edges orientation permutation is [0] = 0; (00000000000) "If the permutation has been visited at an earlier depth" will always be true when [0] is encountered, therefore every time the IDDFS discovers a node that satisfies G1, the branch will be pruned and nearestG1Depth will remain at 0 the entire time, making it irrelevant. updating the nearestG1Depth every time a solved node is checked regardless if it will get pruned out or not will not work , because node { move = L, depth = 1 } is the same as the root node (no affected edges), therefore the nearestG1Depth should not be updated to 1. I don't know if "nearestGxDepth" will be relevant to the other tables or not, but if it will, then I think the current approach will cause a bug - i.imgur.com/GHMkNE3.png basically, what happens when nearestGxDepth is 10 and the current node's depth is 6? we can't assume that if the current node's depth is smaller than the nearestGxDepth, nearestGxDepth should default back to 0, because what if depth 5 of the same branch was also solved? I think a work around for that is to store the nearestGxDepth in a stack instead of a variable. push 0 to the stack before starting the IDDFS, and then do this every iteration: while (nearestDepthStack.top() > currenNode->depth) { nearestDepthStack.pop(); } and updating nearestGxDepth like this instead: if (goal is satisfied) push the current depth to the nearestDepthStack, but only if it is bigger than the current stack.top(). haven't tested it yet, so maybe I just "fixed" a non existing bug. edit: I compared ben's approach vs these: 1) ben's original approach 2) updating nearestG1Depth regardless if it gets pruned 3) like 2), but updating it using the stack method 1) and 3) yielded the same result 2) didn't work, 41 Ids had a value of 0. here's the finished table: pastebin.com/M5Yfdg9p
Just because "Crap++" has a bloated reputation for bad programmers over engineering the simplest things does NOT imply that _everyone_ has fallen for its pitfalls. If you actually _read_ Ben's article on Medium you see he discusses data structures early on -- the hallmark of a good programmer. Instead of whining about "Crap++" how about providing a good C version so we can judge how it compares on run-tune performance and code readability versus Bens C++ version?
@@puppergump4117 It compiles with g++, with all warnings on and in strict mode (-pedantic), with 0 warnings from the compiler. You can also use the provided Docker image, which is pre-baked with all the required dependencies. I've compiled it in both Windows and Linux. The ASM bit is an optimized way of rotating sides of the cube, which I discussed in my Medium article (the part about bitboard-type structures).
No program is used to open anything. The video and Medium articles are for programmers and math enthusiasts. The open-source code can be compiled using g++, generally under Linux.
I love how it writes out the resulting cube as if it might not always solve it correctly.
Man your work is amazing, This is just perfect
Hey, thanks Khaled. That's really nice of you to say.
Hey Ben, this is some sweet stuff! I'm taking Genetic Programming in college right now and want to make my term project a solver. Your stuff is definitely inspiring. Would love to be able to talk to u personally if you're available!
This guy deserves 9 million subscribers
Good video keep up bro
Really nice work, thank you for sharing :D! I've just found your project and your articles, and they will be VERY useful in the undergrad project I'm working on, which aims to implement korf's algorithm. I might be a little bit lost though. I started reading about permutations and groups, and have a general comprehension about it. My problem now consists on understanding the main difference between mapping all the cubies faces like you described in the article as the 3rd way of representing the cube (if I got it right) and the fourth way, where we map each cubie position and orientation. I didn't quite understand how to map the orientation of a dislocated cubie, and without mapping those I get a problem where the two representations don't match when it comes to the parity (when I break the permutations down in transpositions, in the 3th way, i don't always get an even number of transpositions like I do when I do the same process with the permutations of the 4th representation). If you have any tips or further reading recommendations I'll be forever in debt :D And thanks again for sharing
Hi Davi, glad you found the article and video helpful. Regarding the orientations, my Medium article links to an older version of the program, version 2.2.0. The newest version, 4.0.0, stores the orientations and positions a bit differently (in a more "standard" way, for lack of a better word).
For what it's worth, I now use the 4th structure in both the algorithms I've implemented, Korf's and Thistlethwaite's. The 3rd structure was useful for a tree-based Thistlethwaite solver, but I've since optimized that code quite a bit with pattern databases. As such, the 4th structure--storing orientations and positions--is by far superior.
Here's the code that shows the data structure in action: github.com/benbotto/rubiks-cube-cracker/blob/4.0.0/Model/RubiksCubeIndexModel.h and github.com/benbotto/rubiks-cube-cracker/blob/4.0.0/Model/RubiksCubeIndexModel.cpp
Also, if you haven't already found it out there, Jaap Scherphuis's Puzzle Page has a ton of great information about the cube: www.jaapsch.net/puzzles/index.htm
Let me know if you have questions, or if my response missed the ball. Happy to help.
I'm gonna show this to Zack
amazing!!
hello sir pleas i would like to do the same project please can you tell me how you found the pattern datta base and which heuristic you used and how it works
This looks very nice! I would like to try it out. Unfortunately, I don't have the proper setup to compile the code. It would be nice if the github releases would include the EXE binary so more people can try it out without the need to setup the environment to compile. Ben, can you please add the binary to the github release?
Hello @minglw. Thanks for the feedback. I haven't had time to work on this project in a while, and it's been years since I compiled it on Windows (or, really, since I've done any development in Windows whatsoever). I speculate that the included Docker image could be built under WSL2 these days, and then used to compile and run a Linux binary.
At any rate, if you feel inclined to contribute instructions for building under Windows, or to add executables to the releases, I'd be happy to accept a pull request.
Hi Ben. I'm currently working on a school project related to algorithms applied to the rubiks cube. One of the things that I'm trying to understand is the way Kociemba's algorithm works, and how it has achieved/found the number of 20 moves on average to solve any scramble.
While searching for this information, I've found that Kociemba works similarly to Korf's algorithm. From what I understand, the whole deal is finding a way to utilize the brute computational force in a way that is able to find a solution but without having to go through all the possible configurations and eliminate some stuff that you are searching for. To do this, the algorithm works separately in certain phases/sub-problems which involve setting different G groups with restricted ways of twisting the cube faces. (Correct me if I am wrong or something is off. )
My question is, what does the algorithm gain by moving the cube from one group to another, I mean, why does the algorithm find it easier to reach a solution by solving the cube into different states using the moves restricted in each group, and how does this help to find the number of 20 moves.
Thanks for the video btw, it was helpful.
Hi Wast,
I haven't implemented Kociemba's algorithm, but it works in the same manner as Thistlethwaite's. There are a few questions in your comment, the first of which is what is gained by moving the cube from one group to another. The short answer is that the branching factor in each successive group is reduced, making it computationally easier to solve.
There are 18 possible twists that can be applied to a cube, so using a brute force breadth-first search to solve an arbitrarily scrambled cube has a branching factor of 18. (It's actually smaller than 18 because some combinations of twists are redundant or commutative.) That's a huge branching factor. It would take millions of years to solve a cube. As such, the strategy employed by Thistlethwaite's/Kociemba's is to move from one group to a new group that can be solved using fewer twists, thereby reducing the branching factor. For example, if all 12 edge pieces are oriented, then it is impossible to disorient the edges without quarter turns of the front and back faces. Put differently, in this group the cube is solvable without using quarter turns of the front and back faces. The branching factor is therefore reduced by 4. Each successive group is solvable with a smaller subset of twists.
The second question is how moving through the groups is used to show an upper bounds on the number of moves required to solve a cube. To prove an upper bounds, the first step is to mathematically figure out how many possible states are in a group. That involves a rather intimate understanding of the Rubik's Cube, and some group theory. For the sake of an example, I'll continuing on the example of orienting edges. There are 2^11=2048 possible ways the edges can be oriented: each edge can be in one of two states, oriented or disoriented, but 11 edges dictate the orientation of the 12th (i.e. it's not possible to disorient only one edge piece). Next, the cube is searched recursively until all of these 2048 states are reached, and the number of moves required to reach each state is recorded. That process continues from group to group. Adding up the maximum number of moves required to move from each group to the next is then the worst case scenario, specifically the maximum number of moves required to solve the cube using the particular algorithm.
More detail is available in my code, linked in the description. This in particular may be helpful: github.com/benbotto/rubiks-cube-cracker#quick-solver
Here's an idea: What if the algorithm started in the solved state and tried to get to the current state, then just reversed the moves taken to get there? Would that be less work?
That's how the pattern databases are generated--starting from the solved state and finding every permutation of a subset of the cubies.
Answering your question more directly, moving from the solved state to an arbitrary scrambled state would be very difficult.
Im gonna use this
ur underrated
Hi, I just compiled and ran your magnificent program! thanks a lot for sharing! I haven't tested it yet (It's initializing the Database), but, is there a way to set up an initial state of the cube manually? I guess it can be done modifying the source code, Is there a place where I can look for to do that? Thanks in advance! Cheers!
I read your medium article about this and this video summarizes your project nicely. Thank you for all these implementation details. They are very neccessary to think through, especially in this complex task.
Funny, how one additional cube layer makes the problem so difficult, computationally. The 2x2 cube can be easily solved with simple BFS in seconds. No tricks needed.
4x4, 5x5, ... won't be solvable at all, if you want it to be an optimal solution. Even with best hardware, am I right?
Hi everluck. Thanks for the nice words.
It is stunning how quickly the computational complexity grows by simply adding a layer. 4x4, to my knowledge, has not been solved optimally. I won't go so far as to say that it can't be solved optimally on modern hardware: with an enormous amount of disk space and memory, and that's an emphatic "enormous", Korf's approach might be feasible. But that kind of hardware is well out of my reach =)
A non-optimal 4x4 or 5x5 solver wouldn't be much harder than the 3x3, though.
Hi!
Very nice program! I'm looking for a method to solve my cube too. I'm listing the rubiks cube. What method would be best(python)?
Hi MiB0. I'd go with Thistlethwaite's algorithm with python. It's fun and challenging and solves cubes quickly.
@@BenBotto Thanks for ur answer! Im very bad in programming…is there any tutorial?
Hey Ben, awesome work you're doing here. I'm currently trying to implement Thistletwhaite's algorithm but I'm not sure what heuristic I should use for each step. Instead of using pattern databases could I just use something as simple as # of unsolved edges / corners for a given group? Thanks!
You might be able to. With A*, the nice thing is that any heuristic can be used so long as it always provides an underestimate for the number of moves required to get from one state to another. The distance between groups is short enough with Thistlethwaite's algorithm that it can even be implemented without any heuristics, i.e. just with a decision tree, which is what I did in my first implementation.
At any rate, I think it's worth it to implement pattern databases for Thistlethwaite's algorithm. Each group is small enough that a database of every possible permutation of that group can be created in a small amount of time and stored in less than 1MB on disk/in memory. Those databases then act as a perfect heuristic--that is, they always give the exact number of moves required to get from one group to the next. With perfect heuristics, the time to solve a cube is effectively instant.
Have you looked at the Thistlethwaite pattern databases in my code (github.com/benbotto/rubiks-cube-cracker/tree/4.0.0/Model/PatternDatabase/Thistlethwaite)?
@@BenBotto Thanks for the response! Yeah I noticed that your Thistletwaite's algorithm implementation in version 2.2.0 only uses IDDFS and I'm just trying to do the same for now to keep things simple and implement pattern databases once I can get this working. By decision trees, is this just a series of individual IDDFS that are used to get from one group to another?
I noticed an abnormally high memory usage (~2GB of ram used after the first IDDFS and ran out of memory at depth 6), is this because I am using an inefficient programming language such as Java and my data structure is not optimized?
Thank you so much again for your help!
@@Ilikerotmghacks Yes, that essentially what I meant by decision trees.
2G of memory sounds too high for IDDFS regardless of the language, but I suppose it depends on your implementation. With IDDFS, the space complexity is generally O(d), where d is the depth of the tree. So at depth 6, only 6 nodes should be stored, which shouldn't occupy anywhere near 2GB.
Turned out to be an issue with my implementation. May I also ask what your branching factor was for each of the 4 subgoals?
Hi, I'm currently implementing Thistlewaithe's algorithm using only IDDFS, it works well when the last goal has a solution under depth 15, but if it's over it searches for hours not finding any solution, should I work on optimizing the searcher or find a way to limit goal 4 under 15
Personally I would implement pattern databases. Then the Thistlethwaite algorithm will be able to solve any scramble in no time.
How can I run this on Mac?
How good is to creatr a project of cube solve for 1 year coder ..
Give me some advice..
I am learning cpp c ...
That's all i am focusing on...
What more language do i need to learn to make this projects..
It's a great project for a first-year programmer: interesting algorithms, data structures, storage and memory constraints, math, plenty of room for design patterns... In my opinion, C++ and C are perfect for this sort of project because they are fast and efficient, plus they are both fun languages.
@@BenBotto thank u
@@BenBotto it means i have to to complete these before starting the project🙂🙂.isn't it?
Hi! I'm also trying to implement a solver and I'm using a very similar approach. my cube is represented as a 48 uint8_t array like yours.
I'm having trouble understanding how to generate the lookup tables for Thistlethwaite's algorithm. I read your article about generating indices from a permutation, but I still don't understand the logic of the actual tables.
The way to do it is to BFS backwards (from a solved state) using the group's allowed moves, and then ranking the permutations based on the moves so that closer to the solved state equals a lower rank (index)?
if I index the permutations based on edge orientation for example, like in G0->G1 (even though its really quickly so a lookup table is not needed. but just for example) how do I know which moves led to this state then? or is it just there to tell the IDDS that the permutation exists and how close it is to the solution, but not how to get to the solution?
Regardless, I wanted to say thank you for explaining in great detail everything about your project. you helped me more than you realise and I really appreciate it so thank you!
Hi NULL. For the Thistlethwaite algorithm I didn't actually use lookup tables. Using lookup tables would speed the algorithm up quite a bit, but it only takes about a minute to solve a cube using that algorithm. I used lookup tables for the Korf algorithm, which is markedly more complex and computationally expensive.
Anyway, a lookup table is just a hash table of permutation ranks to number of moves. I.e. it's just a huge array of numbers, where each index is a permutation rank and each element is an estimated number of moves to solve the cube from that state. The tables don't store the moves required to get to the various states. (Storing moves would require _a ton_ of space.) From any state, the lookup tables provide a lower-bounds estimate (an underestimate) of the number of moves required to solve the cube. That estimate can be used with an A* search. In a nutshell, the estimates give the search algorithm an idea of whether a twist is moving closer to or farther away from the solved state, and allows for pruning moves that are moving away from the solution rather than toward it.
Regarding generating the tables, I did use BFS for the smaller tables. BFS, however, takes a lot of RAM, so for the larger tables I used a custom IDDFS algorithm. I used non-recursive implementations of both algorithms which performed better than my original recursive versions.
Lastly, I speculate that the permutations in each group of the Thisthlethwaite algorithm could be iterated through in their entirety and stored in reasonably-sized pattern databases. Again, that's just speculation, but if it is the case then the pattern databases would give be perfect--each element would contain the exact number of moves to get to the next group. As such, IDA* would be able to solve any scramble effectively instantaneously. If you implement Thisthethwaite's algorithm working with pattern databases, I would love to see it!
Hopefully that helps, and good luck on your project! It's a fun one.
As an afterthought, I thought I would point this out in case it's not clear: With the Thisthethwaite algorithm, having estimates of the number of moves required to solve the cube isn't helpful. You would need estimates of the number of moves to get from one group to the next, e.g. from G0->G1. Starting in G0, making one twist might move the cube farther away from the solved state but at the same time closer to G1 (because Thisthlethwaite is non-optimal). So you can't simply start at the solved state and iterate through moves using BFS to generate the databases.
@@BenBotto Thanks for clarifying. I was way off.
My thought was that since G4 contains all the other groups, I can just use that as a "base" to iterate from as long as I only use the allowed moves of said group. Obviously, I realise now that it doesn't work like that. What would you do instead?
G0->G1 for example, there are many permutations where G1 would be satisfied.
My thought was to generate an ID based on the permutation AND the orientation of the edges, but it still doesn't solve the issue since there are many positions where all the edges are solved, so there's still no "base" case.
@@null06f I can think of a few ways of tackling this, but here's the way I would probably go about creating a pattern database for G0->G1.
In G1, only the edge orientations matter. In other words, if all of the edges are oriented then the cube is in group G1, regardless of the positions of the edges. There are 12 edges, and the orientation of 11 of the edges dictate the orientation of the 12th, due to edge parity. Each edge can be in one of two orientations. So, there are 2^11=2048 possible permutations of the edge orientations.
I would use IDDFS to generate the database. BFS can be used, but using IDDFS will simplify things, and the efficiency gained by using BFS isn't worth the added complexity in my opinion. I can go into details on that if you want, or you can trust me on it.
Assuming IDDFS, the algorithm is loosely as follows.
Initialize the database as 2048 unsigned bytes, each set to 0x0F. (Let 0x0F mean infinity.)
Start at the solved state and iterate over depths 1...n until all 2048 permutations have been found.
Each time a new edge orientation permutation is encountered
If the permutation has been visited at an earlier depth {
prune the branch
} else {
If the permutation satisfies G1 {
store the depth as the nearest G1 in a variable
write 0 to the database for the permutation
} Else {
write to the database the distance from the permutation to the nearest G1 permutation (distance = depth - nearestG1Depth), but only if this distance is shorter than the current entry in the database for the permutation. (Remember that these entries are initialized to infinity.)
}
}
The end result would be a database with exact distances from each state to G1.
@@BenBotto Managed to get a working table after a few trials and errors, just wanted to say thanks again for going above and beyond and explaining everything. it was a huge help
just wanted to point something out in case anyone else is going to use this info:
the only solved (solved means G1 is contended) edges orientation permutation is [0] = 0; (00000000000)
"If the permutation has been visited at an earlier depth" will always be true when [0] is encountered, therefore every time the IDDFS discovers a node that satisfies G1, the branch will be pruned and nearestG1Depth will remain at 0 the entire time, making it irrelevant.
updating the nearestG1Depth every time a solved node is checked regardless if it will get pruned out or not will not work , because node { move = L, depth = 1 } is the same as the root node (no affected edges), therefore the nearestG1Depth should not be updated to 1.
I don't know if "nearestGxDepth" will be relevant to the other tables or not, but if it will, then I think the current approach will cause a bug - i.imgur.com/GHMkNE3.png
basically, what happens when nearestGxDepth is 10 and the current node's depth is 6?
we can't assume that if the current node's depth is smaller than the nearestGxDepth, nearestGxDepth should default back to 0, because what if depth 5 of the same branch was also solved?
I think a work around for that is to store the nearestGxDepth in a stack instead of a variable. push 0 to the stack before starting the IDDFS, and then do this every iteration:
while (nearestDepthStack.top() > currenNode->depth) { nearestDepthStack.pop(); }
and updating nearestGxDepth like this instead:
if (goal is satisfied) push the current depth to the nearestDepthStack, but only if it is bigger than the current stack.top().
haven't tested it yet, so maybe I just "fixed" a non existing bug.
edit: I compared ben's approach vs these:
1) ben's original approach
2) updating nearestG1Depth regardless if it gets pruned
3) like 2), but updating it using the stack method
1) and 3) yielded the same result
2) didn't work, 41 Ids had a value of 0.
here's the finished table: pastebin.com/M5Yfdg9p
C++ hmmmmmm
Just because "Crap++" has a bloated reputation for bad programmers over engineering the simplest things does NOT imply that _everyone_ has fallen for its pitfalls.
If you actually _read_ Ben's article on Medium you see he discusses data structures early on -- the hallmark of a good programmer.
Instead of whining about "Crap++" how about providing a good C version so we can judge how it compares on run-tune performance and code readability versus Bens C++ version?
@@MichaelPohoreski Well, I can't compile it because of that asm volatile nonsense. Also, why stop at C? Just go straight into binary.
@@puppergump4117 It compiles with g++, with all warnings on and in strict mode (-pedantic), with 0 warnings from the compiler. You can also use the provided Docker image, which is pre-baked with all the required dependencies. I've compiled it in both Windows and Linux.
The ASM bit is an optimized way of rotating sides of the cube, which I discussed in my Medium article (the part about bitboard-type structures).
@@BenBotto oh ok, I was trying to compile with Visual Studio lol
why nobydy show what programm he used to open its crap??
It didnt work...
But Idea is nice.
No program is used to open anything. The video and Medium articles are for programmers and math enthusiasts. The open-source code can be compiled using g++, generally under Linux.