Midi ROSP le 26 mars à 12h - Matthieu Guillot

Plus courts chemins stochastiques appliqués au jeu de golf

Un joueur de golf cherche à minimiser le nombre de coups pour rentrer sa balle dans le trou. Pour cela, il doit décider à chaque coup, dans quelle direction jouer et quelle distance parcourir, c.à.d. déterminer un point cible intermédiaire entre le départ et le trou, et itérer depuis sa nouvelle position jusqu’à ce que sa balle rentre. Lorsqu’un joueur sait parfaitement viser une cible donnée, le problème se ramène à un problème de plus court chemin : il faut essentiellement déterminer où placer les cibles intermédiaires de manière à éviter les obstacles (eau, arbres, sable, etc…).
Cependant, en général, les trajectoires effectives diffèrent plus ou moins des trajectoires souhaitées en fonction du degré d’habilité du joueur. Le problème devient alors stochastique et le joueur doit maintenant déterminer une stratégie : quel coup jouer à partir de n’importe quelle position possible sur le terrain (puisqu’il ne sait plus à l’avance là où il risque d’atterrir). On se propose d’étudier le problème où le joueur cherche à minimiser le nombre de coups moyen : ce problème se ramène à un problème de plus court chemin stochastique.
Nous présenterons ici les hypothèses utilisées pour modéliser notre problème : représentation du terrain, modélisation des joueurs, trajectoires de balle, etc… ainsi que l’outil de simulation que nous avons développé pour évaluer le résultat d’un coup et/ou d’une stratégie donnés. Nous détaillerons également la première stratégie gloutonne que nous avons mise en œuvre, utile à la fois comme test de notre simulateur, et comme solution initiale de nos futurs algorithmes d’optimisation. Nous expliquerons ensuite comment utiliser notre simulateur pour instancier le problème de plus court chemin stochastique (états, actions et matrice de transition) et les outils que nous utiliseront pour résoudre ce problème.