Jeux et recherche heuristique

Les jeux sont etudies en Intelligence Artificielle depuis ses origines. Historiquement le jeu d'Echecs et l'Alpha-Beta ont ete les plus etudies. Des algo- rithmes et des structures de donnees utilisees initialement pour les jeux comme l'approfondissement iteratif et les tables de transpositions ont ete ensuite reu- tilises pour de nombreux autres problemes. Nous presentons dans ce chapitre di erents algorithmes utilises pour les jeux. Les jeux sont etudies en Intelligence Arti cielle depuis ses origines. His- Nous commencons par deux sections sur les jeux a deux joueurs, la premiere traite de l'Alpha-Beta et de certaines de ses optimisations, la deuxieme porte sur les algorithmes de Monte-Carlo qui ont donne recemment de tres bons resultats sur certains jeux et qui ont une portee tres generale. On peut noter au passage les contributions essentiellement francaises aux algorithmes de Monte-Carlo, on peut meme parler d'une ecole francaise du Monte-Carlo dans les jeux. Nous abordons ensuite les puzzles et l'analyse retrograde. Nous concluons avec une section sur les jeux video.