Un jeu de cartes
Bonsoir à tous 
Un petit problème trouvé sur un autre site, simple ?
Sur une ligne on dispose des cartes portant chacune un numéro (quelconque, possiblement égaux). Deux joueurs à tour de rôle prélèvent une carte à l'une des extrémités de la ligne jusqu'à épuisement des cartes. Puis chacun fait ses comptes et celui qui a récupéré une somme maximale a gagné.
En fonction du nombre de cartes et des numéros choisis, quel joueur a une stratégie gagnante ? Quelle est-elle ? Comment maximiser les gains ou minimiser les pertes ?
Merci d'avance pour la participation.
Domi
Un petit problème trouvé sur un autre site, simple ?
Sur une ligne on dispose des cartes portant chacune un numéro (quelconque, possiblement égaux). Deux joueurs à tour de rôle prélèvent une carte à l'une des extrémités de la ligne jusqu'à épuisement des cartes. Puis chacun fait ses comptes et celui qui a récupéré une somme maximale a gagné.
En fonction du nombre de cartes et des numéros choisis, quel joueur a une stratégie gagnante ? Quelle est-elle ? Comment maximiser les gains ou minimiser les pertes ?
Merci d'avance pour la participation.
Domi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je note $n$ le nombre de cartes et $c_1,c_2,\ldots,c_n$ les numéros qu'elles portent. Alors :
1) Si $n=2p$ est pair, le joueur qui commence peut récupérer toutes les cartes de rang pair ou toutes les cartes de rang impair. Il peut donc toujours gagner ou faire match nul.
Je ne pense pas qu'il puisse faire mieux si l'autre joue parfaitement (mais j'ai la flemme de le démontrer proprement). Son gain maximal est donc
$$\max(c_1+c_3+\ldots+c_{2p-1},c_2+c_4+\ldots+c_{2p}).$$
2) Si $n=2p+1$ est impair, alors :
- si le premier joueur choisit $c_1$, alors (si mon idée précédente est correcte) le deuxième peut obtenir au plus $G_2=\max(c_3+c_5+\ldots+c_{2p+1},c_2+c_4+\ldots+c_{2p})$. Le gain du premier est alors $G_1=c_1+\min(c_3+c_5+\ldots+c_{2p+1},c_2+c_4+\ldots+c_{2p})$.
- si le premier joueur choisit $c_{2p+1}$, alors le deuxième peut obtenir au plus $G'_2=\max(c_1+c_3+\ldots+c_{2p-1},c_2+c_4+\ldots+c_{2p})$. Le gain du premier est alors $G'_1=c_{2p+1}+\min(c_1+c_3+\ldots+c_{2p-1},c_2+c_4+\ldots+c_{2p})$.
Le premier joueur peut donc gagner si et seulement si $G_1>G_2$ ou $G'_1>G'_2$.
En bidouillant un peu on voit que c'est équivalent à
$$c_1+c_{2p+1}>c_2+c_4+\ldots+c_{2p}-(c_3+c_5+\ldots+c_{2p-1})>-|c_1-c_{2p+1}|.$$
et la stratégie du premier joueur est simplement de toujours choisir la plus grosse carte.
Tu as raison , pour un nombre pair de cartes le premier joueur va au pire annuler mais dans certains cas il peut faire mieux que la différence entre les sommes de rangs pairs et impairs .
Un exemple : 3 ; 1 ; 2 ; 4 , les rangs pairs et impairs ont la même somme mais le premier joueur gagne au moins 2 .
Pour un nombre impair de cartes , prendre systématiquement la plus grosse carte est clairement mis en défaut par des positions de ce style : 1;1;1;9;2 .
Je soupçonne ce problème d'être très difficile .
Domi
Je pense aussi que le cas général de ce problème doit être extrêmement difficile.
Pour un nombre pair n de cartes, on a déjà observé que le premier joueur peut imposer de prendre les cases de rang pair ou impair. Le jeu n'a d'intérêt que si les sommes pair et impair sont égales.
On observe qu'après un coup de chaque joueur, on a une situation à n-2 cartes où n-2 est encore pair.
Le joueur 1 peut à nouveau étiqueter pair-impair les cartes restantes et imposer d'avoir au moins la moitié du total restant.
Ce qui veut dire que si le premier joueur a pris un avantage au premier coup, il est assuré de le conserver.
Bien entendu, s'il n'a pas pu prendre l'avanatage au premier coup, il peut éventuellement le prendre plus tard et gagner.
Donc, dans le cas n pair, avec égalité des sommes de rang pair et de rang impair, le premier joueur gagne s'il peut à un moment prendre l'avantage.
Dans cet exemple à 8 cartes :
3 3 4 2 5 6 3 4
le premier joueur gagne en prenant le 4 : quelle que soit la carte choisie par le joueur 2, il a un avantage qu'il est sûr de conserver.
les sommes de rang pair et impair sont égales à 15.
Aldo
Le joueur 1 ne peut donc espérer s'en sortir que si la valeur de la carte qu'il choisit est supérieure à cette différence.
Même sans calculer cette différence, il ne peut faire mieux que de choisir au premier coup la plus grande possible.
Le contre-exemple donné par Domi : 1;1;1;9;2 n'en est pas vraiment un puisque le joueur en premier perd quelle que soit la carte choisie au premier coup.
En quelque sorte, dans le cas n impair, le meilleur jeu du premier joueur est extrêmement simple : prendre toujours la carte la plus grande et advienne que pourra !
Bien entendu, idem pour le meilleur jeu du joueur en second dans le cas n pair.
Aldo
def coup(cartes): n=len(cartes) if n%2==1: if cartes[0]>cartes[n-1]: return 0 else: return n-1 elif sum(cartes[::2])>sum(cartes[1::2]): return 0 else: return n-1 def jeu(cartes): n=len(cartes) g=[0,0] j=0 while n>0: c=coup(cartes) print('Joueur',j+1,'prend',cartes[c]) g[j]+=cartes[c] del cartes[c] j=1-j print('Cartes ',cartes) print('Gains ',g) n-=1Voilà ce que ça donne sur les exemples précédents :
Il semblait difficile d'établir une stratégie pour le joueur en premier mais cela va être grandement facilité par la connaissance de la stratégie adverse !
On suppose que le joueur en premier ne peut pas prendre immédiatement l'avantage.
A partir du moment où le joueur 1 connaît d'avance la meilleure réponse adverse, comme il ne dispose pour son premier coup que de deux possibilités, il n'a en fait que deux variantes à étudier : pour chacune des cartes qu'il peut prendre au premier coup, il peut calculer la différence des cartes de rang pair et impair après le coup du deuxième joueur et opter pour la différence la plus avantageuse.
Mais il faut tenir compte de l'avantage pris par le joueur en second sur la première carte !
On vérifie aisément que dans les deux cas, la différence "cartes de rang pair et impair" est égale à la différence des deux premières cartes prises (on partait d'une différence nulle).
Ce qui veut dire que les deux stratégies sont équivalentes !
Donc, stratégie du joueur en premier dans le cas n pair : jouer n'importe quoi jusqu'à ce que se présente une possibilité de prendre l'avantage, ce qui lui assure la victoire.
Si cette possibilité ne se présente jamais, la partie sera nulle.
Jusqu'ici, on s'est uniquement basé sur l'objectif de remporter la partie. Le fait d'optimiser gains ou pertes est une autre affaire...
Aldo
Par exemple
2 6 3 1 3 1 1
Si le joueur 1 commence modestement par le 1 de droite, il gagne.
S'il commence par le 2 à gauche, il perd. En effet, Joueur 2 prend 6, joueur 1 prend 3 et joueur 2 qui a déjà l'avantage joue dans une configuration paire, il est sûr de gagner.
C'est cette possibilité locale (2 6 3) pour le joueur 2 de prendre l'avantage malgré un coup de moins qui crée le déséquilibre...
Aldo
$$\left\{\begin{array}{l}\operatorname{gainmax}(c_1)=c_1\\\operatorname{gainmax}(c_1,\ldots,c_n)=\max(c_1-\operatorname{gainmax}(c_2,\ldots,c_n),c_n-\operatorname{gainmax}(c_1,\ldots,c_{n-1}))\end{array}\right.$$
Ça m'étonnerait qu'on puisse donner à partir de là une expression simple de $\operatorname{gainmax}(c_1,\ldots,c_n)$ en fonction de $c_1,\ldots,c_n$, mais on peut faire un programme pour le calculer et donner la meilleure stratégie :
Avec l'exemple d'Aldo ci-dessus : La liste [1, 1, 3, 1, 3, 6, 2] donne l'ordre dans lequel les joueurs prennent les cartes s'ils jouent au mieux, et le 1 est le gain maximal du joueur qui commence.
Le cas pair est complètement traité par les remarques déjà faites à condition de ne pas chercher pas à maximiser le gain .
Nous avons tous choisi des étiquettes entières et positives alors que rien ne l'imposait . On peut remarquer qu'on ne change pas le problème en multipliant les étiquettes par une constante ( non nulle ) , on peut donc considérer les étiquettes entières . En enlevant à chaque étiquette la plus petite d'entre elles on peut aussi considérer qu'elles sont toutes positives ou nulles , on ne change pas le résultat quand les cartes sont en nombre pair , on le change de +/-1 dans le cas contraire ( sans changer la stratégie ) .
Je ne sais si quelqu'un à d'autres idées , personnellement je garde le problème dans un coin de ma mémoire .
Merci à Juge Ti et Aldo
Domi
Supposons que « total des cartes de rang pair » = « total des cartes de rang impair ».
On s’intéresse uniquement au cas où les deux joueurs cherchent uniquement à gagner la partie, sans tenter d’optimiser ce gain.
Comme déjà vu, le joueur en premier gagne s’il parvient à un moment quelconque à prendre un avantage malgré la réplique du joueur en second.
Par exemple
8 1……..2
Le joueur 1 prend le 8 à gauche et gagne car le joueur 2 ne peut pas égaliser.
Mais il y a mieux, le joueur 1 ne gagne que si, à un moment du jeu, il prend l’avantage quelle que soit la réplique du joueur 1. Cela semble évident, en effet, dans le cas contraire, on jouera jusqu’à épuisement des cartes sans que le joueur 2 perde.
Mais il n’y a pas toujours un gros 8 aussi "évident" à voir :
1 1 8 1………..
Si le joueur 1 commence par le 1 de gauche, il gagnera lorsque le joueur 2 prendra le 1 qui suit, lui offrant ainsi le magnifique 8.
Mais rien n’oblige le joueur 2 à prendre ce 1, il peut prendre une carte à droite !
Attention aussi à une grosse carte qui pourrait être un leurre :
2 4 9 7………....
Le joueur 1 peut prendre le 2 en espérant que le joueur 2 se précipite sur le 4 et lui offre le magnifique 9.
Et bien, cela ne mène nulle part car le joueur 2 poursuivra sur le 7 et son total des deux premières cartes (4+7) est égal à celui du joueur 1 (2+9).
On va appeler alternance gagnante une suite de cartes telle que le joueur 1 obtienne un avantage après que chacun ait pris une carte alternativement du même côté.
Par exemple :
2 3 2 5 8 1……....
est une alternance gagnante à gauche puisque 2+2+8 > 3+5+1
Autre exemple
………………..2 9 5 1
est une alternance gagnante à droite car 1+9 > 5+2
Supposons que la position initiale comporte une alternance gagnante à gauche.
Le joueur 1 prend la première carte de cette alternance et attend que son adversaire prenne la seconde.
Mais ce n’est pas si simple car le joueur en second peut choisir de jouer à droite !
Ceci nous donne la clé du mystère :
On va aussi calculer l’alternance à droite mais bien sûr en considérant que la carte déjà prise par le joueur 1 fait partie de l’alternance.
Exemple
2 3 8 1 ………….1 9 2 1 2
présente une alternance gagnante à gauche.
Joueur 1 prend donc le 2 de gauche.
Nous calculons donc l’alternance à droite en y ajoutant la première carte de joueur 1 :
…………………1 9 2 1 2 (2)
ce qui donne (2)+ 1 + 9 qui est supérieur à 2 + 2 + 1
Joueur 2 est donc pris dans la tenaille : qu’il choisisse la carte de gauche ou de droite, il tombe dans une alternance gagnante pour joueur 1.
Le jeu est donc résolu : joueur 1 gagne si et seulement si l’une des cartes pour son premier coup lui offre une alternance gagnante à gauche ET à droite.
Exemples :
2 8 6 ………. 7 9 2 1
Joueur 1 gagne en prenant le 1 de droite car (1) + 8 > 2 + 6 ET 1+9 > 2+7.
1 1 3 1 2 4 1 1
Si joueur 1 prend le 1 de gauche, il obtient une alternance gagnante à gauche mais pas à droite, partie nulle !
S’il prend le 1 de droite, il a une alternance gagnante à droite mais pas à gauche, partie nulle.
Bien entendu, cela fonctionne avec toute sorte de nombres, entiers, réels, etc avec quand même une addition et un ordre total.
Le cas n impair nous oblige à entrer dans la considération du meilleur gain possible dans le cas n pair.
En effet, dans le cas n impair, après le premier coup de joueur 1, le joueur 2 se trouve face à une situation paire mais avec un handicap égal à la première carte choisie par 1. Il est donc crucial pour lui de gagner plus que ce handicap, ce qui me semble peu calculable autrement que par ordinateur.
Bien entendu, dans le cas n impair, la partie n’a d’intérêt que si la somme des cartes de rang impair est supérieure ou égale à la somme des cartes de rang pair. Dans le cas contraire, le joueur en second est assuré de la victoire.
Aldo
J'ai l'impression que pour résoudre ce jeu il "suffit" d'appliquer un algorithme minimax : Page wikipedia
A chaque coup le joueur essaye de minimiser le score maximum que l'autre joueur peut atteindre. Pour résoudre le problème on est obligé de dérouler presque tout l'arbre (le "presque" vient du fait qu'on peut sans doute trouver des heuristiques pour stopper la recherche dans certaines branches)
2 3 2 3 2 3 5 1 …………… 3 6 2 1 2 1 2
D’après ce qui a été vu, le joueur 1 devrait l’emporter en prenant le 2 de gauche puisque
2+2+2+5 > 3+3+3+1
et
2+1+1+6 > 2+2+2+3
C'est-à-dire que le joueur 2 se retrouvera en infériorité, qu’il choisisse de jouer à gauche, offrant le 5 ou de jouer à droite, offrant le 6.
Mais le joueur 2 peut subtilement opter pour le choix retardé !
Il prend tout ce qu’il peut à gauche sauf le 3 fatidique qui offrirait le 5, puis il prend à droite.
Avant d’arriver au 2 fatidique qui offrirait le 6, faisons les comptes :
Joueur 1 : 2 + 2 + 2 +1 +1 contre Joueur 2 : 3 + 3 + 2 +2
Il mène déjà de 2 !
Il peut allègrement prendre le 3 de gauche qui offre le 5 (ou même le 2 de droite qui offre le 6 car un 3 suit) sans se retrouver en désavantage.
La condition que nous avions donnée pour une victoire de joueur 1 était nécessaire mais pas suffisante.
Pour que joueur 1 s’impose, il lui faut des conditions encore plus favorables : que chacune des deux fortes cartes de gauche et de droite lui apporte l’avantage, quel que soit le moment où le joueur 2 se décidera à lui offrir une de ces cartes.
Nommons les cartes G1 G2 G3 ….. D3 D2 D1,
Avec G comme gauche et D droite.
Le joueur 1 gagne en prenant la carte G1 si la double condition suivante est réalisée :
Il existe deux cartes Gi et Dj (i impair et j pair) telles que, pour tout p impair (p<j-2) :
G1+G3+G5+…+Gi+D2+D4+D6+…+D(j-2) > G2+G4+G6+...+G(i+1)+D1+D3+D5+.…+Dp
ET
Pour tout q pair (q<i-2)
G1+G3+G5+…+G(i-2)+D2+D4+D6+…+Dj > G2+G4+G6+…+G(i-3)+D1+D3+D5+…+D(j+1)
De la même manière, le joueur 1 gagne en commençant par la carte D1 si la condition symétrique est réalisée (il suffit d’intervertir D et G).
Résumé : le joueur 1 gagne si, pour l’une des cartes G1 ou D1, la double condition est réalisée.
Exemple simple :
2 2 5 4 …. 4 6 2 1 2
Le joueur 1 prend le 2 de gauche.
Si le joueur 2 prend aussi à gauche, joueur 1 prend le 5 et joueur 2 prend le 4
Si le joueur 2 prend uniquement à droite, il perd aussi :
2+1+6=9, alors que 2+2+4=8
Par contre le joueur 2 peut se sauver en prenant une fois seulement à droite (le 2) sur lequel joueur 1 prend le 1 contigu à droite.
Joueur 2 a ainsi grappillé une unité salvatrice, il retourne jouer à gauche, offrant le 5 mais conserve l’équilibre : 2+1+5 = 2+2+4
Joueur 1 ne gagnera que si ce genre de sauvetage n’existe pas :
2 3 2 3 8 1…….1 7 2 2 2
Joueur 1 commence en prenant le 2 de gauche.
Quel que soit le moment choisi par joueur 2 pour offrir le 8 à gauche ou le 7 à droite, il permettra à joueur 1 de prendre l’avantage et donc de gagner la partie.
Nous allons tenter de voir de combien le joueur 1 peut gagner la partie (lorsqu’il gagne !)
Supposons que la double condition ci-dessus soit réalisée.
Joueur 1 est donc gagnant.
Joueur 2 choisira la suite concédant le plus petit avantage possible.
Soit A cet avantage.
On peut vérifier que Joueur 1 et Joueur 2 n’ont pris respectivement que des cartes dont les rangs étaient tous de même parité.
Dans cette situation existe donc une différence de A entre le total des cartes de rang pair et le total des cartes de rang impair.
Joueur 1 peut donc au minimum remporter de A la fin de la partie.
Sur l’ensemble de la partie, il est assuré de gagner au moins de 2A.
Résumé : si joueur 1 trouve un début de partie lui assurant un avantage de A, il peut gagner la partie d’au moins 2A.
Aldo
P.S. Je me rends bien compte que tout cela n'est pas super lisible !
G1..........G(i-1) Gi G(i+1) ......................D(j+1) Dj D(j-1)............D1
Joueur 1 prend G1
Tôt ou tard, Joueur 2 devra prendre G(i-1) et entrer dans la séquence G(i-1) Gi G(i+1)
ou prendre D(j-1) et entrer dans la séquence D(j-1) Dj D(j+1).
Joueur 1 gagne si ces deux séquences se terminent à son avantage, quelque soit le moment choisi par Joueur 2 pour prendre G(i-1) ou D(j-1).
Aldo
Il y a deux moyens qui permettent de s'en sortir rapidement.
Tout d'abord, une carte Gi ne peut être candidate que si elle est supérieure à la suivante G(i+1). En effet, avant de prendre Gi, le joueur 1 n'a pas encore d'avantage. S'il a l'avantage en prenant Gi et en laissant G(i+1) c'est au minimum que Gi > G(i+1)
Ensuite, le critère que nous avions donné précédemment concernant les alternances gagnantes, s'il n'est pas suffisant, permet de sérieusement débroussailler la recherche : on n'aura à considérer que les nombres présentant une alternance gagnante (à gauche pour Gi et à droite pour Dj).
Exemple pratique :
1 2 1 2 4 3 7 3 1 6 2 3 2 2 4 1
On vérifie d'abord que la somme des cartes de rang pair = somme des cartes de rang impair = 22
En prenant le 1 de gauche, le joueur 1 fait apparaître les cartes Gi = le 7 à gauche et Dj = le 4 le plus à droite.
Joueur 2 devra tôt ou tard céder un de ces cartes. Quelle que soit la manière choisie, Joueur 1 prendra alors l'avantage.
Le 4 de gauche était aussi un candidat mais il est éliminé car ne présente même pas le critère de l'alternance gagnante :
1+1+4 n'est pas supérieur à 2+2+3.
Après le premier coup de joueur 1 qui prend le 1 de gauche, le joueur 2 peut limiter la casse en ne perdant que d'une unité en prenant le 2 de gauche : Joueur 1 prend le 1 de gauche - Joueur 2 prend le 1 de droite - Joueur 1 prend le 4 de droite - Joueur 2 prend le 2 à droite.
1+1+4 contre 2+1+2
Comme déjà vu, Joueur 1 pourra par la suite au moins doubler cet avantage et gagner la partie par une différence de 2.
Aldo
J'ai pris un moment pour lire ta prose
J'ai bien compris que tu te plaçais dans le cas d'un nombre pair de cartes avec des sommes égales sur les pairs et impairs et je vois ce que tu entends par alternance gagnante gauche ou droite , mais je n'ai pas trop compris les Gi et Dj .
En tout cas ça semble compliqué et je ne suis pas sûr que même dans ce cas "simple" on puisse faire beaucoup mieux que la solution électronique du Juge Ti .
J'ai peut-être raté quelque chose .
Domi
merci d'avoir eu ce courage !
On analyse le cas où Joueur 1 prend la carte à gauche G1.
Il faut bien voir que tout au long de la partie, Joueur 1 est toujours mené (à égalité de coups joués de part et d'autre) ou au mieux à égalité. En effet, s'il prend l'avantage à un moment quelconque, une stratégie simple lui assure la victoire.
Il ne gagnera donc que s'il y a deux cartes de rang impair Gi à gauche et Dj à droite qui lui apportent un avantage s'il prend l'une d'elles. Tôt ou tard, Joueur 2 devra prendre G(i-1) ou D(j-1), offrant ainsi la carte fatidique Gi ou Dj.
Bien entendu, la recherche de ces cartes Gi et Dj n'est pas immédiate. On a le premier critère Gi > G(i+1), puis le critère des alternances gagnantes.
Une fois les cartes candidates repérées, il faudra calculer toutes les possibilités. C'est à ce moment qu'un ordi peut s'avérer utile...
Aldo
Le premier joueur découpe un gâteau comme il le souhaite .
Mais peut-être faut-il supposer que des parts strictement égales ça n'existe pas ?
Domi
Pour le moment, je n'ai pas obtenu mieux que 2 7 9 1 4 1 5 (disposés en cercle).
Le découpeur gagne sur tous les choix du premier joueur sauf un ! (lequel ?...).
Bon, la recherche continue.
Aldo
Domi