F-Nim

[diapublication, suivi vers fr.rec.jeux.enigmes]

Bonjour,

Voici un autre jeu qui, une fois résolu stratégiquement, pourra fournir
le sujet d'une programmation en Python[¹].

Comme dans le(s) jeu(x) de Nim, c'est un jeu à deux joueurs dans lequel
il s'agit de retirer des allumettes jusqu'à ce qu'il n'en reste plus.
Voici la règle complète.

==========================================================================
On a un seul tas de N allumettes. Le premier joueur retire le nombre
d'allumettes qu'il veut, sa seule interdiction étant de retirer la
totalité du tas. Ensuite, chaque joueur retire un nombre d'allumettes
de son choix, entre 1 allumette et deux fois le nombre d'allumettes
que vient de retirer son adversaire. Le gagnant est celui qui retire la
dernière allumette et vide le tas.
==========================================================================

Il s'agit de trouver la meilleure stratégie pour chaque joueur en fonction
de la taille N du tas au départ.

==========================================================================
Prenons un exemple avec N = 15.
Le premier joueur A doit retirer un nombre d'allumettes compris entre
1 et 14 (il n'a pas le droit de tout retirer au premier coup).

Supposons que A retire 4 allumettes, il en reste 11.
Alors B peut retirer n'importe quel nombre entre 1 et 8 (8 = 2×4).
B retire 3 allumettes, il en reste 8.
A peut retirer n'importe quel nombre entre 1 et 6 (6 = 2×3).
A retire 1 allumette, il en reste 5.
B peut retirer n'importe quel nombre entre 1 et 2 (2 = 2×1)
B retire 1 allumette, il en reste 4.
A peut retirer n'importe quel nombre entre 1 et 2 (2 = 2×1)
A retire 1 allumette, il en reste 3.
B peut retirer n'importe quel nombre entre 1 et 2 (2 = 2×1)
B retire 2 allumettes, il en reste 1.
A retire la dernière allumette, il a gagné.

Noter que B aurait pu ne retirer qu'une allumette à son dernier coup,
mais ça n'aurait rien changé parce que A aurait pu retirer les deux
dernières allumettes et gagner quand même.
==========================================================================


[¹] Pour info, j'ai eu un tel programme (pas en python !) dans une
calculette TI 58 dotée d'une mémoire (programme + données) de 480
octets. Ce programme était capable de gagner systématiquement dès
qu'il était dans une situation permettant de le faire. Je crois même
que le programme pouvait tourner sur une TI 57 (seulement 50 octets
de mémoire disponibles pour le programme, les données étant à part).

--
Olivier Miakinen