Strategie gagnante

par **miikou** » 10 Déc 2009, 16:50

bonjour,

Existe t-il une strategie gagnante pour le puissance 4 ?

bonne chance

par **nodgim** » 10 Déc 2009, 17:49

C'est quoi ce problème de stratégie gagnante puissance 4 ?

par **Ben314** » 10 Déc 2009, 18:06

Oui, il y a (évidement) une stratégie gagnante au puissance 4 (comme au dames, aux échecs, au go... et plus généralement à tout jeu de "type fini" "à information ouverte").
Ca c'est la réponse "théorique" : la stratégie EXISTE.
La réponse "pratique", c'est que, dans le cas des échecs, des dames du go (et je crois aussi du puissance 4) on NE LA CONNAIT PAS !!!!

C'est la même chose qu'en math. lorsque le tableau de variation d'une fonction permet de savoir qu'elle s'annule, MAIS on ne sait pas exprimer la valeur exacte du réel qui annule la fonction.

Pour nodgin : une stratégie gagnante, c'est une "recette" qui, quand on l'applique permet de gagner à tout les coup (ou bien de ne jamais perdre et donc de faire au moins nul).
Tu as surement déjà vu les petits jeux d'allumettes type "chaque joueur enlève de 1 à 3 allumettes et celui qui prend la dernière a perdu" où la "stratégie" consiste à compter modulo 4 le nombre d'allumettes restantes.
Le plus connu des jeux dont on connait parfaitement la stratégie est le "jeu de nim".

par **ffpower** » 10 Déc 2009, 18:55

Ben, ce que tu dis est faux,car dans les jeux que tu cites ( a part le go je crois ), il peut y avoir des matchs nuls. Cela dit pour le puissance 4, je crois avoir lu qu'il y a une strategie gagnante pour le premier joueur ( je ne sais pas si elle est explicite ), mais que si le 1er joueur ne commence pas par jouer au milieu, alors le second a une strategie gagnante..

par **Ben314** » 10 Déc 2009, 19:17

Le fait qu'il y ait une notion de "match nul" ne change pas le problème.
La notion de "stratégie gagnante" peut alors vouloir dire :
En étant le premier (ou le second) joueur je suis sûr de gagner
OU BIEN
Que je soit premier ou second je suis sûr de ne pas perdre (i.e. de faire au moins nul)
S'il y avait plus de 3 issus (par exemple des gain d'argent), il y aurait encore une "stratégie gagnante".

Le "point faible" de la preuve et plutôt qu'il faut savoir que le jeu ne peut pas durer indéfiniement. Aux échec c'est la "règle des 50 coups" qui l'affirme, aux dames, il y a une série de régles concernant les fins de parties qui disent que s'il ne reste que ça, alors la partie est nulle ce qui assure (plus ou moins) qu'une partie ne peut durer indéfiniement.

P.S. en cherchant sur GOOGLE, je suis tombé sur ça (via wikipédia)
http://www.connectfour.net/Files/connect4.pdf
qui, si j'ai bien compris (je ne lit l'anglais que... sous la torture) c'est une thèse d'info prouvant que la stratégie gagnante au puissance 4 est pour celui qui commence.

P.S.2 (pour ffpower) il y a aussi des match nuls au puissance 4 et, aux echecs, la plupart des gens conjecturent que la "statégie gagnante" est un nul assuré pour les deux.

P.S.3 (encore pour ffpower) je vient juste de me rendre compte que j'emploie le mot "stratégie gagnante" alors qu'effectivement je devrait uniquement employer le mot "stratégie" qui colle bien mieux avec ce que raconte au début de ce post.... désolé.

par **ffpower** » 10 Déc 2009, 19:33

Oui, si on parle de "stratégie pour ne pas perdre", je suis dac
J'étais moi aussi tombé sur cette these dans le passé. Y en a qui se sont bien amusé quand même^^

par **Ben314** » 10 Déc 2009, 19:46

Comme tu dit...
Aprés, j'avais une fois discuté avec un informaticien qui me disait qu'ils en sont plus tout à fait à explorer bêtement l'arbre (heureusement pour eux) et j'avais cru comprendre (mais j'ai tout oublié...) qu'il y avait quand même de "jolies astuces" dans la programation de ce type de problèmes...

Personellement, j'ai tapé 3 versions du puissance 4 (la première avec un apple II en assembleur...) en cherchant à chaque fois à améliorer l'algorithme.
Pour la V3 (turbo pascal+assembleur 80486) j'avais utilisé la notion de "menace, i.e. d'alignement de 3 pions avec un vide au bout, et fait des calculs pour savoir qui sera à la fin obligé de jouer "le trou" (Quand il y a plus de 3 'menaces' (cas rare) c'est pas si évident que ça). La dernière version me battant systèmatiquement, j'ai (évidement!!!!) arrété de l'améliorer... (c'était il y a environ 15 ans...)

par **miikou** » 10 Déc 2009, 19:51

j'attendais plutot la preuve mais le vocabulaire que tu as employé montre que tu la connais ou du moins que tu sais d'ou ca vient ..

QUESTION SUBSIDIAIRE : quel est l'algorithme de victoire ? ( si l'on peut le definir biensur .. )

par **Ben314** » 10 Déc 2009, 20:50

miikou, je pense que pour avoir la réponse, il faudrait qu'il y en ait un dans le lot qui se tape la lecture (peut-être en diagonale) des 91 pages D'ANGLAIS du lien ci dessus puis qu'il fasse sympathiquement un résumé aux autres...

Je propose qu'on soumette au vote pour désigner l'heureux élu... :zen:

P.S. Je rapelle que moi, à part sous la torture....

par **Ben314** » 12 Déc 2009, 13:27

Bon, comme il n'y avait pas de volontaire, je suis allé regardé le "machin".
C'est super intéressant car c'est tout sauf de la "brute force" dans l'arbre des possibilités.
L'immense partie du texte explique (trés bien) les différentes façons de voir (trés tôt dans la partie) qui... va perdre (et sans sortir un ordi.)
Les méthodes qu'il donne sont tout à fait applicable pour un "humain" un peu entrainé (et c'est super bien expliqué).
Par contre, pour aller jusqu'a prouver que le premier a une stratégie gagnante, il lui faut quand même un programme...

P.S. j'était content de voir qu'une partie du raisonement est axé sur la notion de menace et sur la question de savoir qui vas être obligé de jouer le 'trou'. Par contre d'autres parties m'avaient totalement échapées...

par **ffpower** » 12 Déc 2009, 16:55

Ah compter la parité du nb de coups restants,quand j étais petit je gagnais souvent mon grand père grace a ca^^
J'étais allé un peu regarder le "machin" comme tu dis, mais il parlait d'un programme qu'il utilisait,ca m'avais refroidi. Je rejetterai un coup d oeil alors peut être...

par **Ben314** » 12 Déc 2009, 17:46

En fait, les neuf dixièmes de l'article expliquent... ce qu'il a mis dans le programme et c'est trés "humainement compréhensible" et avec des tonnes d'exemples.

par **Sve@r** » 20 Déc 2009, 14:59

J'ai participé durant qq années a des tournois d'Othello, jeu de stratégie de retournement de pièces où on compte à la fin les pièces de sa couleur. Ce jeu se joue traditionnellement sur un plateau 8x8 mais on peut trouver des parties en 10x10.
Et je sais que la stratégie gagnante de ce jeu a été trouvée pour un plateau 6x6. c.a.d. que l'ordinateur est capable de calculer tous les coups possibles sur un plateau 6x6 et donc de choisir le meilleur coup pour chaque coup de l'adversaire. Et dans ce jeu, sur un 6x6, ce sont les noirs (qui commencent) qui gagnent.

Strategie gagnante

strategie gagnante

Qui est en ligne