World record Square-1 of Polish Open 2008 not acknowledged

[Ron]

Fellow cubers,

After investigations WCA Board decided not to acknowledge the world record Square-1 that was achieved during Polish Open 2008.

Grzegorz Prusak, who already owns the world record for Square-1, was given an incorrect and very easy scrambled position in his third attempt of the event.
Immediately after his solve he informed the WCA delegate about the irregularity. The scrambled position was checked with the scramble sheet.
Both delegate and competitor confirmed that the scrambled position was incorrect and very easy to solve.

We thank Grzegorz for his honesty and sportsmanship.

WCA decided the following for the results of Polish Open 2008:
1) the third attempt of Grzegorz will be changed to DNF
2) the average of Grzegorz will be changed to DNF
3) Grzegorz will stay the winner of the event, in 1st position

For future competitions we advise WCA delegates to replace such attempts by another attempt.
In this case the competitor did a retry with the correct scramble, but it was not done under official WCA conditions.
(For the record: his result was 15.53 seconds.)

WCA will work on improving the scramble program for Square-1 to also show the correct scrambled position. We ask our community to help us.

Kind regards,

Ron van Bruchem
WCA Board

[BryanLogan]

Just out of curiosity, was it considered to give him an 18.30 time? This would basically give him an average of his other two solves, it's within his ability, and leaves him in first place.

Otherwise, I think people who are browsing the WCA database might get confused by this irregularity.

Anyways, thanks to Grzegorz Prusak for being honest.

[timhabermaas]

That's awesome, Grzegorz!

Anyway: Does the square-1 scrambler has to be written in Javascript? I ask, since i already have written a sq-1 scrambler in Ruby and i believe it's not that much work to display the final state of the puzzle.

[Ron]

Just out of curiosity, was it considered to give him an 18.30 time?

No, we only accept results achieved under official conditions.

Anyway: Does the square-1 scrambler has to be written in Javascript?

Requirements:
- fast generation of random positions and the required move sequences to get there
- not too lengthy move sequences (<=70 moves) and not significantly longer than current sequences
- image of each generated random positions, with print option
- preferrably available on all platforms
- preferrably one program that handles all puzzles
- offline use
As far as I know you cannot run Ruby offline (without a local webserver installed), so we prefer Javascript or similar.

Thanks,

Ron

[timhabermaas]

Requirements:
- fast generation of random positions and the required move sequences to get there
- not too lengthy move sequences (<=70 moves) and not significantly longer than current sequences
- image of each generated random positions, with print option
- preferrably available on all platforms
- preferrably one program that handles all puzzles
- offline use

I don't see a problem in any of these requirements. The only thing i worry about is the 3x3 scrambler

As far as I know you cannot run Ruby offline (without a local webserver installed), so we prefer Javascript or similar.

Ruby is just a normal scripting language, so it works offline. You probably mix it up with Ruby on Rails - the web framework written in Ruby.

Platform will be Java and programming language Java/Ruby.
I'll later create a source repository (git) and will publish the url here, if it's set up properly.

[timhabermaas]

The only thing i worry about is the 3x3 scrambler

Sorry, i forgot to mention why i worry about it: The new regulations require a random state + solver. I heard that Clement is currently writing one. So it would be great, if we could combine the two applications. Actually i don't want to write a solver from scratch.

[jbcm627]

Requirements:
- fast generation of random positions and the required move sequences to get there
- not too lengthy move sequences (<=70 moves) and not significantly longer than current sequences
- image of each generated random positions, with print option
- preferrably available on all platforms
- preferrably one program that handles all puzzles
- offline use

I don't see a problem in any of these requirements. The only thing i worry about is the 3x3 scrambler

Hmm, may try this. I don't know how convienient this would be for larger cubes (over 5x5x5), but it is certainly possible to do random state for that as well. I have been considering making an NxNxN solver ever since I finished an NxMxL scrambler I made recently... I might try this in javascript somewhat soon, and if that language proves too slow, try C++ or something and use Qt so it has support on almost every OS. Adding in other puzzle images shouldnt be too difficult, either. Random state clock scrambles shouldn't be too hard I don't think, nor square-1... perhaps I'll just try random state for every puzzle Might as well do it right if we are going to do it again, I suppose. Although, if Clement is working on a solver, should I bother? Or is he doing that only for 3x3x3? I hope this doesn't take me too long to do... if I manage to finish it at all...

[BryanLogan]

I wonder if the Square-1 can be broken into phases:

1) Random permutation
2) Random layer
3) Random permutation again (to ensure permutation after layer)
4) Random shape

In theory, this should be completely random by the end, and it would simply be huge tables. Also, when scrambling, you should be in cube shape after step 1, 2, and 3, so that will help the scramblers, since it gives them good checkpoints.

[jbcm627]

I wonder if the Square-1 can be broken into phases

I don't see the need to do this... Jaap has already made an optimal solver which solves in <= 30 moves. It would just need to be adapted to scramble to a random state, instead of solved; as in, just invert the solution to a random position. The large issue I believe is image generation, but if a random position is chosen, this should be fairly straightforward.

[Lucas]

I already posted a lot about this in the other thread, but unfortunately it got deleted, and I did not want to retype everything.

Jaap has written an optimal solver than will solve random states autonomously, as well as a sub-optimal solver without this -r option. So, all we need to do is combine these: Configure the 2-phase solver (unless the optimal is considerably faster than I'm used to) to generate n (i.e. n=3 for competitions) random states and output to a file. Then we just need a program that can generate printable scrambles from that file.

I could actually brute-force this down to a click of a single batch file, but it would only work on Windows. :-/

I would still like to note that there are two viable definitions of random, because after "a lot" of twists, the distribution of shapes is not even (at least I'm pretty sure it shouldn't be). The choice is between even or weighted distribution of the shapes.

[jbcm627]

I already posted a lot about this in the other thread, but unfortunately it got deleted, and I did not want to retype everything.

Jaap has written an optimal solver than will solve random states autonomously, as well as a sub-optimal solver without this -r option. So, all we need to do is combine these: Configure the 2-phase solver (unless the optimal is considerably faster than I'm used to) to generate n (i.e. n=3 for competitions) random states and output to a file. Then we just need a program that can generate printable scrambles from that file.

I could actually brute-force this down to a click of a single batch file, but it would only work on Windows. :-/

I would still like to note that there are two viable definitions of random, because after "a lot" of twists, the distribution of shapes is not even (at least I'm pretty sure it shouldn't be). The choice is between even or weighted distribution of the shapes.

:-/ too bad it was deleted. Was Jaap's code in C? It looks like it. If so, it shouldn't be too difficult to just merge them into a single executable, mod it to generate 3 scrambles, and hopefully port it just as easily. He has included all of the source code with his programs (http://www.geocities.com/jaapsch/puzzles/square1.htm#progs), so we could just compile these together. The remaining problem is image generation...

I would also say weighted scramble positions... so picking a random state from among all possibilities. So for example, if there are 400 billion configurations (appx), and a specific shape occurs in, say, 10 billion of these, and another shape in 5 billion, the shape with 5 billion configurations should occur half as often.

[StefanPochmann]

I would also say weighted scramble positions... so picking a random state from among all possibilities. So for example, if there are 400 billion configurations (appx), and a specific shape occurs in, say, 10 billion of these, and another shape in 5 billion, the shape with 5 billion configurations should occur half as often.

That certainly isn't what Lucas meant. Looking at it that way, every shape obviously occurs exactly 8!^2 times (ignoring the middle slice... multiply with fixed number if you want to consider it as well).

If you look at the shape graph, you can see the "double square" shape has only one neighbour, while other shapes have many neighbours. Compare it to a city bus system. Randomly taking buses you'll simply more likely end up in the city center than at a certain place on the edge of the city.

Or the minimal example: Imagine you have three states A, B and C and A/B are neighbours and B/C are neighbours. Randomly moving around, it's more likely you end up at B than at A or C (Exercise for the reader: prove this and determine the exact probabilities).

[jbcm627]

Ah, ok, I think I see now. And boo Markov chains. I also argued that there were a couple defnitions of scrambling in another thread, under a different context, while analyzing jaap's cube scrambler.

I would now like to argue that a random position should be chosen, I guess now I would argue that it should be unweighted, considering this new information. The path taken to reach a certain position shouldn't be considered... we simply want to pull a random state out of all the possibilities, without consideration regarding what it would take to get to that state. It is getting back to a solved state that should be the problem. I would therefore like to state that the weighted definition is not a valid definition of a scramble, as I don't believe scrambling should be defined by the moves you apply to it, but rather selecting a state out of all possibilities.

This arguement also holds when considering cubes. If you are randomly turning a cube, it is also true that some states will appear with higher frequency than others. When considering optimal (fewest turn) paths to states, there are multiple optimal paths to certain states, while only 1 optimal path to others. Although trivial, an example would be the (U R') permutation having one path, and (U' D) having 2 paths: itself, and (D U'). Seeing that (U' D) and (D U') are different paths is not necessarily trivial, I suppose... it is arguable. To better understand, you can see comments about scrambling in the source code of this if you are interested. If you still do not consider this example valid, you can look up 2 different algorithms with the same number of turns/moves that execute the same permutation.

So if we are going to consider weighted positions as legitimate... as in, take into consideration the path taken to get to a certain state, then we should also do this with 3x3x3 cubes... and not use Cube Explorer, as it generates random unweighted positions I believe.

This said, I will accept that randomly turning a puzzle will generate a pseudo-random position. For example, it is possible that some states are unable to be reached by traveling a distance of say, 40 moves on a 4x4. It may lie at 39 moves, or 41 moves, but it is possible there is a state that does not exist that can be solved in exactly 40 moves. But for all practical purposes, randomly turning the cube will choose a pseudo-random position from among the many (thus legitifying the current big cube scramblers). A random position would still be prefferable, however.

As a side note, interestingly, this distinction between different definitions of random is not applicable when considering 1x1xN cubes. Thus generating a weighted number of moves and applying them to a 1x1xN cube will also generate a random position, and vice versa.

[StefanPochmann]

So if we are going to consider weighted positions as legitimate... as in, take into consideration the path taken to get to a certain state, then we should also do this with 3x3x3 cubes... and not use Cube Explorer, as it generates random unweighted positions I believe.

Obviously you haven't understood the concepts "infinity" and "limit". For the 3x3x3, weighted and unweighted are the same.

[jbcm627]

So if we are going to consider weighted positions as legitimate... as in, take into consideration the path taken to get to a certain state, then we should also do this with 3x3x3 cubes... and not use Cube Explorer, as it generates random unweighted positions I believe.

Obviously you haven't understood the concepts "infinity" and "limit". For the 3x3x3, weighted and unweighted are the same.

Can you please explain this further, then? I do not understand why the reasoning I used is inaccurate.

[StefanPochmann]

I don't really know how to answer that. Why you think weighted/unweighted are not the same for the 3x3, I have no idea. You tell me. And I recommend you answer the above A/B/C exercise, and also the variation where A/C are neighbours as well, i.e., all three states are neighbours of each other.

[jbcm627]

I'm not going to put too many messy details in here (well I didn't even do all the details anyways thanks to mathematica), but I will put a brief description of a solution to the problem you posted first. Its still sort of long winded. You can find it here. Correct me if I'm wrong.

So... back to Square-1. And Cubes. I really am not trying to argue whether or not the probability of a shape occurring while randomly turning it is weighted or not, but instead something else entirely: why that is not the best definition for scrambling. For the Square-1, you will find a shape diagram here. From this you can see it is arguable that some shapes are more readily attained from other shapes while executing a large number of random turns; the shapes in the middle (more connecting lines) will occur with higher frequency. This is a wonderful phenomenon.

It has nothing to do with what I view as a scramble. This is where I disagree with the definition of scrambling as moving from one state to an adjacent state. Moving from state to state is a problem for the solver, not the scrambler, even if the scrambler wants to do it an infinite number of times. We simply wish to take our state map, and place our solver upon it somewhere, without caring how he gets to the solved state, nor how we got to the specific position. We do not wish to consider the paths involved, that is for the solver. This is about as simple as I can put it. I can still see how it is arguable that you scramble using moves also, but I just do not consider this ideal.

In addition to this, consider a Cube. Now consider all states exactly 2 moves away from a given state, as given here, representing the space of all states 2 QTM moves away. Again realize we are scrambling with a finite number of moves, and you may see my point. It is perhaps more pertinent when dealing with scrambles that are a fixed number of moves, like 40 moves for the 4x4x4, but still applicable to this case. Here, if we consider the given state to be the solved state, and apply 2 move scrambles to it, many scrambled states (particularly, ones with moves that are on the same axis) will be generated with a higher frequency. This is the problem with using the definition of random moves; it will increase the probability of reaching these states; especially with Jaap's cube scrambler which tends to generate move moves on the same axis than it should (see discussion here). Thus, I consider it an unideal form of generating scrambles, although I will admit its effectiveness in terms of practicality.

If you were to consider the map of all states for a 3x3, as you attempted to reach an infinite number of moves, perhaps you would indeed find that all states were generated with equal probability. But in the limited cases of (finite length) scrambles, you will find more than one optimal path to many many states. You will reach some states with a higher probability than others while just executing a finite number of random turns.

There are of course special cases as I mentioned before, such as the 1x1xN, in which the separation between scrambling through moves and random positions becomes obscured, along with 1x2x2 as well. These all have simple maps which do not include multiple paths to a state, such as the 2x2x1 map:
A-B-C-D-E-F-A (back to beginning; cyclic map)
Its 6 states, represented as A through F, are obviously hit upon with equal probability as you tend towards an infinite number of moves. Thus we must pick one of these states, giving each an equal probability of being chosen. The case is similar with 1x1xN cubes. But when you introduce the possibility for 2 paths to lead to the same position, the idea of generating scrambles using moves will break down for fixed length finite scrambles.

While this may only apply to scrambles with a fixed length, the point is as follows: we should not need to base the scrambles on how the puzzle moves, but instead leave that to the solvers. We need only pick a position from the many, without regard to how the puzzle may turn to that position.

[StefanPochmann]

I'm not going to put too many messy details in here (well I didn't even do all the details anyways thanks to mathematica), but I will put a brief description of a solution to the problem you posted first. Its still sort of long winded. You can find it here. Correct me if I'm wrong.

I confirm your results, and admit that I actually didn't notice the oscillation.

We simply wish to take our state map, and place our solver upon it somewhere, without caring how he gets to the solved state, nor how we got to the specific position. We do not wish to consider the paths involved, that is for the solver.

Please change "we" to "I" (meaning you). It's exactly like Lucas said, there are two possible obvious definitions, but which is better is not obvious and I'm certain we won't all agree.

But in the limited cases of (finite length) scrambles, you will find more than one optimal path to many many states. You will reach some states with a higher probability than others while just executing a finite number of random turns.

Who cares? That has nothing to do with with the current discussion. We're not talking about that kind of scrambling, but about random state generation where we pick a random state and generate an algorithm producing that state.

[jbcm627]

Please change "we" to "I" (meaning you). It's exactly like Lucas said, there are two possible obvious definitions, but which is better is not obvious and I'm certain we won't all agree.

Can I not edit posts on here? Oh well... I agree, it should be "I".
And I agree that we may disagree.

Who cares? That has nothing to do with with the current discussion. We're not talking about that kind of scrambling, but about random state generation where we pick a random state and generate an algorithm producing that state.

I pointed it out in trying to argue why I think the possible moves on a puzzle shouldn't be considered when choosing a state, rather only in determining whether a state is solvable or not... Although, then again, I can see how this would be pertinent, and could be considered. I just consider it unideal.

[Lucas]

I pointed it out in trying to argue why I think the possible moves on a puzzle shouldn't be considered when choosing a state, rather only in determining whether a state is solvable or not... Although, then again, I can see how this would be pertinent, and could be considered. I just consider it unideal.

Well, even trying to stay with definitions like that can get troublesome.
Note that we are trying to measure a competitor's ability to solve a physical puzzle. I view it as a formal version of "let me do a lot of random moves on this, and see how fast you can solve it." It's not at all unideal, it's just how you consider the structure of the puzzle scrambles.

If my old Mathematica input of Jaap's graph (http://www.geocities.com/jaapsch/puzzles/square1d.htm) is right, then the distribution is very uneven (and toggles among even/odd depths, but for weights it seems almost trivial to choose that randomly), and shape 13 on row 4 has the highest probability, about 1/20.