En quête d'une demonstration mathématique

[invite229754d7]

Bonjour,

Je dois développer un jeu, cela fait partie de mon projet informatique. Et je rencontre quelques difficultées pour la 3e partie du projet qui necessite une approche purement mathématique pour la résolution du problème posé. Je vous serais reconnaisant si vous pouviez me proposer quelques pistes de recherches et me donner quelques indications.

Le projet consiste à programmer un jeu qui se presente sous la forme d'une grille à m ligne et n colonnes avec des cases pouvant prendre 2 couleurs (noir ou blanc). Au départ toutes les cases sont noires. Le but du jeu est de rendre la grille blanche mais ce jeu admet plusieurs règles que l'utilisateur peut choisir au début du jeu:
- en cliquant sur une case, le joueur change sa couleur ainsi que celle de ses 4 voisines (nord,sud,est,ouest)
- en cliquant sur une case, toute la colonne et ligne correspondante change de couleur
- le clic sur une case fait changer sa couleur ainsi que celles des 4 autres qui se situent dans le coin

Voici l'illustration en image:


... le choix des règles est completement libre et on peut en inventer autant qu'on veut.
Maintenant ce qui me pose problème c'est la résolution du jeu, i.e qu'il faut proposer un algorithme de recherche de solution. Comment je pourrais faire pour savoir si c'est possible de gagner ou non ? Et si c'est possible de gagner alors comment gagner ? Quelles cases faut-il cliquer ?

Merci d'avance.
H.F

PS: J'ai un niveau de Terminal S en math
-----

[Coincoin]

Salut,
Quand est-ce qu'on perd à ton jeu ?
Je suppose qu'un algorithme essayant toutes les possiblités est bien trop bourrin et peu efficace...

[invite56460777]

Je voudrais savoir quelque chose:
Je suis un joueur, Je clique sur une case et les autres se transforment en blanc suivant la règle choisie au départ.
Après mon premier coup, l'ordinateur peut-il noircir de nouveau des cases?

[invite229754d7]

Quand est-ce qu'on perd à ton jeu ?
Je suppose qu'un algorithme essayant toutes les possiblités est bien trop bourrin et peu efficace...

On ne perd jamais dans ce jeu

Essayer toutes les possibilités demande trop de calcul. Dans une petite grille de 5*5, on a 25 cases et chaque case peut prendre 2 statut donc on a 2^25 possibilités rien que pour le premier clic!

Je suis un joueur, Je clique sur une case et les autres se transforment en blanc suivant la règle choisie au départ.
Après mon premier coup, l'ordinateur peut-il noircir de nouveau des cases?

Oui, on peut cliquer autant de fois qu'on veut sur une case et on peut faire changer la couleur d'une case autant de fois qu'on veut.

Voici quelques pistes que j'ai:
- Rien ne sert de cliquer une case 2 fois car cela reviendra à n'avoir jamais cliquer dessus.
- De la même manière, si on visite une case (en cliquant dessus ou en changeant sa couleur de manière indirect en ayant cliqué sur une de ses voisines), cette case change de couleur. Si on visite une case un nombre impaire de fois, son statut est changé et passe de noir en blanc. Si on la visite un nombre pair de fois alors sa couleur reste inchanger.

J'avais posé la question à mon prof d'info, il ne connaît pas la méthode lui-même. Il dit que cela nécessite un travail de recherche et que à la fin avec tous les étudiants et tous les profs qui font ce projet on va bien arriver à trouver quelque chose.
On lui a dit que peut-être il n'y a jamais de solution apres tous et là il nous a répondu qu'il est capable de démontrer qu'il existe une solution ou non grâce aux systèmes linéaires mais que la démonstration ne nous est probablement pas accessible. (Je vais la demander par email pour voir de quoi elle a l'air...)

[A voir en vidéo sur Futura]

[Coincoin]

Si je comprends bien alors, le but du jeu est de minimiser le nombre de coups pour remplir la grille, c'est ça ?
Il faut voir comment toi tu jouerais et essayer de comprendre les raisonnements que tu fais pour pouvoir les porter dans une logique informatique (plus facile à dire qu'à faire, je te l'accorde)

[invite229754d7]

Si je comprends bien alors, le but du jeu est de minimiser le nombre de coups pour remplir la grille, c'est ça ?

Ce n'est pas vraiment ça. Il faut que l'ordinateur indique quelles cases cliquées pour pouvoir gagner si le joueur le demande. Donc quand l'ordinateur sera sollicité, il ne cliquera pas plusieurs fois sur une même case mais il peut très bien cliquer un très grand nombre de cases.

[shokin]

Il y a quand même un but. Sinon, l'ordinateur a plein de possibilités.

ça dépend des règles que tu choisis...

et je me doute que ce ne sera pas si simple... (du fait qu'aucune des deux couleurs ne prime sur l'autre, à moins... de bien préciser les règles...)

Shokin

[invite229754d7]

Il y a quand même un but. Sinon, l'ordinateur a plein de possibilités.

Le but est de rendre la grille blanche...

ça dépend des règles que tu choisis...

Chaque règle peut être traité séparément mais je pense qu'une méthode globale de recherche de solution doit pouvoir être trouver. Ce projet est completement libre et j'ai déjà fais le gros du travail qui consistait à le programmer en C. Maintenant la 3e partie est plus ouverte et même si je pense que je ne vais pas y arriver je continue à chercher. Et je préfère chercher une méthode globale que traiter les règles une par une.

[martini_bird]

Salut,

en fonction des dimensions m x n de la "matrice", toutes les règles ne permettent pas de gagner, n'est-ce-pas?

Par exemple si m=n=2, les règles 1 et 2 me font perdre.

Le choix des règles intervient donc dans la stratégie du joueur?

[invite229754d7]

en fonction des dimensions m x n de la "matrice", toutes les règles ne permettent pas de gagner, n'est-ce-pas?

En effet, il existe des cas où il n'y a aucunes solutions possibles.

[Evil.Saien]

Salut,
il y a longtemps maintenant j'avais fait un jeu d'echec ou l'ordinateur pouvait intervenir, et j'avais programmé comme algorithme que l'ordi verifie toutes les solutions plusieurs coups a l'avance...
Ici je me demande pourquoi tu fais pas pareil...
Au premier coup t'as pas 2^25 possibilités !!
T'as 25 cases a tester pour 3 coups différents, pour moi ca fait 25 * 3 coups possibles... soit 75 ! C'est vraiment rien

Maintenant le plus difficile c'est de trouver un bon critère de selection de la case. Ca peut etre:
- Le plus de cases blanches generées
- Le moins de cases noires génerées
- Le meilleur coup au long terme (pour cela faut vérifier toutes les possibilités pour un certain nombre de coup a l'avance, garder la meilleur combinaison et jouer le premier coup)
- Aléatoire il parait que le hasard fait bien les choses

[yat]

Pour n*m cases, l'algo bourrin donne 2^(n*m) combinaisons à tester (et pas au premier clic, mais pour toute la partie).
En effet, si j'ai bien compris les rêgles du jeu, l'ordre des clics n'a strictement aucune importance, et il est inutile de cliquer deux fois sur une case.

Au final, la seule chose à déterminer, c'est sur quelles cases on clique. On a donc n*m cases, et pour chacune, on doit essayer ce que ça donne en la cliquant et en ne la cliquant pas. On a donc bien deux possibilités pour chaque case, ce qui nous donne bien 2^(n*m) combinaisons.

En gros, avec un carré de 5 de coté, c'est tout à fait gérable, mais si on passe à 6 ça risque de prendre du temps, et avec 7 il vaut mieux oublier, et trouver un algo un peu moins beubeu.

Alors en approfondissant un peu, on peut déterminer pour chaque case quelles sont les cases qui la feront changer de couleur si on les clique, déterminer si le nombre de cases cliquées dans cet ensemble doit être pair ou impair (si le tableau est noir au début, tout doit êtrer impair car toutes les cases doivent changer de couleur, mais un ensemble associé à une case déjà blanche doit contenir un nombre pair de cases cliquées), et après il nous reste un système d'équations de parité à résoudre.

J'essaye pour un 2x2, avec la rêgle ligne et colonne (les cases sont numérotées de A à D, dans le sens de la lecture) :

Pour la case A, l'ensemble (A,B,C) doit contenir un nombre impair de clics. De même pour les ensembles (A,C,D), (A,B,D) et (A,B,C).

Du coup
B+C+D = impair
A+C+D = impair
A+B+D = impair
A+B+C = impair

Dans des équations de parité, + et - sont équivalents (si a+b est pair, a-b est pair...)
Donc, des deux premières équations on déduit B-A = pair, soit B+A = pair, donc d'après la quatrième équation, C = impair.
De même, on peut déduire que A, B, C et D sont impairs, donc égaux à 1, et par conséquent pour remplir tout le tableau il faut cliquer sur toutes les cases.

Pour prendre un autre exemple, je garde les mêmes rêgles, mais au départ la case A est déjà blanche. L'ensemble (A,B,C) doit donc contenir un nombre pair de cases cliquées.
J'ai donc :
B+C+D = impair
A+C+D = impair
A+B+D = impair
A+B+C = pair

Ce qui me donne :
A+B = pair donc C = pair
B+C = pair donc A = pair et B = pair.
C+D = impair donc D = impair.

Ce qui signifie qu'il faut cliquer uniquement sur la case D.

Pour faire un algo, un bon vieux pivot de Gauss des familles devrait faire l'affaire.

[Evil.Saien]

Je suis tjs pas d'accord avec le 2^(m+n) ! En effet, on va tester ce que donne le resultat si on clique sur une case, la je suis d'accord, mais pas si on clic pas dessus ! Je vois pas l'interet d'evaluer le reultat si on clic pas sur une case puisque rien ne change !
Prenons un carré 2x2, donc 4 cases...
On a alors 4 possibilité de clicage, 3 clic différent, donc au final 12 possibilité (<16)

[yat]

Je suis tjs pas d'accord avec le 2^(m+n) ! En effet, on va tester ce que donne le resultat si on clique sur une case, la je suis d'accord, mais pas si on clic pas dessus ! Je vois pas l'interet d'evaluer le reultat si on clic pas sur une case puisque rien ne change !
Prenons un carré 2x2, donc 4 cases...
On a alors 4 possibilité de clicage, 3 clic différent, donc au final 12 possibilité (<16)

Attention, ce n'est pas le nombre de possibilités pour un coup particulier. C'est le nombre total de combinaisons. Chaque case est cliquée ou ne l'est pas. L'ordre n'a strictement aucune importance.

Forcément avec ta méthode de comptage c'est beaucoup plus compliqué, mais je peux quand même te montrer ce que ça donne pour un tableau de 4 cases :
La première possibilité est de ne cliquer aucune case.
Ensuite, si on en clique une seule, il y a quatre possibilités.
Si on en clique deux, on a quatre possibilités pour la première, trois pour la deuxième, ce qui fait douze, mais comme l'ordre ne compte pas ça ne nous fait que 6 possibilités.
Si on clique trois cases, on a 4*3*2=24 possibilités, mais ces trois cases cochées peuvent l'être dans six ordres différents, ce qui nous laisse au final 4 possibilités.
Enfin, si on coche toutes les cases, il n'y a bien sur qu'une manière de le faire.

Au final, on a 1+4+6+4+1=16 combinaisons possibles.

Mais bon, il n'est pas nécessaire de se compliquer autant la vie. L'ordre n'a aucune importance, et il est inutile de cliquer une case plus d'une fois. La manière la plus simple de décrire une stratégie, c'est de dire pour chaque case si elle est cliquée ou pas (ou alors, cliquée un nombre pair ou impair de fois, ce qui revient au même). Pour n cases, on a donc tout naturellement 2ⁿ combinaisons, soit 2^(n*m) pour un tableau de n*m cases.

[Evil.Saien]

Ah oui, je me rend compte qu'on ne parlait pas du meme problème...
Moi je parlais d'une solution ou l'ordinateur devait intervenir pour proposer un coup au joueur. Dans ce cas, on ne peut pas vraiment faire d'algorithme génerale puisqu'on ne peut pas prévoir le situation du joueur.
Alors que toi tu proposes une méthode pour resoudre entierement le jeux...
Maintenant je suis d'accord avec toi.

[yat]

Ah oui, je me rend compte qu'on ne parlait pas du meme problème...
Moi je parlais d'une solution ou l'ordinateur devait intervenir pour proposer un coup au joueur. Dans ce cas, on ne peut pas vraiment faire d'algorithme génerale puisqu'on ne peut pas prévoir le situation du joueur.
Alors que toi tu proposes une méthode pour resoudre entierement le jeux...
Maintenant je suis d'accord avec toi.

En fait c'est pas encore tout à fait ça. Le problème dont tu parles est bien, à mon avis, l'énoncé de H.Filbert. Mais c'est aussi ce problème que je cherche à résoudre.

Simplement, on peut partir d'un tableau qui comporte déjà des cases blanches, comme je l'ai fait dans mon deuxième exemple. Et à partir de là, on connait les combinaisons de clics qui aboutissent à la résolution du problème (ce sont les solutions du système). Ce n'est, à mon avis, qu'en connaissance de ces combinaison que l'ordinateur peut proposer une case à cliquer : il suffit d'en prendre une au hasard parmi celles qui doivent l'être (c'est bien ce dernier point que je n'avais pas précisé, et qui est pourtant nécessaire pour répondre à la question initiale), et ce en fonction de la situation courante dans laquelle le joueur humain s'est empétré.

Pour faire plus efficace, on peut aussi calculer les combinaisons gagnantes au départ, et inverser le bit d'une case quand le joueur clique dessus. Il suffira donc au moment ou il demandera de l'aide, de choisir la combinaison qui comporte le moins de 1, et de prendre un de ces 1 au hasard.

[invite229754d7]

il y a longtemps maintenant j'avais fait un jeu d'echec ou l'ordinateur pouvait intervenir, et j'avais programmé comme algorithme que l'ordi verifie toutes les solutions plusieurs coups a l'avance...
Ici je me demande pourquoi tu fais pas pareil...

A mon avis il y a quelques différences qd même i.e que dans le jeu d'échec l'ordinateur peut bien calculer les coups à l'avance mais l'ensemble de ces calculs ne le menera pas forcement à la victoire. Tandis qu'ici l'ordi doit être capable de terminer le jeu s'il est possible de le terminer. L'ordi ne doit pas calculer les 3 meilleurs coups possibles mais les 3 coups qui font partie d'une certaine logique qui le menera à terminer le jeu donc ces 3 coups font déjà partie d'une suite de coups, déjà connus pour mener à la victoire.
Et le plus dur c'est de trouver cette logique qui fait gagner l'homme ou l'ordi à coup sur.

J'essaye pour un 2x2, avec la rêgle ligne et colonne (les cases sont numérotées de A à D, dans le sens de la lecture) :

Pour la case A, l'ensemble (A,B,C) doit contenir un nombre impair de clics. De même pour les ensembles (A,C,D), (A,B,D) et (A,B,C).

Du coup
B+C+D = impair
A+C+D = impair
A+B+D = impair
A+B+C = impair

Dans des équations de parité, + et - sont équivalents (si a+b est pair, a-b est pair...)
Donc, des deux premières équations on déduit B-A = pair, soit B+A = pair, donc d'après la quatrième équation, C = impair.
De même, on peut déduire que A, B, C et D sont impairs, donc égaux à 1, et par conséquent pour remplir tout le tableau il faut cliquer sur toutes les cases.

Pour prendre un autre exemple, je garde les mêmes rêgles, mais au départ la case A est déjà blanche. L'ensemble (A,B,C) doit donc contenir un nombre pair de cases cliquées.
J'ai donc :
B+C+D = impair
A+C+D = impair
A+B+D = impair
A+B+C = pair

Ce qui me donne :
A+B = pair donc C = pair
B+C = pair donc A = pair et B = pair.
C+D = impair donc D = impair.

Ce qui signifie qu'il faut cliquer uniquement sur la case D.

Pour faire un algo, un bon vieux pivot de Gauss des familles devrait faire l'affaire.

C génial ce que tu m'as passé là. Merci beaucoup
J'avais demandé ça à mon prof et il m'a répondu que c'est trop long de l'écrire par email et qu'il allait m'expliquer ça la semaine prochaine en TP. Donc merci encore pour tous le temps que tu as consacré à ça. J'ai une bonne base de travail maintenant.

Pour faire plus efficace, on peut aussi calculer les combinaisons gagnantes au départ, et inverser le bit d'une case quand le joueur clique dessus. Il suffira donc au moment ou il demandera de l'aide, de choisir la combinaison qui comporte le moins de 1, et de prendre un de ces 1 au hasard.

C'est une excellante idée

[invitea8961440]

A mon avis il y a quelques différences qd même i.e que dans le jeu d'échec l'ordinateur peut bien calculer les coups à l'avance mais l'ensemble de ces calculs ne le menera pas forcement à la victoire. Tandis qu'ici l'ordi doit être capable de terminer le jeu s'il est possible de le terminer. L'ordi ne doit pas calculer les 3 meilleurs coups possibles mais les 3 coups qui font partie d'une certaine logique qui le menera à terminer le jeu donc ces 3 coups font déjà partie d'une suite de coups, déjà connus pour mener à la victoire.
Et le plus dur c'est de trouver cette logique qui fait gagner l'homme ou l'ordi à coup sur.


C génial ce que tu m'as passé là. Merci beaucoup
J'avais demandé ça à mon prof et il m'a répondu que c'est trop long de l'écrire par email et qu'il allait m'expliquer ça la semaine prochaine en TP. Donc merci encore pour tous le temps que tu as consacré à ça. J'ai une bonne base de travail maintenant.


C'est une excellante idée

Et ton jeu sevira à quoi:à jouer sans aucun doute !

[invite229754d7]

Et ton jeu sevira à quoi:à jouer sans aucun doute !

Très bonne question.
Les exos de physique, math, bio etc. qu'on fait en lycée, fac, école, à quoi ils sert ?

[leg]

bonsoir filbert, il y a un livre interressant du moins je pense, c'est le livre de ian stewart, lunivers des nombres éditions belin pour la science.
www.edition-belin.com
www.pourlascience.com
a la fin de ce livre il y a toute une série de jeu mathem avec les explications mathématiques.
il y a aussi mathematique des jeux de jean paul delahaye même édition
A + leg.

[invite229754d7]

livre de ian stewart, lunivers des nombres éditions belin pour la science.

mathematique des jeux de jean paul delahaye même édition

Merci pour ces référence. Je vais voir si je les trouve à la bibliotèque.