— Fais voir un peu ton problème ?
— (ref)
— Ah oui. Il faut déterminer si avec un plateau donné on finit avec un seul pion ou non.
— Voilà.
— Eh bien tu écris un programme qui part du plateau initial, essaye successivement tous les coups possibles, et affiche “yes” dès que le coup produit une situation où il ne reste plus qu’un pion, et “no” s’il a essayé tous les coups possibles. Par exemple, 01100110, ça donnerait :

01100110
  → 00010110 
  →→ 00010001 ❌
    → 00011000
      →→ 00000100 ✅
      →→ 00100000 ✅
  → 10000110
    →→ 10000001 ❌
    →→ 10001000 ❌
  → 01100001
    →→ 00010001 ❌
    →→ 10000001 ❌
  → 01101000
    →→ 00011000
      →→→ 00000100 ✅
      →→→ 00100000 ✅
    →→ 10001000 ❌

— C’est ça. Il y a juste un problème…
— Évidemment ça va être un programme récursif, ou bien qui utilise une pile, pour stocker les états intermédiaires de façon à y revenir après avoir exploré une branche.
— Justement. Relis la spec.
— Eh ben ? Ah oui. “Un entier positif n ≤ 32000 représentant la taille du plateau”. Ouch.
— Tu vois le problème.
— Et ton IA, elle dit quoi ?
— Elle s’entête à optimiser des trucs à la marge. Elle dit qu’il faut prendre un format binaire. Elle dit qu’il faut mémoïser les résultats.
— Elle a raison, regarde sur notre exemple il y a déjà des positions redondantes. Par ex. si la situation 10000110 conduit à un échec, inutile d’examiner la situation 01100001 qui est son inverse exact !
— C’est pas faux.
— Elle te l’a trouvé, l’IA, cet optim’ ?
— Tu parles. Elle n’arrive même pas à capter n ≤ 32000. Elle dit “programme correct, conforme à la spec” mais en fait, non.
— Il doit y avoir un moyen…
— Autre que d’essayer de jouer tous les coups possibles tu veux dire ?
— Cette histoire de plateau de zéros et de uns, ça ressemble à un langage…
— Un langage ?
— Oui, par exemple, à chaque fois que tu vois 110 tu peux le remplacer par 001, on est d’accord ?
— Oui.
— Donc 110 est gagnant. OK ?
— Oui. Et aussi 0110, et 00110, et 001100…
— Expressions Régulières !!
— Hein ?
— On prend des expressions régulières !
— Ha ? Non, je ne vois pas.
— Mais si. On a :
010 qui dénote tous les plateaux contenant déjà un pion gagnant précédé de 0 à N cases vides, et suivi de 0 à N cases vides
— OK !
— Ensuite on a :
0*1100* qui dénote tous les plateaux dans lesquels on est à un coup de la victoire, en sautant à droite.
0*0110* la même, mais en sautant à gauche.
— En fait on peut ignorer celle là, en utilisant la précédente mais sur le plateau inversé.
— Pas khon !
— Ensuite ?
— On a
0*11010* qui dénote les plateaux dans lesquels on est à 2 coups de la victoire, en sautant à droite, puis à gauche.
— Et remarque un truc:
0*110101010* → 0*001101010* = 0*110101010* → 0*0011010* = 0*11010* → 0*00110* = 0*110* etc. Ça se réduit !
— Tu as raison, donc:
0*11(01)+010* est aussi une expression gagnante.
— Comment on trouve toutes les autres ?
— Bah demande à ton IA !

(à suivre)

dev-1-ai-0

Publié sur LinkedIn le 11/05/2025