Cette énigme permet d’aborder un domaine important de l’intelligence artificielle : les programmes qui jouent. Depuis le milieu du XXe siècle jusqu’à la révolution amenée par le deep learning et les réseaux de neurones dans les années 2010, et rendue possible par l’augmentation de la puissance des machines, ces logiciels faisaient partie des réussites les plus populaires de l’IA. Si les dames, les échecs (voir page 64) ou le go dépassent de loin le cadre de cet ouvrage, il est possible de découvrir un certain nombre de principes de base à l’aide de jeux beaucoup plus simples, comme le morpion, le Puissance 4 ou encore le jeu de Nim.Énigme 10 : Saurez-vous modéliser le jeu de Nim avec un graphe, et vous en servir pour déterminer lequel des deux joueurs a une stratégie gagnante, puls la mettre en œuvre ? Le programme doit fonctionner pour un jeu de Nim avec n allumettes au départ, et dans lequel il est possible d’enlever 1,2,…, p allumettes à chaque tour, quelles que soient les valeurs de n et p. Rappel : le perdant est le joueur qui est obligé de prendre la dernière allumette.
Soultion page 171…