Stratégie gagnante pour un jeu

par **TimTim2007** » 25 Avr 2007, 15:33

Bonjour,

Je voudrai savoir si quelqu'un connais ce jeu dont les règles :
Ça se joue entre deux joueurs, et chacun son tour.
Le jeu et sous forme d'une grille qui est vide au début et chaque joueur a le droit de choisir une ligne ou une colonne, et il coche autant de cases qu'il veut (au minimum 1).
Le gagnant c'est celui qui coche la dernière case.

merci

par **serge75** » 25 Avr 2007, 19:56

Ce jeu ne permettant pas le match nul, et étant fini (le nombre de parties possible est fini), il existe fatalement une stratégie gagnante pour l'un des deux joueurs... De là à la trouver c'est une autre histoire, c'est un problème dont la complexité risque d'augmenter de façon non polynomiale avec n (le nombre de ligne et de colonnes de ta grille). En d'autres termes, si n est petit, il doit être possible de trouver informatiquement (ou par le raisonnement, qui sait.... en tous cas il est sûr que j'ai pas le courage de me pencher dessus) la stratégie gagnante... Mais pour n grand, il est fort vraissemblable qu'une telle stratégie soit hors d'atteinte.
A suivre quand même, si quelqu'un est plus courageux que moi.
Serge.

par **TimTim2007** » 26 Avr 2007, 19:07

Donc pas de solution pour ce problème :\

par **nuage** » 26 Avr 2007, 20:36

Salut,
à vu de nez je dirais que c'est un jeu genre Nim.
Il y a donc presque certainement une solution gagnante calculable en O(n) (n taille de la grille).
Mais le calcul dépasse mes compétences. :mur:

par **TimTim2007** » 26 Avr 2007, 20:56

:cry: :cry:

par **Clembou** » 26 Avr 2007, 21:11

TimTim2007 a écrit:Bonjour,

Je voudrai savoir si quelqu'un connais ce jeu dont les règles :
Ça se joue entre deux joueurs, et chacun son tour.
Le jeu et sous forme d'une grille qui est vide au début et chaque joueur a le droit de choisir une ligne ou une colonne, et il coche autant de cases qu'il veut (au minimum 1).
Le gagnant c'est celui qui coche la dernière case.

merci

C'est un peu le jeu de celui qui atteint en premier 100.
Cela se joue à deux joueurs. Le premier joueur choisit un chiffre entre 1 et 9 et le deuxième, en choisit un autre (cela peut être le même) et l'additionne au chiffre du premier et ainsi de suite. Le premier qui atteint 100 a gagné

Le but en fait c'est d'atteindre 89 comme cela le joueur qui vient ensuite n'a plus qu'à prendre un chiffre a et l'additionner à 89 et le gagnant additionne 11-a et a gagné.

Essaie de moduler cette stratégie de gagner à ce jeu en fonction de tes regles. Cela marche pour une grille 10x10.

par **nuage** » 26 Avr 2007, 21:11

En fait il manque des précisions sur la règle. Par exemple : les cases cochées sont-elles consécutives ? Peut-on traverser une ligne (colonne) partiellement barrée etc...

par **TimTim2007** » 26 Avr 2007, 22:36

nuage a écrit:En fait il manque des précisions sur la règle. Par exemple : les cases cochées sont-elles consécutives ? Peut-on traverser une ligne (colonne) partiellement barrée etc...

-On a une grille 5x5.
-chaque joueur choisi une ligne(colonne)(partiellement barréé ou non) et coche 1 ou 2 ou 3 ou 4 ou toute la ligne (colonne) si c'est possible.
-Les cases cochées peuvent etre sonsecutives ou non.

par **Clembou** » 26 Avr 2007, 23:10

TimTim2007 a écrit:-On a une grille 5x5.
-chaque joueur choisi une ligne(colonne)(partiellement barréé ou non) et coche 1 ou 2 ou 3 ou 4 ou toute la ligne (colonne) si c'est possible.
-Les cases cochées peuvent etre sonsecutives ou non.

A donc c'est plus facile, ça ressemble un peu à mon jeu. En fait le but c qu'à ton avant dernier coup il y ait 5 cases comme ça ton adversaire ne peut choisir que 1,2,3,4 cases forcément tu auras gagné....

par **TimTim2007** » 27 Avr 2007, 11:55

Mais non t'as bien compris les règles.
S'il reste par exemple 5 cases, on se peut qu'ils sont dans la même ligne (colonne).Et comme on a droit à cocher 1,2,3,4 ou 5 par ligne ou (colonne), mon adversaire cochera toute la ligne (colonne), et il gagnera la partie.

C'est ce cas par exemple: http://picasaweb.google.com/TimTim2007/5x5

Et c'est moi qui a jouer le dernier et j'ai lui laissé effectivement 5 cases.Et c'est lui le gagnant car il cochera toute la ligne ..

par **Clembou** » 27 Avr 2007, 14:06

TimTim2007 a écrit:Mais non t'as bien compris les règles.
S'il reste par exemple 5 cases, on se peut qu'ils sont dans la même ligne (colonne).Et comme on a droit à cocher 1,2,3,4 ou 5 par ligne ou (colonne), mon adversaire cochera toute la ligne (colonne), et il gagnera la partie.

C'est ce cas par exemple: http://picasaweb.google.com/TimTim2007/5x5

Et c'est moi qui a jouer le dernier et j'ai lui laissé effectivement 5 cases.Et c'est lui le gagnant car il cochera toute la ligne ..

Ok !! Bon, je vais essayer de faire une partie

Je suis les bleus et un autre joueur les rouges...

http://img247.imageshack.us/my.php?image=jeuud1.jpg

En fait le jeu devient plus complexe car on peut s'occuper que des lignes et des colonnes. Or si tu vois à mon avant dernier coup, je n'ai laissé une intersection entre une ligne et une colonne (en bas à droite). Le joueur rouge ne peut que jouer sur la ligne ou sur la colonne et donc j'ai gagné.

Essaie de chercher ainsi comment on peut arriver à obtenir ce résultat...

par **TimTim2007** » 27 Avr 2007, 16:59

Mais pas du tout !
Dans ton cas, l'adversaire pourra gagner aussi :
http://picasaweb.google.com/TimTim2007/123

tu vois ?

Stratégie gagnante pour un jeu

stratégie gagnante pour un jeu

Qui est en ligne