Avant-propos
Cet ouvrage traite d'intelligence artificielle et de jeux. Il s'adresse aux étudiants, aux
élèves d'écoles d'ingénieurs, aux enseignants, aux chercheurs et à tous ceux qui souhaitent s'initier ou se perfectionner en intelligence artificielle pour les jeux. Les connaissances requises pour aborder ce livre sont les notions de base d'informatique enseignées
en premier cycle : savoir lire et écrire un algorithme et savoir l'implémenter dans un langage informatique (pour ce livre le C++ ).
Le livre commence par traiter les algorithmes pour les jeux à deux joueurs, puis les
algorithmes pour les jeux à un joueur et finit par les approches alternatives.
Les sept premiers chapitres portent sur les algorithmes pour les jeux à deux joueurs.
Le premier algorithme traité est aussi le plus classique, à savoir !' Alpha-Bêta. Le premier chapitre explique ce qu' est une fonction d'évaluation. Il prend comme exemple le
jeu du Virus qui est ensuite réutilisé pour les chapitres deux et trois. Le deuxième chapitre montre comment utiliser cette fonction d'évaluation dans un algorithme Alpha-Bêta
qui prévoit plusieurs coups de suite. De nombreuses heuristiques améliorant l' Alpha-Bêta
sont aussi décrites. Le troisième chapitre explique l'utilisation d'une table de transposition
qui est l'amélioration la plus importante de l 'Alpha-Bêta. Le quatrième chapitre clôt les
algorithmes de recherche en profondeur d'abord pour les jeux à deux joueurs avec les algorithmes de menaces. Ceux ci sont appliqués au Football des philosophes. Le cinquième
chapitre traite de la recherche arborescente Monte-Carlo qui est un algorithme récent qui
donne de meilleurs résultats que l 'Alpha-Bêta pour certains jeux comme le jeu de Go qui
sert d'illustration à ce chapitre. Le sixième chapitre traite des algorithmes de recherche
en meilleur d'abord. Le septième chapitre présente l'analyse rétrograde qui permet de
résoudre parfaitement les fins de parties ainsi que certains jeux comme !' Awele.
Les chapitres huit à douze décrivent les algorithmes pour les jeux à un joueur. Le
huitième chapitre traite spécifiquement de la recherche du plus court chemin sur une carte.
Le neuvième chapitre porte sur la recherche d'une solution de coût minimal pour les
puzzles comme le Rubik's cube, le Taquin ou le voyageur de commerce. Le dixième
chapitre montre comment utiliser l'analyse rétrograde pour les puzzles comme le Taquin
ou le Rubik's cube. Le onzième chapitre montre comment utiliser les méthodes de MonteCarlo pour les puzzles pour lesquels on ne dispose pas de bonnes heuristiques comme
le Morpion Solitaire ou SameGame. Le douzième chapitre présente des rudiments de
programmation par contraintes avec comme exemple le Sudoku.
Les chapitres treize à seize sont des introductions à des approches scientifiques complémentaires. Le treizième chapitre est une brève introduction aux algorithmes pour les
jeux à information incomplète. Le quatorzième chapitre montre des rudiments de théorie
combinatoire des jeux. Le quinzième chapitre présente les bases de la théorie des jeux. Le
seizième chapitre évoque les jeux généraux.
Le principe de chaque chapitre est de commencer par des explications d'algorithmes
suivies d'exercices pratiques pour mettre en œuvre les algorithmes sur des jeux. Les exercices sont corrigés en C++ à la fin de chaque chapitre. Les source des corrigés sont dis-
Cet ouvrage traite d'intelligence artificielle et de jeux. Il s'adresse aux étudiants, aux
élèves d'écoles d'ingénieurs, aux enseignants, aux chercheurs et à tous ceux qui souhaitent s'initier ou se perfectionner en intelligence artificielle pour les jeux. Les connaissances requises pour aborder ce livre sont les notions de base d'informatique enseignées
en premier cycle : savoir lire et écrire un algorithme et savoir l'implémenter dans un langage informatique (pour ce livre le C++ ).
Le livre commence par traiter les algorithmes pour les jeux à deux joueurs, puis les
algorithmes pour les jeux à un joueur et finit par les approches alternatives.
Les sept premiers chapitres portent sur les algorithmes pour les jeux à deux joueurs.
Le premier algorithme traité est aussi le plus classique, à savoir !' Alpha-Bêta. Le premier chapitre explique ce qu' est une fonction d'évaluation. Il prend comme exemple le
jeu du Virus qui est ensuite réutilisé pour les chapitres deux et trois. Le deuxième chapitre montre comment utiliser cette fonction d'évaluation dans un algorithme Alpha-Bêta
qui prévoit plusieurs coups de suite. De nombreuses heuristiques améliorant l' Alpha-Bêta
sont aussi décrites. Le troisième chapitre explique l'utilisation d'une table de transposition
qui est l'amélioration la plus importante de l 'Alpha-Bêta. Le quatrième chapitre clôt les
algorithmes de recherche en profondeur d'abord pour les jeux à deux joueurs avec les algorithmes de menaces. Ceux ci sont appliqués au Football des philosophes. Le cinquième
chapitre traite de la recherche arborescente Monte-Carlo qui est un algorithme récent qui
donne de meilleurs résultats que l 'Alpha-Bêta pour certains jeux comme le jeu de Go qui
sert d'illustration à ce chapitre. Le sixième chapitre traite des algorithmes de recherche
en meilleur d'abord. Le septième chapitre présente l'analyse rétrograde qui permet de
résoudre parfaitement les fins de parties ainsi que certains jeux comme !' Awele.
Les chapitres huit à douze décrivent les algorithmes pour les jeux à un joueur. Le
huitième chapitre traite spécifiquement de la recherche du plus court chemin sur une carte.
Le neuvième chapitre porte sur la recherche d'une solution de coût minimal pour les
puzzles comme le Rubik's cube, le Taquin ou le voyageur de commerce. Le dixième
chapitre montre comment utiliser l'analyse rétrograde pour les puzzles comme le Taquin
ou le Rubik's cube. Le onzième chapitre montre comment utiliser les méthodes de MonteCarlo pour les puzzles pour lesquels on ne dispose pas de bonnes heuristiques comme
le Morpion Solitaire ou SameGame. Le douzième chapitre présente des rudiments de
programmation par contraintes avec comme exemple le Sudoku.
Les chapitres treize à seize sont des introductions à des approches scientifiques complémentaires. Le treizième chapitre est une brève introduction aux algorithmes pour les
jeux à information incomplète. Le quatorzième chapitre montre des rudiments de théorie
combinatoire des jeux. Le quinzième chapitre présente les bases de la théorie des jeux. Le
seizième chapitre évoque les jeux généraux.
Le principe de chaque chapitre est de commencer par des explications d'algorithmes
suivies d'exercices pratiques pour mettre en œuvre les algorithmes sur des jeux. Les exercices sont corrigés en C++ à la fin de chaque chapitre. Les source des corrigés sont dis-