Rush Hour
Mémoire de fin d'études 2004-2005 de Samuel Hiard
Présentation du jeu
Le Rush Hour est un jeu de réflexion solitaire où l'aire de jeu a une taille de 6 cases sur 6.
On peut y placer, au maximum 12 voitures, qui occupent 2 cases adjacentes, et 4 camions, qui occupent
3 cases adjacentes et formant une ligne droite. Une voiture se distingue des autres: la voiture rouge.
Elle doit obligatoirement se situer sur l'aire de jeu, car le but de ce jeu est de faire sortir la
voiture rouge en n'effectuant que des déplacements légaux sur les véhicules, sachant qu'un déplacement
légal est un déplacement qui fait avancer ou reculer le véhicule sur l'axe dans lequel il a été placé.
Objectif de mon travail de fin d'études
L'objectif de mon travail de fin d'études a été, dans un premier temps, de définir la notion de difficulté
pour une configuration du Rush Hour et, dans un second temps, de concevoir un logiciel permettant de
trouver une configuration difficile à résoudre par un joueur humain ou, de façon optimale, la configuration
la plus difficile possible pour ce jeu.
Méthode de résolution
Ce problème n'est pas évident à résoudre, même si de premier abord cela semble le cas. N'oubliez pas que
le jeu d'échecs ne comporte que 8 cases sur 8 et que, pourtant, il a fallu des années avant d'obtenir un
logiciel qui a battu le plus grand maître des échecs. Fort heureusement, même si le problème est de taille,
il n'est pas aussi difficile à résoudre que celui de la conception de Deep Blue.
Un programmeur débutant obtient assez rapidement une version correcte du programme, dans le sens où, si
on laisse le programme s'exécuter assez longtemps, il finira par trouver la solution. Evidemment, ce temps
approchera fort probablement de la dizaine d'années. La plus grande partie de mon travail a été d'optimiser
le processus, pour finalement obtenir une version qui donne un résultat en approximativement 2 semaines, ce
qui est long, mais c'est un prix que j'ai accepté de payer.
Le problème est qu'il existe approximativement 36 milliards de configurations fournissant une solution.
Calculer et parcourir ces milliards de configurations ne pose (plus ou moins) pas trop de problèmes, mais
le plus gros problème est de les stocker en mémoire. Considérant qu'il faut environ 16 octets pour conserver
l'information d'une configuration, cela signifie qu'il faut disposer d'une mémoire d'environ 500 Giga-octets.
Grâce à mon étude poussée du problème, j'ai pu réduire cette exigence à 2 Giga-octets, ce qui n'est pas
négligeable. Au total, seulement 300 millions de configurations ont été stockées en mémoire (et sur disque).
Téléchargements
Mémoire: Mon mémoire, en format doc (pas de pdf, désolé)
Résumé: Un résumé, en 20 lignes, de mon travail de fin d'études (toujours pas de pdf)
Code source d'Analyser: Le code source de la partie "analyse des configurations"
Code source de CombMaker: Le code source de la partie "génération des configurations"
ATTENTION: Je décline toute responsablilité pour les dégats logiciels ou matériels
que pourrait générer l'exécution de ce programme. Ce programme utilise des chemins de répertoire spécifiés explicitement
dans le code source. N'exécutez ce programme que si vous êtes SURS ET CERTAINS qu'il ne pourra pas endommager votre système ou vos
données de quelque façon que ce soit.
Retour à ma page personnelle
Dernière modification: 19 avril 2011
Responsable: Samuel HIARD
Mail: S.Hiard@ulg.ac.be
