Scramble filtering limits?

[Jeremy Fleischman]

(dealing with https://github.com/cubing/tnoodle/issues/140)

Here's what TNoodle currently does. Is this different than what was chosen in the past? From http://localhost:8080/readme/scramble:

Scramble Filtering

Scrambles are filtered according to rules set by the WCA Board. Note that these rules are not hardcoded in the WCA Regulations.

This version of TNoodle generates scrambles obeying the following rules:

2x2x2: ≥ 5 moves away from solved 

3x3x3: ≥ 2 moves away from solved 

4x4x4: ≥ 2 moves away from solved 

5x5x5: ≥ 2 moves away from solved 

6x6x6: ≥ 2 moves away from solved 

7x7x7: ≥ 2 moves away from solved 

Clock: ≥ 2 moves away from solved 

Megaminx: ≥ 2 moves away from solved 

Pyraminx: ≥ 8 moves away from solved 

Square-1: ≥ 2 moves away from solved

[Sébastien Auroux]

Hi Jeremy,

thanks for bringing this up, as the limits are incorrect, I guess due to miscommunication. 2x2x2 should be 4 moves, Pyraminx should be 7. That's definitely what we agreed on based on previous WRs having this number of moves. Please fix this with the next version of TNoodle.

Concerning SQ-1: How much is feasable?

Thanks, Sébastien

2013/12/11 Jeremy Fleischman <jeremyfl...@gmail.com>

[Jeremy Fleischman]

This is done in https://github.com/jfly/tnoodle/commit/cd32172c6e6861ea25095c91fc73f9406a88893a. Here are the updated filtering rules:

Scramble Filtering

Scrambles are filtered according to rules set by the WCA Board. Note that these rules are not hardcoded in the WCA Regulations.

This version of TNoodle generates scrambles obeying the following rules:

2x2x2: ≥ 4 moves away from solved 

3x3x3: ≥ 2 moves away from solved 

4x4x4: ≥ 2 moves away from solved 

5x5x5: ≥ 2 moves away from solved 

6x6x6: ≥ 2 moves away from solved 

7x7x7: ≥ 2 moves away from solved 

Clock: ≥ 2 moves away from solved 

Megaminx: ≥ 2 moves away from solved 

Pyraminx: ≥ 7 moves away from solved 

Square-1: ≥ 2 moves away from solved

I'll look into square 1 filtering, but I suspect we won't be able to bump that number up very high.

[Lucas Garron]

Why can't we go high with Square-1, again? Just performance?

My *phone* should be able to brute-force to 5 or 6 moves with a decent algorithm.

»Lucas Garron

--
You received this message because you are subscribed to the Google Groups "WCA Scrambler Team" group.
To unsubscribe from this group and stop receiving emails from it, send an email to wca-scramble...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Jeremy Fleischman]

Right now, square 1 filtering is done with the generic puzzle solver. Clement has improved it a bit, but it's not doing any sort of inteligent puzzle-aware pruning.

[Jeremy Fleischman]

Ok, I was overly pessimistic about what the generic solver is capable of.

I generated 50 sq1 scrambles at depth >= 1, >= 2, >= 3, ... (TNOODLE_SQ1_MIN_DISTANCE=1 ./tmt make run -p scrambles --args="sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1 sq1" 2>&1 | grep -Po "(?<=took )[0-9]*.?[0-9]*" > /tmp/dist1). Here are the averages for each of those (cat /tmp/dist1 | awk '{sum+=$1} END { print "Average = ",sum/NR}'):

1: Average =  0.10248

2: Average =  0.07148

3: Average =  0.05076

4: Average =  0.12944

5: Average =  0.10486

6: Average =  0.18382

7: Average =  0.17754

8: Average =  2.18466

9: Average =  2.20902

10: Average =  4.06726

11: Average =  4.38918

So any of these filtering depths is totally reasonable.

Remember that TNoodle's turning metric counts (x, y) as 1 turn, and / as 1 turn. I'm not sure if this is consistent with what people call "move metric".

[Tim Reynolds]

This is an aside, but

--args=$(yes "sq1" | head -50)

http://superuser.com/questions/86340/linux-command-to-repeat-a-string-n-times

[Sébastien Auroux]

Shall we just go with 11 then?

2013/12/11 Tim Reynolds <timbre...@gmail.com>

[Shuang Chen (陈霜)]

Some statistics about the filtering on 2x2x2 and pyraminx:

"2x2x2 >= 4 moves" => 385 states are filtered, about 1 in 10000, or 0.01%

"pyraminx>=7 moves" => 221233 states are filtered, about 1 in 342, or 0.29%

And for other puzzle, less than 100 states are filtered.

在 2013年12月11日星期三UTC+8下午8时40分47秒，Jeremy Fleischman写道：

[Shuang Chen (陈霜)]

I don't think the length of filtering depend on the implementation of filter. If needed, we can write a 20-move filter on sq1 and about 10-move filter on 3x3x3 to 7x7x7 without much works.

在 2013年12月11日星期三UTC+8下午9时46分41秒，Sébastien Auroux写道：

[Sébastien Auroux]

if it truely is "without much work" please go ahead!

2013/12/11 Shuang Chen (陈霜) <cs0...@gmail.com>

[Jeremy Fleischman]

That's a neat trick, thanks!

[Shuang Chen (陈霜)]

The 20-move filter on sq1 is finished. See:

https://github.com/ChenShuang/tnoodle/commit/1db21288b842cd10c717188250b185fe1837725d


在 2013年12月12日星期四UTC+8上午2时48分51秒，Sébastien Auroux写道：

[Jeremy Fleischman]

Awesome work! I've commented on the diff. Lets get this and your skewb stuff into cubing/tnoodle soon!

[Sébastien Auroux]

Well, crazy. Thanks a lot! Are we still talking about (x,y) being one move and / being one move as well? If so, the current Single WR had 21 moves as optimal solution. This makes filtering out 20 moves quite reasonable. How many percent of all states would this be?

Also, it would be awesome to have filtering for Skewb implemented as of its beginning.

@Sarah, can you help us finding a reasonable bound for this?

2013/12/11 Jeremy Fleischman <jeremyfl...@gmail.com>

[Sébastien Auroux]

SARAH?

We need to define a filter limit for Skewb very soon.

2013/12/11 Sébastien Auroux <sebastien...@gmail.com>

[Sarah Strong]

I suggest ≥7 for Skewb. That would filter 2.2% of the scrambles, which is more than how much is filtered for 2x2x2 and Pyraminx, but since  Skewb is deep-cut and short solutions are harder to see, it seems like a better choice than ≥6, which only filters 0.04% of the scrambles.

[Sébastien Auroux]

ok, agreed. So the same as for Pyraminx, which does also feel consistent to me.

Jeremy, can you make sure this gets implemented? Is the Skewb Scrambler ready by the way?

2013/12/25 Sarah Strong <sa9...@gmail.com>

[Jeremy Fleischman]

Hey Sebastien,

Sorry for the delayed response. As of https://github.com/cubing/tnoodle/commit/c89b791ca1529936848d84c43f41e1a3a1c794a2 and https://github.com/jfly/tnoodle/commit/e701daddacd0083fdeab04fc2d00cf49a9a58601, skewb has been pulled into TNoodle, and appears to be working.

Unfortunately, Chen Shuang's improvements to our square one filtering broke some other stuff, so I had to revert that change (see https://github.com/cubing/tnoodle/issues/151). This means that right now, sq1 filtering is limited to 11 turns by tnoodle's move metric. I do not have the time to learn Chen Shuang's sq1 solver, so he's going to have to look into this. He's pretty busy with finals right now, so I'm not sure if he'll be able to get around to this before 2014. If he can't get to this before 2014, I don't think it's a huge problem to "only" filter sq1 to 11, as that's still way better than our situation in 2013.

-Jeremy

[Sébastien Auroux]

Hey Jeremy,

thanks for your response. No there is no problem having SQ1 filtered with 11 moves only right now. Skewb is way more important to have a "clean" start of the event.

So, can you reconfirm that as of January 1st 2014 TNoodle will filter:

- 2x2x2 scrambles with < 4 moves solutions (so all valid scrambles require >= 4 moves)

- Pyraminx scrambles with < 7 moves solutions (so all valid scrambles require >= 7 moves)

- Skewb scrambles with < 7 moves solutions (so all valid scrambles require >= 7 moves)

Thanks, Sébastien

2013/12/28 Jeremy Fleischman <jeremyfl...@gmail.com>

[Jeremy Fleischman]

Copy pasting from http://localhost:8080/readme/scramble on my development version of tnoodle:

2x2x2: ≥ 4 moves away from solved 

3x3x3: ≥ 2 moves away from solved 

4x4x4: ≥ 2 moves away from solved 

4x4x4 (fast, unofficial): ≥ 2 moves away from solved 

5x5x5: ≥ 2 moves away from solved 

6x6x6: ≥ 2 moves away from solved 

7x7x7: ≥ 2 moves away from solved 

Clock: ≥ 2 moves away from solved 

Megaminx: ≥ 2 moves away from solved 

Pyraminx: ≥ 7 moves away from solved 

Skewb: ≥ 7 moves away from solved 

Square-1: ≥ 11 moves away from solved

This matches what you just said, so we're good!

[Sébastien Auroux]

Great! :)

[Sébastien Auroux]

Btw, I think that these limits should not appear in the regulations (4b3a-4b3c in the current draft). There is absolutely no use in that for anyone and for documentation, the TNoodle documentation seems absolutely sufficient to me.

[Natan Riggenbach]

Glad that this is done, and just to make the request official, please proceed to implement wide moves to ensure random orientation for all non-inspection events except FMC.

Do we agree that 4x4 already has random orientation, BTW?

---

Date: Sat, 28 Dec 2013 14:44:42 +0100
Subject: Re: Scramble filtering limits?
From: sebastien...@gmail.com
To: sebastien...@gmail.com
CC: timbre...@gmail.com; jeremyfl...@gmail.com; w...@worldcubeassociation.org; crease...@gmail.com; bo...@worldcubeassociation.org; sa9...@gmail.com; cs0...@gmail.com; wca-sc...@googlegroups.com

[Jeremy Fleischman]

I believe Lucas's model is for the WCA regulations to define exactly what a WCA scrambler program is, without mentioning any program in particular. In addition, the WCA recommends an official scrambler program that they believe satisfies all those constraints (in the distant future, I could imagine the WCA maintaining its own list of WCA scrambler tests that can be run against a program to certify it as an "official WCA scrambler program").

Speaking a little more concretely, we've already had 1 instance of TNoodle diverging from what the WRC asked for (hence this email thread =)), so I do think it would be good to have 1 true source of requirements for a scrambler (not just filtering rules, but *everything*).

[Jeremy Fleischman]

I can't claim to understand it, but Lucas did write up a proof here: https://github.com/cubing/tnoodle/issues/148#issuecomment-31269353. It would be nice for someone to bless it (Stefan?)

I'm pretty busy tonight, but I should be able to get to https://github.com/cubing/tnoodle/issues/148 and maybe https://github.com/cubing/tnoodle/issues/151 tomorrow.

[ILKYOO CHOI]

Thank you guys.

Let's keep in mind that there is a competition on January 1st, 2014 in India, where the time zone is UTC/GMT +5:30 hours.

We should push out something at least a half day before that so the delegate of the competition can generate the scrambles.

Thanks for all the hard work during the holiday season!

-- ILKYOO

[Stefan Pochmann]

On Wed, Dec 25, 2013 at 8:50 PM, Sarah Strong <sa9...@gmail.com> wrote:

I suggest ≥7 for Skewb. That would filter 2.2% of the scrambles, which is more than how much is filtered for 2x2x2 and Pyraminx, but since  Skewb is deep-cut and short solutions are harder to see, it seems like a better choice than ≥6, which only filters 0.04% of the scrambles.

Your 0.04% for >=6 moves is off by a factor of 10, actually it's 0.4%:

http://www.wolframalpha.com/input/?i=100*(1%2B8%2B48%2B288%2B1728%2B10248)%2F3149280

I'd like us to reconsider, and I'd prefer requiring >=6 instead of >=7 because filtering out 2.2% feels too much.

[Natan Riggenbach]

I also found the reasoning contradictory. If short solutions are harder to see, why should we filter for a higher figure?
More input from knowledgeable people, please.

---

Date: Sat, 4 Jan 2014 04:21:51 +0100

Subject: Re: Scramble filtering limits?

From: stefan....@gmail.com
To: sa9...@gmail.com
CC: sebastien...@gmail.com; jeremyfl...@gmail.com; cs0...@gmail.com; wca-sc...@googlegroups.com; timbre...@gmail.com; crease...@gmail.com; bo...@worldcubeassociation.org; w...@worldcubeassociation.org

[Sarah Strong]

One of the major concerns about adding Skewb was the luck element involved in single WRs, which is basically why I like ≥7 over ≥6. A six move one-look solution still takes a considerable amount of skill to notice during inspection and then execute, so I suspect that single WRs will eventually be held by those who deserve it. As long as the filtering limit isn't like ≥3, where someone who hardly does any skewb solving can get a very fast one-look single, I don't mind too much what the limit is. Other people have expressed that they would prefer ≥6 since it's closer to the percentages for 2x2x2 and Pyraminx, so perhaps ≥6 would be better. 

[Sarah Strong]

>I also found the reasoning contradictory. If short solutions are harder to see, why should we filter for a higher figure? More input from knowledgeable people, please.

I derped. Basically ≥7 is safer ≥6 since it's an event that can have fluke WR singles. I think ≥6 should be fairly safe, though (see above message).

[Sébastien Auroux]

People also pointed out that the Pyraminx Single WR was 6 moves which seems to be true while I thought it was 7 moves before. I agree that we should change Skewb and Pyraminx from 7 to 6.

[Stefan Pochmann]

That counts tips, right? So this would allow the "body" to be scrambled with just two moves. Not saying I'm against that, only want to point it out. And just in case you don't like it, maybe add a second filter requiring four moves for the body.

[Stefan Pochmann]

And I "confirm" that Pyraminx WR was 6 moves (6 body moves, 0 tip moves). I couldn't find the scramble or a reconstruction, but I reconstructed it myself from video yesterday. While the solve is hard to see, I'm certain about the start state and trying to replicate Oscar's moves, I solved in 6 moves.

On Saturday, January 4, 2014 9:21:55 AM UTC+1, Sébastien Auroux wrote:

[Sébastien Auroux]

PING

Are there objections against changing Pyraminx and Skewb to 6 moves? If not, lets make this change with TNoodle 0.8.0.

2014/1/4 Stefan Pochmann <stefan....@gmail.com>

[Jeremy Fleischman]

Double ping. This is decision is blocking tnoodle 0.8.0.

[Ron van Bruchem]

No objection from me

[Lucas Garron]

Yes, there are objections. It would violate the Regulations.

»Lucas Garron

[Sébastien Auroux]

That's not really a valid objection. As long as you insist on listing the filtering limits in the regulations, updating the regulations will be a logical consequence of a decision to change the filtering limits in TNoodle.

2014/1/10 Lucas Garron <crease...@gmail.com>

[Sébastien Auroux]

The grace period we are just anouncing will cause violations of the regulations as well, won't it?

If you don't feel comfortable with making such a small regulations update now, we can just extend the grace period to 4b3c).

Or, after all, we can just blatantly decide to accept this violation in order to not slow ourselves down with self-created burocracy while fixing this self-created mess we are just in.

Last option: Wait until the next regulations update, having more competitions with filter limits we now consider non-optimal, ask Jeremy to release 0.8.1 just for changing these 2 numbers, force all delegates to download again a new version then. I'm not in favour of this though.

2014/1/10 Lucas Garron <crease...@gmail.com>

Yes, then someone please make a proposal to change the Regulations, and give a good explanation to the community of why we should make this change but not all the other ones they care about.

Putting these limits in the Regulations was *on purpose* so that we can't sneak through a change like this.

»Lucas Garron

[Lucas Garron]

Have you considered that the difference between 6 and 7 doesn't matter *that* much, considering no one is getting excessively easy solves and we've been using 7 for Pyraminx since a while? This is also not about bureaucracy, it's about the community.

In any case, TNoodle will probably get a few small, useful features in early 2014 that can be rolled into a release.

»Lucas Garron

[Natan Riggenbach]

Even though I am no expert in the matter, I have tried to read the discussions and have come to agree to 6 for both pyra and skewb. How and when we implement this I will leave to you to figure out with the TNoodle team. I would say the sooner the better, but practical considerations may make it more desirable to wait. We have two days to figure this out anyway as it is too late to release 0.8.0 this week.

On a separate note, this is not about sneaking changes through. There are some technical things that are better left for the experts to discuss and decide on. I think we have enrolled some of the brightest and more knowledgeable people in the different teams/committees involved with this matter, and their opinions and input are enough for me at least. Opening the discussion up contributes little and only puts us in a defensive position whenever less knowledgeable community members start throwing crap around. As you can see, I am no fan of democracy.

---

From: crease...@gmail.com
Date: Fri, 10 Jan 2014 15:19:13 -0800

Subject: Re: Scramble filtering limits?

To: sebastien...@gmail.com
CC: bo...@worldcubeassociation.org; w...@worldcubeassociation.org; wca-sc...@googlegroups.com

[Sébastien Auroux]

Seems liek decision to change the limits is made. Remains when to make it. Jeremy, what's your position?

2014/1/11 Natan Riggenbach <nata...@hotmail.com>

[Jeremy Fleischman]

This is honestly a 2 line change. That said, I'm inclined to leave this until Chen Shuang can look at his sq1 solver and we can start aggressively filtering sq1 at 20 moves. I just read through a whole thread on speedsolving about filtering, and I do care a lot about community perception of the WCA (not my business to make decisions for the board, of course) and tnoodle (I still am looking for people to help me out with this thing!)

As Lucas said, 6 vs 7 doesn't really matter that much, and I like the idea of announcing it very clearly and ahead of time in a more targeted release.

Having said all that, I don't feel very strongly about any of this filtering shit,  and am annoyed that what I bet is a small fraction of our community has made such a fuss about something so unimportant. I am happy to put the change into 0.8.0, whatever the board decides. Software-wise, there's nothing stopping us.

[Natan Riggenbach]

A lot of help you are helping us decide! :P Nah, thanks a lot for all the work put in. Owe you a rocoto.

If the rest of useful features can be implemented before the end of February, I wouldnt mind waiting. But if we are talking March or later, I'd rather the 2 line change happened for 0.8.0 this coming Monday.

What say the other Board members?

-Natán

---

Date: Fri, 10 Jan 2014 19:55:56 -0800

Subject: Re: Scramble filtering limits?

From: jeremyfl...@gmail.com
To: sebastien...@gmail.com
CC: w...@worldcubeassociation.org; bo...@worldcubeassociation.org; crease...@gmail.com; nata...@hotmail.com; wca-sc...@googlegroups.com

[Sébastien Auroux]

I agree with Natán.

[Ron van Bruchem]

Same here.