1.2 Existence de stratégies toujours gagnantes
3
FIGURE 1.4 - Un damier tronqué coloré
La réponse est non, elle se trouve plus facilement que dans le cas du problème numéro
1. On utilise une représentation qui guide naturellement vers la solution. En effet, on
peut observer que pour remplir le damier complet avec des dominos, cela ne pose pas de
problème. On observe aussi que chaque case noire est voisine de cases blanches et viceversa. On est donc obligé de remplir une case blanche à chaque fois qu'on remplit une
case noire. Or dans le cas du damier tronqué, il manque deux cases blanches. On ne pourra
donc pas le remplir puisqu'il y a deux cases noires de plus que de cases blanches. Il arrive
souvent qu'un problème soit difficile avec une représentation et facile avec une autre
représentation. Les chercheurs sur la reformulation automatique de problèmes essaient
d'écrire des programmes qui se déplacent dans l'espace des représentations pour trouver
celle qui est la plus appropriée à la résolution d' un problème.
1.2 Existence de stratégies toujours gagnantes
"- Combien de coups d'avance un grand maître calcule-t-il habituellement?"
"- Un seul."
Richard Réti.
Un exemple de jeu résolu pour lequel il existe une stratégie simple pour gagner est
le jeu de Nim. Le jeu de Nim se joue à deux. On dispose de plusieurs tas d'allumettes,
chaque joueur prend à son tour autant d'allumettes qu'il le veut dans un tas. Le gagnant
est le joueur qui prend la dernière allumette. On joue habituellement le jeu de Nim en
commençant avec quatre tas de 1, 3, 5 et 7 allumettes. La stratégie gagnante consiste
à transformer le nombre d'allumettes de chaque tas en sa représentation binaire. On fait
alors la somme binaire sur chaque bit de la représentation binaire des nombres sans utiliser
la retenue (ce qui est équivalent à faire un XOR des nombres). Si la somme binaire (ou le
XOR) vaut 0, on est dans une position sûre, ce sont les positions qu'on cherche à atteindre
lorsqu'on joue un coup. Si par contre on se retrouve après un coup dans une position non
sûre, on a perdu.
3
FIGURE 1.4 - Un damier tronqué coloré
La réponse est non, elle se trouve plus facilement que dans le cas du problème numéro
1. On utilise une représentation qui guide naturellement vers la solution. En effet, on
peut observer que pour remplir le damier complet avec des dominos, cela ne pose pas de
problème. On observe aussi que chaque case noire est voisine de cases blanches et viceversa. On est donc obligé de remplir une case blanche à chaque fois qu'on remplit une
case noire. Or dans le cas du damier tronqué, il manque deux cases blanches. On ne pourra
donc pas le remplir puisqu'il y a deux cases noires de plus que de cases blanches. Il arrive
souvent qu'un problème soit difficile avec une représentation et facile avec une autre
représentation. Les chercheurs sur la reformulation automatique de problèmes essaient
d'écrire des programmes qui se déplacent dans l'espace des représentations pour trouver
celle qui est la plus appropriée à la résolution d' un problème.
1.2 Existence de stratégies toujours gagnantes
"- Combien de coups d'avance un grand maître calcule-t-il habituellement?"
"- Un seul."
Richard Réti.
Un exemple de jeu résolu pour lequel il existe une stratégie simple pour gagner est
le jeu de Nim. Le jeu de Nim se joue à deux. On dispose de plusieurs tas d'allumettes,
chaque joueur prend à son tour autant d'allumettes qu'il le veut dans un tas. Le gagnant
est le joueur qui prend la dernière allumette. On joue habituellement le jeu de Nim en
commençant avec quatre tas de 1, 3, 5 et 7 allumettes. La stratégie gagnante consiste
à transformer le nombre d'allumettes de chaque tas en sa représentation binaire. On fait
alors la somme binaire sur chaque bit de la représentation binaire des nombres sans utiliser
la retenue (ce qui est équivalent à faire un XOR des nombres). Si la somme binaire (ou le
XOR) vaut 0, on est dans une position sûre, ce sont les positions qu'on cherche à atteindre
lorsqu'on joue un coup. Si par contre on se retrouve après un coup dans une position non
sûre, on a perdu.