Le prolog

26 mars 2011 par Arnaud

J’ai eu quelques retours sympathiques sur l’article au sujet du LISP dans le meilleur de Wikipedia donc merci pour les gentils e-mails.

Voici donc un autre au sujet d’un autre langage utilisé quand on branlotte un peu l’intelligence artificielle: le Prolog (rassurez-vous, cette catégorie continuera à traiter des sujets autres que l’informatique)

J’y avais donné 2 exemples qui n’étaient pas anodins : le sudoku et les échecs.

Commencons par plus simple : comment un cerveau humain fait pour sortir d’un labyrinthe dans les jeux de la page 24 de Tele 7 jour ?

Tout simplement, il prend un chemin, n’importe lequel, le premier pourquoi pas et quand il est bloqué, il revient sur ses pas jusqu’au précèdent embranchement. A la place de prendre à gauche, il prend à droite. Des fois, il arrive à la conclusion qu’il est dans une entière portion qui ne mène nulle part donc il revient encore en arrière.

Le sudoku fonctionne avec le même principe. Quand on n’a plus aucun choix, on fait une hypothèse ; on écrit au crayon un chiffre et on poursuit le jeu jusqu’à ce qu’il y ait une erreur.  Des fois, on est encore bloqué donc on tente une autre hypothèse en écrivant un autre chiffre. En algorithmique, c'est la récursivité ; on re-applique son propre processus, sa même logique à un niveau inférieur.

http://fr.wikipedia.org/wiki/Algorithme_r%C3%A9cursif

(lisez l'exemple préliminaire. Il est pas mal. Passez la phase mathématiques, c'est imbitable, surtout après la cuite du vendredi soir)

Toujours est-il que cette façon d'explorer chaque chemin jusqu'à que l'on soit coincé a un nom : la négation par l’échec. La NAF.

http://fr.wikipedia.org/wiki/N%C3%A9gation_par_l%27%C3%A9chec

(imbitable également mais vous aurez compris le principe)

Pour les échecs -le jeu-, ça devient encore plus compliqué car on ne sait pas ce que l’adversaire va jouer mais c’est là aussi le même principe. Il faut juste rajouter le “si j’avance cette pièce et que l’adversaire bouge celle-la que je bouge celle-ci, etc.”. On peut donc imaginer les milliards de milliards de combinaisons.

Sortir d’un labyrinthe, résoudre un sudoku ou gagner une partie d’échecs, l’ordinateur a un avantage certain : il calcule plus vite que nous.

Le joueur a par contre lui aussi un avantage comme l’Histoire des échecs. Bien souvent, des placements de pièces peuvent rappeler la partie de Protchov contre Patatov au tournoi de 1967 en Patagonie Occidentale par exemple.

Tout de même, un petit résumé peut être trouvé ici :

http://fr.wikipedia.org/wiki/Echecs#.C3.89checs_et_informatique

Venons-en au langage d’IA comme le Prolog.

Selon le Lisp, tout est liste. Plus intéressant, une liste est composée d’un premier de la liste et du reste. Une ligne de métro est juste la prochaine station, et le reste de la ligne le reste de la liste. Si la prochaine station n’est pas la bonne et bien la prochaine station est la première de la ligne et le reste de la ligne est dans la liste. Un bon gros putain de cauchemar.

le Prolog est au contraire un langage qui teste toutes les possibilités, les enregistre et prend la meilleure.

L’article Wikipedia est bien ficelé car il donne des exemples qui peuvent parler à tout le monde.

http://fr.wikipedia.org/wiki/Prolog

Et c’est Francais, cocorico!

Il y est mentionné son usage en linguistique, je travaille sur post la-dessus.