search

ldez / cubejs

cube.js -- JavaScript library for modeling and solving the 3x3x3 Rubik's Cube
http://ldez.github.io/cubejs/
MIT License
315 stars 47 forks source link

Discussing the possibility of new features / improvements #39

Closed emilgoldsmith closed 5 years ago

emilgoldsmith commented 5 years ago

Hi @ldez, I thought this would maybe be the best place to discuss things like this. If you have the time I'd love some help hashing out how feasible these things are and maybe some pointers as to where in the algorithm one could make changes to make this work as while I've been reading a bit about two-phase, I'm far from an expert on it

I was thinking of two things:

  1. A feature that would be really cool would be partial solves, so that you could mark some pieces as irrelevant and for example find optimal cross/X-cross solutions, optimal solutions to initial 2x2x2, 2x2x3 blocks etc. I already have a pretty good idea of how one could structure the outward facing API for this, but I'm not sure if it's easy to augment the algorithm to allow for this? I know CubeExplorer had features like this so I guess it's possible?

  2. I can see that right now we only consider one candidate solution for phase 1, and Kociemba writes that by considering suboptimal solutions for phase 1, it may greatly reduce the solution to phase 2, making the overall solution more efficient. I'm also personally interested in maybe adding in the functionality of listing out several candidate solutions, especially in conjunction with the above features, so as a human one can see several different approaches.

There are probably also other cool optimizations one could make from http://kociemba.org/math/imptwophase.htm though I'm not sure I'm as motivated to personally look into too many of those at the moment.

I guess I'm mainly looking for suggestions on how to approach the first point if you think that's not too big of a task. Do you have any ideas?

Thanks!

akheron commented 5 years ago

I'm afraid point 1 is not possible with Kociemba's algorithm. The sub-states and their corresponding pruning tables have been specifically designed to aim for a fully solved cube, and only it. Cube explorer probably has other optimizations for solving partial states.

Point 2 would be possible, but the you'd have to assign a time limit for the total solve to not try deeper and deeper phase 1 solutions forever.

A cool optimization that I would have liked to have from the start are the symmetry reductions, which would make the pruning tables smaller by a factor of 16 or something. This code is pretty direct translation of the Java algorithm Kociemba made available, and unfortunately it didn't have the symmetry reductions. The reductions were a bit too heavy mathematics at least for me at the time :)

emilgoldsmith commented 5 years ago

Okay, thanks for the feedback! I'll close this issue for now so it doesn't clutter up the issues.

And yes of course one would put some kind of limit on how much one tried phase 1 solutions, and there should probably also be an option in the API that could allow the user to decide how optimal a solution they're looking for.

And for point 1 I was thinking one could maybe make some kind of hack where you tricked Kociemba's algorithm into thinking it was solving a full cube but just always telling it that all the irrelevant pieces were solved or something like that? Maybe I'll look at it a bit more, though I trust you know what you're talking about