Informatique MPI
Pas de colles cette semaine : concours blanc !
Le chapitre de jeux a été terminé, on pourra donner des exercices autour de ce chapitre.
Il faut savoir formaliser un jeu d'accessibilité sous forme de graphe (exprimer les états, les coups possibles, les états gagnants), connaître la définition de stratégie et de stratégie gagnante. La notion d'attracteurs est à connaître, par sa définition inductive, et il faut se rappeler à quoi cela correspond (ensemble des positions gagnantes d'un joueur), mais on ne demande pas de savoir fournir un algorithme pour le calculer ; cela peut cependant être demandé avec un peu de guidage. Les algorithmes MinMax et AlphaBeta sont à connaître ; il faut en connaître le principe, savoir les appliquer sur des exemples (y compris pour AlphaBeta) ; on ne demande pas de savoir construire une bonne heuristique pour un jeu donné, qui permettrait de couper l'exploration au-delà d'une certaine profondeur, mais on peut demander de se servir d'une heuristique donnée dans un des algos.
Enfin, les exercices de TD autour des jeux sont à réviser. Beaucoup d'entre eux demandent de démontrer ou d'infirmer l'existence d'une stratégie gagnante sous certaines conditions, pour l'un ou l'autre des joueurs, et cela ne s'appuie pas directement sur les notions du cours, mais surtout sur des preuves très ad hoc qui vont dépendre du jeu concerné.
