Le jeu le plus court de Halma à 2 joueurs

19

Aux échecs, il est possible que le jeu se termine après 4 coups (2 chacun) avec un mat du fou .

Votre objectif est de trouver le Fool's Mate of Halma : le jeu à 2 joueurs de Halma qui minimise le nombre de tours joués.

Il y a plus de 10 56 états de carte, et j'ai vu le facteur de branchement dépasser 1000, donc il est probable que personne ne trouvera la solution optimale. Au lieu de cela, vous essayez de trouver la meilleure solution possible.

Vous devez soumettre une liste de mouvements et tout code que vous avez utilisé pour générer ces mouvements.

Explication du jeu

Halma est similaire aux Dames chinoises, mais a joué sur un plateau carré 16 * 16.

Au départ, le tableau ressemble à ceci:

Planche de départ

Le but du jeu est de déplacer toutes vos pièces vers les positions de départ des pièces de votre adversaire.

Au tour d'un joueur, il / elle peut:

  • Passer le virage

  • Déplacez une de ses pièces dans un espace vide adjacent. Les espaces adjacents comprennent des diagonales.

  • Prenez l'une de ses pièces et procédez comme suit un nombre illimité de fois: faites sauter la pièce par-dessus une pièce adjacente, en la posant sur l'espace opposé à la pièce sautée.

Voici un exemple pour illustrer le 2ème type de mouvement.

Sauts

Règles

Soumettez une liste des mouvements légaux qui entraînent la fin du jeu.

Soumettez tout code que vous avez utilisé pour générer la liste.

Si vous obtenez un meilleur résultat à partir du code de quelqu'un d'autre, publiez le résultat dans un commentaire ou modifiez sa publication avec les nouveaux résultats.

Chaque mouvement doit être soit Nonepour passer le tour, soit (x1,y1,x2,y2)pour déplacer une pièce, où (x1,y1)sont les coordonnées de la pièce à déplacer et (x2,y2)sont la destination de cette pièce (pour les mouvements de saut, ignorez les coordonnées intermédiaires). Les coordonnées commencent au (0,0)coin supérieur gauche. les coordonnées x augmentent vers la droite, les coordonnées y augmentent vers le bas. Les mouvements doivent être séparés par des retours à la ligne.

Vous pouvez utiliser ce script python pour vérifier vos déplacements. Utilisez python halma_verify.py < filepour vérifier les emménagements file.

La liste la plus courte l'emporte.

boîte en carton
la source
6
quelques discussions techniques sur les mouvements et une solution en 47 mouvements: arxiv.org/pdf/0803.1245.pdf
SeanC

Réponses: