Morpion solitaire parallèle La recherche est maintenant stoppée, après quelques 10 mille milliards de positions cherchées, à partir du coup 60. Pas de meilleure séquence trouvée. Je mettrai sans doute ici des résultats détaillés bientôt.

---------------------

Je fais tourner actuellement une recherche parallèle pour essayer de battre le record, qui est actuellement de 170 croix. Vous pouvez participer en faisant tourner le programme suivant. C'est un code expérimental. Il est écrit pour linux. Je sais qu'il fonctionne plus ou moins bien sur d'autres systèmes unix (il y a un bug sur les Suns).

Ce programme se compose d'un client et d'un serveur. À la réception d'une tache, le client lance une recherche en profondeur d'abord à partir de la position donnée. À partir d'un certain nombre de noeuds (par défaut 10^9), il arrête la recherche et renvoie des sous-taches au serveur. Si il trouve une partie de longueur supérieure à 170, il envoie la partie au serveur (ça ne c'est encore jamais produit). Le client envoie également quelques statistiques pour chaque tache complétée.

Télécharger : msp-0.11.tgz

Le programme est configuré pour se connecter automatiquement à un ordinateur de mon labo où un serveur devrait tourner.

Le morpion solitaire a la particularité que les transpositions (2 séquences différentes menant à la même position) peuvent être détectées rapidement, sans besoin de stocker les noeuds déjà traversés en mémoire.

La stratégie de recherche est la suivante : on cherche à tester l'optimalité de la meilleure partie connue pour le plus grand nombre de coups possible en partant de la fin. Il existe en fait plusieurs parties qui se partagent le record ; j'ai choisi celle de Denis Excoffier . On fait donc une recherche à partir du coup 169, puis 168, 167, etc. Le programme est conçu pour ne pas rechercher les noeuds déjà parcourus quand la profondeur de départ diminue.

Statistiques .

Liens:

Page principale