Création d'intelligence artificiel
Introduction
L'intelligence artificiel est une discipline assez vaste, ici nous nous concentrerons sur une approche utilisable dans le domaine des jeux en ligne. De plus sachez que je(initiateur de l'article) ne suis pas du tout une référence j'ai tous juste suivis quelques cours sur le sujet. Cette article est donc parfaitement perfectible, et vous pouvez bien entendu l'améliorer.
Qu'entends t'on par IA?
IA forte et IA faible
En fait, il y a plusieurs type d'IA, certains chercheurs vont jusqu'à tenter de reproduire le mécanisme de la pensée et donc la conscience de soi, c'est ce qu'on appelle des IAs fortes!
Mais nous nous faisons des jeux en ligne et donc on va s'intéresser plutôt aux IA faibles, à savoir des algorithmes qui simulent l'intelligence. Attention faible ne veut pas dire que c'est facile à faire, de nombreux problèmes d'IAs faibles n'ont pas trouver de solutions optimales ou assez rapides. Voici quelques exemples de problème qu'on peut classer dans les IAs faibles:
Les heuristiques
Comme nous l'avons vu au dessus certains problèmes sont (trop) complexes. Cependant, ils peuvent être simplifié à l'aide d'heuristique c'est à dire à l'aide d'algorithmes faisant appels à des connaissances pour résoudre le problème plus vite mais de façon non optimale.
C'est par exemple ce que fait l'algorithme A star très connu dans le domaine du jeu vidéo et qui permet de calculer un des plus court chemin. En l'occurrence l'heuristique qu'utilise A* c'est d'"avancer vers la destination". C'est d'ailleurs une heuristique assez intuitive. Puis si on se trouve dans un cul de sac on rebrousse chemin et on condamne la zone. C'est d'ailleurs ce qui avait été oublié dans Age Of Empire 1 du coup les bonshommes restaient coincés dans un cul de sac formé par l'eau.
Comment faire?
Et oui c'est bien beau tout çà mais çà ne nous dit pas comment créer pratiquement une IA pour un jeuweb. Le problème c'est que c'est une vaste question, puisqu'elle revient à celle de la création d'un programme.
Spécifier le besoin
D'abord chercher à savoir ce que vous voulez faire, notamment avez vous besoin d'une solution parfaite et les ressources que vous seriez prêt à sacrifier pour avoir cette solution. N'oubliez pas qu'une IA simulant un adversaire doit rester possible à battre…
Par exemple, nous voulons créer une IA capable de jouer au tictactoe. Et ce dans un temps assez cours, maximum 3 secondes de réflexion. Nous souhaitons que cette dernière soit battable mais suffisamment stratégique pour gagner si on joue mal.
Décomposer le problème
Puis, il va vous falloir décomposer le problème afin d'en déduire la méthode et/ou les heuristiques(connaissances) à utiliser. Pour ce point vous pouvez chercher d'éventuel solution existantes à des problèmes identiques ou proches, vous pouvez aussi vous inspirer sur votre façon à vous de raisonner pour résoudre le problème.
De nombreux algorithmes spécifiques au tictactoe ou valable pour l'ensemble des jeux de stratégie à tour existent.
Mais la bonne question a se poser c'est comment je joue au tictactoe?
Et bien pour ma part:
- je connais le but à atteindre à savoir faire une ligne de 3 cases avec ma marques avant l'autre et avant qu'il n'y ai plus de cases vides
- j'observe les cases vide ou je peux jouer
- et je cherche à déterminer ce que l'autre pourrait jouer ensuite si je fais tel action. J'explore donc les solutions future pour un ensemble de case et j'en détermine quel est le meilleurs coup à jouer en essayant de maximiser mes chances d'atteindre le but en minimisant les chance de l'autre.
- si il y a plusieurs partie j'essaie d'endormir l'autre joueur
A noter qu'avant je connaissais (du moins je crois) tous les cas de figure, et avait donc une réponse automatique à chaque configuration du plateau. Notamment je me souviens des situations pièges soit parce que je les ai déjoué après une réflexion soit parce que j'ai perdu.
Et bien la première solution est l'exact description de la méthode min max(en dehors d'endormir l'autre). Cette méthode peut aussi servir à jouer d'autre jeu sans trop de hasard comme les échecs ou un jeu comme age of empire.
La seconde est due au fait que le tictactoe n'est pas un jeu très complexe du coup on peut aisément connaitre les solutions, on voit cependant l'intérêt de l'apprentissage que l'on peut voir un peu comme une mise en cache de situation déjà rencontré et qui ont nécessité un fort calcul par exemple.
Traduire le tout dans un langage
Puis il faut évidement traduire çà avec un langage de programmation, certains peuvent être plus adapté.
Dans le cas du tictactoe je présenterais une implémentation en prolog. Ce dernier à l'avantage de fonctionner grâce à un moteur d'inférence d'ordre 1, ce qui permet de faciliter le développement de nombreuses solutions d'intelligence artificiels.
Voici donc un exemples d'implémentation de la première méthode, il manque juste un petit facteur aléatoire pour choisir entre plusieurs solutions équivalentes:
tictactoe.pl
Voici ce que donne un exemple d'utilisation, j'ai d'ailleurs perdu par inadvertance! A noter que cette IA peut être parfaite si on lui pose une profondeur égale a 9. Il conviendrait donc d'insérer un facteur d'erreur ou de la faire jouer avec une profondeur faible.
NB: il y a peut être un bug au niveau des profondeurs
Prolog
Prolog signifie Programmation Logique, il s'agit d'un langages qui peut être interprété ou compilé. Il existe de nombreux interpréteurs/compilateurs mais les plus connues sont swi-prolog, scitus-prolog(proprietaire) et gnu-prolog. Dans ces exemples j'utilise GNU Prolog.
Ce qui est important de retenir c'est que prolog est base sur l'expressivité de la logique, on va bientôt découvrir de quoi je parle. Et Prolog peux déduire les choses grâce a son moteur d'inférence d'ordre 1.
Le moteur d'inférence
Un moteur d'inférence est un système capable de déduire une réponse a une question grâce a une base de règle et de fait.
Ça va peut être paraitre plus clair avec l'exemple typique de prolog:
helloworld.pl
Une fois la base de faits et de regles creer on peut l'interroger via l'interpréteur ou le code compilé.
Programmation par contrainte
Un autres avantages en Prolog est la programmation par contraintes.
De quoi s'agit il?
Pour faire simple certains problèmes sont juste des problèmes de contraintes. Avec Prolog, il suffit juste d'indiquer ces dernières et de lui demander de trouver une solution. Et ca marche pour beaucoup de problème a contrainte, cependant certains problèmes peuvent prendre trop de temps. Il est possible toutefois de pallier dans certains cas a ce problème en indiquant a prolog une heuristique, lors de la recherche de solution.
Le sudoku est un très bon exemples de problèmes a contraintes. Dans le cas du sudoku il n'y a pas de notion d'ordonnancement des actions, il suffit juste de trouver les chiffres. Ainsi les contraintes sont:
- une case ne peut contenir qu'un chiffre variant de 1 a 9
- les cases d'une ligne doivent contenir des chiffres tous différents
- idem pour les colonnes
- idem pour les 9 carrés du sudoku
sudoku.pl
Interfacer prolog et un autre langage
Vous me dire qu'ils sont bien beau tous mes exemples en prolog, mais votre jeu est en PHP ou autre chose…
Et bien ci dessous sont présentées quelques méthodes pour résoudre ce problème.
Interpréteur prolog dans le langage en question
La première méthode consiste en l'utilisation d'un interpréteur prolog construit avec le langage en questions.
En PHP
Vous pouvez trouver sur ce lien http://www.stefan-baur.de/projects/simpl...gplusplus/ le seul interpréteur du genre (je pense).
L'avantage:
Les inconvénients:
NB: je n'ai pas testé en ce qui concerne les performances, mais ca doit pas être le top du top.
En Ruby
On est très loin de la syntaxe mais les idées sont la notamment le moteur d'inférence
Depot du projet
Presentation rapide
L'avantage:
Les inconvenients:
NB: je n'ai pas testé en ce qui concerne les performances, mais ca doit pas être le top du top.
En C
La c'est très simple, il suffit d'utiliser les sources de gprolog ou équivalent, c'est la meilleure solution.
Voici donc la page du manuel qui parle de ca.
Il n'y a que des avantages pour le peu que c'est bien en C que vous faites votre projet!
En Java
http://sourceforge.net/projects/jprolog/
Le projet est pas mal avancé, mais n'implémente pas toutes les spécifications de prolog.
Interfacer prolog via socket
La seconde méthode consiste a communiquer avec prolog via les socket. La plus part des langages le peuvent a condition que l'hébergeur accorde cette possibilité.
Les avantages:
Les inconvénients:
Interfacer via system,exec ou exec_shell
La 3eme méthode consiste a utiliser les commandes d'exécution shell. C'est possible dans de nombreux langages a condition que l'hébergeur accorde cette possibilité. Ci dessous un exemple en php.
Comme dans cet exemple:
sudoku.php
Les avantages:
Les inconvénients:
— Zamentur 2010/03/04 00:50
Introduction
L'intelligence artificiel est une discipline assez vaste, ici nous nous concentrerons sur une approche utilisable dans le domaine des jeux en ligne. De plus sachez que je(initiateur de l'article) ne suis pas du tout une référence j'ai tous juste suivis quelques cours sur le sujet. Cette article est donc parfaitement perfectible, et vous pouvez bien entendu l'améliorer.
Qu'entends t'on par IA?
IA forte et IA faible
En fait, il y a plusieurs type d'IA, certains chercheurs vont jusqu'à tenter de reproduire le mécanisme de la pensée et donc la conscience de soi, c'est ce qu'on appelle des IAs fortes!
Mais nous nous faisons des jeux en ligne et donc on va s'intéresser plutôt aux IA faibles, à savoir des algorithmes qui simulent l'intelligence. Attention faible ne veut pas dire que c'est facile à faire, de nombreux problèmes d'IAs faibles n'ont pas trouver de solutions optimales ou assez rapides. Voici quelques exemples de problème qu'on peut classer dans les IAs faibles:
- Calculer l'itinéraire parfait pour un drone qui doit récupérer des troupes très dispersées sur une carte et çà avec un minimum de trajet. Ce problème est plus connu sous le nom de "voyageur de commerce". C'est ce qu'on appelle un problème NP-Complet, ce qui en d'autre termes veut dire qu'il ne peut être résolu qu'en listant les toutes possibilités et en cherchant la meilleurs parmi celles ci. Facile quand on a quelques points à relier mais quand on arrive à la quarantaine on dit plus la même chose…
- Faire un PNJ qui réponds au questions d'un joueurs de façon à ce que ce dernier ne sache pas si il s'agit d'un autre joueur ou d'un PNJ, ce PNJ passerait donc le test de Turing
- Jouer en déterminant une stratégie afin d'arriver à gagner dans un jeu (par exemple le tic tac toe ou le jeu de go).
- Remplir de façon optimale un sac à dos avec divers items plus connues sous le nom du problème du sac à dos…
Les heuristiques
Comme nous l'avons vu au dessus certains problèmes sont (trop) complexes. Cependant, ils peuvent être simplifié à l'aide d'heuristique c'est à dire à l'aide d'algorithmes faisant appels à des connaissances pour résoudre le problème plus vite mais de façon non optimale.
C'est par exemple ce que fait l'algorithme A star très connu dans le domaine du jeu vidéo et qui permet de calculer un des plus court chemin. En l'occurrence l'heuristique qu'utilise A* c'est d'"avancer vers la destination". C'est d'ailleurs une heuristique assez intuitive. Puis si on se trouve dans un cul de sac on rebrousse chemin et on condamne la zone. C'est d'ailleurs ce qui avait été oublié dans Age Of Empire 1 du coup les bonshommes restaient coincés dans un cul de sac formé par l'eau.
Comment faire?
Et oui c'est bien beau tout çà mais çà ne nous dit pas comment créer pratiquement une IA pour un jeuweb. Le problème c'est que c'est une vaste question, puisqu'elle revient à celle de la création d'un programme.
Spécifier le besoin
D'abord chercher à savoir ce que vous voulez faire, notamment avez vous besoin d'une solution parfaite et les ressources que vous seriez prêt à sacrifier pour avoir cette solution. N'oubliez pas qu'une IA simulant un adversaire doit rester possible à battre…
Par exemple, nous voulons créer une IA capable de jouer au tictactoe. Et ce dans un temps assez cours, maximum 3 secondes de réflexion. Nous souhaitons que cette dernière soit battable mais suffisamment stratégique pour gagner si on joue mal.
Décomposer le problème
Puis, il va vous falloir décomposer le problème afin d'en déduire la méthode et/ou les heuristiques(connaissances) à utiliser. Pour ce point vous pouvez chercher d'éventuel solution existantes à des problèmes identiques ou proches, vous pouvez aussi vous inspirer sur votre façon à vous de raisonner pour résoudre le problème.
De nombreux algorithmes spécifiques au tictactoe ou valable pour l'ensemble des jeux de stratégie à tour existent.
Mais la bonne question a se poser c'est comment je joue au tictactoe?
Et bien pour ma part:
- je connais le but à atteindre à savoir faire une ligne de 3 cases avec ma marques avant l'autre et avant qu'il n'y ai plus de cases vides
- j'observe les cases vide ou je peux jouer
- et je cherche à déterminer ce que l'autre pourrait jouer ensuite si je fais tel action. J'explore donc les solutions future pour un ensemble de case et j'en détermine quel est le meilleurs coup à jouer en essayant de maximiser mes chances d'atteindre le but en minimisant les chance de l'autre.
- si il y a plusieurs partie j'essaie d'endormir l'autre joueur
A noter qu'avant je connaissais (du moins je crois) tous les cas de figure, et avait donc une réponse automatique à chaque configuration du plateau. Notamment je me souviens des situations pièges soit parce que je les ai déjoué après une réflexion soit parce que j'ai perdu.
Et bien la première solution est l'exact description de la méthode min max(en dehors d'endormir l'autre). Cette méthode peut aussi servir à jouer d'autre jeu sans trop de hasard comme les échecs ou un jeu comme age of empire.
La seconde est due au fait que le tictactoe n'est pas un jeu très complexe du coup on peut aisément connaitre les solutions, on voit cependant l'intérêt de l'apprentissage que l'on peut voir un peu comme une mise en cache de situation déjà rencontré et qui ont nécessité un fort calcul par exemple.
Traduire le tout dans un langage
Puis il faut évidement traduire çà avec un langage de programmation, certains peuvent être plus adapté.
Dans le cas du tictactoe je présenterais une implémentation en prolog. Ce dernier à l'avantage de fonctionner grâce à un moteur d'inférence d'ordre 1, ce qui permet de faciliter le développement de nombreuses solutions d'intelligence artificiels.
Voici donc un exemples d'implémentation de la première méthode, il manque juste un petit facteur aléatoire pour choisir entre plusieurs solutions équivalentes:
tictactoe.pl
/**
* AI for the game Tic Tac Toe
* @author Valentin GRIMAUD http://ljf.no-ip.biz/book/
* @license http://creativecommons.org/licenses/by-sa/2.0/fr/
* @copyright Valentin GRIMAUD
* @version 1.1 alpha
* @sample
* play([[e,x,o],[e,e,e],[o,x,e]],x,X,Y,P,5).
* X=2
* Y=2
* P=10
* play([[e,e,e],[e,o,e],[e,e,e]],x,X,Y,P,5).
* end([[o,x,o],[x,x,o],[o,o,x]],X).
* play(+Tray,+Player,-X,-Y,-P,+Deep)
**/
/**
* Modify an element of a list
* @param + List list The original list
* @param - NewList list The new list
* @param + Index The index of the element to change
* @param + Value The new value of the element
**/
modify_list(_,_,Index,_):-Index=<0,!,fail.
modify_list([_|Q],[Value|Q],1,Value):-!.
modify_list([H|List],[H|NewList],Index,Value):-
NewIndex is Index-1,
modify_list(List,NewList,NewIndex,Value).
/**
* Modify an element of a matrice
* @param + List list The original matrice
* @param - NewList list The new matrice
* @param + Line The index of the line to change
* @param + Column The index of the element to change
* @param + Value The new value of the element
**/
modify_list(_,_,Line,_,_):-Line=<0,!,fail.
modify_list([HOld|Q],[H|Q],1,Column,Value):-
modify_list(HOld,H,Column,Value),!.
modify_list([H|List],[H|NewList],Line,Column,Value):-
NewLine is Line-1,
modify_list(List,NewList,NewLine,Column,Value).
/**
* Create a list with a head and a queue
* @param ? H The head of the list
* @param ? Q The queue of the list
* @param ? List The list compound of the head and the queue
**/
cons(H,Q,[H|Q]).
/**
* Check if the tray is full or not
* @param + list A list which represents the tray
**/
no_full_line([]):-!,fail.
no_full_line([e|_]).
no_full_line([_|Q]):-no_full_line(Q).
no_full([]):-!,fail.
no_full([H|_]):-no_full_line(H),!.
no_full([_|Q]):-no_full(Q).
/**
* Determine if a player has won
* @param + Tray list A list which represents the tray
* @param ? Winner The winner
**/
end([[x,x,x],[_,_,_],[_,_,_]],x):-!.
end([[_,_,_],[x,x,x],[_,_,_]],x):-!.
end([[_,_,_],[_,_,_],[x,x,x]],x):-!.
end([[x,_,_],[x,_,_],[x,_,_]],x):-!.
end([[_,x,_],[_,x,_],[_,x,_]],x):-!.
end([[_,_,x],[_,_,x],[_,_,x]],x):-!.
end([[x,_,_],[_,x,_],[_,_,x]],x):-!.
end([[_,_,x],[_,x,_],[x,_,_]],x):-!.
end([[o,o,o],[_,_,_],[_,_,_]],o):-!.
end([[_,_,_],[o,o,o],[_,_,_]],o):-!.
end([[_,_,_],[_,_,_],[o,o,o]],o):-!.
end([[o,_,_],[o,_,_],[o,_,_]],o):-!.
end([[_,o,_],[_,o,_],[_,o,_]],o):-!.
end([[_,_,o],[_,_,o],[_,_,o]],o):-!.
end([[o,_,_],[_,o,_],[_,_,o]],o):-!.
end([[_,_,o],[_,o,_],[o,_,_]],o):-!.
end(Trail,_):-no_full(Trail),!,fail.
end(_,e).
/**
* Write an action in the tray
* @param + Tray list The original tray
* @param - NewTray list The new tray
* @param + X The index of the element to change
* @param + Y The index of the line to change
* @param + Player The current player
**/
modify_tray(Tray,NewTray,X,Y,Player):-
X<4,Y<4,
modify_list(Tray,NewTray,Y,X,Player).
/**
* Give the adversary
* @param ? Player
* @param ? Adversaire
**/
adversary(x,o):-!.
adversary(o,x).
/**
* Calculate the success probability for a given tray
* @param ? Player
* @param ? Adversaire
**/
success_probability(Tray,Player,10,_):-end(Tray,Player),!.
success_probability(Tray,_,5,_):-end(Tray,e),!.
success_probability(_,_,7,0):-!.
success_probability(Tray,Player,P,Deep):-
Deep>0,!,
NewDeep is Deep-1,
adversary(Player,Adversary),
play(Tray,Adversary,_,Pprec,NewDeep),
P is -Pprec+10.
/**
* Give the possible action for the player
* @param + Tray
* @param + Player
* @param - PossibleAction
**/
possible_action(Tray,Player,OPA,PossibleAction,X,Y,Deep):-
nth(Y, Tray, Line),nth(X, Line, e),
modify_tray(Tray,NewTray,X,Y,Player),
success_probability(NewTray,Player,SP,Deep),
cons([SP,[NewTray,X,Y]],OPA,PossibleAction),
!.
possible_action(_,_,OPA,OPA,_,_,_).
possible_action(Tray,Player,PossibleAction,Deep):-
possible_action(Tray,Player,[],PA1,1,1,Deep),
possible_action(Tray,Player,PA1,PA2,2,1,Deep),
possible_action(Tray,Player,PA2,PA3,3,1,Deep),
possible_action(Tray,Player,PA3,PA4,1,2,Deep),
possible_action(Tray,Player,PA4,PA5,2,2,Deep),
possible_action(Tray,Player,PA5,PA6,3,2,Deep),
possible_action(Tray,Player,PA6,PA7,1,3,Deep),
possible_action(Tray,Player,PA7,PA8,2,3,Deep),
possible_action(Tray,Player,PA8,PossibleAction,3,3,Deep).
/**
* Play an action for a given player
* @param + Tray list The original tray
* @param + Player The current player
* @param - NewTray list The new tray
* @param - P list Probability of the action
* @param + Deep list Deep of the search
**/
play(Tray,Player,NewTray,P,Deep):-
possible_action(Tray,Player,PossibleAction,Deep),
keysort(PossibleAction, PossibleActionSort),
reverse(PossibleActionSort,[[P,[NewTray,_,_]]|_]).
/**
* Play an action and give its position
* @param + Tray list The original tray
* @param + Player The current player
* @param - X list The column position
* @param - Y list The line position
* @param - P list Probability of the action
* @param + Deep list Deep of the search
**/
play(Tray,Player,X,Y,P,Deep):-
possible_action(Tray,Player,PossibleAction,Deep),
keysort(PossibleAction, PossibleActionSort),
reverse(PossibleActionSort,[[P,[_,X,Y]]|_]).
Voici ce que donne un exemple d'utilisation, j'ai d'ailleurs perdu par inadvertance! A noter que cette IA peut être parfaite si on lui pose une profondeur égale a 9. Il conviendrait donc d'insérer un facteur d'erreur ou de la faire jouer avec une profondeur faible.
| ?- [tictactoe].
compiling /home/ljf/test/tictactoe.pl for byte code...
/home/ljf/test/tictactoe.pl compiled, 171 lines read - 21874 bytes written, 43 ms
(8 ms) yes
| ?- play([[e,e,e],[e,o,e],[e,e,e]],x,X,Y,P,5).
P = 3
X = 1
Y = 1
(1472 ms) yes
| ?- play([[x,o,e],[e,o,e],[e,e,e]],x,X,Y,P,5).
P = 5
X = 2
Y = 3
(84 ms) yes
| ?- play([[x,o,o],[e,o,e],[e,x,e]],x,X,Y,P,5).
P = 10
X = 1
Y = 3
(4 ms) yes
| ?- play([[x,o,o],[e,o,e],[x,x,o]],x,X,Y,P,5).
P = 10
X = 1
Y = 2
yes
| ?- end([[x,o,o],[x,o,e],[x,x,o]],Winner).
Winner = x
yes
NB: il y a peut être un bug au niveau des profondeurs
Prolog
Prolog signifie Programmation Logique, il s'agit d'un langages qui peut être interprété ou compilé. Il existe de nombreux interpréteurs/compilateurs mais les plus connues sont swi-prolog, scitus-prolog(proprietaire) et gnu-prolog. Dans ces exemples j'utilise GNU Prolog.
Ce qui est important de retenir c'est que prolog est base sur l'expressivité de la logique, on va bientôt découvrir de quoi je parle. Et Prolog peux déduire les choses grâce a son moteur d'inférence d'ordre 1.
Le moteur d'inférence
Un moteur d'inférence est un système capable de déduire une réponse a une question grâce a une base de règle et de fait.
Ça va peut être paraitre plus clair avec l'exemple typique de prolog:
helloworld.pl
%Base de Faits
%Ici on indique des relations de paternité via un prédicat
%que l'on nomme father mais on aurait pu nommer ca père ou
%autre chose. john ou stephan sont ici des atomes
father(john,stephan). %Stephan est le père de John
father(stephan,sam). %Sam est le père de Stephan
father(brian,stephan). %Stephan est le père de Brian
father(brice,philip). %Philip est le père de Brice
%Base de Règles
%Ici il s'agit d'une règle on utilise d'ailleurs des
%variables commençant par une majuscule. Cette règle
%utilise d'ailleurs le prédicats father. La virgule
%indique un ET logique
grandfather(GrandSon,Grandfather):-
father(GrandSon,Father),
father(Father,Grandfather).
Une fois la base de faits et de regles creer on peut l'interroger via l'interpréteur ou le code compilé.
| ?- [grandfather]. %On charge le fichier grandfather.pl
compiling /home/ljf/test/grandfather.pl for byte code...
/home/ljf/test/grandfather.pl compiled, x lines read - x bytes written, x ms
(x ms) yes
| ?- father(S,stephan). %On demande de trouver les fils de stephan
Son = john ?;
Son = brian ?;
no
| ?- grandfather(brian,GF). %On demande de trouver le grand pere de brian
GF = sam ?
yes
| ?- grandfather(brice,GF). %On demande de trouver le grand pere de brice
no %Comme on ne l'a pas renseigné dans la base de faits ca nous renvoie no
Programmation par contrainte
Un autres avantages en Prolog est la programmation par contraintes.
De quoi s'agit il?
Pour faire simple certains problèmes sont juste des problèmes de contraintes. Avec Prolog, il suffit juste d'indiquer ces dernières et de lui demander de trouver une solution. Et ca marche pour beaucoup de problème a contrainte, cependant certains problèmes peuvent prendre trop de temps. Il est possible toutefois de pallier dans certains cas a ce problème en indiquant a prolog une heuristique, lors de la recherche de solution.
Le sudoku est un très bon exemples de problèmes a contraintes. Dans le cas du sudoku il n'y a pas de notion d'ordonnancement des actions, il suffit juste de trouver les chiffres. Ainsi les contraintes sont:
- une case ne peut contenir qu'un chiffre variant de 1 a 9
- les cases d'une ligne doivent contenir des chiffres tous différents
- idem pour les colonnes
- idem pour les 9 carrés du sudoku
sudoku.pl
/**
* AI for the game Sudoku
* @author Valentin GRIMAUD <http://ljf.no-ip.biz/book/>
* @adapted-from http://pcaboche.developpez.com/article/p...lp/sudoku/
* @license http://creativecommons.org/licenses/by-sa/2.0/fr/
* @copyright Valentin GRIMAUD
* @version 1.0
* @sample
* Le sudoku est décri par une liste les cases vises sont représentées
* par la variable muette "_". La liste résultat sera récupérée via la
* variable Solution.
* solve_sudoku(
* [ 8,_,4,_,_,_,2,_,9,
* _,_,9,_,_,_,1,_,_,
* 1,_,_,3,_,2,_,_,7,
* _,5,_,1,_,4,_,8,_,
* _,_,_,_,3,_,_,_,_,
* _,1,_,7,_,9,_,2,_,
* 5,_,_,4,_,3,_,_,8,
* _,_,3,_,_,_,4,_,_,
* 4,_,6,_,_,_,3,_,1
* ], Solution).
* solve_sudoku([ 8,A1,4,A2,A3,A4,2,A5,9,
* A6,A7,9,A8,A9,A10,1,A11,A12,
* 1,A13,A14,3,A15,2,A16,A17,7,
* A18,5,A19,1,A20,4,A21,8,A22,
* A23,A24,A25,A26,3,A27,A28,A29,A30,
* A31,1,A32,7,A33,9,A34,2,A35,
* 5,A36,A37,4,A38,3,A39,A40,8,
* A41,A42,3,A43,A44,A45,4,A46,A47,
* 4,A48,6,A49,A50,A51,3,A52,1
* ]).
**/
/**
* Describe the constraint in a sudoku
* @param ? Sudoku list A list which represent a sudoku
**/
constraint(Sudoku):-
Sudoku=[A1,A2,A3,A4,A5,A6,A7,A8,A9,
B1,B2,B3,B4,B5,B6,B7,B8,B9,
C1,C2,C3,C4,C5,C6,C7,C8,C9,
D1,D2,D3,D4,D5,D6,D7,D8,D9,
E1,E2,E3,E4,E5,E6,E7,E8,E9,
F1,F2,F3,F4,F5,F6,F7,F8,F9,
G1,G2,G3,G4,G5,G6,G7,G8,G9,
H1,H2,H3,H4,H5,H6,H7,H8,H9,
I1,I2,I3,I4,I5,I6,I7,I8,I9], %On indique qu'il doit s'agir d'un carre de 81 cases
fd_domain(Sudoku, 1, 9), %On indique que chaque cases contient un chiffre entre 1 et 9
fd_all_different([A1,A2,A3,A4,A5,A6,A7,A8,A9]), %On indique que les cases d'une ligne doivent
fd_all_different([B1,B2,B3,B4,B5,B6,B7,B8,B9]), %contenir des chiffres tous différents
fd_all_different([C1,C2,C3,C4,C5,C6,C7,C8,C9]),
fd_all_different([D1,D2,D3,D4,D5,D6,D7,D8,D9]),
fd_all_different([E1,E2,E3,E4,E5,E6,E7,E8,E9]),
fd_all_different([F1,F2,F3,F4,F5,F6,F7,F8,F9]),
fd_all_different([G1,G2,G3,G4,G5,G6,G7,G8,G9]),
fd_all_different([H1,H2,H3,H4,H5,H6,H7,H8,H9]),
fd_all_different([I1,I2,I3,I4,I5,I6,I7,I8,I9]),
fd_all_different([A1,B1,C1,D1,E1,F1,G1,H1,I1]), %On indique que les cases d'une colonne doivent
fd_all_different([A2,B2,C2,D2,E2,F2,G2,H2,I2]), %contenir des chiffres tous différents
fd_all_different([A3,B3,C3,D3,E3,F3,G3,H3,I3]),
fd_all_different([A4,B4,C4,D4,E4,F4,G4,H4,I4]),
fd_all_different([A5,B5,C5,D5,E5,F5,G5,H5,I5]),
fd_all_different([A6,B6,C6,D6,E6,F6,G6,H6,I6]),
fd_all_different([A7,B7,C7,D7,E7,F7,G7,H7,I7]),
fd_all_different([A8,B8,C8,D8,E8,F8,G8,H8,I8]),
fd_all_different([A9,B9,C9,D9,E9,F9,G9,H9,I9]),
fd_all_different([A1,A2,A3,B1,B2,B3,C1,C2,C3]), %On indique que les cases d'un carré doivent
fd_all_different([A4,A5,A6,B4,B5,B6,C4,C5,C6]), %contenir des chiffres tous différents
fd_all_different([A7,A8,A9,B7,B8,B9,C7,C8,C9]),
fd_all_different([D1,D2,D3,E1,E2,E3,F1,F2,F3]),
fd_all_different([D4,D5,D6,E4,E5,E6,F4,F5,F6]),
fd_all_different([D7,D8,D9,E7,E8,E9,F7,F8,F9]),
fd_all_different([G1,G2,G3,H1,H2,H3,I1,I2,I3]),
fd_all_different([G4,G5,G6,H4,H5,H6,I4,I5,I6]),
fd_all_different([G7,G8,G9,H7,H8,H9,I7,I8,I9]).
/**
* Give a solution for each case of the sudoku
* @param ? Sudoku list A list which represent a sudoku
**/
solve_sudoku( Sudoku ):-
constraint(Sudoku), %On applique les contraintes
fd_labelingff(Sudoku). %On demande a prolog de donner une solution
/**
* Give a solution of the sudoku
* @param ? Sudoku list A list which represent a sudoku
**/
solve_sudoku( Sudoku, Sudoku ):-
solve_sudoku( Sudoku ).
| ?- [sudoku].
compiling /home/ljf/test/sudoku.pl for byte code...
/home/ljf/test/sudoku.pl compiled, 90 lines read - 18458 bytes written, 35 ms
(4 ms) yes
| ?- solve_sudoku(
[ 8,_,4,_,_,_,2,_,9,
_,_,9,_,_,_,1,_,_,
1,_,_,3,_,2,_,_,7,
_,5,_,1,_,4,_,8,_,
_,_,_,_,3,_,_,_,_,
_,1,_,7,_,9,_,2,_,
5,_,_,4,_,3,_,_,8,
_,_,3,_,_,_,4,_,_,
4,_,6,_,_,_,3,_,1
], Solution).
Solution = [ 8,7,4,6,5,1,2,3,9,
2,3,9,8,4,7,1,6,5,
1,6,5,3,9,2,8,4,7,
6,5,7,1,2,4,9,8,3,
9,4,2,5,3,8,7,1,6,
3,1,8,7,6,9,5,2,4,
5,2,1,4,7,3,6,9,8,
7,8,3,9,1,6,4,5,2,
4,9,6,2,8,5,3,7,1]
(4 ms) yes % Et voila le résultat 4ms pour trouver le sudoku en 90 lignes de code!
Interfacer prolog et un autre langage
Vous me dire qu'ils sont bien beau tous mes exemples en prolog, mais votre jeu est en PHP ou autre chose…
Et bien ci dessous sont présentées quelques méthodes pour résoudre ce problème.
Interpréteur prolog dans le langage en question
La première méthode consiste en l'utilisation d'un interpréteur prolog construit avec le langage en questions.
En PHP
Vous pouvez trouver sur ce lien http://www.stefan-baur.de/projects/simpl...gplusplus/ le seul interpréteur du genre (je pense).
L'avantage:
- Pas besoin de configuration spécifique
Les inconvénients:
- N'implémente pas bon nombre de fonctionnalité
- Support inexistant ou peu sur
- Pas ou peu de doc
NB: je n'ai pas testé en ce qui concerne les performances, mais ca doit pas être le top du top.
En Ruby
On est très loin de la syntaxe mais les idées sont la notamment le moteur d'inférence
Depot du projet
Presentation rapide
L'avantage:
- Pas besoin de configuration spécifique
Les inconvenients:
- N'implémente pas bon nombre de fonctionnalité
- Support inexistant ou peu sur
- Pas ou peu de doc
NB: je n'ai pas testé en ce qui concerne les performances, mais ca doit pas être le top du top.
En C
La c'est très simple, il suffit d'utiliser les sources de gprolog ou équivalent, c'est la meilleure solution.
Voici donc la page du manuel qui parle de ca.
Il n'y a que des avantages pour le peu que c'est bien en C que vous faites votre projet!
En Java
http://sourceforge.net/projects/jprolog/
Le projet est pas mal avancé, mais n'implémente pas toutes les spécifications de prolog.
Interfacer prolog via socket
La seconde méthode consiste a communiquer avec prolog via les socket. La plus part des langages le peuvent a condition que l'hébergeur accorde cette possibilité.
Les avantages:
- Rapidite les executable sont deja en train de tourner
Les inconvénients:
- Demande que les socket soient activées
- Demande d'avoir la possibilité d'exécuter prolog ou un exécutable
- Tout a développer puisque j'ai pas trouvé
Interfacer via system,exec ou exec_shell
La 3eme méthode consiste a utiliser les commandes d'exécution shell. C'est possible dans de nombreux langages a condition que l'hébergeur accorde cette possibilité. Ci dessous un exemple en php.
Comme dans cet exemple:
sudoku.php
<?php
echo '<pre>';
$sudoku='[ 8,_,4,_,_,_,2,_,9,
_,_,9,_,_,_,1,_,_,
1,_,_,3,_,2,_,_,7,
_,5,_,1,_,4,_,8,_,
_,_,_,_,3,_,_,_,_,
_,1,_,7,_,9,_,2,_,
5,_,_,4,_,3,_,_,8,
_,_,3,_,_,_,4,_,_,
4,_,6,_,_,_,3,_,1
]';
$src_prolog='/home/ljf/test/sudoku.pl';
$cmd='gprolog --query-goal "consult(\''.$src_prolog.'\'),'.
'solve_sudoku('.$sudoku.', Solution),write(Solution),halt"';
$answer = system($cmd);
// Affichage d'autres informations
echo '
</pre>
<hr />Sudoku : ' . $sudoku . '
<hr />Commande : ' . $cmd . '
<hr />Solution : ' . $answer;
Les avantages:
- facile a mettre en place
Les inconvénients:
- Demande d'avoir la possibilité d'exécuter prolog ou un exécutable
- L'exécutable sera a chaque fois relancé ce qui fait perdre du temps
— Zamentur 2010/03/04 00:50