Qui veut jouer au morpion ?

[Vassillia]

Bonjour,

Imaginons une feuille de papier quadrillé infini.
Je vais jouer en premier et faire 1 seule croix verte dans une case, mon adversaire va jouer à son tour et faire n croix rouge dans des cases.
Et ainsi de suite mais on ne peut ni l'un ni l'autre faire une croix dans une case déjà utilisée.

Mon objectif est de construire 4 croix formant un carré, l'objectif de mon adversaire est de m'en empêcher.
Pensez-vous que je vais gagner dans tous les cas pour n=1 ? pour n=2 ? ... Et si oui, comment ?
A partir de quel rang n, pensez que je vais être envahie par les croix rouges et je ne pourrai plus m'en sortir ?

PS : Vous pouvez considérer que je suis têtue et que j'ai le temps de faire autant de croix que nécessaire pour avoir une stratégie gagnante.

[lyceen95]

Le joueur A devrait systématiquement gagner. Le nombre de 'menaces' qu'il peut créer augmente de façon plus ou moins exponentielle, alors que le nombre de cases couvertes par B n'augmente que de façon affine.
Donc, forcément, à un moment, B ne peut plus couvrir toutes les menaces.
Je suis bien conscient que l'argument 'plus ou moins exponentielle' est insuffisant !
Si n=1, A a une stratégie qui lui permet de gagner au 5ème mouvement. f(1)=5.
Il faudrait trouver la forme générale de cette fonction f.
Et pour ça, il faudrait déjà bâtir la bonne stratégie pour n=2

PS : je pars du principe que A a le droit de dessiner un carré dont les bords ne sont pas parallèles au quadrillage. Si les bords du carré doivent forcément être parallèles au quadrillage, ça change pas mal de choses.

[Vassillia]

Bonjour Lyceen95,

Bien pensé, effectivement, je vais gagner systématiquement quelque soit le nombre de croix de mon adversaire fixé à l'avance. Une méthode pour le cas n=1 où les cases grisées sont les possibilités de mon adversaire pour m’embêter.

Quoi qu'il joue au tour 2 (même en dehors des cases grisées), je choisis la case grisée opposée.
Au tour 3, il est contraint de me bloquer sinon j'ai gagné.
Au tour 4, il ne peut plus rien faire car les 2 cases grisées me donnent un carré.

Cela pourrait être intéressant d'avoir la fonction f dont tu parles, j'avoue ne pas l'avoir, je ne trouve pas du tout cela facile à optimiser. Si tu as des idées, je suis preneuse.
En revanche, en y allant comme une bourrine (mais genre très très bourrine) sur le nombre de tours, on a un majorant permettant de gagner avec un carré dont les cotés sont bel et bien parallèles au quadrillage pour n quelconque.

[lyceen95]

La menace après la 4 ème position est double : un carré avec les côtés parallèles au quadrillage, et un autre avec les diagonales parallèles au quadrillage.
Si on se limite aux carrés avec les côtés parallèles aux axes, ça équilibre la partie.
Ici une partie , avec n=1, et cette variante (côtés parallèles au quadrillage) où A gagne au 11ème mouvement.
Les chiffres rouges = les cases jouées par A
Les chiffres noirs = les cases jouées par B
Les cases sur fond jaune = les coups imposés. B devait jouer cette case, sous peine de perdre immédiatement.
Après le coup n°11, les 2 cases bleues sont les 2 menaces, B ne peut en couvrir qu'une.
Peut-être que B a mal joué au coup n°6 ? Non, en fait le coup 6 était lui aussi un coup imposé. Si B laisse A jouer cette case, B perd au tour suivant.



Edit : En fait, au coup n°6, B doit couvrir la case en bas ... mais aussi la case symétrique en haut.
La suite normale de la partie :

En fait, A gagne au coup n°8 ... sauf si on considère que le coup n°5 de B n'était pas optimum.

Edit n°2 :
Le coup n°5 de A n'était pas optimum.
Dans cette nouvelle proposition, après le coup n°5 de A, les 2 cases vertes sont des menaces de 'mat en 2'.
B peut couvrir une seule de ces 2 menaces ; A va donc gagner au coup n°7.

[Vassillia]

Très joli de gagner en 7 coups avec cette nouvelle contrainte, je n'ai pas mieux à proposer.

Je te laisse regarder ce qu'on peut faire si l'adversaire met plus de croix à chaque tour, je suis malheureusement encore très loin de la version optimale donc je continue à chercher de mon coté.

[lyceen95]

Ca peut être la base d'un jeu pas idiot du tout.
On a un goban (19x19).
Le joueur A a 60 pierres blanches, le joueur B a 100 pierres noires. ( à voir si ces nombres sont bien adaptés)
A chaque tour de jeu, A pose une pierre sur le goban. Puis B pose autant de pierres qu'il le souhaite (éventuellement 0).
L'objectif de A est de former un carré, et l'objectif de B est bien sûr de le bloquer.

Si A forme un carré, mais ne s'en rend pas compte, si le joueur B le signale, c'est B qui gagne.

Variante : l'objectidf de A est de former autant de carrés que possible. Et ensuite, on inverse les rôles.
Dans ce cas, on modifie un peu les nombres de pierres au départ : 60 pour A, et 95 seulement pour B.

[Vassillia]

Ce serait sympa, c'est vrai, il faudrait tester l'équilibrage avec des joueurs non expérimentés puis expérimentés enfin si ça n'existe pas deja ? Je n'en sais rien. Je veux bien être ta partenaire de jeu le cas échéant.

Il faut que je me dépêche de trouver la stratégie optimale si l'adversaire fait n croix à chaque tour même en gardant la contraire côtés parallèles au quadrillage. Pour l'instant la méthode à laquelle je pense fait l'affaire pour l'exercice mais n'est pas applicable avec un quadrillage de taille raisonnable. Si tu veux que je te la donne, n'hésite pas, en attendant je laisse chercher.