• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 30,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

4x4x4 FMC (computer and human)

Lucas Garron

Moderator
Staff member
Joined
Jul 6, 2007
Messages
3,551
Likes
84
Location
California
WCA
2006GARR01
YouTube
LucasGarron
#2
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.
 
Joined
Oct 31, 2008
Messages
265
Likes
14
Thread starter #4
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.
 
Joined
Jul 28, 2013
Messages
14
Likes
0
#5
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

Moderator
Staff member
Joined
Jul 6, 2007
Messages
3,551
Likes
84
Location
California
WCA
2006GARR01
YouTube
LucasGarron
#6
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.
 
Joined
Oct 31, 2008
Messages
265
Likes
14
Thread starter #8
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.
 
Joined
Oct 8, 2006
Messages
914
Likes
15
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
#9
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?

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.
 
Joined
Oct 31, 2008
Messages
265
Likes
14
Thread starter #10
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.
 

Lucas Garron

Moderator
Staff member
Joined
Jul 6, 2007
Messages
3,551
Likes
84
Location
California
WCA
2006GARR01
YouTube
LucasGarron
#13
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".
 
Joined
May 7, 2006
Messages
7,287
Likes
38
WCA
2003POCH01
YouTube
StefanPochmann
#14
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.
 
Last edited:
Joined
Mar 2, 2014
Messages
566
Likes
9
Location
Doylestown, PA
#15
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 :)
 
Joined
Mar 2, 2014
Messages
566
Likes
9
Location
Doylestown, PA
#16
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.
 
Joined
Oct 31, 2008
Messages
265
Likes
14
Thread starter #17
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!
 
Joined
Oct 14, 2009
Messages
2,478
Likes
9
Location
Near Toronto
WCA
2009METH01
YouTube
simpsons36109
#19
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?
 
Last edited:
Joined
Oct 31, 2008
Messages
265
Likes
14
Thread starter #20
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.

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.
 
Last edited:
Top