Sub-optimal vs near-optimal

[Stefan]

This is mainly about scrambles.

I'd like to ask everybody to say "near-optimal" instead of "sub-optimal" where appropriate. Sub-optimal is often not really what people want to say. Often they mean something like Cube Explorer scrambles, and that's not just sub-optimal, that's near-optimal. The old fixed 25 moves scrambles for 3x3x3 are sub-optimal as well, as are 1000 moves scrambles (for 3x3x3). Near-optimal suggests sub-optimal, but sub-optimal does *not* suggest near-optimal. If you say sub-optimal, maybe you mean 1000 moves? If you mean near-optimal but say sub-optimal, you're not wrong, but you're also not really expressing what you mean, and that kinda makes you wrong.

There are two reasons for sub-optimality:

• Unintentional - When we're unable to produce optimality, like for 4x4x4 scrambles. We just can't do that (yet).
• Intentional - At least when scrambling for ourselves, we don't want to know in advance that a scramble is easy. So some scramble generators are made so that they for example always use at least 9 moves for 2x2x2 (even for cases they could solve in let's say 3 moves).

So you should say sub-optimal if that's really what you mean, but if near-optimal is what you mean, please say so.

Examples:

New features:
- Suboptimal random state 3x3

As I doubt it makes the scrambles intentionally longer, "near-optimal" would be better here.

I like suboptimal random state 3x3

You like this?

D2 R2 B2 F2 D2 L' D2 U2 B F U R B2 F L F2 R2 F2 D B2 F U2 L2 R2 B L' D2 B' L2 F' D' U F L R U' L' F' U2 L2 F' R2 F2 D2 F' D F' R2 D' U' R' D L F2 L R2 U'

Computers that do simplified sub-optimal solutions still use processing power that is way beyond a human limit

Don't know what "simplified" meant here, but I'm still quite certain "near-optimal" would be more appropriate, as you can generate sub-optimal solutions with almost no processing power at all.

[Skewb is] a complex enough puzzle that has been hosted "unofficially" many times and has working sub-optimal scramblers.

As 2x2x2 and Pyraminx don't seem be have intentionally sub-optimal scramblers, that's a useless argument and probably should've said near-optimal.

that scramble admittedly did not look sub-optimal

With 21 moves that scramble was both sub-optimal and near-optimal, no idea what tasguitar7 meant here but it's wrong someway.

 

[tasguitar7]

Thanks for clearing the confusion. I have no idea what I meant by that either.

 

[Kirjava]

I there a common situation where 'far-optimal' scrambles are used and referenced as sub-optimal?

 

[Andrew Ricci]

I always assumed sub-optimal and near-optimal were interchangeable. Thanks for clearing that up.

 

[qqwref]

I still don't really see anything wrong with saying "suboptimal". While we might not be intentionally making scrambles longer (okay, except for the suboptimal pyraminx/2x2 scrambles in qqtimer, which are by design at least a certain fixed number of moves no matter how easy the positions are), saying "suboptimal" to me says that we specifically aren't making an attempt to provide the shortest possible scramble, just a pretty short one. "Near-optimal", on the other hand, suggests that our scrambler will always produce something close to optimal (e.g. less than k moves away for some small k), which I don't guarantee.

Of course, there's also another naming option that was recently suggested to me: simply call the non-optimal ones "random state". I'll probably just end up doing that, since it's easy and noncontroversial. Or similarly, "efficient random state", which suggests few moves without suggesting anything about optimality.

 

[Stefan]

saying "suboptimal" to me says that we specifically aren't making an attempt to provide the shortest possible scramble, just a pretty short one.

I disagree with that last part. If you say sub-optimal, I don't know "how sub". It could be hundreds of moves. In fact that's what my Perl program in Tom's contest did. Maybe that's a language issue. For you, does "sub" mean "below" or "right below"? I just see it as "below", and as I feel that's valid, "sub" is a poor choice to express yourself if you mean "right below".

"Near-optimal", on the other hand, suggests that our scrambler will always produce something close to optimal (e.g. less than k moves away for some small k), which I don't guarantee.

Do you mean for your pyraminx/2x2 scramblers? I don't know how they work, but I would've expected them to guarantee that. Anyway, I'm really just against it if it's used without details as something positive ("New features: Suboptimal", "I like suboptimal", etc) where "near-optimal" fits better. At least for something like Cube Explorer, when we don't intentionally prevent short lengths. When we do it intentionally like that, it really is a feature, though I wish we had a nice concise term for that as well (neither sub-optimal nor near-optimal really describe it well).

To clarify: I didn't invent the term "near-optimal" and I'm not the only one who has been using it, I just want to popularize it because I think most people aren't even aware of it and don't really think about what they're saying when they say "sub-optimal". I believe the first time I saw "near-optimal" was from Herbert Kociemba, and I've seen at least Tomas Rokicki and Bruce Norskog use it as well.

Herbert:
"The Two-Phase-Algorithm gives near optimal solutions"
Tomas:
"Kociemba extended this algorithm for another purpose: to quickly find near-optimal solutions"
"[Kociemba] has found that in practice nearly optimal solutions are found very quickly"
"Kociemba’s solver solves an arbitrary position to find a near-optimal solution"
Bruce:
"doesn't do especially well at finding near optimal solutions overall."

 

[aronpm]

After reading this, I'm inclined to agree. And yay, I was used as an example

 

[Kirjava]

For 2x2x2, non-near-optimal sub-optimal is preferred to near-optimal.

 

[Stefan]

Of course, there's also another naming option that was recently suggested to me: simply call the non-optimal ones "random state".

Yeah, I think that's better, as that is really what you want to brag about there . At least in a feature list like yours and Aron's (hi Aron) where the sub-optimality wasn't a positive intentional feature.

Or similarly, "efficient random state", which suggests few moves without suggesting anything about optimality.

It doesn't necessarily suggest few moves, "efficient" can also suggest low computation power. At least unless you say "efficient scrambles", which isn't what you/Aron did:

Aron: "Suboptimal random state 3x3 - new default 3x3 scrambler"
You: "added suboptimal random state 3x3x3"

And if it did suggest few moves, I don't see how that isn't suggesting anything about optimality. Feels very similar to "near-optimal" for me, and the latter has the advantage of being an established term already.

 

[macky]

[edit] I misunderstood Stefan's goal in the original post, so you can safely ignore this post.

__

One major gripe I have with "near-optimal" is that it may be interpreted to include optimal. You could argue that the point is really sub-optimality, though I also share Stefan's reaction against what appears to be a negative term.

Feels very similar to "near-optimal" for me, and the latter has the advantage of being an established term already.

Established, but is it used the same way? Did Kociemba, Rockicki, and Bruce ever use "near-optimal" when sub-optimality was intentional? I think in their uses, "near-optimal" also includes optimal.

 

[Lucas Garron]

Is a solver than always produces 21-move scrambles for a 3x3x3 position near-optimal? (i.e. is the solutions still near-optimal if God's algorithm may be 10 moves and you just don't know it?)

What about 20?

(Chen Shuang's 3x3x3 solver in Mark 2 always finds a solution in 21 or fewer moves. It can find one in \( \leq[\math] 20 moves almost as fast.) \)

 

[Stefan]

One major gripe I have with "near-optimal" is that it may be interpreted to include optimal.

Well, when something is optimal, it really shouldn't be called "near-optimal" in the first place. It should be called "optimal".

Can you give an example of what you mean? I can only imagine you mean cases where for example Cube Explorer (*) happens to find an optimal solution, but then while that solution is optimal, Cube Explorer in general isn't, so I'd say calling Cube Explorer near-optimal is still alright. It is near-optimal-but-not-optimal in most cases. Plus the real point of saying "near" is that it's "not far away", so I don't even really mind including optimal. Like when I'm at a party and ask someone "Do you live nearby?" and it's the host living right there, I'd expect a "Yes" rather than a "No". "Sub" on the other hand not only doesn't have the "not far away" connotation, but also really doesn't include optimal. At least in my opinion.

(*) Always meaning the two-phase algorithm not asked for optimal solutions

You could argue that the point is really sub-optimality

Yes, there are situations where that's the point, but frequently it's not.

Established, but is it used the same way? Did Kociemba, Rockicki, and Bruce ever use "near-optimal" when sub-optimality was intentional? I think in their uses, "near-optimal" also includes optimal.

Yes, I also think they "include optimal" in the sense I just described and find alright.

 

[Stefan]

Is a solver than always produces 21-move scrambles for a 3x3x3 position near-optimal? (i.e. is the solutions still near-optimal if God's algorithm may be 10 moves and you just don't know it?)

Same argument as for optimal solutions: Those are a small minority of the cases. In general, i.e., in most cases, it really is near-optimal. Also, the reason we like the length (and why we would mention it for example in a feature list) is that it doesn't produce long scrambles like the old 25 moves or longer. Hmm, maybe "short" would be a good alternative term. How does "short random state scrambles" sound?

 

[macky]

Oh, Stefan, I misunderstood your first post. Yes, I agree (qqwref's and Lucas's objection notwithstanding) that "near-optimal" is better than "sub-optimal" in all cases except where sub-optimality is the point (e.g. 2x2, Pyraminx).

How does "short random state scrambles" sound?

And I like this more than "near-optimal."