Stratégie gagnante d'un jeu de suppression de «bord ou sommet isolé»

Ce jeu d'information parfait joué sur des graphiques est-il connu / étudié?

Étant donné un graphique , deux joueurs alternent en choisissant un bord ou un nœud isolé. Si le joueur choisit une arête les deux nœuds et sont supprimés avec leurs arêtes incidentes. Si le joueur choisit un nœud isolé, le nœud est supprimé. Le premier joueur incapable de bouger perd la partie. $G= (V,E)$ $e = (u,v)$ $u$ $v$

Quelle est la complexité de trouver le gagnant?

Des références à des jeux similaires?

reference-request combinatorial-game-theory Marzio De Biasi
la source

Je suppose que le nœud isolé est supprimé s'il est sélectionné? Si c'est le cas, le joueur 0 gagne également sur tous les chemins non vides en dépensant le premier coup en subdivisant le problème en deux composants égaux puis en reflétant les adversaires se déplaçant sur le composant opposé à partir de ce moment pour maintenir l'isomorphisme. Cela implique que le joueur 1 gagne sur un cycle, car le premier coup réduit le problème à un chemin.

Yonatan N

@YonatanN: oui, un nœud isolé peut être sélectionné (et supprimé); mais la stratégie de simulation fonctionne sur des chemins de longueur paire (le joueur 0 choisit les 2 nœuds centraux comme premier mouvement, puis reflète les mouvements du joueur 1), mais pas sur les chemins de longueur impaire: essayez d'appliquer la stratégie à un chemin de longueur 11, et ça ne marche pas (en effet pour un chemin de longueur 11 le vainqueur est le joueur 1).

Marzio De Biasi

@Marzio De Biasi: Je suis désolé mais quand je joue à de beaux jeux, je joue normalement à la main. Sauf erreur, le joueur 0 a une stratégie gagnante: Observez que: a) pour P1, P2, P5 et P8, le joueur 0 gagne toujours. b) pour P3 et P7, le joueur 1 gagne toujours. c) pour P4 et P6, le joueur 0 peut décider de gagner ou de perdre. Maintenant dans le cas de P11: - Numéroter les nœuds de P11 avec v1, v2, ... v11. - Le joueur 0 prend le bord v9, v10 et le reste est le nœud isolé v11 et P8. Si le joueur 1 prend la v11, le joueur 0 gagnera car il a un chemin égal. Sinon, le joueur 0 gagnera par a), b) et c).

user13136

Selon mon programme , les valeurs de n≤100 telles que le premier joueur perd dans le jeu sur le chemin avec n sommets sont 3, 7, 23, 27, 37, 41, 57, 61, 71, 75, 91 et 95. Malheureusement, je ne vois aucun motif autre que d'être étrange (ce qui était déjà connu), et OEIS n'affiche aucune correspondance.

Tsuyoshi Ito du

@TsuyoshiIto: ... prenez la différence par paire: (3 7) (23 27) (37 41) (57 61) (71 75) (91 95) et vous obtenez 4 4 4 4 4 4 4 ... il semble motif :-) .... (3 ... 23) ... (37 ... 57) ... (71 ... 91) et vous obtenez 20 20 20 ... un autre! :-D

Marzio De Biasi

Réponses:

Je poste une mise à jour en tant que réponse automatique uniquement pour la garder distincte de la question ( qui est toujours ouverte ).

Comme indiqué dans les commentaires (grâce à Tsuyoshi Ito), le problème est résolu en temps polynomial pour les chemins:

$Win(P_n) = 1$ $(n \bmod 34) \in \{3,7,23,27\}$

A partir de 0, la séquence (calculée) des valeurs nim est périodique:

0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
...
the subsequence rseq of length 34:
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6
is repeated

Je n'ai pas travaillé sur une preuve mathématique rigoureuse, mais l'idée est:

supposons que nous voulons calculer l'élément , puis le premier coup (choisir une arête) peut diviser le chemin de différentes manières (n-2,0), (n-3, 1), (n-4,2), ...). La nouvelle valeur nim est égale à: $Win(P_n), n = k*34 + x \; (k\geq 4, 0 \leq x < 34)$ $\lceil n / 2 \rceil$

$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$

Les 34 premiers éléments de l'ensemble sont produits par la première séquence non répétitive (0,1,1,0, ...) (nim) additionnée des éléments de la séquence répétée dans l'ordre inverse à partir de l'élément . $(34-2-x) \bmod 34$

Par exemple: pour : $x = 0$

     0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6 +
     3,4,4,1,1,0,2,1,3,0,1,1,3,2,2,7,5,4,4,3,2,2,3,1,1,0,3,1,2,0,1,1,4,6 =
mex{ 3,5,5,1,3,1,1,1,2,1,2,3,1,1,6,6,0,7,6,1,1,3,2,1,2,1,1,1,3,1,5,5,6,0 } = 4

Pour x = 0..33, la séquence mex résultante est égale à la séquence répétitive:

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6

Les éléments restants de l'ensemble ne sont calculés que sur la ou les séquences répétitives: (pour les paires sont répétées, donc ils ne modifient pas le résultat mex). La séquence mex résultante pour x = 0..33 est: $rseq[j \bmod 34] + rseq[(34-2-x-j) \bmod 34]$ $j \geq 34$

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,4,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,4,

Ce qui est égal à la séquence répétée sauf pour et ; mais les valeurs sont inférieures au mex correspondant sur la séquence non répétitive, donc: $x=16$ $x=33$

$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$ = $mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{n-2-33}+P_{33}\}$

et pour , $(k\geq 4, 0 \leq x < 34)$ $Win(P_{k*34 + x}) = Win(P_{34+x}) = Win(P_x)\;$

Marzio De Biasi
la source

Selon mon calcul, le premier joueur a une stratégie gagnante pour , donnant un contre-exemple à votre revendication ssi .

P_{23}

$P_{23}$

W i n (P_{n}) = 1

$Win(P_n)= 1$

(n \mod 34) \in {3, 7, 23, 27}

$(n \mod\, 34) \in \{3, 7, 23, 27\}$

user13136

@ user13136: avez-vous vérifié les valeurs nim? Pour la valeur nim est 0 (j'ai les mêmes valeurs de Tsuyoshi avec un programme différent, mais peut-être que nous nous trompons tous les deux).

P_{23}

$P_{23}$

Marzio De Biasi

Je pense qu'une faille possible dans vos programmes pourrait être l'ignorance du , auquel cas le premier joueur perd toujours. Si vous le souhaitez, nous pouvons jouer le cas maintenant.

P_{0}

$P_0$

P_{23}

$P_{23}$

user13136

Désolé, je dois partir maintenant.

user13136

(n_{17}, n_{18}) \to (n_{5}, n_{6}) \to (n_{11}, n_{12}) \to (n_{1}, n_{2})

$(n_{17}, n_{18}) \to (n_{5}, n_{6}) \to (n_{11}, n_{12}) \to (n_{1}, n_{2})$ (vous pouvez supprimer les commentaires précédents contenant les mouvements)

Marzio De Biasi