Recherche en multitâche de la solution la plus courte d'un Rubik's Cube
On trouve sur Internet des programmes calculant la ou les solutions les plus
courtes d'un Rubik's Cube (3*3*3), le plus court se mesurant en termes de nombre
de mouvements quart de tours de faces. Mais dès que l'on s'attaque à un Cube
particulièrement embrouillé, ces programmes sont très, très gourmands en temps
de calcul. Par exemple, même en choisissant le programme le plus optimisé,
l'extraction de toutes les solutions du SuperFlip peut nécessiter deux jours
pour un PC moyen ! les solutions ayant un minimum de 24 mouvements quart de
tours (24q). Pour mémoire, le SuperFlip est l'une des figures mythiques des
amateurs de Rubik's Cube où l'on a fait tourner toutes les arrêtes d'un quart
de tour sans rien changer d'autre !
Pour réduire ce temps de calcul, la solution informatique est de répartir ces
opérations sur plusieurs processeurs et de les conduire ainsi en parallèle. Car
c'est une des caractéristiques des PC actuels que de disposer de plusieurs
processeurs ; le miens, pourtant pas de première jeunesse, en possède quatre. Je
propose donc ici une version multiprocesseurs du fameux algorithme
« Optisolver ». Avec mon PC, cette nouvelle version a divisé par quatre les
temps de résolution, ce qui est appréciable vu les durées en cause. J'utilise
les 'briques' déjà développées dans mon programme RubixCube déjà présenté sur
ce site (
http://codes-sources.commentcamarche.net/source/51633-rubix-cube).
Toute la nouveauté est contenue dans les fichiers « QSolverMP.cpp » et
« QSolverMP.h ». L'essentiel du problème consistant à déterminer avec une bonne
approximation le nombre de cycles nécessaires à l'opération puis ensuite de
répartir sur chaque processeur une part de calcul équivalente.
La Classe interne « CMv » assure ce comptage en reprenant les règles de
parcourt de l'arbre de résolution du programme d'origine. Les réductions dues
aux symétries du Cube sont aussi prises en compte. Sans tenir compte des
symétries, le premier niveau de l'arbre possède 12 noeuds c'est à dire un
mouvement positif par face et son pendant négatif (6 * 2). Le deuxième niveau
en possède 114, 30 mouvements redondants ou nuls étant éliminés des 12*12
prévisibles (ex : U2 et U'2 ou U, U'). La classe « CMv » détermine ainsi le
nombre de noeuds au niveau 4 (10_119 noeuds sans symétries). Pour trouver les
solutions, le programme passe obligatoirement par ces noeuds, définissant ainsi
les branches principales de l'arbre - Un arbre pouvant avoir jusqu'à 24, 25
niveaux et un nombre impressionnant de branches et de noeuds finaux (ce qui
explique les temps de calcul).
Le SuperFlip déjà cité plus haut, compte tenu de ses 48 symétries, ne possède
que 260 noeuds au niveau 4 et 4_775_431_656 au niveau 24 où se trouvent ses
166 solutions primaires, développables en 15_936 solutions différentes. En
effet, les symétries combinées à la propriété de réversibilité de cette figure
permettent de composer 96 formes différentes à partir d'une seule solution
primaire. Cette caractéristique n'est pas toujours aussi favorable car dans
d'autres figures, les solutions obtenues sont redondantes.
La procédure
« BYTE CMv::MultiProcess(BYTE nbProc, DWORD allowed[], int &totalTics) »
utilise ce principe pour affecter un quota à chaque processeur en déterminant
un cycle début et un cycle fin. De même, la procédure
« void CMv::progressCount(WORD minMoves, WORD maxMoves, int *pCount) »
détermine l'avancement du travail en comptabilisant les noeuds déjà parcourus et
permet d'afficher un pourcentage pour faire patienter l'utilisateur.
La procédure
« bool SearchNode::isNotAvailable( SearchNode *pSn, DWORD allowed,
int *pCount) const »
placée dans la boucle de résolution indique les cycles qui ne doivent pas être
exécutés par cette tâche (car hors des limites assignées).
Le traitement lui-même « OptiSolver » doit être modifié pour séparer
l'initialisations du calcul toujours exécutée en mono tâche
« void solveStart(const CKube &cube) »
et le parcourt de l'arbre de résolution qui lui est répartit sur les différents
processeurs « UINT solverLoop(Counters &count, DWORD allowed, int *pCount) ».
Les contingences du travail multitâche apparaissent ici :
- Les compteurs de statistiques cessent d'être une variable interne pour
pouvoir combiner les informations des différentes tâches.
- La variable « DWORD allowed » contient les numéros des cycles début et
fin alloués à chaque processeur. Ces numéros sont calculés par
« CMv::MultiProcess() » et sont exploités par la procédure
« SearchNode::isNotAvailable() ».
- Le pointeur « int *pCount » adresse la variable où est comptabilisée la
progression du travail de ce programme (information en pourcent).
Une attention particulière doit être portée aux variables partagées par des
tâches parallèles. Si elles sont seulement lues, il n'y a pas de problème, mais
quand elles sont modifiées (lues et écrites), il faut prévoir une exclusion
pour que les opérations ne puissent pas se marcher dessus et que les processeurs
travaillent successivement (« CCriticalSection csOut » et « CCriticalSection
csSync »). Pour attendre la fin du traitement, il serait bête de consommer du
temps CPU dans une boucle d'attente, un « CEvent evEnd » et un
« WaitForSingleObject(evEnd, INFINITE) » sont utilisés.
La mise en pratique de ce partage devient assez simple en créant des tâches,
une (un thread) par processeur, « UINT qsolverThread(LPVOID pParam) », chacune
devant parcourir la partie de l'arbre qui lui est assignée grâce à la procédure
« UINT solverLoop() ». Les premières tâches à terminer le travail s'arrêtent ;
la dernière, examine les résultats acquis (par tout le monde), et soit termine
le processus de calcul, ou soit boucle et relance les autres tâches en ajoutant
deux points supplémentaires à la profondeur de l'arbre. Le processus tourne
ainsi jusqu'à l'obtention du résultat souhaité. Une version simplifiée,
n'utilisant pas les threads, traite le cas où seulement un processeur est
disponible.
L'application se présente sous la forme d'un
«Dialog based MFC appWizard (exe) »
réalisé avec l'atelier Microsoft Visual cpp 6. Elle comporte une grande fenêtre
CEdit où s'affichent le résultat des calculs, dessous une nouvelle fenêtre
CEdit, plus petite, pour la ligne de commande, puis encore dessous, des
paramètres d'exécutions et des touches de lancement du processus et de fin. Le
premier paramètre indique le nombre de processeurs disponibles dans le système,
nombre qui peut être modifié pour essais avant une résolution. Le deuxième
paramètre permet de programmer la profondeur de la recherche :
- 0 pour arrêt à la première solution trouvée,
- 1 pour obtenir toutes les solutions longueur minimum,
- 2 à n pour ajouter les solutions possédant 2 ou 2 * (n - 1) mouvements
quart de tours en plus.
Il est à noter qu'un Cube avec un mélange donné possède des longueurs de
solutions (en quart de tours) toujours de valeur soit paires soit impaires. Par
exemple, un Cube avec une solution à 10q peut avoir trois solutions à 12q, rien
en 11q, ou pour un autre Cube, une solution à 15q puis 7 à 17q, rien en 14q. Si
l'on souhaite tester cette règle, il faut toutefois rester raisonnable avec
l'augmentation de la profondeur de recherche du fait du fameux temps de calcul
engendré. Un point de plus augmente l'arbre de deux niveaux et multiplie le
temps de calcul par 100 environ.
L'interface utilisateur de ce démonstrateur est plutôt spartiate, nécessitant
d'entrer la configuration du Cube à résoudre avec le clavier dans la fenêtre
CEdit ligne de commande et la présentation des résultats se fait seulement sous
la forme formules listées. Pour la définition du Cube, trois formats connus des
amateurs, sont acceptés :
- Le format position : L:OWGGORWGB F:YROGGOWRR R:BGRYRBBYG B:WRGOBWOWR...
- Le format Singmaster,
- Le format manoeuvre composé de la suite de mouvements à exécuter.
En retour, la ou les solutions sont fournies naturellement en format manoeuvre.
Il est possible de communiquer des informations, entrées ou sorties, avec
d'autres programmes par l'intermédiaire du presse papier. Mon programme
RubixCube, déjà cité, peut être utile pour coder des entrées ou visualiser des
sorties.
Cette nouvelle façon optimisée de résoudre sera incorporée dans mon programme
RubixCube lors de la prochaine mise à jour. Ce qui permettra de disposer
alors d'une interface plus évoluée.
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.