F-Nim

[Olivier Miakinen]

[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

[Olivier Miakinen]

[copie et suivi vers fr.comp.lang.python]

Le 22/10/2022 06:36, Dominique a écrit :
>
> J'ai corrigé en lignes 17 à 22 :
>
> nbf=0
> while nbf<3:
> nbf=int(input('Combien de frites au départ \(Au minimum 3\) ? '))
> nbm=0
> while nbm<2:
> nbm=int(input('Combien de frites pouvons-nous manger à chaque tour
> \Minimum 2\) ? '))

Comme je viens de reprogrammer en python ce programme de F-Nim dont
je parlais, je me suis fait une petite routine de saisie d'entier
avec nombre mini et éventuellement maxi :

=======================================================================
def saisie(message, mini, maxi = 0):
if maxi <= 0:
invite = f'{message} (au moins {mini}) ? '
erreur = f'Vous devez choisir un nombre au moins égal à {mini}.'
else:
invite = f'{message} (entre {mini} et {maxi}) ? '
erreur = f'Vous devez choisir un nombre entre {mini} et {maxi}.'
result = int(input(invite))
while result < mini or result > maxi > 0:
print(erreur)
result = int(input(invite))
return result
=======================================================================


Exemple :
=======================================================================
print("Bienvenue à F-Nim !")
have = saisie("Combien d'objets au départ", 2)
percent = saisie("Pourcentage de fiabilité du programme", 0, 100)
=======================================================================

Résultat :
=======================================================================
Bienvenue à F-Nim !
Combien d'objets au départ (au moins 2) ? 1
Vous devez choisir un nombre au moins égal à 2.
Combien d'objets au départ (au moins 2) ? 10
Pourcentage de fiabilité du programme (entre 0 et 100) ? 110
Vous devez choisir un nombre entre 0 et 100.
Pourcentage de fiabilité du programme (entre 0 et 100) ? 50
=======================================================================


--
Olivier Miakinen