Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Feature Request: Limit prefix of solutions/generators #98

Open
coldsun0630 opened this issue Jan 22, 2025 · 32 comments
Open

Feature Request: Limit prefix of solutions/generators #98

coldsun0630 opened this issue Jan 22, 2025 · 32 comments

Comments

@coldsun0630
Copy link

coldsun0630 commented Jan 22, 2025 •
edited
Loading

It would be good if there's a feature that can limit prefix(a sequence of moves) of generators/solutions. Here's a simple example (let's just say the only possible moves are 1QTM of 3x3x3):

Puzzle: 3x3x3
Scramble: U
Banned prefix: U, U'
Solutions:
• R R F R F' U' R R B' R' B
• R R F D R' D' R R F' U' R
• (...)

//
It'd be also useful for reducing computation time for some symmetrical cases. Let's take the 'superflip' case as an example. You know that the very first move of any possible solutions are symmetrical to U move. To reduce those 12 symmetries into one, we can do something like this:

Puzzle: 3x3x3
Scramble: U R R F B R B B R U U L B B R U' D' R R F R' L B B U U F F ('superflip' case) + U
Banned prefix: U'
Solutions:
• R R B' D F' R B' L' F' R' L D' L L F U' B L' F R B R' L

Then we can get the final solution:

• U R R B' D F' R B' L' F' R' L D' L L F U' B L' F R B R' L

Of course, this trick works with or without "Banned prefix", but the time will be reduced even more if that feature was available (by 11/12 in the example).

//
I suggested this because it seemed like the 'symmetry reduction' feature didn't work on my console. The computation time of "a symmetrical case" and "a symmetrical case + U" were the same per each depth in the same condition. I think it's not implemented yet?
@lgarron
Copy link
Member

lgarron commented Jan 22, 2025

Are you looking for this in the C++ implementation or the Rust implementation?

The Rust implementation supports this, although it's not hooked up as a commandline argument yet.

@coldsun0630
Copy link
Author

coldsun0630 commented Jan 23, 2025 •
edited
Loading

So you mean by "banned prefix", is supported in the Rust implementation?

I'm using it for some heavy search, so C++ version (which has multi-threading support) would be preferred.

@rokicki
Copy link
Collaborator

rokicki commented Jan 23, 2025 via email

@coldsun0630
Copy link
Author

coldsun0630 commented Jan 23, 2025 •
edited
Loading

My main interest is only in saving computation time. I wouldn't care about the "limiting prefixes" thing, if symmetry reduction is actually a viable option and way more straightforward to be implemented.

I should mention that I am at a very beginner level in programming. I would like to, but I'm afraid to say that making any contribution to a project like this seems very difficult for me now.

/
In FTO, I'm looking for optimal solutions of 4 cases.

I managed to find a 21 move solution for 1 case (it doesn't necessarily mean that 21 move is optimal, due to cube rotations):

Scramble: U F BL' U F BL' U F R BL' L B' R L B' R L B' R B R' B' BR' U' BR U B R B' R' U' BR' U BR B L B' L' BL' U' BL U L B L' B' U' BL' U BL L R L' R' F' U' F U R L R' L' U' F' U F
//pure superswap of triangles + superflip of corners

Solution: U F' BR' U B' D R D' B R' F' BR' U D' L B' L' D F' B BR'
//pseudo superswap of triangles + superflip of corners
//(+ failed to find any ≤21 movers for the pure one.)

I have tried for a ≤20 movers searching (depth ≤19 with "scramble+U", in fact) and couldn't get any solutions, for 2 cases (again, it yet doesn't mean an optimal solution is at least 21 movers, due to cube rotations):

Scramble: U D' F' B U D' L' BR F' B L' BR R' BL F' B R' BL R B R' B' BR' U' BR U B R B' R' U' BR' U BR B L B' L' BL' U' BL U L B L' B' U' BL' U BL L R L' R' F' U' F U R L R' L' U' F' U F
//pure superswap of edges + superflip of corners

Scramble: U F BL' U F BL' U F R BL' L B' R L B' R L B' U D' F' B U D' L' BR F' B L' BR R' BL F' B R' BL R B R' B' BR' U' BR U B R B' R' U' BR' U BR B L B' L' BL' U' BL U L B L' B' U' BL' U BL L R L' R' F' U' F U R L R' L' U' F' U F
//pure superswap of triangles + superswap of edges + superflip of corners

And few minutes ago, a depth 20 search (for ≤21 movers) just completed and still no output, for 1 case (〃):

Scramble: U F BL' U F BL' U F R BL' L B' R L B' R L B' U D' F' B U D' L' BR F' B L' BR R' BL F' B R' BL
//pure superswap of triangles + superswap of edges

Log:
Solving FTO-superswap_triangles+superswap_edges+U
Depth 20 in 61420.3 lookups 5147769629523 rate 83.8122

A depth 21 search on my processor is roughly estimated at 9 days, and I need to check all 12 possible cube rotations to prove its optimality, per case.
I would just like to know if any of those cases can lead to raise the current lower bound of FTO, and that's all for now. Of course, you can ignore it if you're not interested in.

@rokicki
Copy link
Collaborator

rokicki commented Jan 24, 2025 via email

@rokicki
Copy link
Collaborator

rokicki commented Jan 24, 2025 via email

@rokicki
Copy link
Collaborator

rokicki commented Jan 24, 2025 via email

@coldsun0630
Copy link
Author

Sorry for late response. I was writing a script for translating algorithms to UF corner be fixed. Now scrambles for all 4 cases are reduced to <BR, BL, B, D, br, bl, b, d> (which is not essential to be done), and any outputs should be able to be reduced into single-layer turns, later.

Also, you might want to use one that fixes a corner; that will solve your problem with cube rotations.

Yes, I had forgotten that obvious fact. I could fix one of any pieces that has a unique permutation. Thanks for reminding that and giving me a hint.

Can I ask what FTO definition you are using?
If you're not using one that is symmetry reduced, consider that.

Here's the definition file I use:
https://pastebin.com/j3d8tPfU

If you want to use symmetry on the FTO you can generate an appropriate tws file by (...)

Do you mean by 'symmetry' ignoring the permutation of centers on the same face? If so, then I may using the correct one.

By specifying this move set, you are fixing a single corner. Of course all
solutions (and inputs) will be restricted to these moves, so you'll have to "undo" the move mapping. With this, the symmetry will be reduced from 24 to 4, so the speed won't be as fast as the symmetrical one above, but it will still be faster than the one with no symmetry.

Not really important thing, but doesn't it actually reduce from 12 to 2? Since the corners of FTO have only two possible orientations. (The other 2 of 4 orientations are not reachable with those regular turns.)

What kind of machine are you using? How much RAM, how many threads?

I've just checked my hardware info through my terminal:

 *-memory
      size: 31GiB
 *-cpu
      product: 12th Gen Intel(R) Core(TM) i5-12600K

i5-12600K has 16 threads(P6+E4), and I was running twsearch with '-M 16384 -t 12' options (which threads are allocated to all the performance cores, ...probably).
My physical memory is 64GB(32GB*2), and I literally just noticed my Ubuntu only recognizes 32GB of memory. (Maybe because I'm running Linux through microsoft-standard-WSL2. I think I need to troubleshoot this now, or just install Ubuntu directly.)

If the conversation is going slightly off-topic from the issue, and if this isn't the best place to discuss such things, I could try reaching out to you via email, or Discord. (I'm also in the FTO server.)

@rokicki
Copy link
Collaborator

rokicki commented Jan 25, 2025 via email

@coldsun0630
Copy link
Author 

bun ./cubing.js/src/bin/puzzle-geometry-bin.ts --ksolve --rotations --optimize FTO > ftosymm.tws

Following your instruction, I have generated 'ftosymm.tws' and opened it with notepad, and I can't figure out which part makes it symmetric and let the prune table be more efficient. It does seem to me, to have no differences with the FTO.tws file I'm already using. Also, I can see some random rotation names like "Move D_BR_R_Fv", and it seems to be not easy to know which one is which. (If those rotations does matter with recognizing symmetries, does adding definitions of rotations to the .tws file (the one I was using) do the same trick? If so, how does it let twsearch know that those moves are actually one of rotations, not turns?)

Also, instead of generating "ftosymm2.tws" or "ftosymm3.tws", I think I could just do "--moves U,F,R,L,u,f,r,l" on twsearch. Does it make any difference, from generating and using a .tws file which only contains U,F,R,L,u,f,r,l moves?

If you want to use slice moves too you can specify them with 2U (for instance) instead of Us.

I'm afraid I don't quite understand it. Does it mean that I can do something like this? (I couldn't find any documentations for puzzle-geometry-bin.ts):

bun ./cubing.js/src/bin/puzzle-geometry-bin.ts --ksolve --rotations --optimize --moves U,F,BR,BL,L,R,B,D,u,f,br,bl,l,r,b,d,2U,2F,2L,2R FTO > ftosymm4.tws

It's actually 4. The total state space is reduced by 2, but the symmetry reduction is still a factor of 4, because the symmetry of the moves is still 4-way.

I see. So you mean twsearch (or its prune table) can handle rotations like U vs. D, but not mirrors like U vs. U'? Then, may not clean as reducing on the prune table level, but the 'scramble+U trick (=limiting solutions to those starting with a U move)' will still work though, I guess?

Did you make this by hand, or by modifying an existing tws?

I just downloaded the MFTO.tws file on the FTO Discord server, then analyzed and redefined it for FTO while adding some other moves, all by hand.

@rokicki
Copy link
Collaborator

rokicki commented Jan 26, 2025 via email

@coldsun0630
Copy link
Author

Okay so umm... To summarize, if I add "Moves" for rotations to the .tws file, twsearch tries to search conjugations by those defined "Moves", and will notice symmetries like U = Rv B Rv'? (Hence the pruning table will be efficiently reduced, treating them as a node and put those move sequences(U, Rv B Rv', ...) as key values of the same node.)

According to my understandings:

  1. The 3x3x3.tws which already built in the twsearch won't reduce for symmetries, because the x, y, z moves are not defined(contained) in the file.

  2. When '--moves' option is not applied, twsearch may contain the rotation "Moves" to its output, which implies the pruning table still does interact with those rotation "Moves".
    For example, if I give Uv' (or its equivalent position) as ScrambleAlg, then it will output Uv as an optimal solution, and Rv Bv Uv' as second optimal, instead of treating it as a solved state or outputting solutions like F' D' U B BL' D' U R BR' D' U L F' D' U B as an optimal.

Then, I need to do:

A. Get contained the rotation "Moves" (Uv, Fv, ...) in the .tws file, to get advantage of symmetry reduction in the pruning table.

A.1. Limiting subgroup of moves (to single/double layer turns) in twsearch should not prevent from reducing symmetries, since rotation moves are already contained in the .tws file.

B. Limit those "Moves" with "--moves U,F,R,L,B,D,BR,BL" or "--moves U,F,R,L,u,f,r,l" to not waste computation time, by avoiding the repetitive interactions with other defined moves like `Uv, Fv, Rv, ... (=rotations)".

I feel like I’m getting a bit closer to understanding how the things work. Please correct me if I'm wrong. Thank you.

@rokicki
Copy link
Collaborator

rokicki commented Jan 27, 2025 via email

@coldsun0630
Copy link
Author

coldsun0630 commented Jan 28, 2025 •
edited
Loading

No, twsearch never considers rotations as "moves" when searching.

One last. How does twsearch know and automatically classify which 'Move' is a rotation or not, when all are just labelled as 'Move' in the file? The 'symmetry reduction' (i.e., searching through all conjugations by each 'Move' and checking if they're equivalent)?

@rokicki
Copy link
Collaborator

rokicki commented Jan 28, 2025 via email

@coldsun0630
Copy link
Author

I see.
I'll redo my research using your advice. I'll let you and the community know if I find something from it. Thanks so much for sticking with me. :)

@DougCube
Copy link

I'm using a fully symmetry-reduced definition file and running these 4 scrambles thru to see what I can find for them.
I'm using a very fast machine with 128 GB of RAM.

I've been trying to improve the lowerbound for God's number on FTO.

@coldsun0630
Copy link
Author

coldsun0630 commented Jan 31, 2025 •
edited
Loading

Good to hear that!

Are you using consumer product? Are you running all 4 instances in parallel?
Are you searching with the tricks described above? (fixed corner --moves, start searching from "U"-ed position)

I'm currently on with 50GB of RAM. If your processor is, say, a 9950X, then it'd be at least 2.4x faster than my 12600K (yeah, slow as snail for these kind of work).
I might stop mine if your machine is good enough (to replace it), and if you'd like to help me out. :)

@DougCube
Copy link

DougCube commented Feb 1, 2025

Don't stop yours. It takes me like 8 hours per if I was searching for one solution. But I'm searchng for all optimal solutions.
So far this is what I have for the first scramble, and it confirms 21 is the optimal length for it:

U F L BL' D' F B BR U' F L BR D' BL' B BR U BR U BL BR [21]
U F' BR' U B' D R D' B R' F' BR' D' U L B' L' D B F' BR' [21]
U F' BR' D U B' R B D' R' F' BR' D' U L B' L' D B F' BR' [21]
U BL B BR' D' BL R F U' BL F B D' BR' R F U F U BR F [21]
U BL' F' U D R' L R D' L' BL' F' D' U B R' B' D R BL' F' [21]
U BL' F' U R' D L D' R L' BL' F' D' U B R' B' D R BL' F' [21]
U BR R F' D' L BR BL U' BR BL R D' F' L BL U BL U F BL [21]
U BR' BL' D U L' B L D' B' BR' BL' U D' R L' R' D BR' L BL' [21]
U BR' BL' U L' D B D' L B' BR' BL' U D' R L' R' D BR' L BL' [21]
...

I'm not running all of them in parallel. I'm using a C++ wrapper around twsearch and my own definition file. It basically accomplishes a lot of the optimizations listed above.

@rokicki
Copy link
Collaborator

rokicki commented Feb 1, 2025 via email

@rokicki
Copy link
Collaborator

rokicki commented Feb 1, 2025 via email

@coldsun0630
Copy link
Author

Okay. I'm currently looking into 'superswap of triangles + superswap of edges (+d move)' case (the 4th one).
No output until depth 20, so it should break the current lower bound of 21 move.

Searching the 21th depth on my machine is estimated at <2days. Let's see what comes out.

@coldsun0630
Copy link
Author 

Scramble:
U F BL' U F BL' U F R BL' L B' R L B' R L B' U D' F' B U D' L' BR F' B L' BR R' BL F' B R' BL
// superswap of triangles + superswap of edges

Solutions:
U F U' B' BR' D' L' D' R L' R BR U' R D' BR F R' F' BL U F L  [23]
U F L D' BL U' L F D R U B' R L F BR L F U B U R F'  [23]
...

I'll move on to other scrambles.

@rokicki
Copy link
Collaborator

rokicki commented Feb 19, 2025 via email

@coldsun0630
Copy link
Author

I have found two 23-movers and three 22-movers so far.
I have also found a 24-length solution for a pure cycle case(=centers are unique) which is suspected to be optimal.
I'm currently running the program for other seemingly-hard cases (≥21 moves).

For some less-symmetrical cases, the time is estimated at 13d [Depth 22] / 167d [Depth 23] on my machine.
I expect it will take quite a long time to go through all the cases.

I actually think there is some chance that a 24-mover case will exist, but knowing it and picking it up is just a whole different story. (The equivalences of center pieces makes the prediction harder.)
Whether or not the lower bound gets updated, I'll disclose the result to the community (and ping you so you'll get noticed) after the attempt has been completed.

@rokicki
Copy link
Collaborator

rokicki commented Feb 22, 2025 via email

@coldsun0630
Copy link
Author

Glad to hear that. Thanks, I'll consider to do so if I find a good 24-mover candidate worth your biggg machine. :)

@DougCube
Copy link

I had stopped running mine because it kept crashing my machine. :(

@rokicki
Copy link
Collaborator

rokicki commented Feb 23, 2025 via email

@DougCube
Copy link

I was running on a machine with 128 GB of RAM, but it was running is WSL2 inside Windows 10 Pro, which I didn't know at the time defaults to limiting to half of the physical memory. I have since changed it to 96GB. I was also running other stuff on the machine. And I was unnecesarily using '--alloptimal' on a highly symmetric scramble.

I also forgot to 'tee' the result into a file and lost all work when it crashed. :(

@rokicki
Copy link
Collaborator

rokicki commented Feb 23, 2025 via email

@coldsun0630
Copy link
Author

I was running on a machine with 128 GB of RAM, but it was running is WSL2 inside Windows 10 Pro, which I didn't know at the time defaults to limiting to half of the physical memory. I have since changed it to 96GB. I was also running other stuff on the machine. And I was unnecesarily using '--alloptimal' on a highly symmetric scramble.

I also forgot to 'tee' the result into a file and lost all work when it crashed. :(

Mine is also WSL2 with Windows 10 Pro (currently) and no crash over days of execution.
Maybe you can try limiting threads (-t option) to let the processor run Windows OS stably.

I set the twsearch to use 14 (of 16) threads & 48 (of 64GB) of RAM.
While twsearch is on, I do browsing + some GPU-heavy stuffs, and everything works just fine.

Here's my exact command line of the twsearch, which is on execution now:
./build/bin/twsearch -M 49152 -t 14 --mindepth 22 --alloptimal --moves U,F,R,L,u,f,r,l "samples/main/ftosymm.tws" "samples/main/FTO-test_scr.scr"

/
Plus: after logging into the Windows OS, I recommend to run twsearch at first or it will get a bit slower, about 15-20% in my experience. (Possibly due to: partially using swap memory, allocating efficient cores, etc.).
I reboot every time whenever I run new instance of searching.

You need to turn off Windows Update before doing everything though. (Yes, I also had lost all work once too.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@lgarron @rokicki @coldsun0630 @DougCube