182
Bases de patterns
Exercice : Quelle est la taille de la base de patterns qu' on va engendrer ?
Exercice : É crire un algorithme qui permet d' engendrer cette base de patterns. É crire
tout d' abord les variables nécessaires. On veut aussi une fonction qui code une position,
c 'est à dire qui fasse une bijection entre entiers et positions. É crire ensuite un algorithme
qui engendre toutes les configurations possibles et qui teste tous les coups possibles de
chaque configuration pour trouver si la configuration est à une distance donnée. É crire
ensuite la fonction principale d' analyse rétrograde.
10.2 Le Rubik's cube
Dans son article de 1985 [53), R. Korf donne une méthode qui permet à un programme
d' apprendre à résoudre presque instantanément des problèmes de Rubik's Cube. Pour cela
son programme apprend des macro-coups qui échangent des cubes à certaines positions
sans changer la configuration des autres cubes. Le programme résout instantanément après
apprentissage tous les problèmes de Rubik's Cube en utilisant en moyenne 85 coups.
Un problème beaucoup plus difficile est de trouver des solutions optimales au Rubik's
Cube. Une solution optimale est la plus petite séquence de coups permettant de résoudre
un cube. La recherche de solutions optimales au Rubik's Cube est un problème résoluble
par IDA * . On peut pour cela utiliser des bases de données de patterns afin de mieux
évaluer la fonction h [56).
Par exemple, On peut créer des patterns qui ne contiennent que les 8 cubes de coins,
la position et l ' orientation du dernier cube est déterminée par la position et l 'orientation
des cubes précédents.
Exercice : Combien y a-t-il de combinaisons possibles des 8 cubes de coin ?
On peut énumérer ces patterns dans une base de données et leur associer le nombre de
coups nécessaires pour atteindre la position finale. Le nombre de coups varie de 0 à 11,
on utilise donc 4 bits pour stocker un nombre, la table utilise alors 42 Mo de mémoire.
La valeur moyenne de h pour cette table est de 8.764 comparée a 5.5 pour la distance de
Manhattan.
Exercice : Combien y a-t-il de combinaisons possibles pour des patterns composés de
6 des 12 cubes de bord ?
Pour utiliser ces deux heuristiques à la fois, la seule façon de faire est de prendre le
maximum des deux pour h. La combinaison d'IDA * et des bases de données de patterns
permet de résoudre optimalement pratiquement tous les problèmes de Rubik's cube. Sans
les bases de données de patterns la résolution est beaucoup plus lente.
Bases de patterns
Exercice : Quelle est la taille de la base de patterns qu' on va engendrer ?
Exercice : É crire un algorithme qui permet d' engendrer cette base de patterns. É crire
tout d' abord les variables nécessaires. On veut aussi une fonction qui code une position,
c 'est à dire qui fasse une bijection entre entiers et positions. É crire ensuite un algorithme
qui engendre toutes les configurations possibles et qui teste tous les coups possibles de
chaque configuration pour trouver si la configuration est à une distance donnée. É crire
ensuite la fonction principale d' analyse rétrograde.
10.2 Le Rubik's cube
Dans son article de 1985 [53), R. Korf donne une méthode qui permet à un programme
d' apprendre à résoudre presque instantanément des problèmes de Rubik's Cube. Pour cela
son programme apprend des macro-coups qui échangent des cubes à certaines positions
sans changer la configuration des autres cubes. Le programme résout instantanément après
apprentissage tous les problèmes de Rubik's Cube en utilisant en moyenne 85 coups.
Un problème beaucoup plus difficile est de trouver des solutions optimales au Rubik's
Cube. Une solution optimale est la plus petite séquence de coups permettant de résoudre
un cube. La recherche de solutions optimales au Rubik's Cube est un problème résoluble
par IDA * . On peut pour cela utiliser des bases de données de patterns afin de mieux
évaluer la fonction h [56).
Par exemple, On peut créer des patterns qui ne contiennent que les 8 cubes de coins,
la position et l ' orientation du dernier cube est déterminée par la position et l 'orientation
des cubes précédents.
Exercice : Combien y a-t-il de combinaisons possibles des 8 cubes de coin ?
On peut énumérer ces patterns dans une base de données et leur associer le nombre de
coups nécessaires pour atteindre la position finale. Le nombre de coups varie de 0 à 11,
on utilise donc 4 bits pour stocker un nombre, la table utilise alors 42 Mo de mémoire.
La valeur moyenne de h pour cette table est de 8.764 comparée a 5.5 pour la distance de
Manhattan.
Exercice : Combien y a-t-il de combinaisons possibles pour des patterns composés de
6 des 12 cubes de bord ?
Pour utiliser ces deux heuristiques à la fois, la seule façon de faire est de prendre le
maximum des deux pour h. La combinaison d'IDA * et des bases de données de patterns
permet de résoudre optimalement pratiquement tous les problèmes de Rubik's cube. Sans
les bases de données de patterns la résolution est beaucoup plus lente.