Stratégie

Les principes

La stratégie du jeu est basée sur l'évaluation de la situation du jeu. Il existe des situations "gagnantes". Si vous trouvez le jeu dans une situation gagnante, quel que soit votre coup vous ne le laisserez pas dans une situation gagnante. Par contre si vous ne le trouvez pas dans une situation gagnante, vous pourrez trouver un "coup gagnant" pour mettre le jeu dans une situation gagnante, votre adversaire ne pourra alors que vous le laisser dans une situation non gagnante, et si vous ne faites pas d'erreur par la suite vous êtes sur de gagner.

Le choix du joueur qui commence est très important. Avec les options par défaut, la situation de départ est gagnante, et le joueur qui commence ne peut gagner que si son adversaire fait une erreur (et si vous jouez contre l'automate et choisissez de commencer vous ne devriez pas pouvoir gagner car l'automate est programmé pour ne pas faire d'erreur!).

Par contre vous pouvez par les préférences modifier l'état initial pour que ce soit une situation non gagnante. Alors celui qui commence sera avantagé puisqu'il pourra mettre le jeu dans une situation gagnante.

Si vous souhaitez des informations sur les principes sur lesquels se base cette stratégie, vous trouverez un très bon article sur les jeux de Nim dans la version anglaise de Wikipedia.

L'évaluation de la situation

L'évaluation de la situation de jeu dépend de l'option de fin de jeu : option dite "misère" (celui qui est contraint de ramasser le dernier objet perd), ou option dite "normale" (celui qui peut ramasser le dernier objet gagne). Cette évaluation demande des petits calculs arithmétiques qui sont les mêmes pour les deux options.

Calculs

Appelons N le nombre maximum d'objets ramassables incrémenté de 1. L'évaluation de la situation de jeu demande des calculs de modulo N (notés usuellement %N), reste de la division entière par N, et d'où exclusif binaire (noté usuellement ^), ou exclusif bit à bit sur la représentation binaire des deux nombres.

Soit n_i le nombre d'objets de chaque tas et m le nombre de tas.

On commence par calculer les restes modulo N pour les m tas : r_i=n_i%N

On fait ensuite un où exclusif de tous les restes :

s= r₁ ^ r₂ ^ ….. ^ r_m

Option dite"normale" (celui qui peut ramasser le dernier objet gagne)

La situation est gagnante si s est nul.

Option dite "misère" (celui qui est contraint de ramasser le dernier objet perd)

Si il y a au moins un reste supérieur à 1, la situation est gagnante si s est nul

S'il n'y a pas de reste supérieur à 1, la situation est gagnante si s=1.

La recherche du meilleur coup

Si vous avez trouvé le jeu dans une situation gagnante, vous le laisserez dans une situation non gagnante, et votre seul espoir est que votre adversaire fasse une erreur, essayez de mettre le jeu dans une situation inhabituelle pour lui...

Par contre si vous avez trouvé le jeu dans une situation non gagnante vous pourrez par le calcul trouver un ou plusieurs coups gagnants. Selon les mathématiciens vous devriez toujours trouver au moins un coup gagnant. Le calcul dépendra en partie de l'option de fin choisie, "normale" ou "misère".

Nous partirons pour ces calculs de N nombre maximum ramassable incrémenté de un, des nombres d'objets n_i de chacun des tas, et des calculs faits pour l'évaluation de la situation : restes r_i et résultat s des où exclusifs.

Option dite "normale"

Les coups gagnants sont ceux qui font passer s de sa valeur actuelle à 0.

On calcule pour chaque tas d_i=r_i-s ^ r_i. Alors :

A) si d_i est supérieur à 0, enlever d_i objets au tas i est un coup gagnant.

B) si d_i est inférieur à 0, n_i supérieur ou égal à N, et N+ d_i est supérieur à 0, enlever N+ d_i objets au tas i est aussi un coup gagnant.

Option dite "misère"

Les coups gagnants seront ceux qui font passer s de sa valeur actuelle à 0 avec au moins un reste supérieur à 1, ou qui feront passer s à 1 avec tous les restes à 0 ou 1.

Le calcul des coups gagnants dépendra de la situation trouvée :

A) il y a plus d'un reste supérieur à 1 : on applique le même algorithme que dans l'option dite "normale".

B) un seul reste est supérieur à 1 : pour le tas où le reste est supérieur à 1, on peut enlever un nombre d'objets égal à ce reste, ou ce reste moins 1, selon le nombre de restes déjà à 1, en vue de laisser un nombre impair de restes à 1 ; pour les autres tas on peut trouver d'autres coups gagnants en appliquant le B de l'option dite "normale".

C) tous les restes sont à 0 ou 1 (la position est supposée être non gagnante, il y a un nombre pair de restes à 1) : on peut soit enlever 1 objet sur un des tas où le reste est à 1, soit enlever N-1 objets sur un des tas où le reste est nul mais le nombre d'objets non nul (s'il existe de tels tas).

Cas particuliers

Les calculs sont plus simples s'il y a peu de tas ou d'objets ramassables

Jeu à un seul tas

Dans l'option dite "normale", la situation est gagnante si le reste modulo N du nombre d'objets est nul. Dans l'option dite "misère", la situation est gagnante si ce reste égale 1.

Si la situation est non gagnante, dans l'option dite "normale" le coup gagnant est d'enlever le nombre d'objets égal au reste. Dans l'option dite "misère", le coup gagnant est d'enlever un nombre d'objets égal au reste décrémenté de 1 si le reste est supérieur à 1, et d'enlever N-1 objets si le reste est nul (on supppose la partie non finie, il reste alors au moins N objets).

Jeu à 2 tas

Appelons r₁ et r₂ les restes modulo N des nombres d'objet des tas avec r₁ supérieur ou égal à r₂.

Dans l'option dite "normale" la situation est gagnante si r₁=r₂. Si ces restes sont différents, le coup gagnant est celui qui les remet identiques, en enlevant un nombre d'objets, soit égal à r₁-r₂ au tas de reste r₁, soit égal à N-r₁+r₂ au tas de reste r₂ s'il a encore au moins N objets.

Dans l'option dite "misère", la situation est gagnante si r₁ est supérieur à 1 et que r₁=r₂, ou si r₁=1 et r₂=0. Si r₁ et r₂ sont supérieurs à 1, les coups gagnants sont les mêmes que dahs l'option dite "normale". Si r₁ est supérieur à 1 et r₂ vaut 0 ou 1, les coups gagnants sont enlever r₁+r₂-1 objets au tas de reste r₁, ou enlever N-r₁+r₂ objets au tas de reste r₂, s'il a au moins N objets. Enfin si r₁ et r₂ valent tous les deux 1, les coups gagnants sont d'enlever 1 objet à l'un des tas, et s'ils valent tous les deux 0, c'est enlever N-1 objets à un tas qui a encore des objets.

Cas où N égale 2

On ne peut enlever qu'un objet à chaque coup, on est toujours dans la situation ou les restes sont à 0 ou 1. Dans l'option dite "normale" la situation est gagnante si le nombre total d'objets est pair, et dans l'option dite "misère" si ce nombre est impair. On peut s'apercevoir que tous les coups sont équivalents, le tas d'où l'on retire un objet n'a pas d'importance. Ce cas de jeu n'a donc pas d'intêret car on peut connaitre le vainqueur avant le début du jeu : le premier joueur dans l'option dite "normale" si le nombre total d'objets est impair, et le second joueur s'il est pair, et l'inverse dans l'autre option.