10.3 Les bases de patterns additives
10.3 Les bases de patterns additives
183
On peut faire mieux que prendre le maximum des distances précalculées. Si deux
bases de patterns ne contiennent que des pièces différentes, on peut additionner les distances (33].
Exercice : Trouver une heuristique additive simple pour le Taquin 4x4.
10.4 La compression de bases de patterns
Lorsqu' une base de patterns a une taille trop grande pour être contenue en mémoire
vive, on peut la compresser (34]. Pour cela, on choisit un sous ensemble des pièces de la
base la plus grande, et on calcule pour chaque configuration du sous ensemble la distance
minimale sur toutes les configurations du sur ensemble contenant la configuration du sous
ensemble. Par exemple, si on a calculé toutes les distances des 9 premières pièces du
Taquin, on calcule pour chaque configuration de 7 pièces la distance minimum sur toutes
les configurations à 9 pièces qui contiennent la configuration à 7 pièces. Cette distance
compressée est plus grande que la distance de la base de 7 pièces et donne donc une
meilleur heuristique admissible.
10.5 Sokoban
Sokoban est un jeu a un joueur, amusant mais difficile. Le principe est qu'un robot
cherche à ranger des caisses dans un labyrinthe en les poussant vers des emplacements
cible. Il n 'est possible de pousser qu' une seule caisse à la fois. Si deux caisses sont voisines au bord cela forme un interblocage, aucune des deux caisses ne peut plus être déplacée et le problème devient insoluble. Il existe une multitude d' autres interblocages. Une
façon de se prémunir contre les interblocages d' un labyrinthe et de les énumérer avec de
l ' analyse rétrograde et de construire une base de patterns des interblocages spécifiques à
un labyrinthe (27]. Détecter ainsi les interblocages permet à IDA* d'être plus efficace en
arrêtant la recherche dès qu' une position est prouvée insoluble.
10.6 La vie et la mort au jeu de Go
Avec l ' analyse rétrograde, on peut aussi construire des bases de patterns pour les jeux
à deux joueurs. Ainsi pour accélérer la résolution de problèmes de vie et de mort au jeu de
Go, on peut engendrer des patterns relativement petits répertoriant les positions vivantes
plusieurs coups à l ' avance ( 14, 19, 23]. Ces patterns permettent d' accélérer notablement
la résolution de problèmes de vie et de mort.
10.3 Les bases de patterns additives
183
On peut faire mieux que prendre le maximum des distances précalculées. Si deux
bases de patterns ne contiennent que des pièces différentes, on peut additionner les distances (33].
Exercice : Trouver une heuristique additive simple pour le Taquin 4x4.
10.4 La compression de bases de patterns
Lorsqu' une base de patterns a une taille trop grande pour être contenue en mémoire
vive, on peut la compresser (34]. Pour cela, on choisit un sous ensemble des pièces de la
base la plus grande, et on calcule pour chaque configuration du sous ensemble la distance
minimale sur toutes les configurations du sur ensemble contenant la configuration du sous
ensemble. Par exemple, si on a calculé toutes les distances des 9 premières pièces du
Taquin, on calcule pour chaque configuration de 7 pièces la distance minimum sur toutes
les configurations à 9 pièces qui contiennent la configuration à 7 pièces. Cette distance
compressée est plus grande que la distance de la base de 7 pièces et donne donc une
meilleur heuristique admissible.
10.5 Sokoban
Sokoban est un jeu a un joueur, amusant mais difficile. Le principe est qu'un robot
cherche à ranger des caisses dans un labyrinthe en les poussant vers des emplacements
cible. Il n 'est possible de pousser qu' une seule caisse à la fois. Si deux caisses sont voisines au bord cela forme un interblocage, aucune des deux caisses ne peut plus être déplacée et le problème devient insoluble. Il existe une multitude d' autres interblocages. Une
façon de se prémunir contre les interblocages d' un labyrinthe et de les énumérer avec de
l ' analyse rétrograde et de construire une base de patterns des interblocages spécifiques à
un labyrinthe (27]. Détecter ainsi les interblocages permet à IDA* d'être plus efficace en
arrêtant la recherche dès qu' une position est prouvée insoluble.
10.6 La vie et la mort au jeu de Go
Avec l ' analyse rétrograde, on peut aussi construire des bases de patterns pour les jeux
à deux joueurs. Ainsi pour accélérer la résolution de problèmes de vie et de mort au jeu de
Go, on peut engendrer des patterns relativement petits répertoriant les positions vivantes
plusieurs coups à l ' avance ( 14, 19, 23]. Ces patterns permettent d' accélérer notablement
la résolution de problèmes de vie et de mort.