Megaminx Scrambler

Call it what you may, but doesn't that provide us with the end result we want?
Well, while you want it, I find it irrelevant. You really don't need more than 2^32 scrambles. You get no practical advantage from this at all, it just makes things more complicated and gives you a false sense of safety (from the terrifying unrandomness). And you might generate duplicate scrambles if you're fast enough and not careful (side effect of making things complicated is risk of doing something wrong).

What's important is the quality of the scrambling, not the number of possible outcomes (if the latter is reasonable (so don't say I said a megaminx scrambler with ten possible outcomes can be good)).
 
Last edited:
[Reseed] after it's 32 bit string has been used, and possibly with the system clock?
Actually... reseeding with the system clock might be *worse* than simply trusting the PRNG's internal state of for example 48 bits to do its job. Cause even if the system clock updated 100 times a second and you lived 100 years, you'd only be able to get about 2^38 different system clock values and thus seeds.
 
Well, I've scanned all the hard drives I own which I can get spinning, and I have found some, but not all of the code used to calculate the statistics in that post. What I have here is the driving class for testing the different scramble generators. Unfortunately I'm missing a few important classes such as Scrambler, Cube3, and Megaminx. Unfortunately these are where the scrambles are actually applied to the puzzles and those are very tedious to write. Also the code is neither pretty nor streamlined nor commented, so tread carefully.

I will work on regenerating the missing classes and when I get them going / find them, I'll repost them here. But at least with this piece, anyone who wants to can verify that IF my scramble generators and scrambler appliers where coded correctly, then the logic for calculating the statistics is what I claimed it was (whether or not that is the correct way to test scramble validity is an entirely different matter).

A few notes on the code:
It ignores centers on both megaminx and 3x3
The meaning of the megaminx scramblers names' are (as best I can remember):
MEGAMINXDTSR = Double Turn Single Rotation similar to the WCA scrambler in only chooseing ++ -- and ' (no - + ")
MEGAMINXDTSR = Double Turn Variable Rotation (allows ++ -- ' ")
MEAGMINXST = Single Rotation (allows + ++ - -- and ')
There were others available but it would seam that these are the last ones tested.

Code:
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class CubeStats extends MathUtils{
	
	public static void main(String[] args) {
		
		long start = System.currentTimeMillis();
		File out = new File("/home/spdqbr/Desktop/stats.txt");
		try{
		BufferedWriter bw = new BufferedWriter(new FileWriter(out));
		/*
		Scrambler scrambler = new Scrambler(Scrambler.CUBE3)
		
		Cube3 puzzle = new Cube3();
		
		
		int sides = 6;
		int stickersPerFace = 8;
		//int[] scrambleLengths = {200,500,1000};
		int[] mins = {1,10,20,30,35,40,50,1,10,20,30,40};
		int[] maxs = {10,20,30,40,45,50,60,20,30,40,50,60};
		int trials = 1000000;
		int[] totals;
		Integer[] scrambled = null;
		Integer[] scrambledNoCenters = null;
		String scramble;
		for(int z = 0; z<mins.length; z++){
			totals = new int[stickersPerFace*sides*sides];
		for(int i = 0; i<trials; i++){
			puzzle.reset();
			scramble = scrambler.generateScramble(mins[z],maxs[z]);
			//scramble = Megaminx.WCAScrambleString(scrambleLengths[z]);
			puzzle.applyScramble(scramble);
			//puzzle.orient();
			scrambled = puzzle.getState();
			//scrambledNoCenters = stripCenters(scrambled);
			for(int j = 0; j<scrambled.length; j++){
				totals[j*sides+scrambled[j]] ++;
			}
		}*/
		
		
		Scrambler[] scramblers = {new Scrambler(Scrambler.MEGAMINXDTSR),
		new Scrambler(Scrambler.MEGAMINXDTVR), new Scrambler(Scrambler.MEGAMINXSR)};
		int[][] lengths = {new int[] {500,1000,2000},new int[] {175,180,210,220,250,500,1000,2000},
				new int[] {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 125, 150, 175, 200, 500, 1000,2000}};
		
		Megaminx puzzle = new Megaminx();
		
		for(int si = 0; si < scramblers.length; si++){
		Scrambler scrambler = scramblers[si];
		bw.write("New scrambler "+scrambler.name+"\n");
		bw.write("Sample scramble: "+scrambler.generateScramble()+"\n");
		
		int sides = 12;
		int stickersPerFace = 10;
		int[] scrambleLengths = lengths[si];
		//int[] scrambleLengths = {26,27};
		int trials = 1000000;
		int[] totals;
		Integer[] scrambled = null;
		Integer[] scrambledNoCenters = null;
		String scramble;
		for(int z = 0; z<scrambleLengths.length; z++){
			totals = new int[stickersPerFace*sides*sides];
		for(int i = 0; i<trials; i++){
			puzzle.reset();
			scramble = scrambler.generateScramble(scrambleLengths[z]);
			//scramble = Megaminx.WCAScrambleString(scrambleLengths[z]);
			puzzle.applyScramble(scramble);
			puzzle.orient();
			scrambled = puzzle.getState();
			scrambledNoCenters = stripCenters(scrambled);
			for(int j = 0; j<scrambledNoCenters.length; j++){
				totals[j*sides+scrambledNoCenters[j]] ++;
			}
			
		}

		System.out.println();
		double stddev = stdDev(totals);
		double mean = mean(totals);
		
		bw.write(scrambler.name+"\n");
		System.out.println("mean        = "+mean);
		bw.write("mean        = "+mean+"\n");
		System.out.println("Scramble Length = "+scrambleLengths[z]);
		bw.write("Scramble Length = "+scrambleLengths[z]+"\n");
		System.out.println("StdDev      = "+stddev);
		bw.write("StdDev      = "+stddev+"\n");
		System.out.println("Sd% of mean = "+stddev/mean*100+"\n");
		bw.write("Sd% of mean = "+stddev/mean*100+"\n\n");
		bw.flush();
		}
		}
		bw.flush();
		bw.close();
		}catch(Exception e){
			//absorb
		}
		System.out.println(Test.longToTime(System.currentTimeMillis()-start));
		
	}
	
	public static String substitute(String in){
		StringBuffer out = new StringBuffer();
		StringTokenizer st = new StringTokenizer(in, " ");
		String[] subs = {"Wh", "DG", "Pu", "Or", "Br", "Te", "LG", "Re", "DB", "LB", "Pi", "Ye"};
		while(st.hasMoreTokens()){
			String temp = st.nextToken();
			if(temp.substring(0,1).equals("\n")){
				temp = temp.substring(1,temp.length());
				out.append("\n");
			}
			int num = 0;
			if(temp.length() == 2){
				num = Integer.parseInt(temp.substring(0,1));
			}else if(temp.length() == 3){
				num = Integer.parseInt(temp.substring(0,2));
			}
			out.append(subs[num]+", ");
		}
		return out.toString();
		
	}
	
	public static Integer[] stripCenters(Integer[] in){
		int[] centers = {10, 27, 30, 33, 36, 39, 92, 95, 98, 101, 104, 131};
		Integer[] out = new Integer[in.length-12];
		int offset = 0;
		for(int i = 0; i<in.length; i++){
			if(Arrays.binarySearch(centers, i)>=0)
				offset++;
			else
				out[i-offset] = in[i];
		}
		return out;
	}
}
 
Another thought: Pick six megaminx states perfectly randomly and generate scrambles for them. Now call these six scrambles "R++", "R--", "D++", "D--", "U" and "U'". And use them in the WCA scrambler. Still think that 2^70 scrambles means it's bad?

And I just finished an analysis of where the centers end up with what probability:
Code:
          DLB   DLF   DRB   URF   ULF   B     F     U     URB   DRF   ULB   D       min   max      sum
     pink 8.329 8.329 8.326 8.338 8.341 8.327 8.340 8.347 8.338 8.327 8.340 8.320   8.320-8.347 => 100.000
    blue2 8.329 8.329 8.326 8.338 8.341 8.327 8.340 8.347 8.338 8.327 8.340 8.320   8.320-8.347 => 100.000
   orange 8.347 8.347 8.329 8.320 8.338 8.336 8.331 8.321 8.320 8.336 8.331 8.346   8.320-8.347 => 100.000
   purple 8.338 8.338 8.341 8.329 8.326 8.340 8.327 8.320 8.329 8.340 8.327 8.347   8.320-8.347 => 100.000
turquoise 8.320 8.320 8.338 8.347 8.329 8.331 8.336 8.346 8.347 8.331 8.336 8.321   8.320-8.347 => 100.000
   green2 8.340 8.340 8.328 8.327 8.339 8.332 8.334 8.331 8.327 8.332 8.334 8.336   8.327-8.340 => 100.000
    green 8.327 8.327 8.339 8.340 8.328 8.334 8.332 8.336 8.340 8.334 8.332 8.331   8.327-8.340 => 100.000
    white 8.326 8.326 8.347 8.341 8.320 8.339 8.328 8.329 8.341 8.339 8.328 8.338   8.320-8.347 => 100.000
     blue 8.338 8.338 8.341 8.329 8.326 8.340 8.327 8.320 8.329 8.340 8.327 8.347   8.320-8.347 => 100.000
      red 8.340 8.340 8.328 8.327 8.339 8.332 8.334 8.331 8.327 8.332 8.334 8.336   8.327-8.340 => 100.000
    brown 8.327 8.327 8.339 8.340 8.328 8.334 8.332 8.336 8.340 8.334 8.332 8.331   8.327-8.340 => 100.000
   yellow 8.341 8.341 8.320 8.326 8.347 8.328 8.339 8.338 8.326 8.328 8.339 8.329   8.320-8.347 => 100.000

See also:
http://www.stefan-pochmann.info/spocc/other_stuff/tools/scramble_megaminx/
 
Last edited:
Sorry, but I don't see why anyone would care where the centers end up, since no piece is fixed in the scramble. The centers really have nothing to do with the scramble quality. Besides, this is such a small part of the puzzle (and one which can be solved with about 3 moves) that of course it will look completely random after 70 moves. Looking at where the green-white-red corner ends up on a 70-move 100x100 scramble would also be indistinguishable from random, but that doesn't mean the scramble is good. (And really, you can never prove a non-purely-random scrambler is perfect, only that it is flawed or that you have not yet noticed any flaw.)

In addition your silly arguments do not prove that having 2^70 possible combinations is not a problem. It's the algorithm I am concerned with, not the output. Your examples also centered around the idea of using randomness to create the initial list, and thus were strictly better (i.e. closer to random) than the original scrambling algorithm, which relies on 70 single moves. The 2^70 limit does not prove that there is no macroscopic randomness, but just suggests it, because we have chosen some tiny subset of the sample space and then assumed it is representative of the entire thing, without any reason to believe it is. It's not like we randomly chose 2^70 positions - they are determined algorithmically to be all positions which are 70 Pochmann-scrambler moves away, and we really know nothing about this set.
 
Sorry, but I don't see why anyone would care where the centers end up
I care because I was curious about it by itself and because I can now extend my program to analyze more stuff. Centers just seemed the easiest thing to implement, so I started with that. And if others implement their own independent analyzer and are able to compute the same thing, we can compare our results to find mistakes or be more confident that we didn't make any. Also, if I had found a significant deviation or pattern for centers already then I would've worried about the scrambling method at this point already. You say "of course it will look completely random", but I wasn't so sure and wanted to get us actual numbers. But I'm sorry if me posting these results bothered you.

Hawk said he felt his cross edges feel too easy to solve so I intend to get us some actual numbers for that, too. And you said you'd like to see an analysis of how close edges and corners are to being paired up, and I intend to get us that as well.

Besides, this is such a small part of the puzzle (and one which can be solved with about 3 moves) that of course it will look completely random after 70 moves. Looking at where the green-white-red corner ends up on a 70-move 100x100 scramble would also be indistinguishable from random
Wrong. To be indistinguishable from random, all my values would have to be 8.333% (exactly 1/12). Clearly this is not the case.

In addition your silly arguments do not prove that having 2^70 possible combinations is not a problem.
1. I don't understand why they're silly. Can you explain?
2. Having 2^70 possible combinations is not a problem.
3. I would never claim they prove it. But I think they help illustrating it better. Besides, their main purpose is to rebut the opposite idea, that a small number is a problem.

Your examples also centered around the idea of using randomness to create the initial list, and thus were strictly better (i.e. closer to random) than the original scrambling algorithm, which relies on 70 single moves.
Um, no, I'd say they're better because they offer more change than simple single turns. Note that the six scrambles are hardcoded into the supposed program once and for all time and for everyone. There are about 10^408 possible such programs and yes my supposed creation would use randomness to pick one, but each one of these programs has no more randomness than the current WCA scrambler.

The 2^70 limit does not prove that there is no macroscopic randomness, but just suggests it, because we have chosen some tiny subset of the sample space and then assumed it is representative of the entire thing, without any reason to believe it is. It's not like we randomly chose 2^70 positions - they are determined algorithmically to be all positions which are 70 Pochmann-scrambler moves away, and we really know nothing about this set.
Wait. I'm confused. Do we know nothing about it or do we know that it suggests lack of randomness? What is it?
 
Last edited:
Motivated by the discussion here I took a closer look at the Assembler Code of the Random function Random(N) of the Cube Explorer in Delphi6, which computes a pseudorandom integer between 0 and N-1. RandSeed is a 32 bit integer variable and has 2^32 different values. On entry, the EAX register contains N.
I added some comments

XOR EBX, EBX
; This sets EBX to 0

IMUL EDX,[EBX].RandSeed,08088405H
INC EDX
MOV [EBX].RandSeed,EDX
; so the new RandSeed is (134775813*RandSeed + 1) (mod 2^32)
; At least if the multiplication would be unsigned. But because it is signed,
; this may be wrong - I do not know exactly.

MUL EDX
;Unsigned multiplication of EDX and EAX, Result in EDX:EAX. After this
;Operation EDX holds (RandSeed*N)/2^32, which is a number
;between 0 and N-1. This number is returned by the function.

The RandSeed sequence has the full period 2^32.
So the Random Generator gives 2^32=4294967296 different values.
To generate a Random cube I use Random(8!), Random(12!) Random(2^11) and Random(3^7) for random generation of the permutations and orientations of corners and edges.
If the cube has odd parity, the cube is discarded. This will happen for approximately 1/2 of the random cubes.

We will get "only" about 2^31 different valid cubes by the built in random generator. This is about 4.96505*10^-9 percent of the cube space....
 
Also, if I had found a significant deviation or pattern for centers already then I would've worried about the scrambling method at this point already.
I wouldn't be (any more) worried if that happened. The goal of a scramble is to scramble the pieces relative to the centers. In the extreme case, if the centers were oriented in the same way every time, it would not necessarily affect the scramble quality at all; look at the 3x3 scrambler. Nobody cares if their cube is in a random orientation because 15 seconds is plenty of time to fix that. Essentially the orientation of the puzzle is a variable that runs 'perpendicular' to the position of the puzzle, and one can be easily modified without affecting the other, so knowing the distribution of one gives us absolutely no data about the distribution of the other.

Looking at where the green-white-red corner ends up on a 70-move 100x100 scramble would also be indistinguishable from random
Wrong. To be indistinguishable from random, all my values would have to be 8.333% (exactly 1/12). Clearly this is not the case.
You're completely wrong here. A discrete random variable will almost never (probability -> 0 as number of trials -> infinity) have exactly the distribution that the probabilities say; that's why we have to use statistical tests to check if something is random or not. When I say indistinguishable from random I mean that there is no statistically significant difference between the results you get and the results a random state scrambler would turn up.

Having 2^70 possible combinations is not a problem.
There are approximately 12*4 * (11*4)^12 (this is about 2^71) positions that are 13 moves away from solved on the megaminx. So here is a hypothetical scrambler: choose a position that is 13 or fewer moves away from solved on the megaminx, and provide the optimal solution. This should have ~2^70 positions within an order of magnitude or two. Clearly this is not a good scrambler.
You seem to be completely misinterpreting me: I am not saying that 2^70 combinations means there MUST be a problem; I am instead saying that it means there is PROBABLY a problem. It is a red flag that suggests we need further investigation before we will know if the scrambling method is acceptable. You have chosen 2^70 elements of the megaminx positions set without knowing which elements you chose. Perhaps it is a representative sample, but perhaps it is not and the scrambles are in some way easier (or harder!) than average. I think we need to know this.

Wait. I'm confused. Do we know nothing about it or do we know that it suggests lack of randomness? What is it?
For someone who is so pedantic you are making quite a lot of thought errors. The definition of the set suggests that it may lack randomness, because the set is a tiny subset of the set of megaminx positions. It's a tiny subset which is specifically defined, and we do not know whether this definition provides good scrambles or scrambles that are on average biased in a certain way, because the definition is not "we randomly chose 2^70 positions and solved them" but rather something more algorithmic. As for no knowledge, it is true: we know pretty much nothing about the set itself except that it contains all of the scrambles which are 70 Pochmann-scrambler moves from solved. I really have no clue about the macroscopic properties of the set itself, which is why we need to do more analyses.


We will get "only" about 2^31 different valid cubes by the built in random generator. This is about 4.96505*10^-9 percent of the cube space....
Perhaps we *should* start using random.org data then...
 
We will get "only" about 2^31 different valid cubes by the built in random generator. This is about 4.96505*10^-9 percent of the cube space....
Thanks a lot for checking that. I've been wondering for quite a while and tried looking for information about Pascal's or Delphi's PRNG but couldn't find anything.

Essentially the orientation of the puzzle is a variable that runs 'perpendicular' to the position of the puzzle, and one can be easily modified without affecting the other, so knowing the distribution of one gives us absolutely no data about the distribution of the other.
1. You can and apparently do think of the centers solely as a frame, a reference defining where all other pieces have to move to. But that's just one perspective. I can equally well choose to use the white/purple/green corner or the yellow/orange edge as reference and regard the centers as one moving piece.
2. If already the centers deviate significantly, I would worry that other pieces, scrambled with the same algorithm, might deviate similarly.
3. The scrambler does *not* pick a random side to turn next, it can only "turn" the top or the left one. Thus "puzzle orientation" does matter.

Wrong. To be indistinguishable from random, all my values would have to be 8.333% (exactly 1/12). Clearly this is not the case.
You're completely wrong here. A discrete random variable will almost never (probability -> 0 as number of trials -> infinity) have exactly the distribution that the probabilities say; that's why we have to use statistical tests to check if something is random or not.
No you're wrong. You'd be right if I let's say analyzed a million somewhat randomly selected scrambles. But I didn't. I analyzed all 2^70 possible scrambles. I'm not analyzing some outputs of the system. I'm analyzing the system. And proved that it introduces a bias that a truly random one wouldn't have.

Having 2^70 possible combinations is not a problem.
[...]
You seem to be completely misinterpreting me: I am not saying that 2^70 combinations means there MUST be a problem; I am instead saying that it means there is PROBABLY a problem.
[...]
I think I do and did understand you. You made your position quite clear early in the thread. But you and hawk still somewhat give the impression that a small number of outcomes is a problem. One example is you picking the above quote of mine and commenting a lot on it as if it were wrong. But I only said that a small number of outcomes is not a problem. That's not wrong. It really isn't a problem. It can indicate there might be a problem, but it's not a problem itself. In your hypothetical scrambler, the small number of scrambles isn't the problem, the scrambles almost not scrambling is the problem.

And I wouldn't like people to read this thread and think it is a problem. People shouldn't worry about the quality of our scrambles purely because of a small number of possible outcomes. Like for example...

We will get "only" about 2^31 different valid cubes by the built in random generator. This is about 4.96505*10^-9 percent of the cube space....
Perhaps we *should* start using random.org data then...
... this guy.
 
Last edited:
This is starting to get a little over my head but I'm not understanding how you can say that a small number of outputs is not a problem. It MIGHT not be a problem, it might be. It depends on whether the states we can generate are a representative sample of the entire set of states. Correct?
So we'd need to check that. We can't say either way whether it's a problem yet.
It bugs me, yes. I'd like us to be able to generate all possible states. But if we can't, or we can't practically, a representative sample will satisfy me.
 
This is starting to get a little over my head but I'm not understanding how you can say that a small number of outputs is not a problem. It MIGHT not be a problem, it might be.
There, Michael, see?

It depends on whether the states we can generate are a representative sample of the entire set of states. Correct?
No that doesn't depend. If the scrambler doesn't generate a representative sample of the entire set of states, then that might be a problem. The small number of outputs is not.

And Michael: Do you think I'm trying to prove the WCA scrambler to be good, maybe because I came up with it and want to "defend" it/myself? Not at all the case. I want it analyzed and will gladly accept any result. As usual I take the agnostic middle ground. I'm not saying it's good, I'm not saying it's bad. I just don't like people saying it's bad for flawed reasons. I'd just as much fight flawed points arguing that it's good.
 
This is starting to get a little over my head but I'm not understanding how you can say that a small number of outputs is not a problem. It MIGHT not be a problem, it might be.
There, Michael, see?

It depends on whether the states we can generate are a representative sample of the entire set of states. Correct?
No that doesn't depend. If the scrambler doesn't generate a representative sample of the entire set of states, then that might be a problem. The small number of outputs is not.

And Michael: Do you think I'm trying to prove the WCA scrambler to be good, maybe because I came up with it and want to "defend" it/myself? Not at all the case. I want it analyzed and will gladly accept any result. As usual I take the agnostic middle ground. I'm not saying it's good, I'm not saying it's bad. I just don't like people saying it's bad for flawed reasons. I'd just as much fight flawed points arguing that it's good.
I won't flatter myself, I'm assuming when you say Michael you're addressing Michael Gottlieb.

Well, I think having a small amount of outputs can definitely be a problem. We could have a scrambler that generates 500 states. They might fit the expected distributions of oriented and permuted pieces perfectly, that wouldn't be the problem. Granted, I don't think that will be an issue with the numbers we're talking about here.
 
I won't flatter myself, I'm assuming when you say Michael you're addressing Michael Gottlieb.
Oops. Yeah. That happens if you guys are hiding.

Well, I think having a small amount of outputs can definitely be a problem. We could have a scrambler that generates 500 states.
I agree:
What's important is the quality of the scrambling, not the number of possible outcomes (if the latter is reasonable (so don't say I said a megaminx scrambler with ten possible outcomes can be good)).
 
You can and apparently do think of the centers solely as a frame, a reference defining where all other pieces have to move to. But that's just one perspective.
You say "just one perspective" as if there are other meaningful ones from the context of speedsolving. There aren't. Nobody fast holds an edge/corner fixed and moves the centers and the rest of the pieces around it. The ending position after the scramble, relative to the centers, is all that is important.

I analyzed all 2^70 possible scrambles. I am not analyzing some outputs of the system.
You're saying you literally looked at all 2^70 (~10^21) things? How did you manage that? (By the way, you did not state this when you posted the results, so it isn't fair to criticize me for not knowing this.) This does change the interpretation of the results you posted.

People shouldn't worry about the quality of our scrambles purely because of a small number of possible outcomes.
I've said many times, though, it is not the quality of single scrambles I am concerned with, but the quality of the algorithm that generates those scrambles. The small number of outcomes does not tell us there is anything wrong with individual scrambles, just that the algorithm which produces scrambles is provably not uniformly random with regard to Megaminx positions.

And Michael: Do you think I'm trying to prove the WCA scrambler to be good, maybe because I came up with it and want to "defend" it/myself? Not at all the case.
Actually this IS the vibe I am getting from your posts. You are attacking my wording more than anything else... when I take shortcuts and write "scrambles" instead of "distribution of scrambles", or "is a problem" for "is something that introduces an element of doubt into the scrambler's macroscopic randomness", you attack the philosophy you think the words are describing, even though I have clearly stated exactly what I mean several times. You seem to be arguing even when you agree with my point, just because you think the way I said things might be misinterpreted. To be honest, I feel this is more the behavior of someone who is desperately trying to defend something they made than the behavior of someone who agrees with my point that several characteristics of the scrambler signify that it needs to be looked at more carefully before we can assume it is unbiased. Even if you are not consciously trying to defend your scrambler, insisting that you are only arguing against me for the purpose of correcting my errors in wording is an arrogant lie.

This is starting to get a little over my head but I'm not understanding how you can say that a small number of outputs is not a problem. It MIGHT not be a problem, it might be.
There, Michael, see?
I have stated many times that I mean exactly this. The small number of outputs signifies that we cannot assume the scrambler is unbiased without actually examining it. There is no excuse for why you keep deliberately misinterpreting my statements.

But you and hawk still somewhat give the impression that a small number of outcomes is a problem.
I have stated many times exactly what I mean. There is no excuse for why you keep deliberately misinterpreting my statements.


If you want to keep talking, go ahead, but I'm done. This topic is devolving into deliberate failure to communicate, condescending remarks, and arrogance. It looks like you are not trying to make a point, but just to be insulting and annoying. If you want to have an actual argument, let me know.
 
My apologies, I missed that statement. Then yes, I agree with your last post.
 
You're saying you literally looked at all 2^70 (~10^21) things?
Yes. That's what I said. Can't you just trust me a bit?

How did you manage that?
Same way I for example analyzed all 3x3x3 scrambles up to 100 moves before: Dynamic programming. See the code (still available on the page) if you're interested, and I can explain it further if necessary (though it's really rather easy, I even used a static 3-dimensional table rather than using and reusing 2-dimensional ones, because I find it cleaner that way).

By the way, you did not state this when you posted the results, so it isn't fair to criticize me for not knowing this.
Well I presented it as the probabilities of where the centers end up. Of course I wouldn't have done that if I had only analyzed a subset, that would just be wrong. At least I would've used past tense and provided details like the used sample size. If I say I show you the probabilities, you ought to assume that I'm showing you the exact ones (except negligible rounding) and not some randomized experimental results. Also, I did mention it in the program.

Actually this IS the vibe I am getting from your posts.
Really not the case. That I created it is a coincidence. I'm defending it against what I consider flawed arguments because I don't like flawed arguments, not because I made it. Why do I defend the Cube Explorer scrambling the same way? I didn't make that one. Explain? And remember the Matyas issue where I quite a bit criticized both his believers and his doubters for their flawed arguments for or against him? I'm a proponent of solid reasoning, that's all. Btw, it's not nice to call my arguments stupid, me arrogant and a liar. I know I've been somewhat gruff, too, but I don't think I went nearly that far and explicitly personal.

My apologies, I missed that statement. Then yes, I agree with your last post.
No worries, I might've edited that in after you read the post. And just like you said, it's clear we're really not talking about *that* small numbers anyway.

Done, too (until I have new analysis results or am asked something).
 
Last edited:
Motivated by the discussion here I took a closer look at the Assembler Code of the Random function Random(N) of the Cube Explorer in Delphi6, which computes a pseudorandom integer between 0 and N-1. RandSeed is a 32 bit integer variable and has 2^32 different values. On entry, the EAX register contains N.
I added some comments

XOR EBX, EBX
; This sets EBX to 0

IMUL EDX,[EBX].RandSeed,08088405H
INC EDX
MOV [EBX].RandSeed,EDX
; so the new RandSeed is (134775813*RandSeed + 1) (mod 2^32)
; At least if the multiplication would be unsigned. But because it is signed,
; this may be wrong - I do not know exactly.

MUL EDX
;Unsigned multiplication of EDX and EAX, Result in EDX:EAX. After this
;Operation EDX holds (RandSeed*N)/2^32, which is a number
;between 0 and N-1. This number is returned by the function.

The RandSeed sequence has the full period 2^32.
So the Random Generator gives 2^32=4294967296 different values.
To generate a Random cube I use Random(8!), Random(12!) Random(2^11) and Random(3^7) for random generation of the permutations and orientations of corners and edges.
If the cube has odd parity, the cube is discarded. This will happen for approximately 1/2 of the random cubes.

We will get "only" about 2^31 different valid cubes by the built in random generator. This is about 4.96505*10^-9 percent of the cube space....

I have somewhat wondered about the actual "randomness" of Cube Explorer's random states.

Some things I note about the procedure. Each internally generated cube (legal or illegal state) uses 4 random numbers. 4 is a factor of the number of states of the PRNG (2^32). That means that once we pick an initial seed, (and assuming the PRNG is only being used to generate random cubes), then the sequence of internally generated cubes will repeat themselves after 2^30 cubes (or approximately every 2^29 legal cubes). We are locked into a cycle that will only generate 1/4 of the possible cubes that we could get (unless we reseed, or "waste" a PRNG value once in awhile, or do something similar). I would prefer the number of PRNG values used to determine a cube to be relatively prime to the number of PRNG states.

My second comment has to do with the throwing away of the illegal cubes. Approximately half the generated cubes are thrown away. Clearly there will be streaks where a number of consecutive cubes are thrown away. Let's say there is a streak of three consecutive cubes that are thrown away, followed by one that is legal, so it's not thrown away. Note that there will be four different possible initial seeds that will result in this particular legal cube being returned. Let's say the next cube generated is also a legal cube. So it may very well be that only that one initial seed will result in that particular cube being the first cube returned. So the one cube will be four times more likely to be the first returned cube than the other one. Personally I would prefer a procedure that would always pick legal cubes, so none are thrown away, and thus avoiding this type of bias.
 
Back
Top