Circus Maximus est-il soluble ?

Question

Circus Maximus est un jeu de course de chars dans lequel les joueurs placent leurs 3 chars dans la case de départ, puis font la course à tour de rôle sur le parcours ovale pour être le premier à placer ses 3 chars sur les cases d'arrivée,

Puisqu'il n'y a que 15 emplacements de départ, et qu'à chaque tour, les deux joueurs n'ont accès qu'à une carte de déplacement 1, 2, 3, 4 ou 5 en ligne droite (ou à une carte de tangage pour changer de direction), mais doivent tout de même réserver une carte pour chaque char...

Ce jeu ne devrait-il pas pouvoir être résolu au moins comme un jeu à 2 joueurs avec un temps de calcul minimal ? Par "soluble", j'entends qu'une solution par force brute peut être obtenue avec le matériel PC disponible pour une personne moyenne, et qu'il existe une séquence de coups qui, si elle est suivie, permet de gagner.

Les règles peuvent être trouvées aquí .

Answer 1

Je pense que vous avez raison de dire qu'en principe, et peut-être même en pratique, une IA optimale pourrait être construite pour ce jeu afin de déterminer qui peut gagner à partir de la position de départ, bien que cela nécessiterait probablement plus de puissance de calcul que ce que vous êtes susceptible d'avoir à portée de main. La meilleure approche pour résoudre par force brute un jeu comme celui-ci est proche de ce que l'utilisateur 1873 suggère dans les commentaires : plutôt que de considérer toutes les lignes de jeu, il suffit de considérer toutes les positions du plateau et de déterminer la valeur de chaque position du plateau. C'est l'approche généralement adoptée pour résoudre les fins de parties d'échecs ; bien que cet échiquier ait beaucoup plus de cases (j'en compte environ 200, bien que le diagramme ne soit pas très clair) que l'échiquier moyen, le fait que toutes les pièces soient identiques ici aide un peu, et donc cela peut être à portée de main ; notez que les fins de parties d'échecs avec 6 et 7 pièces ont été résolues depuis un certain temps maintenant. Il y a environ (200 choisir 3) = 200*199*198/6 = 1313400 positions pour les chariots d'une équipe, et donc environ 1,7 trillion de positions pour tous les chariots qui devraient être évalués.

Notez que vous n'avez pas besoin de construire explicitement une "matrice de déplacement" de 1,7 trillion x 1,7 trillion d'entrées. serait être trop grande. Au lieu de cela, le jeu pourrait être résolu par une sorte de retour en arrière : d'abord, identifier les positions qui sont clairement gagnées, et quelle personne les gagne. Ensuite, il faut revenir en arrière, c'est-à-dire jouer un tour en sens inverse, pour identifier toutes les positions à partir desquelles les positions gagnées peuvent être atteintes, puis évaluer chacune de ces positions à l'aide d'un court arbre de déplacement pour ce tour afin de déterminer lesquelles de ces positions conduisent à une victoire forcée par un joueur ou l'autre. Vous avez besoin d'un "arbre de mouvement" ici parce qu'un tour n'est pas un simple mouvement, mais consiste plutôt en de multiples mouvements imbriqués des deux joueurs. Une fois que ce premier tour de retour en arrière a été effectué, un autre tour peut être traité de la même manière ; les positions peuvent être continuellement ajoutées à une file d'attente pour évaluation, avec un tas de nouvelles positions "one-move-back" ajoutées chaque fois que la file d'attente se vide.

Malheureusement, le problème se situe au niveau de l'arbre des déplacements ; le facteur de ramification est suffisamment important pour qu'une solution explicite ne soit pas pratique (mais peut-être pas irréalisable pour quelqu'un disposant d'une puissance de calcul suffisante). Un "arbre de mouvement" consiste en une affectation des cartes 1-5 à 3 chars (plus la possibilité de jeter des cartes) pour chaque joueur, plus un certain entrelacement ; cela donne à peu près (sans tenir compte des cartes jetées) 75 coups à la première branche (3 chars différents qui peuvent être déplacés, fois 10 (piocher 3 cartes parmi 5) + 10 (piocher 2 cartes parmi 5) + 5 (piocher 1 carte parmi 5) coups possibles pour le char pioché) et jusqu'à 28 coups à la deuxième branche (2 chars qui peuvent être déplacés, fois 4 (piocher 3 cartes parmi 4) + 6 (piocher 2 cartes parmi 4) + 4 (piocher 1 carte parmi 4) coups possibles pour le char pioché). Puisque les cartes peuvent être jetées pour des tours, nous allons les réduire à 100 et 50, et appeler cela 10 mouvements à la branche inférieure ; cela donne environ 50 000 mouvements pour chaque joueur qui doivent être pris en compte dans l'arbre des mouvements, ou environ 2 milliards de branches possibles à examiner sur l'arbre des mouvements. Je soupçonne que ce chiffre est fortement surestimé - peut-être d'un facteur de 100 environ - mais une analyse plus minutieuse serait beaucoup plus délicate à manier ici. Même ainsi, je suppose qu'il y a plusieurs millions de façons possibles de jouer chaque tour, et même si un élagage alpha-bêta standard (en utilisant des valeurs de position établies) réduira ce nombre, il est probable qu'il faudra encore beaucoup de travail à chacun des 1,7 trillion de nœuds pour établir une valeur.

Étant donné que les positions peuvent devoir être évaluées plusieurs fois (si la première fois détermine qu'elles ne peuvent pas encore être entièrement résolues), le travail global effectué est susceptible d'être de l'ordre de plusieurs exaflops (c'est-à-dire des quintillions d'opérations au total) de calcul. Il s'agit d'un lot d'opérations - mais notez que vous pourriez avoir accès à une puissance de calcul de l'ordre du pétaflop/seconde, et ainsi effectuer la résolution complète en quelques milliers de secondes - c'est-à-dire quelques heures (voire quelques jours). Le plus gros goulot d'étranglement sera probablement la vitesse d'accès à la base de données des valeurs des positions, puisque quelque chose de l'ordre d'un téraoctet (la taille approximative de cette base de données) est encore un peu trop grand pour être gardé en mémoire à ce stade ; il faudrait qu'il soit soigneusement conçu pour garder autant que possible en mémoire et pour être très intelligent dans ses accès au disque.

Si le jeu était un peu plus connu, il ferait un excellent projet de fin d'études pour un programmeur (ou une équipe) de superordinateur suffisamment motivé.

Answer 2

En quelque sorte.

Un ordinateur pourrait forcer le mouvement optimal à chaque tour en se basant sur les décisions prises par l'adversaire. On pourrait même construire une matrice (énorme) de tous les coups possibles pour une partie. Mais il n'y a pas de chemin unique de choix d'un joueur qui garantirait une victoire. Votre adversaire peut faire des choix qui contrent efficacement les vôtres et lui donnent l'avantage et vice-versa.

Mais il existe un ensemble de règles suffisamment limité pour qu'il soit possible de créer une matrice de toutes les solutions gagnantes dans une base de données moderne et, à partir de cette base de données, de renvoyer rapidement la stratégie la plus efficace pour contrer le dernier coup de votre adversaire. Ce programme ne serait pas trivial à écrire, mais les règles sont suffisamment simples pour que cela ne soit pas déraisonnable.