Inscription / Connexion Nouveau Sujet

1 2 +


Posté par
GBZM
re : Petit jeu entre nous 17-11-21 à 15:48

Eh oui, dpi, je suis très mauvais joueur et je ne joue que si je suis sûr de gagner.
Tu as enlevé les 11. Moi j'en enlève 7 dans la rangée de 9. Il reste donc 1,3,5,5,2. À toi.

Posté par
dpi
re : Petit jeu entre nous 17-11-21 à 16:45

On fait durer: j'enlève les 2 .Il reste 1,3,5,5

Posté par
GBZM
re : Petit jeu entre nous 17-11-21 à 18:42

J'en enlève 2 sur la rangée de 3 : 1,1,5,5.

Posté par
Vassillia
re : Petit jeu entre nous 17-11-21 à 19:53

Si tu veux GBZM, je le connais sous le nom de jeu de Grundy.
Je serai d'ailleurs curieuse de savoir comment tu décides quoi jouer. La seule méthode que je vois, c'est tester tous les coups possibles en me servant d'une certaine liste OEIS, tu as surement mieux.
On verra ça après, je vous laisse finir votre jeu.

Posté par
GBZM
re : Petit jeu entre nous 17-11-21 à 22:50

Mes petits programmes python :

def calc_Grundy(n) :
    if n == 2 : return [0,0,0]
    elif n>2 :
        G=[0,0,0]
        for k in range(3,n+1) :
            div=[G[i]^G[k-i] for i in range(1,(k+1)//2)]
            g=0
            while g in div : g+=1
            G.append(g)
    return G

%time Grundy=calc_Grundy(20000)
CPU times: user 19.3 s, sys: 0 ns, total: 19.3 s
Wall time: 19.3 s

from functools import reduce

def Grundysum(L) :
    GL = [Grundy[k] for k in L]
    return reduce(lambda x,y : x^y, GL)

    
def mvt_gagnant(L) :
    GS=Grundysum(L)
    if  GS== 0 :
        print("Position perdante")
    elif GS > 0 :
        for o in range(len(L)) :
            n=L[o]
            for i in range(1,(n+1)//2) :
                divL=L[: o]+[i,n-i]+L[o+1:]
                newGS=Grundysum(divL)
                if newGS == 0 :
                    divL.sort(reverse=True)
                    return divL


mvt_gagnant([33,32,13])
[32, 31, 13, 2]

Posté par
GBZM
re : Petit jeu entre nous 17-11-21 à 22:58

Avec le nom de Grundy, nos amis curieux pourront trouver toutes les informations nécessaires.

Posté par
Vassillia
re : Petit jeu entre nous 18-11-21 à 00:05

Ah oui, on peut aussi refaire la liste soi-même, je suis moins courageuse
Pratique ton petit programme qui cherche tout seul le coup gagnant, j'aime beaucoup, je vais le garder dans un coin si tu veux bien.
Quand je disais que je ne croyais pas trop à une erreur de ta part, je ne savais pas que c'était à ce point là. Le pauvre dpi n'avait aucune chance. Bravo GBZM, je pense que personne ne contestera que tu as largement gagné ce jeu !

Posté par
dpi
re : Petit jeu entre nous 18-11-21 à 08:50

Arrivé à         I
                           I
                       IIIII
                        IIIII  
Je retrouve une configuration du jeu historique,je passe et je te laisse la main

Posté par
GBZM
re : Petit jeu entre nous 18-11-21 à 10:22

Eh oui dpi, ce n'est pas marrant de jouer quand on est sûr de perdre !

Posté par
dpi
re : Petit jeu entre nous 18-11-21 à 10:53

Je voulais dire à toi... pour voir...

Posté par
GBZM
re : Petit jeu entre nous 18-11-21 à 11:15

Je crois que c'est tout vu : dans la position où je t'ai amené, on est sûr de perdre. Mais dès le départ, en commençant un jeu de Marienbad avec 6 lignes 1,3,5,7,9,11, j'étais sûr de gagner.

Petite question : on joue au jeu de Marienbad avec n lignes 1, 3, 5, ..., 2n-1. Qui gagne ? celui ou celle qui commence, ou l'autre ? (Les deux joueurs connaissent parfaitement le jeu.)

Posté par
dpi
re : Petit jeu entre nous 18-11-21 à 11:50

Déjà pour n=3 ,le débutant perd
pour n>3  pair il gagne , impair  il  perd.

Posté par
LittleFox
re : Petit jeu entre nous 18-11-21 à 12:03


J'avais déjà rencontré les nombres de Grundy et les jeux de Nim.
J'étais d'abord parti sur mod 3 comme verdurin mais le fait qu'il n'y ai pas de positions perdantes entre 10 et 20 contredisait cette théorie.
J'ai ensuite vu assez vite que les nimbers correspondaient aux nombres que vous aviez déjà sortis. Un petit programme pour calculer jusqu'à 1000 et je me suis retrouvé sur l'oeis:

Mon programme ressemble à celui de GBZM sinon que j'utilise un set plutôt qu'une liste pour calculer la Nim-somme.
Ça reste un algorithme en O(n²) ce qui n'est pas très efficace. Mais je n'ai pas trouvé mieux pour calculer toute la liste.

def get_grundy(max_n):
    grundy = []
    for n in range(max_n+1):
        s = set(grundy[i] ^ grundy[n-i] for i in range(1, (n+1)//2))
        g = 0
        while g in s:
            g += 1
        grundy.append(g)
    return grundy


timeit(lambda:get_grundy(1000), number=100) / 100
0.02954680400000001
timeit(lambda:get_grundy(20000), number=1) / 1
11.591382100000033

Posté par
GBZM
re : Petit jeu entre nous 18-11-21 à 12:20

dpi @ 18-11-2021 à 11:50

Déjà pour n=3 ,le débutant perd

Ben non, il gagne. n=3, ça veut dire 1,3,5. Le débutant joue 1,3,2.

Posté par
GBZM
re : Petit jeu entre nous 18-11-21 à 12:26

Et après, tu vois bien que ça ne dépend pas de la parité du nombre de lignes : pour 5 lignes, le débutant gagne ; pour 6 lignes aussi, comme tu as pu le voir.

Posté par
Vassillia
re : Petit jeu entre nous 18-11-21 à 13:06

Je dirais que je laisse mon adversaire commencer pour n=1 et pour n=4k pour tout k\in \mathbb{N^*}.
Dans les autres cas, je commence.

Posté par
Vassillia
re : Petit jeu entre nous 18-11-21 à 13:58

Autre variante, on finira peut-être par en trouver une que GBZM ne connait pas encore pour avoir une toute petite chance de gagner et puis sinon, on apprendra comment gagner aussi

Initialement, il y a 2 tas, le premier comporte m jetons et le second comporte n jetons.
Les joueurs jouent à tour de rôle et à chaque tour, un joueur peut prendre un nombre quelconque de jetons dans un unique tas OU prendre le même nombre de jetons dans les 2 tas.

Le perdant est celui qui ne peut plus jouer donc le gagnant est celui qui remporte le dernier jeton (je n'ai jamais trop compris la logique de faire l'inverse).

Quels vont être les couples  (m,n) perdants pour celui qui commence ?

Posté par
LittleFox
re : Petit jeu entre nous 18-11-21 à 14:59


(0,0) est perdant.
Une position (m,n)  est gagnante si et seulement si il existe une position perdante de la forme (m-x,n), (m,n-y) ou (m-x,n-y) avec 1<x<=m et 1<y<=n.

On peut construire un tableau où chaque ligne, chaque colonne et chaque diagonale contient une seule position perdante.

Posté par
dpi
re : Petit jeu entre nous 18-11-21 à 15:13

Pour en finir sur le sujet Marienbad :
Je disais 2n+1 donc  avec n=3--->7
Position perdante pour celui qui démarre. Donc j'aurais gagné...
pour 9 si tu me laisses démarrer ,je les enlève tous.....
pour 11 ,j'étais sûr de perdre...
Je connais la règle binaire ...

Posté par
LittleFox
re : Petit jeu entre nous 18-11-21 à 15:14


Ce petit code génère les premières positions perdantes:

 Cliquez pour afficher


Et après un petit tour par l'oeis on arrive sur le jeu de Whytoff :

Posté par
GBZM
re : Petit jeu entre nous 18-11-21 à 16:23

dpi @ 18-11-2021 à 15:13


Je disais 2n+1

Non, vérifie, tu ne disais rien du tout. Et j'avais bien précisé que n est le nombre de lignes au départ (vérifie aussi, c'est le message juste au-dessus du tien).
Dpi, ça faciliterait les échanges si tu prenais en considération ce qu'on écrit ...

Posté par
Vassillia
re : Petit jeu entre nous 18-11-21 à 18:36

Bien joué LittleFox, c'est exactement ça mais tu as trouvé trop vite... Encore plus difficile alors :

On reprend les règles du jeu de Marienbad, c'est à dire qu'il y a plusieurs tas et à tour de rôle chaque joueur va prendre le nombre de jetons de son choix dans un unique tas.
Mais, attention, impérativement une seule fois avant la fin de la partie, un des joueurs au lieu de prendre des jetons va passer mais devra dire :
-je garde la règle d'origine c'est à dire celui qui prend le dernier jeton perd
-je change la règle donc celui qui prend le dernier jeton gagne
Lorsque c'est fait la règle ne peut plus changer.

Comment on se débrouille pour savoir si on va gagner ou pas et comment faire ?
Résolu par J.H.Conway, hommage à ce mathématicien brillant.

1 2 +




Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !