Qu’est-ce qu’une stratégie
En théorie des jeux, on appelle stratégie une fonction, possiblement probabiliste, qui associe à l’état courant de la partie (et/ou éventuellement l’historique des coups joués) le prochain déplacement d’un joueur.
On appelle stratégie gagnante une stratégie qui assure, quelque soit celle de l’adversaire, de remporter la victoire. Dans notre cas il n’existe pas de stratégie gagnante.
On appelle stratégie optimale une stratégie qui assure d’avoir la meilleure sortie possible pour toute stratégie de l’adversaire (gagner si possible, sinon match nul si possible).
Dans certains cas, le calcul d’une stratégie optimale est irréaliste car trop long. Il convient alors de considérer des stratégies sous-optimales. Voici quelques idées pour vos programmes :
- Vous pouvez utiliser un algorithme glouton, qui prend à chaque étape une décision optimale d’un certain point de vue en espérant que globalement la stratégie ne sera pas mauvaise. Un exemple de stratégie gloutonne est d’aller toujours chercher le morceau de fromage le plus proche de votre position.
- Vous pouvez vous inspirer de ce que fait l’adversaire, par exemple mimer ses déplacements pour mieux le surprendre à un moment donné, ou au contraire tenir compte de sa position pour aller ailleurs.
- Il est surtout important d’avoir une stratégie qui soit différente de celles des autres. Puisque les données initiales (labyrinthe, points de départ des joueurs, emplacements des morceaux de fromage) sont symétriques, avoir la même stratégie que votre adversaire ne peut que vous mener statistiquement à un ex-æquo.
Stratégies avec ou sans mémoire
On distingue classiquement deux types de stratégies : les stratégies sans mémoire pour lesquelles la décision ne dépend que de l’état courant de la partie, et les stratégies avec mémoire qui peuvent dépendre de l’historique de la partie.
Évidemment, les stratégies avec mémoire contiennent les stratégies sans mémoire. Il suffit de considérer qu’une stratégie sans mémoire est un cas particulier de stratégie avec mémoire, où la mémoire est de taille 0. En conséquence, il y a beaucoup plus de stratégies avec mémoire que de stratégies sans mémoire.
Un résultat marquant de la théorie des jeux
Certains jeux sont dits concurrents (ou simultanés) car les différents joueurs prennent des décisions en même temps, c’est le cas de PyRat. D’autres jeux sont séquentiels et c’est à chacun son tour de jouer (échecs, jeu de go…).
Il existe un résultat puissant en théorie des jeux qui dit qu’un jeu séquentiel pour lequel il n’existe pas de match nul et dont l’objectif est d’atteindre une certaine configuration pour gagner est entièrement déterminé. C’est-à-dire qu’en fonction de la situation de départ, un des deux joueurs a forcément une stratégie gagnante.
Dans le cas où un cas d’égalité existe, il existe parfois des stratégies non-perdantes. Par exemple, au jeu du morpion, le joueur qui commence pourra toujours obtenir au moins un égalité.
Toutefois, ce n’est pas parce qu’une stratégie gagnante existe qu’elle est facilement calculable. Dans le cas du jeu de go par exemple, la combinatoire est telle que déterminer une stratégie gagnante prendrait quelques milliers d’années (AlphaGo utilise donc une stratégie pour laquelle il n’y a pas de garantie de victoire).