Prépa Code Connexion Inscription

On considere une version simple du jeu de Nim : un tas contient n allumettes. A tour de role, chaque joueur retire 1, 2 ou 3 allumettes. Celui qui prend la derniere gagne.

Ecrire une fonction position_gagnante_nim(n, joueur) qui renvoie True si le joueur dont c'est le tour peut gagner en jouant de facon optimale (strategie parfaite), False sinon.

Le parametre joueur vaut 0 ou 1 et designe le joueur courant. La valeur renvoyee ne depend que de n (la symetrie du jeu fait que le joueur courant est toujours celui qu'on considere). Le parametre est present pour permettre une ecriture generique de la recurrence minmax.

Contrainte : implementer l'algorithme minmax recursif, sans memoisation, en considerant les 3 coups possibles. Les tests se limiteront a n <= 20.