Fewest Moves World Record

[la-chose]

Au Czech Open : Istvan Kocza - 22 moves
Scramble: D' R2 D L2 F2 D L R2 B' D2 U2 L2 D F' L2 U L2 F U
Solution :
Xcross verte : F D' F L' B R2
2ème F2L : R B R' B2 D B D' (12 mouvement avec annulation de R2 R)

et d'ici, il aurait du faire : U' B U' L U2 L' (18 mouvements au total soit 1 move de moins que le mélange !)

mais il a fait quelque chose de ce genre là : U2 B L U' L F' L' F U' L' (22 moves au total)


(Ceci est une traduction de ce post)

[TMOY]

Et il ne s'est pas mis à sauter partout comme l'avait fait Jimmy, c'est moins drôle

[cyril]

et d'ici, il aurait du faire : U' B U' L U2 L' (18 mouvements au total soit 1 move de moins que le mélange !)

Le mélange en fewest moves n'est-il pas justement censé être optimalisé via CubeExplorer ?

[rafoo]

Je ne vois rien de la sorte dans le règlement ; Cube Explorer n'est pas un solveur optimal et c'est souvent assez long de lui demander de résoudre un cube de manière optimale.

[deadalnix]

Le mélange en fewest moves n'est-il pas justement censé être optimalisé via CubeExplorer ?

Non, cube explorer trouve une solution pour ledit mélange, mais pas forcément optimale. La contrainte de base du logiciel est < 25 mvts.

[rafoo]

Oui enfin ce qui compte surtout c'est le temps qu'il passe à chercher. La limite de longueur ne sert que pour le premier résultat rendu par Cube Explorer, après quoi il jettera de toute façon toute solution plus longue. Par contre il lui arrive d'améliorer une solution au bout de plusieurs minutes.

Dans tous les cas, si on veut une solution optimale, on utilise pas Cube Explorer mais un optimal solver.

[cyril]

OK, je pensais que Cube Explorer était optimal pour un nombre de solutions qui tend tellement bien vers (42+1)E18 (moyennant quelques secondes de calcul) qu'on le considérait comme optimal tout court.

En tous les cas, jolie performance d'Istvan !

[deadalnix]

Dans tous les cas, si on veut une solution optimale, on utilise pas Cube Explorer mais un optimal solver.

Cube explorer s'en sort bien à ce jeu la quand même.

[rafoo]

Dernier paragraphe de http://kociemba.org/math/optimal.htm, Kociemba explique qu'il a un solveur optimal 5 fois plus rapide (en tout cas dans ma version de Cube Explorer, quand on demande une solution optimale il utilise cet algorithme "standard" ; ça m'étonnerait qu'il ait changé ça vu le coût en mémoire) et ici, encore au dernier paragraphe, il rappelle qu'il perd des coups en phase 2. Et il ne prétend pas avoir le meilleur solveur optimal ! (je crois qu'une étude comparative des solveurs optimaux est passée sur Domain of the cube qui donnait celui de Rokicki plus rapide mais j'ai pas envie de chercher maintenant).

En général, Cube Explorer s'approche à quelques coups de la solutions optimale si on l'arrête assez vite : "This algorithm quickly provides a solving sequence of 19 moves on average, usually only one or two moves more than the perfect solution.". Mais il est vrai qu'en général un solveur optimal passe beaucoup plus de temps à prouver l'optimalité de la séquence qu'à trouver la séquence.

[Arsonist]

Mais il est vrai qu'en général un solveur optimal passe beaucoup plus de temps à prouver l'optimalité de la séquence qu'à trouver la séquence.

Et justement, comment, en pratique, on prouve l'optimalité d'une séquence?

[deadalnix]

On prouve pas que la séquence est optimal après coup. On trouve la séquence d'un telle manière qu'elle le soit. Par exemple en faisant du Iterrative deepening - depth first A*.