Analyser la complexité du jeu d'agression

L'agression est un jeu à deux joueurs où les joueurs placent des troupes et attaquent des territoires sur une carte représentée comme un graphe. Chaque joueur prend à tour de rôle pour mettre ses troupes sur des territoires vides jusqu'à ce qu'il n'en ait plus. Une fois que toutes les troupes sont placées, ils commencent à attaquer. Un joueur ne peut attaquer que s'il a plus de troupes adjacentes que l'ennemi dans un territoire. Le joueur avec le plus de territoires à la fin gagne, et en cas d'égalité, le joueur avec plus de troupes survivantes gagne.

Ce papier examine à quel point le jeu peut être complexe en considérant différentes dispositions de troupes, séquences d'attaque et types spécifiques de cartes. On a découvert qu'il est NP-complet de déterminer les meilleurs coups pour le premier joueur, ce qui signifie que c'est assez dur à résoudre même avec des approches directes. On a aussi regardé comment le jeu fonctionne spécifiquement quand la carte est organisée comme un appariement (une paire de sommets connectés) ou un cycle (une boucle de sommets connectés).

L'aggression a été créée en 1973 par le mathématicien Eric Solomon. Elle est apparue dans diverses ressources éducatives axées sur les mathématiques. Le jeu peut se jouer sur des cartes données ou des cartes dessinées par les joueurs. Les joueurs ont un nombre fixe de troupes à distribuer sur les territoires durant la première phase. Les troupes restent dans les territoires où elles sont placées et ne peuvent pas bouger. Si un joueur ne peut pas placer de troupes, il passe.

Une fois que les deux joueurs passent, ils commencent la Phase d'attaque. Le joueur qui a fini de placer ses troupes en premier attaque en premier. Les joueurs alternent les attaques sur les territoires ennemis selon la force de leurs troupes. Si un joueur réussit à attaquer et à éliminer toutes les troupes ennemies dans un territoire, ce territoire est alors considéré comme le sien. Le jeu continue jusqu'à ce qu'il n'y ait plus d'attaques possibles.

Dans notre étude, on catégorise l'agression comme un jeu combinatoire partisan. Cela signifie que c'est un jeu à tours où les deux joueurs ont une information complète sur l'état du jeu, et ils ne peuvent jouer qu'avec leurs propres troupes. On pense que ce jeu n'a pas été étudié auparavant pour son niveau de difficulté ou sa théorie des jeux.

Les cartes du jeu peuvent être vues comme des graphes. Les territoires représentent des nœuds, et les frontières entre eux représentent des connexions. Bien que les cartes correspondent généralement à des graphes planaires, cette étude examine divers types de graphes puisque les règles du jeu s'appliquent à tous.

Certaines structures de graphes facilitent les stratégies :

• Si tous les bords possibles sont présents (un graphe complet), les deux joueurs devraient placer toutes leurs troupes sur un nœud. Cela se traduit généralement par un match nul.
• Si le graphe est une étoile (un nœud central connecté à d'autres), les joueurs devraient aussi placer des troupes sur le nœud central, ce qui mènerait encore à un match nul.

Cependant, pour les appariements, chemins et Cycles, déterminer les résultats des joueurs devient compliqué. On a trouvé :

• Les joueurs peuvent faire match nul sur des appariements avec au plus deux bords.
• Les joueurs peuvent aussi faire match nul quand il y a autant de bords que de troupes.
• Le deuxième joueur peut gagner s'il y a au moins trois bords et que son nombre de troupes dépasse celui des bords de six ou plus.
• Pour les cycles de longueurs trois, quatre et cinq, les deux joueurs peuvent également faire match nul.

On a aussi créé une question connexe : Étant donné un graphe, des affectations de troupes pour les deux joueurs, et un ordre d'attaque pour le deuxième joueur, le premier joueur peut-il gagner ? On a découvert que même dans une version réduite du jeu, cela reste NP-complet, même pour des graphes bipartis.

D'autres jeux sur des graphes, comme cops et voleurs ou araignées avides, ont été examinés de manière plus approfondie, mais il semble que l'agression manque d'un corpus similaire.

#Mise en place du jeu

Dans l'agression, on a deux joueurs, Lata et Raj. Le jeu se déroule en deux phases : placement et attaque.

#Phase de placement

Dans cette phase, Lata et Raj prennent à tour de rôle pour placer leurs troupes sur les sommets du graphe. Lata joue toujours en premier. On note le nombre de troupes que Lata place sur un sommet comme une fonction, et de même pour Raj. Chaque joueur a un budget fixe de troupes pour le placement, et aucun des deux joueurs ne peut avoir de troupes sur le même sommet.

La phase de placement se termine lorsque les deux joueurs passent leur tour. Après cette phase, les joueurs passent à l'attaque.

#Phase d'attaque

Le joueur qui a fini de placer des troupes en premier commence la phase d'attaque. Pendant cette phase, les joueurs peuvent attaquer des sommets vulnérables, c'est-à-dire qu'ils ont des troupes dans des sommets voisins. L'objectif est de réduire le nombre de territoires contrôlés par l'adversaire.

Un joueur gagne en ayant plus de territoires après que toutes les attaques sont terminées. S'ils ont le même nombre de territoires, le joueur avec plus de troupes restantes gagne ; un match nul complet aboutit à un match nul.

#Question algorithme

On a formulé une question sur les Stratégies gagnantes dans le jeu. Étant donné un graphe, un placement de troupes, et une séquence d'attaques planifiées pour Raj, Lata peut-elle gagner le jeu ? Cette question mène à déterminer si Lata a une stratégie gagnante.

Pour prouver la difficulté de cette question, on a utilisé un problème NP-complet connu appelé le problème de la clique multicolore comme base pour une réduction. Si on peut transformer ce problème en notre question de jeu, cela démontre que notre question de jeu est également NP-complete.

#Stratégies gagnantes

Dans les scénarios où le graphe est une union disjointe de bords, Raj peut toujours faire match nul en plaçant des troupes aux extrémités opposées de n'importe quel bord où Lata place des troupes. Si Lata joue sur un bord, Raj peut placer des troupes à l'autre extrémité, s'assurant ainsi un match nul.

Quand il y a beaucoup de bords par rapport aux troupes, Lata a aussi une stratégie de match nul garantie. Par exemple, si Lata place des troupes sur un bord, Raj peut imiter ce placement à l'autre extrémité, menant à un équilibre des territoires.

Dans les cas avec un petit nombre de bords, Raj peut avoir une stratégie gagnante. Par exemple, dans un appariement de plus de deux bords et avec un nombre de troupes supérieur, Raj peut tirer parti de son avantage en troupes pour sécuriser plus de territoires et gagner.

#Cycles

Quand on considère les cycles, les stratégies peuvent aussi mener à des nuls ou à des victoires, selon la distribution des troupes. Pour les cycles de longueur trois, quatre ou cinq, les deux joueurs peuvent assurer un match nul grâce à un placement et une imitation de coups soignés.

#Exemple de stratégie de match nul pour les cycles

Dans un triangle (trois sommets), les joueurs peuvent placer leurs troupes sur des sommets disponibles de manière à ce que les attaques deviennent impossibles, ce qui mène à un match nul. Pour un cycle à quatre sommets, peu importe où un joueur commence, l'autre peut répondre efficacement jusqu'à atteindre un match nul.

#Considérations futures

L'analyse actuelle fournit une base solide pour comprendre l'agression, mais il reste encore beaucoup de questions sans réponse. Par exemple, que se passe-t-il dans des scénarios où le graphe est planaire ou a une structure d'arbre ? Comment la variante à une seule troupe du jeu change-t-elle les dynamiques ? Quel joueur émerge victorieux sur des chemins ou des cycles plus longs ?

On suggère aussi une nouvelle variante du jeu appelée Micro Agression, où les joueurs ne peuvent placer qu'une seule troupe par tour. Les premières découvertes indiquent qu'elle pose des défis différents et peut mener à de nouvelles stratégies.

Dans l'ensemble, l'agression est un jeu captivant avec de riches possibilités d'étude, mettant en évidence la complexité de la stratégie et de la prise de décision dans un contexte compétitif. De futures recherches éclairciront des aperçus et des stratégies plus profondes, ouvrant des portes à la fois pour des applications théoriques et pratiques dans la théorie des jeux.