# 4x4x4 FMC (computer and human)



## rokicki (Mar 12, 2014)

We're live! Give it a shot, human or computer, your code or someone
else's. Let's see what we can do. Two months, five positions.

http://codercontest.com/toms-fmc-4x4x4/


----------



## Lucas Garron (Mar 12, 2014)

I took some while to convince everyone to use regular scrambles for official FMC, but we have been doing it without major problems for over a year now.

Just generate a 4x4x4 TNoodle scramble. You can't prevent humans from cheating with a computer, so you might as well make it easy for humans to scramble their cubes.

Some suggestions:

- OBTM for the metric.
- Change to the format from 1 scramble make it a (trimmed) average of 5. This requires a more general approach instead of very specific searching/luck, but it does allow some tuning.
- Use separate scrambles for the human vs. computer-aided challenges.
- No limits on human+computer interaction, as long as any solution is accompanied with code and a decent explanation at the end of the contest (i.e. the solution didn't just appear out of thin air). I'd rather use this to encourage openness instead trade secrets.


----------



## cmhardw (Mar 12, 2014)

I'm very interested in the human challenge. I agree with Lucas about just posting a standard scrambling alg.


----------



## rokicki (Mar 12, 2014)

Okay, this is starting to shape up. Prizes based on OBTM trimmed average of five.
Leaderboard showing current scores but not solutions. Gold stars for leaders of
individual positions, and leaders on BTM. Initial timeline probably two weeks.

Is it useful to distinguish "computer-assisted" (Javascript player, but no search)
vs fully manual (just paper and cubes)? I think not, but am happy to be corrected.

I'll need to write some code and set it up on a host; this may take a bit of time.
If anyone wants to help that would be cool.


----------



## Jokern (Mar 12, 2014)

A 200 move scramble is not a problem at all for the computer part of the competition. For the computer competition it is more important to make the scramble long so you don't have any help from that, because it is easier to cheat. (I guess it will be hard if source code have to be supplied but still)

For the human competition a normal scramble is enough.

Also I do very much look forward to this being a thing!


----------



## Lucas Garron (Mar 12, 2014)

Jokern said:


> A 200 move scramble is not a problem at all for the computer part of the competition. For the computer competition it is more important to make the scramble long so you don't have any help from that, because it is easier to cheat.



That doesn't really make sense. Assuming you're trying to beat our current reference (Chen Shuang's code, used in TNoodle), the scramble won't really help you beat... the scramble.
And if you had a long scramble and wanted to get a short scramble to "cheat", you could always run it through Chen Shuang's code for that.

So, it doesn't really make sense to try to restrict anyone's access to a short version of the scramble.


----------



## Stefan (Mar 12, 2014)

Lucas Garron said:


> you could always run it through Chen Shuang's code for that.



If you can find it. And I'm under the impression that that's nearly impossible  (I just tried (because I thought Clement had coded that) and failed)

Looking forward to this challenge.


----------



## rokicki (Mar 12, 2014)

I actually think I'm going to just use "random-move" type scrambles and make them somewhat
longer than what tnoodle would generate. This way there won't be an obvious phase
decomposition.

Locating and using a 4x4x4 solver may be trivial for many on this list but it may be nontrivial for
others.

I hope to get this up sometime in April. In the meantime if someone wants to start a 4x4x4 FMC
challenge thread just for kicks, since it is apparently of interest, feel free to do so.


----------



## cuBerBruce (Mar 14, 2014)

There used to be a 4x4x4 FMC event in the weekly contest on this forum. It seems to me the boundary between "good" and "mediocre" was something on the order of 100 moves. The time limit was 2.5 hours. Of course, any assistance by computers, other people, or alg sheets is not allowed in "true" FMC. For an online-based competition, it is basically impossible to determine if such rules are being complied with.

Any contest for essentially human-based solutions must be very clear to what exactly is allowed as far as computer assistance is concerned. Evens so, compliance with rules I would think would be virtually impossible to determine. I would think having prize money for such a category is likely to create controversy.

I think a leaderboard is likely to reduce the number of entries. If people know their solution isn't good enough to win, they likely won't bother to submit it. What reason would someone have to submit their solution(s) early? Perhaps, earliest solution is used as a tiebreaker. But would contestants really want to let others know what the score to beat is?



rokicki said:


> Is it useful to distinguish "computer-assisted" (Javascript player, but no search)
> vs fully manual (just paper and cubes)? I think not, but am happy to be corrected.



Using a computer applet may give a user advantages over an official-style FMC solve (physical cubes and pen and paper). These are mainly important if only a limited time (say 2.5 hours) is allowed to produce a solution. Some ways an applet could possibly help a user save time include:
- Use of instant reset to solved state, or instant reset to scramble state.
- Use of macros to apply whole algorithms 
- Automatic recording of moves made. With a physical cube, the person must remember what moves he's made, or write down the moves as he proceeds (which takes time).

I don't think there should be separate categories for applet (no search) solving and pure physical cube and paper solving, but I think it should be clear what an applet can and can't do if they're allowed.

For physical cubes, it should also be clear what's allowed. For 4x4x4, I like to use a 5x5x5 cube rather than a 4x4x4. This allows me to rotate the cube at will without worrying about losing track of the proper orientation of the cube.


----------



## rokicki (Mar 15, 2014)

Wow, some very insightful comments! I'm going to have to rethink some things.

You're correct; prize money doesn't mix well with rules that are unenforceable.

I'll give this some thought.


----------



## kinch2002 (Mar 15, 2014)

I'm excited for the human challenge. I'd like unlimited time!

Agreed no prize money for the human section. Computer solutions could have some though, to encourage people.


----------



## Kirjava (Mar 15, 2014)

I would find BTM more interesting than OBTM, but will go with whatever really.


----------



## Lucas Garron (Mar 16, 2014)

cmowla said:


> there's no way to logically say that FTM of the 3x3x3 is equivalent to OBTM of the 4x4x4 because inner slices on the 4x4x4 involve different piece types than on the 3x3x3.



I think it's very obvious that a move in *Face* Turn Metric should turn a *face* of the cube, and not just an internal slice.
For a single move in FTM/HTM/OBTM on 3x3x3, there is an externally contiguous moving part of the puzzle while the rest of the puzzle is an (externally) contiguous part that stays still. For conventional twistypuzzles, I think this is by far the most natural way to determine "equivalent" metrics.

You may argue that it makes more sense *for some other reason* to judge 4x4x4 algorithms based on slices, but I don't really see anything relevant about "inner pieces".


----------



## Stefan (Mar 17, 2014)

cuBerBruce said:


> I think a leaderboard is likely to reduce the number of entries. If people know their solution isn't good enough to win, they likely won't bother to submit it. What reason would someone have to submit their solution(s) early? Perhaps, earliest solution is used as a tiebreaker. But would contestants really want to let others know what the score to beat is?



There could be some prize(s) given out randomly, and you get a better probability the earlier you submit your solution. That would encourage both participation as well as submitting good results early.


----------



## unsolved (Mar 21, 2014)

I decided to take a crack at writing my own 4x4x4 solving program. If anyone else has started on such a program, or if one is already in existence, please let me know if I am re-inventing the wheel. I am taking some of my chess code and adapting it for a fast bit-move generator that should outperform matrix calculations.

For example, you can replace 4 separate matrix swaps with bit-AND/bit-OR operations that should execute much more quickly.

U+ keeps the down face the same, and F[1]=R[1], F[2]=R[2], F[3]=R[3], and F[4]=R[4].
Likewise R[n]=B[N] for N = 1 to 4, and B[N]=L[N] and L[N]= the original F[N], so you need to "copy" the 4 front cubes before swapping them to the right.

There is a mathematical/coding trick to do all of these "swaps" with just one operation.
You lay out the 16 cubes per face as bits such as 0000 for cube 1, which means you have 2 cubes/byte.
The upper 4 bits = cube 1, the lower 4 bits = cube 2, etc.
You need 8 bytes, a single long long integer, to store a cube face.

So the new F face after a U+ becomes f_face_variable = (f_face_variable & FFFF000000000000) | (r_face_variable & 0000FFFFFFFFFFFFFFFF);
You replace 4 swaps with only one statement that operates on two 8-byte variables and two 8-byte hexadecimal constants. It's very fast.

When you move just the f slice clockwise (by itself) the math is f_slice_variable = (f_slice_variable & 0000FFFF00000000) | (r_slice_variable & FFFF0000FFFFFFFF);

I am using procedure pointers to speed up the solve by eliminating all of the IF branchpoints that could result.
I just encode the moves as triplets, like F+, F-, and F2, then I make sure no subsequent move would undo the most recent move, or add to it in the same fashion.
So the program won't do F+ F- and think that is a valid "depth 2" position. Nor will it do F2 F+ or F2 F- back to back.
It will allow F+ T+ F+ though, as it should, etc.

I still have to code the notation part. I entered a random 10-move scramble and it found the answer pretty quickly.
I just had no way to see the answer


----------



## unsolved (Apr 20, 2014)

Well I just finished my 4-turns-from-solution database tonight. I have every position with 4 or fewer turns stored in a RAM-based database for probing during the search. The program was able to solve a center swap after only examining 90,188 leaf nodes!







One way people can verify the computer solves is if you let them access your machine via something like TeamViewer, available at TeamViewer.com

I will also be making this version of the program available free to download, that is always another way people can verify the programs are doing as they say.


----------



## rokicki (Apr 22, 2014)

cmowla said:


> I don't want to rush you, Mr Rokicki (I've seen how much of your spare time has been spent on helping others in the software sub-forum), but I was just wondering what happened with this? I recall you mentioned sometime in April the comp would start. (I probably won't be participating though).



Did I actually give a date? Hmm, if I did I'm sorry.

I'm a bit stuck actually; I would prefer *not* to write a bunch of login/registration/track submissions code, but
I'm not sure managing submissions by email would work either. I could potentially abuse the forum to accept
submissions directly in the forum (either encrypted or not).

I'm actually hoping anyone will participate, either human or computer, even if their solution is not the "current
winning one"; even though I enjoy the competitive aspect, I've been very impressed with the sense of
community and mutual support in this forum and would love to see that reflected.

Let me try to put some ideas together and I will probably announce something on May 15th, for better or worse.

Oh, and I appreciate the respect, but please call me just Tom. Thanks!


----------



## rokicki (May 14, 2014)

We're up! The contest is underway. 4x4x4 FMC, computer or human, let's see what we can do.

Two months; plenty of time.

http://codercontest.com/toms-fmc-4x4x4/


----------



## vcuber13 (May 14, 2014)

> you must use WCA syntax (2U) to indicate an inner slice turn.





> 12a2) Outer Block Moves (outer slice plus adjacent inner slices; n is defined as total number of slices to move; n may be omitted for two slices)


In WCA notation 2U = Uw, not a slice move.



> Double slice turns (E, M, S, N)



What is N? And how many moves are you counting for these moves?


----------



## rokicki (May 14, 2014)

vcuber13 said:


> In WCA notation 2U = Uw, not a slice move.



Oops. Sorry. 2U means an inner slice move; I've removed the reference to the WCA notation.



vcuber13 said:


> What is N? And how many moves are you counting for these moves?



N is M'; M is N'. There are two metrics on the contest; OBTM counts N or M as two moves, while
BTM counts it as one.

I also removed the statement that "these are test scrambles". The scrambles provided are the
actual scrambles.

Thanks for the fixes! The applet should help people answer both of these questions, but it's better
to be clear in the writeup.


----------



## cmhardw (May 16, 2014)

Yay, this is exciting! Thanks for hosting this!


----------



## rokicki (May 16, 2014)

My pleasure! Happy to report some submissions have come in already.
Hope to get many more, and then learn about what people did, and how
they did it.

I am *amazed* at what people can do with FMC on the 4x4x4 looking at
some earlier threads.


----------



## irontwig (May 16, 2014)

Okay, you really need to have a box for comments about the solution, as FMC solutions rarely are self explanatory. As for the applet, I think it would be nice to be able to label the sides in some ways (like have an "R" somewhere on the R face), since after some rotations it's hard to know which side is which.


----------



## rokicki (May 16, 2014)

irontwig said:


> Okay, you really need to have a box for comments about the solution, as FMC solutions rarely are self explanatory. As for the applet, I think it would be nice to be able to label the sides in some ways (like have an "R" somewhere on the R face), since after some rotations it's hard to know which side is which.



Excellent suggestions! Don't expect them to happen immediately, however.

Is there a syntax for comments that people use? Perhaps // means that
and everything through to the end of line is a comment (so the comments are
actually interspersed throughout the actual algorithm)?


----------



## cuBerBruce (May 16, 2014)

rokicki said:


> Is there a syntax for comments that people use? Perhaps // means that
> and everything through to the end of line is a comment (so the comments are
> actually interspersed throughout the actual algorithm)?



I think there are a number of problems with trying to intersperse comments in the solution itself. For example, if you use inverse scramble, NISS techniques, and insertions, the flow of the actual steps used don't line up with the actual end result. I think it's better to just have a separate text box for writing a free-form explanation.

Another point is that the explanation will generally include additional moves that get cancelled out or combined in the final solution. The skeleton of the solution is generally shown first, with insertion points indicated with special characters, which often are in the middle of some skeleton step. The actual algs used for insertions are generally shown at the end of the explanation.


----------



## rokicki (May 22, 2014)

I still don't have comment support; sorry. But I do want to mention; please, one solution
per submission please. I'm judging these automatically, and newlines in a submission
are allowed. If you have five solutions to the five different scrambles, submit them one
at a time. Thanks!

Happy to see the activity that is taking place in the contest!


----------



## qq280833822 (May 24, 2014)

Hi rokicki, would you mind making some results public. Such as the length of the shortest solution? 

Btw, how can I know whether my solution is submitted successfully? (I haven't received any confirmation email after my submission.)


----------



## rokicki (May 27, 2014)

Howdy!

I will make some intermediate results public soon, including information about who is
leading, but I probably won't make intermediate lengths-so-far public at this point.

Best way to make sure your submission is successfully received right now is to 
submit it through the applet; if the cube is solved in the applet, your submission
should be fine. But I plan to close the loop soon and give you explicit confirmation
on which scramble (if any) is solved and the calculated length per metric.

Stay tuned!

-tom


----------



## rokicki (May 31, 2014)

Leaderboard, 31 May 2014.

Computer:
Shuang Chen
Charlie Tsai
Kåre Krig

Human:
Charlie Tsai

I have sent the leader of the Computer division and the Human division a
gift card for $30 to add to their puzzle collection or whatever else they may
want to use it for.

At this point I will not share any more information on the actual scores.

All submissions I have received have correctly solved a scramble, except for
one, and I have already notified the relevant participant and he has already
corrected his submissions.


----------



## cuBerBruce (Jun 3, 2014)

Just thought I would post a few of my thoughts regarding the competition.

It appears to me that the applet has a serious memory leak. It seems to cause the browser to eventually use well over a gigabyte of RAM, resulting in problems with the browser freezing for periods of time, and even crashing.

In official competitions, obviously you can't use algorithm sheets or look up algorithms online. This doesn't seem to be explicitly disallowed for human solutions. Of course, if someone pre-generated a huge list of algorithms by computer (such as for all 3x3x3 last layer cases, for example), then used that list in developing a solution, one might argue that is in effect making use of a computer search. For my own human solutions submitted so far, I have not made use of any printed or online algorithm lists - only algorithms I either knew or could figure out without using a computer.

I am guessing Tom is allowing a human solution to be developed after already having developed a computer solution for the same scramble, as long as the person does not use anything from the computer solution in developing the human solution. I think ideally the human solution for a given scramble should be developed prior to working on a computer solution.


----------



## rokicki (Jun 3, 2014)

Howdy, Bruce!

Thanks for the note on the applet. I'm sorry for any problems you are having with the
applet; I shamelessly lifted and modified the alg.cubing.net applet, and I could possibly
have broken something. The applet does save its state, so if you suspect there is an
issue coming you can always close it and reopen it; I hope that will resolve the memory
issues.

The human portion of the competition is somewhat on the honor system; I have no way
to enforce any sort of constraints. This is why the official cash prizes are only for the
computer solutions (although I may award random prizes at random times for anything
I feel like). I plan to add a textarea to the applet so people can explain their solution,
but even then there's no guarantee they haven't cheated in any number of ways.

On the other hand, people do have names and reputations, and this is pretty much a
friendly crowd, so I'm not too worried about people cheating. If they obviously cheat
I may disqualify them or terminate the human part of the competition (or terminate
both).

I am allowing people to submit any solutions they want in any order; computer or
human, or both. Yes, it's possible someone "picked something up" from a computer
solution and used it in the human solution. Given the few people competing so far,
and the fact that they are all fairly well known in the community, I'm not too worried.

I'm curious to see how well humans can do right now in FMC (it's certainly well
beyond what *I* can do). Already the results are somewhat enlightening to me.

Thanks for your comments, and for your participation! Feel free to add more.

-tom


----------



## 10461394944000 (Jun 3, 2014)

rokicki said:


> Thanks for the note on the applet. I'm sorry for any problems you are having with the applet; I shamelessly lifted and modified the alg.cubing.net applet, and I could possibly have broken something. The applet does save its state, so if you suspect there is an issue coming you can always close it and reopen it; I hope that will resolve the memory issues.



i'm pretty sure the memory leak is in the standard alg.cubing.net app too


----------



## ch_ts (Jun 3, 2014)

I don't want to reveal my solution lengths yet, but I will reveal that my human solutions were done by reduction (which may not necessarily be the best approach). I did reductions without any algorithms, but using ideas developed in the weeks after Tom announced he would hold a contest and before it opened. Then just a regular 3x3x3 FMC. I will also reveal that none of my 3x3x3 human solutions were sub-30 moves, so that is an area where I could definitely improve. I thought there used to be a 4x4x4 fmc in this forum, however it looks like they don't do it anymore and I couldn't find any old 4x4x4 fmc solutions to study.

I personally think that the way people (including me) do reduction is inefficient and could use some work. For example, imagine if people used a set of ~50 algorithms (or comparable to what people know for CFOP) during reduction. In my opinion, doing reduction without algorithms is somewhat like doing 3x3x3 without algorithms (or using a minimal set) - basically a beginner method. I tried to come up with a good method in the past but nothing came out of it, but maybe somebody else can during the contest. (then again, reduction may not be the best approach)


----------



## rokicki (Jun 21, 2014)

Leaderboard: Human:

Bruce Norskog
Charlie Tsai

And that's it. I'd love to see more human solutions.

Congratulations, Bruce, for taking over the lead on the
Human competition!

Computer standings remain unchanged.


----------



## cuBerBruce (Jun 29, 2014)

rokicki said:


> Congratulations, Bruce, for taking over the lead on the
> Human competition!


Obviously, I was pleased to be on top of the leaderboard (human category). I see no mention of the metrics on the leaderboard listings. I am guessing that means that there is no difference in the rankings between OBTM and BTM. I would not be surprised at all that the rankings for the two metrics would be very similar. I mostly have been aiming to get a good OBTM move count, and hope that I'll get some decrease from that in the BTM count. My best OBTM solution so far has no such decrease for BTM, though.

I note that my solutions, like Charlie Tsai's, are based upon reduction. I think some form of reduction will be the most widely used strategy for the human solutions (and maybe computer solutions as well). Of course, you need to work at doing the reduction efficiently as you can. Getting some edges paired during the center solving phase can make a difference in reducing the move count of the edge pairing phase. And, of course, you avoid the parities. I now have the 3x3x3 phase solved in close to 30 moves for all five scrambles, although only one is actually less than 30 in FTM (OBTM). So someone that can readily produce sub-30 solutions for 3x3x3 could certainly overtake me on the leaderboard.


----------



## rokicki (Jul 10, 2014)

Current rankings:

Computer, OBTM:

Shuang Chen
Stefan
Charlie Tsai
Kåre Krig

Computer, BTM:

Shuang Chen
Charlie Tsai
Stefan
Kåre Krig

Human (same for both metrics):

Bruce Norskog
Charlie Tsai

Roughly five more days to go!

-tom


----------



## Stefan (Jul 11, 2014)

If I submit solutions A and B for the same scramble and A is better in BTM and B is better in OBTM, do you use A for my BTM score and B for my OBTM score?


----------



## rokicki (Jul 11, 2014)

Stefan said:


> If I submit solutions A and B for the same scramble and A is better in BTM and B is better in OBTM, do you use A for my BTM score and B for my OBTM score?



Yes.


----------



## rokicki (Jul 15, 2014)

It's over! Results in a few hours. Thank you all for participating.


----------



## rokicki (Jul 16, 2014)

Tom's Fewest Moves Challenge: The Results

After two months, the results are in! First, the human results.

There were only two competitors in the human division, and here
are their results:



```
OBTM                Avg.  BTM                 Avg.
                   ------------------------  ------------------------
1. Bruce Norskog   75  75  76x 71  67x 73.6  72  72x 69  67  67x 69.3
2. Charlie Tsai    79  87x 72x 79  81  79.6  79  86x 71x 76  79  78.0
```

Bruce wins first place in both metrics, and Charlie wins second
place. Congratulations to both competitors; these are amazingly
short solutions!

There were five competitors in the computer division. These are
their results. First, the Outer Block Turn Metric:



```
OBTM                    Avg.
                   ----------------------------
1. Stefan Pochmann 41   41   42x  40x  41  41.0
2. Shuang Chen     42x  41x  42   41   41  41.3
3. Charlie Tsai    50   48x  49   52   53x 50.3
4. Bruce Norskog   47   53   56x  43x  52  50.6
5. Kare Krig       92x  95  109x 102   99  98.6
```

Next, the Block Turn Metric:



```
BTM                     Avg.
                   ----------------------------
1. Stefan Pochmann 38x  37x  38   37   37  37.3  
2. Shuang Chen     38x  39x  39   38   38  38.3
3. Bruce Norskog   46   44   49x  41x  46  45.3
4. Charlie Tsai    47x  48   47   49   50x 48.0
5. Kåre Krig       69   67x  73x  70   69  69.3
```

In both metrics, Stefan Pochmann wins first place, and Shuang
Chen wins second. It was a very tight competition; congratulations
to both winners!

All winners will be hearing from me by email within the next
24 hours. I'd love to see how people approached this problem
in this thread!

(In the tables above, the x's mark the high and low solutions
omitted from the calculated average.)


----------



## Stefan (Jul 16, 2014)

Thanks for hosting the contest!

I used Shuang Chen's 4x4x4 solver for reduction to 3x3x3, and then the huge optimal solver of Cube Explorer 5.01*s*. With a script of my own in between.



Spoiler: More details



I slightly modified Shuang Chen's solver to feed our scrambles into it, to search more (multiplying the numbers like PHASE1_SOLUTIONS by 100 or 1000), and to print not just one solution but keep printing solutions that are not more than three moves longer than the shortest so far (counting in OBTM, as that's what that solver uses). I stopped it when I had around 1000 OBTM-short reductions (or rather, solutions containing them) for each scramble.

Then I used a (messy and quite possibly buggy) script of my own to extract the reductions (and 3x3 parts), minimize them for OBTM (some cancellations were possible) and BTM (much was possible, as Shuang Chen's solver doesn't use BTM), sort them by resulting move count and produce input files for Cube Explorer that looked like this:

```
L U R' B U' F2 B D' U R F2 L2 U2 R' U2 R' D2 B2 // line4 BTM 22 redux: Dw Fw D' Lw2 B Uw Lw U2 Fw2 2U2 D' B2 U2 Lw D' R2 F Uw2 Rw2 D L2 Bw2
  F2 L U R' B U' F2 B D' U R F2 L2 U2 R' U2 R' D2 B2 // line4 BTM 22 redux: Dw Fw D' Lw2 B Dw y Lw U2 Fw2 2U2 D' B2 U2 Lw D' R2 F Dw2 y2 Lw2 x2 D L2 2F2 z2
  B2 L U R' B U' F2 B D' U R F2 L2 U2 R' U2 R' D2 B2 // line4 BTM 22 redux: Dw Fw D' Lw2 B Dw y Lw U2 Fw2 2U2 D' B2 U2 Lw D' R2 F Dw2 y2 Lw2 x2 D L2 2B2
B' L2 B' U2 D2 L2 F R2 B L U2 F D B' L' U R2 F' B' L' // line13 BTM 22 redux: R2 Dw2 Bw' U' Rw' 2B' S2 L' F2 Uw D B' L2 Uw L D2 2B2 Dw2 R' B' Rw2 Dw2
  U2 B' L2 B' U2 D2 L2 F R2 B L U2 F D B' L' U R2 F' B' L' // line13 BTM 22 redux: R2 Dw2 Fw' z U' Lw' x' 2F' S' L' F2 Dw y D B' L2 Dw y L D2 2B2 Dw2 R' B' Lw2 x2 2U2 y2
  D2 B' L2 B' U2 D2 L2 F R2 B L U2 F D B' L' U R2 F' B' L' // line13 BTM 22 redux: R2 Dw2 Fw' z U' Lw' x' 2F' S' L' F2 Dw y D B' L2 Dw y L D2 2B2 Dw2 R' B' Lw2 x2 2D2
.
.
.
```
This is the start of my input file for scramble 1 for BTM. Each line is a 3x3x3 part that I want Cube Explorer to optimize, and in the comment the already "optimized" reduction leading to that 3x3x3 part (gets shown in Cube Explorer as "Pattern Name"). Note that most of the time each reduction gets "tripled" because when the reduction for example ends in Bw2, you can append a B2 or F2 for free (doesn't change the BTM length as they just turn the Bw2 into 2B2 or 2F2 z2). This gives you three times as many 3x3x3 chances to try.

Then in a Cube Explorer clickfest, I tried the cubes from the shortest reductions first, and stopped searches when they couldn't lead to a shorter solution than I had already found at that point. Only tried the first few dozen or so for each scramble, gave up when I would've needed like 14 HTM to improve. Oh and for BTM I used the "Allow Slice Moves" option, which I somehow hadn't known existed.


Tom, one thing I'm curious about: How did you produce the scrambles? Looks like 3x3+reduction+random, but the 3x3 part is pretty long and the reduction part is pretty short. Doesn't look like Shuang Chen's solver, so I'm wondering...


----------



## Renslay (Jul 16, 2014)

Congrats to everyone! Impressive numbers.


----------



## ch_ts (Jul 16, 2014)

Tom, will the actual solutions be posted anywhere? Or should we share our own solutions here?


----------



## cmhardw (Jul 16, 2014)

Wow, impressive numbers from the computer and from the human competition! Very exciting, and congrats to the winners!


----------



## goodatthis (Jul 16, 2014)

Wow, impressive! I'm really curious to see the solutions to the human solutions, especially how they were able to obtain them.


----------



## ch_ts (Jul 16, 2014)

These were my solutions:

Human FMC:

Scramble 1

Scramble 2 

Scramble 3

Scramble 4

Scramble 5

Scrambles 1, 3, 4, 5 were done using cmowla's reduction method described here. Initially they were all done centers first then edge pairing, about 55 moves for reduction and I thought that was pretty good. But then Tom updated the leaderboard and I found cmowla's method and used it to try to get ahead of Bruce. If I had known his actual score, I don't know if i would have tried as hard as I did.


Computer solutions were done using my reduction method (4 reduction steps) using single slices for the BTM metric and using wide turns for the OBTM metric. One ugly hack I tried was to check at end of step 1 if step 2 was also accidentally solved, otherwise find another solution, and if it worked I would use it for steps 3 and 4. It didn't find anything after 15 minutes so I stopped the search. 

3x3x3 solutions were found using Cube Explorer.

Computer BTM: (used single slice turns during reduction)

Scramble 1

Scramble 2

Scramble 3

Scramble 4

Scramble 5

Computer OBTM: (used wide turns during reduction)

Scramble 1

Scramble 2

Scramble 3

Scramble 4

Scramble 5


----------



## cuBerBruce (Jul 16, 2014)

Here are my explanations for my "human" solutions. Due to length, I've used a spoiler.

I note that as far as solving the centers are concerned, all face turns (single-layer) can be considered to be commuting moves. That potentially allows for "one" centers solution to essentially produce many different configurations for the edge pieces for the start of the edge pairing phase. This can hopefully be used to get a few edges paired up before even starting the edge pairing phase. Being allowed to use Tom's applet was especially helpful to do this fairly efficiently.

In some ways, I'm somewhat disappointed that only one other person competed in this category. My 3x3x3 phase solves were not particularly super by today's standards (and there was no 1-hour time limit, obviously) so I think a good FMC'er should have been able to beat my solutions.



Spoiler





```
Scramble 1:

First center: Uw2 F' Rw R' Fw' (5)
2nd center: F' Uw' L' Fw' R2 Fw (11)
3rd center: F Uw' R' Uw' (15)
4th center: Fw2 R2 Fw2 (18)
Finish centers: F2 Uw L Uw' (22)
2 dedges already paired
3rd - 9th dedges: B' (R' U' R) Dw (L U' L') (R' U2 R) (R' D' R) (L D2 L') Dw' (40 - 2 = 38)
10th - 12th dedges: F Dw2 R' D R Dw2 y (44)

3x3x3 phase (explained in terms of 3x3x3)
2x2x1: F' U'  (2)
2x2x2: . R D * R (5)
Insert at ".": D (6)
2x2x3: L B L B' (10)
Pseudo F2L minus 1 slot: L' F L F2 (14)
Use premove F' to correct for pseudo F2L minus 1 slot.
Tripod: L2 U L U' L2 (19)
All but 2 corners, 2 edges: U L' U' L (23)
Premove correction: F' (24)
Insert cyclic-shifted J-perm to solve final 4 pieces.
Insert at "*": D L' D' L2 B2 R' U' R B2 L' (34-3 = 31)

OBTM: 44 + 31 = 75
BTM: 42 + 30 = 72

Solution:
Uw2 F' 2R Fw' F' Uw'
L' Fw' R2 Fw F Uw' R' Uw'
Fw2 R2 2F2 Uw L Uw'
B' R' U' R Dw L U' L' R' U2 D' R L D2 L' Dw'
F Dw2 R' D R Dw2 y
F' E' y' R D2 L' D' L2 B2 R' U' R B2
R B L B' L' F L F2
L2 U L U' L2 U L' U' L F'



Scramble 2:

First 2 centers: R L D Fw' D F Uw Rw' D' L' R2 Fw' (12)
3rd-4th centers: F Uw' F R Uw B2 R Uw (20)
Finish centers: R2 Fw2 L2 Fw2 (24)
2 dedges already paired
3rd-6th dedges: Dw' (L U2 L') (L D L') Dw (32-2 = 30)
6th-12 dedges: R2 F R Bw' (D F' D') (R' B2 R) (R' U F' R U') Bw x' y' (46-2 = 44)

3x3x3 phase:

Premoves: D' R' (2)
2x2x2: L' D R U' (6)
2x2x3: D' . B2 D B2 L B * L' D2 (14)
C-E pair extension: D' B D (17-1 = 16)
F2L minus 1 slot: D L2 D' (19-1 = 18)
Tripod: B (19)
Edges: L U' L' U (23)
Premove correction: D' R' (moves already counted)
This leaves 4 corners, solved by two insertions.
Insert at ".": D F' D' B2 D F D' B2 (31-6 = 25)
Insert at "*": F' R' F L' F' R F L (33-2 = 31)

OBTM: 44+31 = 75
BTM: 43+29 = 72

Solution:
R L D Fw' D F Uw Rw' D' L' R2 2F' Uw' F R Uw B2 R Uw R2 Fw2 L2 Fw2
Dw' L U2 D L' Dw R2 F R Bw' D F' D' R' B2 U F' R U' Bw x' y'
L' D R U' F' D' B2 D F B2 L S z' R' F L' F' R F D B D2 L2 D' B
L U' L' E y R'



Scramble 3:

First 2 centers: R' L' Dw' B2 Lw' F' Dw' L' Dw2 B2 Dw (11)
3rd center: D' Lw F' U B2 Rw (17)
4th center: F Rw' F2 Rw (21)
Finish centers: Uw2 F2 Uw2 (24)
3 dedges already paired
4th-9th dedges: F' (U R') (R' U R) Dw (D' R D) (R' F D' F') (F U' F') Dw' (42-3 = 39)
10th-12th dedges: D Lw' L D L' D' Lw (46)

3x3x3 phase:

1x2x3: F' D R' D' U R' F . (7)
2x2x3: R L2 F R2 (11)
Edges: L2 B2 D' * B D L B2 L' B (20)
A 5-cycle of corners remains.
Insert at ".": F' R' B' R F R' B R  (28-4 = 24)
Insert at "*": R2 B L' B' R2 B L B' (32-2 = 30)

OBTM: 46+30 = 76
BTM: 42+27 = 69

Solution:
R' L' Dw' B2 Lw' F' Dw' L' Dw2 B2 2D Lw F' U B2 Rw F Rw' F2 Rw Uw2 F2 Uw2
F' U R2 U R 2D R D R' F D' U' F' 2D' 2L' D L' D' Lw
F' D R' E y R2 B' R F R' B M2 x2 F M2 x2 B2 D' R2 B L' B' R2 B L D L B2 L' B



Scramble 4:

Full solution:
First center: D' Rw Bw (3)
2nd center (adj.): F' U Rw2 B' Rw' (8)
3rd center: R Fw Dw' F2 Dw Fw' (14)
Finish centers: Fw D' R' Fw D U2 Bw2 (21-2 = 19)
2 dedges already paired
3rd - 4th dedges: Bw2 R' B2 R Bw2  (24-2 = 22)
5th - 10th dedges: D' F (F L F') Rw' (F' R F) (F' L F) (U R2 U') Rw (38-3 = 35)
11th - 12th dedges: D' R' Dw' R' B U' R B' Dw y' (44)

Solving inverse for 3x3x3 phase.

2x2x2: D F' R2 B'  (4)
2x2x3: R U2 R2     (7)
F2L - 1: F U F2   (10)
Edges: L' U' B' U2 B2 . L' B' L2  (18)
Insert at ".": F' L' B' L F L' B L (18+8-5 = 21)
Insert at end: L' B L F' L' B' L F (21+8-2 = 27)
Use inverse as solution to 3x3x3 phase.

OBTM: 44+27 = 71
BTM: 41+26 = 67

Solution:
D' Rw 2F z' U Rw2 B' 2R' Fw Dw' F2 2D R' Fw D U2
R' B2 R Bw2 D' F2 L F' Rw' F' R L F U R2 U' Rw D' R' Dw' R' B U' R B' Dw y'
L2 B L B2 U2 B U L F2 U' L F' R2 F L' F' U2 R' B2 L' B' R2 B L S' z D'



Scramble 5:

First 2 centers: F' D2 L B' U Uw Lw Fw' L2 Fw' (10)
Paired center pieces: B' F' U Rw (14)
Finish centers: F D2 Rw' D2 Rw2 (19)
4 dedges already paired
5th-7th dedges: U2 Rw2 (F' R F) (U R' U') Rw2 (28)
8th-12th dedges: B' L' Dw (R' U2 R) (R U' R') Dw' x' y2 (38-1 = 37)

3x3x3 phase:
2x2x2: R B' D2 F2 (4)
Siamese 2x2x2's: D' B2 L2 D2 B L B' (11)
F2L minus 1 slot: D' L' F L F' (16)
All but 2 corners, 2 edges: R D' R' . B' D2 B (22)
Insert at ".": R D2 R' D' R D2 L' D R' D' L (33-3 = 30)
(sub-optimal J-perm)

OBTM: 37+30=67
BTM: 37+30=67

Solution:
F' D2 L B' U Uw Lw Fw' L2 Fw' B' F' U Rw F D2 Rw' D2 Rw2
U2 Rw2 F' R F U R' U' Rw2 B' L' Dw R' U2 R2 U' R' Dw' x' y2
R B' D2 F2 D' B2 L2 D2 B L B' D' L' F L F'
R D R' D' R D2 L' D R' D' L B' D2 B
```


----------



## rokicki (Jul 16, 2014)

Stefan said:


> Thanks for hosting the contest!



My pleasure!



> How did you produce the scrambles? Looks like 3x3+reduction+random, but the 3x3 part is pretty long and the reduction part is pretty short. Doesn't look like Shuang Chen's solver, so I'm wondering...



I used Shuang Chen's solver as integrated into tnoodle to generate the scrambles.
Then I inserted four random clockwise quarter turns at the front and at the back
(making some efforts to avoid cancellations). I figured this was a reasonable
compromise between getting truly random positions, having overly long scrambles,
and having the scrambles provided be as good as a computer could do.

Oh, the Cube Explorer allow-slice-move option! Very nice; I had not even thought
of that.


----------



## Stefan (Jul 16, 2014)

Ok, I guess the reduction parts are just short by accident then (they were shorter than what I got for the scrambles, despite my much more extensive search). I don't think they improved the solver in tnoodle, only added dependencies making it harder to compile (that's why I used his original standalone version, very easy to use and modify).


----------



## Stefan (Jul 16, 2014)

Charlie, your second and fourth computer BTM solutions contain "D2 U2". I guess you didn't use the slice moves option?


----------



## cuBerBruce (Jul 16, 2014)

I noticed some of Charlie's solutions "should" have been one move less in BTM. (Related to Stefan's comment.) This is because of sequences such as "F B'" or "U2 D2" which could be rewritten as "S' z" or "E2 y2" so as to be counted as a single move. Unfortunately (in my view), the applet and the code Tom used to score the submissions did not automatically detect such optimizable situations in counting BTM moves. So for my own submissions, at least, I tried to make sure I converted any such sequences before submitting to be sure I got proper BTM credit for them. This can be likened to the situation in 3x3x3 FMC where someone writes "R y F" instead of "R2 y" and getting it counted as two moves when only one was needed. (I guess I messed up once on a solution that ended up counting for OBTM only anyway.)

I spent most of the contest period working on my "human" solutions, and didn't get started on the "computer" solutions until around the last week. I figured the solver code that is used for the WCA scrambles might be hard to beat (assuming 3x3x3 phase replaced with optimal solve). I assumed Shuang Chen was already making use of that (or some improvement on it) and I didn't know if I wanted to spend time trying to compile the tnoodle code myself.

Instead, I mainly opted to see what I could come up with using the following 4-phase approach.

1. Solve tricolor centers and make edge piece permutation parity even.
2. Finish solving centers and pair up at least N dedges using <U, D, L, R, F, B, Uw2, Lw2, Fw2>, with N typically 8.
3. Finish reducing to 3x3x3 (no reduction parities) without computer search.
4. Optimally solve the remaining pseudo-3x3x3 configuration (treating it as a 3x3x3) with Cube Explorer.

For Scramble #2 (BTM), I used Charlie's 8-step solver, replacing the last four steps with an optimal solution from Cube Explorer.

See spoiler for my actual "computer" solves.



Spoiler





```
BTM

Scramble #1
Tricolor centers: Uw L2 B 2U' Rw U2 Fw' Dw (8)
Centers + 8 dedges: F R U Lw2 U B R2 Uw2 F' R Fw2 (19)
Finish Reduction: Rw' F L2 F' Rw2 B U' L B' U Rw' y2 (30)
3x3x3 solve: D2 F2 L D' L F2 R2 F' L U' D2 F' U F' D2 L2 (46)

Scramble #2
Tsai Step 1: B' U 2F2 2D R' U 2B' (7)
Tsai Step 2: 2L2 R D2 F' 2U2 F Rw (14)
Tsai Step 3: F L2 U' B 2R2 B 2U2 2R2 2U2 (23)
Tsai Step 4: L2 U2 2F2 L2 D' 2L2 (29)
3x3x3 phase: U' L' D F2 D' L' E2 F2 M' D' R' U2 L2 B2 M' (44)
(Charlie used the same first four steps except I used a different last move to cancel out the first move of the optimal slice-turn metric 3x3x3 solve. Hmm... Charlie seems to have used a sub-optimal FTM 3x3x3 solve.)

Scramble #3
Tricolor centers: 2L' 2B 2L' B 2D' R 2B' 2R2 D 2R (10)
Centers + 8 dedges: D B' L2 Uw2 F2 L' D F Lw2 F' Uw2 (21)
Finish Reduction: Fw L' F' L Fw' U Fw D R' B D' R 2F' x2 (34)
3x3x3 solve: D S' R U2 F2 L2 U S L2 F' U D F E2 M (49)

Scramble #4
Tricolor centers: Uw2 B Lw D' Fw2 R B2 Dw' 2L' (9)
Centers + 9 dedges: F' L' B U' Fw2 U Lw2 D F R' Fw2 (20)
Finish Reduction: U' Rw' B L' B' Rw (26)
3x3x3 solve: F2 U L2 B R' L2 F E y R2 F' B' R2 F L' U' (41)
Note: tricolor center solve also formed 5 dedges.

Scramble #5
Tricolor centers: U' L2 2F' 2U' L2 F 2L' 2F (8)
Centers + 8 dedges: D B Uw2 L U' Lw2 U Lw2 F2 U' Uw2 Fw2 Lw2 (21)
Finish Reduction: Fw R' F R Fw2 B' U B U' Fw y2 (31)
3x3x3 solve: L E2 B' U' R B2 F R D2 M U' F' D' B D' (46)

OBTM
Scramble #1
Same solution as for BTM.
Tricolor centers: Uw L2 B 2U' Rw U2 Fw' Dw (9)
Centers + 8 dedges: F R U Lw2 U B R2 Uw2 F' R Fw2 (20)
Finish Reduction: Rw' F L2 F' Rw2 B U' L B' U Rw' y2 (31)
3x3x3 solve: D2 F2 L D' L F2 R2 F' L U' D2 F' U F' D2 L2 (47)
Note: 3x3x3 phase is both 16f* and 16s*.

Scramble #2
Tricolor centers: Fw' Uw2 R Bw' Rw Uw' B2 R Uw (9)
Centers + 8 dedges: L Uw2 L' B2 Lw2 U R Fw2 B' R2 Uw2 (20)
Finish Reduction: L B' Lw F R2 F' Lw' F2 Rw F D' L F' D L Rw' y2 (36)
3x3x3 solve: B' R B2 L' U D2 R' U' L' D' R' U' B2 D' B R' L' (53)
Note: For BTM, the L Rw' at end of reduction could be optimized. For OBTM, the L is really part of 3x3x3 solve.

Scramble #3
Tricolor centers: F' Uw' Lw' Uw' Lw D Fw2 U Rw Uw (10)
Centers + 8 dedges: U F U D Uw2 L2 B Uw2 R' F Lw2 D' Fw2 (23)
Finish Reduction: R' Uw' L' D L Uw U F Uw' B R' U B' R Uw (38)
3x3x3 solve: F' E y B R D2 L' B2 D B' R2 F2 U2 B L2 U2 R' D2 (56)

Scramble #4
Same solution as for BTM.
Tricolor centers: Uw2 B Lw D' Fw2 R B2 Dw' 2L' (10)
Centers + 9 dedges: F' L' B U' Fw2 U Lw2 D F R' Fw2 (21)
Finish Reduction: U' Rw' B L' B' Rw (27)
3x3x3 solve: F2 U L2 B R' L2 F E y R2 F' B' R2 F L' U' (43)
Note: 3x3x3 phase is optimal in both FTM and STM.

Scramble #5
Same solution as for BTM.
Tricolor centers: U' L2 2F' 2U' L2 F 2L' 2F (12)
Centers + 8 dedges: D B Uw2 L U' Lw2 U Lw2 F2 U' Uw2 Fw2 Lw2 (25)
Finish Reduction: Fw R' F R Fw2 B' U B U' Fw y2 (35)
3x3x3 solve: L E2 B' U' R B2 F R D2 M U' F' D' B D' (52)
```


----------



## ch_ts (Jul 17, 2014)

Yeah, originally I wasn't going to submit any OBTM solutions, my single slice solutions were going to serve as both BTM and OBTM solutions, since I thought Shaung's solver would be difficult to beat. In the end, I added 1 line of code to also turn the outer layer whenever turning an inner layer so at least my solutions would be ~50 moves instead of ~60 moves in OBTM. And that's all I did for that.

I think it's unnecessary to search Dw, Lw, or Bw since they don't really reach any new positions that can't be reached with Uw, Rw, and Fw. (This is not the case in single slice turn metric: 2D, 2L, and 2B do reach new positions.) It seems like Shuang's solver/scrambler doesn't search these moves, I haven't checked the code, but the solutions don't seem to use these moves. My solver did use these moves since I didn't put in any extra effort to convert it from single slice to wide turns.


----------



## Stefan (Jul 17, 2014)

The "U2 D2" were in the 3x3x3 parts, though, where you said you used Cube Explorer, and it would've improved your BTM scores, not your OBTM scores. I just ran the 3x3 parts of your BTM solutions through Cube Explorer, it found solutions 2, 3, 0, 2 and 1 moves shorter.

My solutions for OBTM:
41 Dw Bw R' Dw2 B Rw Bw D2 Rw2 D' 2U2 R2 U2 Fw L' F2 U Lw2 Fw2 R F2 Dw2 F L B' D L' D U2 M' D B2 U2 L2 D' L2 D' R2 F2
41 U2 D 2F E' Bw' Rw' Bw' L D2 Rw2 Uw' F' Uw2 B R U2 B2 Uw2 F Bw2 L' Uw2 R' B2 L' F R' U' B2 R' S U2 B2 L' U' B E
42 L' Dw' Bw2 Lw Bw' Dw B2 2D' L U' F' Lw B U2 R' D' Bw2 D' Lw2 Dw2 F2 D 2R2 F D' B D' F' R' D' B' U' L' F U F L B' L' B2
40 Lw2 U' R' B Fw2 U2 L2 Lw' Dw' D2 L U2 F' R Fw' F2 R2 U' R' B2 Fw2 R 2D2 F R2 F R' F2 D F L2 U R' B D U2 L' B' L
41 Lw D B Uw Fw U Lw' Uw F Lw2 D L2 B' Fw' E 2R2 B U F' U Rw2 Uw2 F2 D' F2 B D M' S U' L U' R' U B U' B2

My solutions for BTM:
38 Dw Bw R' Dw2 B Rw Bw D2 Rw2 D' 2U2 R2 U2 Fw L' F2 U Lw2 Fw2 R F2 2D2 L E2 R2 D' L D' R D2 F' U2 M2 B D2 R L U2
37 same as for OBTM
38 L' Dw' Fw2 Lw Dw' Lw U2 2L' F R' D' Bw L U2 B' D' Rw2 U' Bw2 Dw2 L2 U 2B2 S R' F2 R2 L U R' B D2 B' L' D' R2 S' M'
37 Dw2 2R2 F Lw' Bw2 L' Bw L2 F' 2L D' L' U B' R2 D2 Fw2 U' F L2 Uw2 Lw2 F' L B U2 S' E2 R' F U R' D' F' D' L2 U'
37 same as for OBTM

And here's my main script:
https://gist.github.com/pochmann/d79d582724e96a5d3add
It BTM-optimizes algorithms by replacing consecutive moves on the same axis with as few equivalent moves as possible. I didn't see an obvious smart way (does anyone?), so I brute-forced it. The *hash* function takes consecutive moves on the same axis and turns them into a number like 21030, the first digit telling the axis and the last four telling the angles that the four layers on that axis get turned. Then for each of the three axes, I went through all 4^8 possible such combinations of moves (without repetitions like Dw Dw2, of course), computed the hash, and kept the best move combination for each hash. That was then used later to optimize the algs. And I have a *removeRotations* function that removes the cube rotations present in Shuang Chen's solutions and those that my BTMizing inserts (they don't increase the move count, but I dislike them).


----------



## qq280833822 (Jul 17, 2014)

Although the context has finished, I'm going to continue optimizing the solution to see how short it can be. 

Scramble 1:
R2 u' L2 f2 u' L' f' R D2 R2 D' u2 R2 u f F r2 F L2 r2 D' r2 (22 OBTM reduction)
+ D F2 R2 B' U2 F2 U L2 D' R' D2 B L2 U2 L U B' (39 OBTM)

Scramble 2:
U' F2 f' D' B2 u' L2 f' r' D2 u' f U F' f y U' F' r2 U' D B U' f2 (23 OBTM reduction)
+ D' F R' B' L2 D2 B U2 L2 U' B L' R2 U2 B' F2 D2 (40 OBTM)

Scramble 3:
f' r' f R' f R' U2 D L' f' u' F' y R2 U R2 D' F2 r2 D B u2 f2 r2 (23 OBTM reduction) 
+ D' R' F L F2 R D' R2 B D2 U' B R B' F2 D L' (40 OBTM)

Scramble 5:
B f U' F' R' f u' B2 u2 L' D' f' r2 f2 D F R2 r2 B' D' f2 (21 OBTM reduction)
+ U2 R2 D R' B' U2 F' D U2 L2 D U F' L' R2 F2 R2 D' (39 OBTM)


----------



## ch_ts (Jul 17, 2014)

Stefan said:


> The "U2 D2" were in the 3x3x3 parts, though, where you said you used Cube Explorer, and it would've improved your BTM scores, not your OBTM scores. I just ran the 3x3 parts of your BTM solutions through Cube Explorer, it found solutions 2, 3, 0, 2 and 1 moves shorter.



OK, I see what you mean. No, I didn't notice the slice moves option in Cube Explorer.


----------



## Stefan (Jul 17, 2014)

Sweet, how did you find that one? Did you improve your solver? Or just found a better search limit configuration? The best reduction I found using your old one was 24 moves (and I only found one), and this is 23.


----------



## cuBerBruce (Jul 17, 2014)

Stefan said:


> The "U2 D2" were in the 3x3x3 parts, though, where you said you used Cube Explorer, and it would've improved your BTM scores, not your OBTM scores. I just ran the 3x3 parts of your BTM solutions through Cube Explorer, it found solutions 2, 3, 0, 2 and 1 moves shorter.



Stefan, you neglected checking for step boundary optimizations. My solution for scramble #2 was 4 moves shorter than Charlie's, not 3. See my solutions.

In addition to not selecting "Allow slice moves" (only in Cube Explorer 5.00 and later), he (at least on scramble #2) apparently didn't check the "optimal" check box either, using a 19f instead of the 17f* solution.


----------



## qq280833822 (Jul 17, 2014)

Well, after my losing the context, I'm going to write a new solver optimized towards the length of solution without concerning the memory cost or solving time.
I try to merge step 1 and step 2, and now it's a two-phase reduction solver. Although the solver is much slower and cost more memory than the three-phase reduction solver, tt's practical to see how short the reduction can be.


----------



## rokicki (Jul 17, 2014)

qq280833822 said:


> Well, after my losing the context, I'm going to write a new solver optimized towards the length of solution without concerning the memory cost or solving time.
> I try to merge step 1 and step 2, and now it's a two-phase reduction solver. Although the solver is much slower and cost more memory than the three-phase reduction solver, tt's practical to see how short the reduction can be.



Wow, you've got a two-phase 4x4x4 solver going? I tried doing this last
month, but my first phase didn't complete on random positions in any
reasonable length of time (I gave it a day for a random position). I also
thought it is practical to do the reduction phase optimally, but (so far)
have not succeeded. Can you describe your approach?


----------



## Stefan (Jul 17, 2014)

No, he means two-phase *reduction* (instead of his previous three-phase reduction).

Still cool, though. Congratulations on that sub40 solve!


----------



## qq280833822 (Jul 17, 2014)

Oh it's a two-phase reduction solver, the only difference to the three-phase solver used in WCA scrambler is that I merged phase1 and phase2. If we treat the 3x3x3 part as a single phase, it should be a three-phase solver.
As the reduction is finished in two phases, we can try to find or estimate the near-optimal reduction solutions by trying sub-optimal phase1 solutions as kociemba did in his two-phase algorithm.


----------



## cuBerBruce (Jul 18, 2014)

I just thought I would mention a kind of interesting situation on one of my "computer" solves.

It was for scramble #5.

Scramble:
F U F U F2 R2 D' R2 B2 D B2 D2 B2 R2 U' F R F' B' D' R2 D' L'
Uw2 F' Uw2 U2 Rw2 Fw2 B D F' B D' L2 B2 Rw' Fw2 R' U B U' Rw' Uw R' Fw B U L D R

Reduction:
U' L2 2F' 2U' L2 F 2L' 2F
D B Uw2 L U' Lw2 U Lw2 F2 U' Uw2 Fw2 Lw2
Fw R' F R Fw2 B' U B U' Fw y2

The reduction created a logical 3x3x3 state with a prebuilt 2x2x1 block. It also had a prebuilt C-E pair that would extend
that 2x2x1 block to a 3x2x1 block. In fact, applying:

D' L' F' L2 D2

builds a *2x2x3 block* (with puzzle being viewed as a 3x3x3) with only *5 moves!*

U' L2 2F' 2U' L2 F 2L' 2F
D B Uw2 L U' Lw2 U Lw2 F2 U' Uw2 Fw2 Lw2
Fw R' F R Fw2 B' U B U' Fw y2 D' L' F' L2 D2

Now, the big question is: why did that happen on a "computer" solve instead of on a "human" solve where I could actually take advantage of it? 

EDIT: So far, I've found (without computer searching) a 29-move solution for the above reduction. While I know that F2L minus 1 slot can be achieved in 10 moves, I used 12 in this solution.

Skeleton:
2x2x3: D' L' F' L2 D2 (5)
F2L minus 1 slot: F . R2 * F' U2 R U2 R (12)
Edges: R U R' U' F' U' F U (20-1 = 19)

This left a 5-cycle of corners.

I found pairs of 3-cycle insertions that would cancel 2+2 moves or 3+1 moves. Thus, it looked to me like I would get a 19+8+8-4 = 31-move solution. However, the insertions cancelling 2 moves each were so close together, that there was a move from the 2nd insertion that cancelled out a move from the first insertion. This extra double-cancellation brought down the final move count to 29f (also 29s).

Insert at ".": D L' D' R2 D L D' R2 (27-2 = 25)
Insert at "*": D B2 D' F' D B2 D' F (33-2-2 = 29)

Final solution: D' L' F' L2 D2 F D L' D' R2 D L B2 D' F' D B2 D' U2 R U2 R2 U R' U' F' U' F U (29f/29s)


----------



## qq280833822 (Jul 19, 2014)

After several hours' search, all 5 scrambles are solved no more than 40 OBTM moves. See #55.


----------



## ch_ts (Jul 19, 2014)

qq280833822 said:


> After several hours' search, all 5 scrambles are solved no more than 40 OBTM moves. See #55.



Wow, that's great. 

Does anybody know a case that might be especially difficult to reduce (based on intuition, theory, or whatever) and maybe Shuang could try his solver on it?


----------



## Kare (Aug 13, 2014)

Sorry about being a bit late here, I forgot about the competition and got reminded during euros.

My solver used an approach I have been thinking about for a few years and finaly got a reason to test. While it proved to be inefficient compared to the other methods used I find it a interesting and will post an outline of the algorithm. It's based on how I like to do FMC for 3x3, and only slightly adopted to a computer, so no standard reduction to 3x3. Phase 1 is solve a lot of pieces cheaply, phase 2 is commutator insertions to solve the rest. Both steps are greedy, adding a few moves at a time never branching out.

Phase 1: Solve lots cheaply.

Do a complete search of depth 5. Find the sequence Z that results in the most solved pieces. Now apply the first move of Z to the cube. Do another depth 5 search. If there is a depth 5 alg producing more solved pieces than the remainder of Z would, then swithch to the new sequence, else keep the remainder of Z. Apply another move and once again do a depth 5 search.

Once we are at a local maxima with no improvements in sight phase 1 gives up. By now most pieces are solved.

Phase 2: Insertions

Generate all possible sequences of the form (XYX') Z (XY'X') Z' or Z'(XYX')Z(XY'X') where X is orthogonal to Y and Z. Y and Z are not the same slice. This results in 2*36*24*21 = 36288 commutators. Not all commutators are 3-cycles, but I keep them all as I did not want to spend the effort to filter the list and it runs fast enough anyway.

I take the partial solution from step one and loop over all possible places to insert a commutator, loop over all commutators evaluating which insert results in the most solved pieces. From all possible insertions resulting in the best score I choose the one costing the least moves after cancelations. If no insertion results in more solved pieces the program terminates with no solution found. Rinse and repeat untill we have done enough insertions to solve the entire puzzle.

Remarks:
Phase 2 can't change parity, so the program will only find a solution if phase 1 ends with 
neither corner nor edge parity. This is solved by subtracting 2 solved pieces per parity 
from the score of a position. Phase 1 might still end with a parity, but it is rare.

By far the most common reason phase 2 fails is that we get into a position that is solved
except for two twisted corners. This is avoided by having permuted but twisted corner be 
worth -1 point each.

The program solves each side to the position it had when scrambled. So if we scramble with 
WCA orientation the soulution should end up with WCA orientation. Because of this we can 
solve each scramble 24 times with all the different puzzle rotations inserted before the 
solution and then choose the shortest.


----------



## unsolved (Dec 12, 2014)

I think it's time for a new contest now that my program is finally working


----------



## qq280833822 (Dec 17, 2014)

unsolved said:


> I think it's time for a new contest now that my program is finally working



It seems that you have found shorter solutions for this contest?


----------



## unsolved (Dec 17, 2014)

qq280833822 said:


> It seems that you have found shorter solutions for this contest?



Playing around with new technology, trying to interleave the new access code in properly. In certain positions I can chop 7-ply from the trunk of the tree.







You can see the obvious bug here, of course. It's a little tricky, but once I get this worked out, this thing will be cruising


----------



## qqwref (Dec 17, 2014)

You've made good progress, but I don't think you're even a factor of a million off from solving arbitrary random scrambles. Not the right thread


----------



## unsolved (Dec 17, 2014)

qqwref said:


> You've made good progress, but I don't think you're even a factor of a million off from solving arbitrary random scrambles. Not the right thread



Well, considering there is no stage solving in this version....






...but that is not my lofty goal for now. One pruning algo at a time. And I think I have the centers code ironed out. I copied/pasted the wrong variable name into a parameter I was passing to a search function prep call. D'oh!


----------



## unsolved (Mar 23, 2015)

Maybe we can do another FMC in June 2015? I'm working on a 5x5x5 program now while waiting for some 4x4x4 database generation to finish. I will have a new experimental version of my 4x4x4 program by mid-April, so if anyone else wants to start tuning up their software, this might be enough notice for the proposed June timeframe.


----------



## rokicki (Mar 23, 2015)

unsolved said:


> Maybe we can do another FMC in June 2015? I'm working on a 5x5x5 program now while waiting for some 4x4x4 database generation to finish. I will have a new experimental version of my 4x4x4 program by mid-April, so if anyone else wants to start tuning up their software, this might be enough notice for the proposed June timeframe.



I wouldn't mind *entering* such a 4x4x4 FMC. (If I *run* it, I feel a bit odd about *entering* it.)

If someone else wants to run it, that would be great.

I don't feel I need to wait until June, either. 

-tom


----------



## ch_ts (Mar 23, 2015)

I could run it... but with no prize or small prize like $10


----------



## rokicki (Mar 23, 2015)

ch_ts said:


> I could run it... but with no prize or small prize like $10



That would be very nice! I am not sure how much prizes motivate folks to enter; I think
people willing to spend the time to try it, pretty much just want to see how they do.

This probably goes double for the computer part of it (the part I care most about).


----------



## Christopher Mowla (Mar 23, 2015)

I really don't see why unsolved is interested in 4x4x4 FMC because his solver is in a completely different metric. In addition, seeing the last competition, where the best computer results came from tweaking ch_ts' solver's solutions a bit, I doubt anything has changed since the last competition. Perhaps a human competition could spark new ideas to be implemented for the next competition, however.


----------



## unsolved (Mar 23, 2015)

rokicki said:


> I don't feel I need to wait until June, either.
> 
> -tom



Well my new 4x4x4 version will be available then. I'm using pre-computed databases that will be loaded into large RAM buffers to aid in the search. I am also building a new 60-core computer in April. Combining the two should result in something interesting. My program handles the solve from start to finish, and does not rely on any outside software. I give it the scramble, and it does all the rest, without assistance or intervention.

You guys can start whenever you want to, of course. It's just my software/hardware won't be ready for a while.



cmowla said:


> I really don't see why unsolved is interested in 4x4x4 FMC because his solver is in a completely different metric.



My single slice half turn solutions to random scrambles are in the neighborhood of 65 turns presently. I don't know how that translates to the metric that the contest uses. But apply whatever move counts that you like to the solutions. It is my hope to get the move counts down to 45 with the new hardware and software.


----------



## ch_ts (Mar 23, 2015)

Great to see people are still interested!

So, the preliminary rules:

Two categories: computer and human
$10 top prize in each category
Single slice turn metric - something different from last year, may encourage different approaches
Will start late spring, run for 1 month - i'm interested in seeing what unsolved has/will have


----------



## unsolved (Mar 24, 2015)

ch_ts said:


> Great to see people are still interested!
> 
> So, the preliminary rules:
> 
> ...



Well I am pulling what's left of my hair out now with my 5x5x5 solver over stuff like this:






Two nights ago a 7-ply search on the 5x5x5 took 90 minutes and 8-ply was over a day and a half.

Tonight 8-ply was down to 17 seconds with pre-computed databases loaded into RAM, but it throws the parallel search code into a tizzy.

Grrrrrrrrr.

*Edit: Finally nailed it!*






I'll take 21 seconds for 8-ply in a 5x5x5 solve without corner pruning  It's a shame about the hash collisions though. For a 6 GB buffer and only 3 Turns-From-Solved loaded into RAM, I would not expect 138 hash collisions. I guess with two 64-bit variables x 6 = 96 bytes/cube, transforming that much data into a mere 64-bit hash is bound to produce duplicate hash numbers. I'll have to work on a more random hash function. The 4x4x4 collision rate is only 3 or 4 for the entire 5-turns-from-solved database.


----------



## ch_ts (Mar 28, 2015)

Without looking at all the details of your solver, I think that you could get better performance with a more careful selection of stages and tables than trying to max it out on the hardware side. Nevertheless, I am trying to make this fmc as favorable as possible for you :tu


----------



## unsolved (Mar 29, 2015)

ch_ts said:


> Without looking at all the details of your solver, I think that you could get better performance with a more careful selection of stages and tables than trying to max it out on the hardware side. Nevertheless, I am trying to make this fmc as favorable as possible for you :tu



I appreciate the sentiment, but I suffer from no delusions regarding the prospects of winning  I've always had an interest in brute force searching, and I've solved endgame positions for checkers requiring 253 plies and chess endings of 535 plies. All for fun, although I did have 3-4 papers published on the results back in 2003 and 2004.

I have 12 different stage solving procedures ready to fire up and test on the new hardware. Whichever shows the most promise from random scrambles fed to it in April and May I will use for the contest.


----------



## leeo (Jun 3, 2015)

By following the patterns of the BH 3-cycle blindfold method, I can generate all 1760 edge 3-cycles from any origin (buffer), and all 1009 corner 3-cycle from any origin (buffer). On this vein, I've been experimenting with a different approach: Permit a startup time of one CPU second (3 GHz Dual-Core) with no file load permitted. Then budget 5 seconds solution time for each challenge scramble to find the fewest moves possible in that time constraint. I think that emulating the (unassisted) FMC techniques with these internal catalogs could have promise: What results are possible? I'm currently attempting to generate all 3'548'160 edge 5-cycles in that budget.


----------



## unsolved (Jun 3, 2015)

leeo said:


> By following the patterns of the BH 3-cycle blindfold method, I can generate all 1760 edge 3-cycles from any origin (buffer), and all 1009 corner 3-cycle from any origin (buffer). On this vein, I've been experimenting with a different approach: Permit a startup time of one CPU second (3 GHz Dual-Core) with no file load permitted. Then budget 5 seconds solution time for each challenge scramble to find the fewest moves possible in that time constraint. I think that emulating the (unassisted) FMC techniques with these internal catalogs could have promise: What results are possible? I'm currently attempting to generate all 3'548'160 edge 5-cycles in that budget.



So, basically, you want a contest specifically tailored to something you have already written, without allowing any other program to use their own strengths. Does that about sum it up?


----------



## clement (Dec 5, 2015)

Hello
Here are my solutions for BTM only. My solver cannot solve using double layer moves, so solutions are not optimised for OBTM metric.
1. F U 2R2 B2 L' B' L Fw' R2 Rw' 2U2 B' 2L' 2F2 2L2 2R' 2B' 2D' B' 2U2 B2 D2 (L2 R2) D2 2D Lw2 F' R2 B' 2B2 2L2 B' Lw2 D2 B2 L2 2F2 (37)
2. U 2F' 2D F D' 2R2 U' 2R F' L D' F2 2D' B2 U 2R' B2 2R' L2 2F R2 B2 2B' R2 2D2 2B' 2F2 R2 2D2 B2 D' F2 2R2 2B2 D' F2 U2 2B2 L2 U2 L2 (41)
3. 2U R B2 2B Lw 2B' U' 2R' B' R' 2D2 2L2 2F' 2U' B2 2R R2 F2 2F R2 2D2 2F2 R 2D2 2B 2R2 U2 R2 2B2 L2 D2 L' B2 R U2 2R2 B2 2U2 2B2 R2 (40)
4. U2 F2 2B2 U' 2F2 L U' L' 2D2 F R U2 2D2 2F2 L' 2D' 2F 2R' F2 R' 2B2 L 2R2 2F' L 2F U2 F2 2L2 2D2 R' U2 2B2 D2 R 2U2 B2 D2 R2 B2 L2 B2 (42)
5. 2B2 2D2 F2 U' L' U B R' U 2B2 L 2L' 2U L2 2D B2 2R 2F 2D2 L 2F' R2 2F' D2 2F' U2 F2 R U2 2D2 B2 2R2 2B2 L' B2 R2 Bw2 2D2 2R2 2F2 (40)


----------

