Existe-t-il une définition standard de la "stratégie perdante optimale" dans les jeux avec une stratégie gagnante ; échecs, Connect 4, etc.

Question

Je pense à des jeux séquentiels, basés sur des règles, où les deux joueurs sont parfaitement informés l'un de l'autre et des mouvements qu'ils pourront effectuer (comme les échecs, Connect 4, tic-tack-toe, Nim, etc.).

Dans ce type de jeu, il est courant que l'un des deux joueurs ait une stratégie gagnante (ou une stratégie de tirage au sort). C'est ainsi qu'une position dans le jeu est déclarée "gagnable" ou "non gagnable".

J'ai lu des articles sur les solutions à ces jeux. Connect 4 est un exemple de jeu résolu, alors que les échecs et le go ne le sont pas encore.

Le problème est que, si pour le joueur en position gagnante, on peut dire que certaines stratégies sont strictement meilleures que d'autres, pour le joueur qui n'est pas en position gagnante, cela n'a aucun sens. La définition ne peut pas être utilisée pour ce joueur puisqu'il ne peut pas jouer de bons coups.

Dans ce domaine, il est courant d'entendre des choses comme.. : "si les deux joueurs jouent avec leur stratégie optimale, voici comment le jeu se terminera". Comme dans la vidéo YouTube de Numberphile sur Connect 4 par exemple (je vous conseille de la regarder, mais bon), comment peuvent-ils comparer les stratégies des joueurs perdants ? D'un point de vue strict, leurs mouvements n'ont pas d'importance, mais si vous jouez à Connect 4 contre un autre humain, A) vous ne savez généralement pas quel joueur a l'avantage et B) il est idiot de démissionner au premier mouvement simplement parce que vous êtes le deuxième joueur - si vous jouez contre un humain, vous pouvez toujours gagner. Le concept de stratégie gagnante n'est pas du tout pertinent dans les jeux où l'on ne sait pas si l'on est en train de gagner ou non ; si l'on est probablement en train de perdre, alors on devrait peut-être jouer des coups pour déstabiliser l'adversaire, ou pour survivre le plus longtemps possible. Mais le fait est que pour jouer de manière "optimale" dans de tels jeux, il faut savoir si l'on gagne ou si l'on perd (ce qu'en tant qu'êtres humains, ni nous ni nos adversaires n'avons tendance à savoir), parce que les objectifs des uns et des autres peuvent être différents. Il serait préférable, selon moi, que les meilleurs coups dans n'importe quelle position (gagnante ou perdante) puissent être inclus dans la même définition, mais c'est un bonus, je suppose.

Quels sont ces objectifs ? Quelles sont les méthodes utilisées pour définir les stratégies optimales des joueurs perdants ?

Answer 1

• La maximisation du nombre de tours jusqu'à ce que la perte se produise est une pratique courante.
• Les tables de fin de partie d'échecs utilisent souvent la "distance jusqu'à la mise à zéro" - le nombre de tours jusqu'à la remise à zéro du décompte de la règle des cinquante coups (c'est-à-dire une prise ou un déplacement de pion) ou jusqu'à la fin de la partie. On peut considérer qu'il s'agit d'une optimisation du nombre de tours jusqu'à ce que la partie se rapproche d'un match nul. Il est utile car, selon ce critère, le coup optimal ne dépend pas de l'écart existant par rapport à la règle des cinquante coups.

Answer 2

Il s'agit principalement d'une intuition, mais elle peut s'avérer utile. Les définitions des positions "gagnables" et "non gagnables" sont basées sur l'hypothèse que le joueur en position gagnable joue toujours un coup qui place l'autre joueur en position non gagnable. Mais si vous ne supposez pas que a priori que l'un ou l'autre des joueurs joue de façon optimale, il faut prendre en compte tous les coups possibles dans une position gagnable, et pas seulement le meilleur coup.

Pour simplifier, je définirai un coup "gagnant" comme un coup qui met l'adversaire dans une position ingagnable.

Cela nous permet de comparer les positions gagnables : une position gagnable est meilleure qu'une autre position gagnable si une plus grande proportion des coups disponibles sont des coups gagnants. On peut donc dire que le coup optimal dans une position "ingagnable" est le coup qui place l'adversaire dans la pire position gagnable disponible, c'est-à-dire qui maximise la possibilité pour l'adversaire de gaffer et de perdre la victoire.

Nous pouvons facilement généraliser cela aux deux joueurs : le coup optimal dans n'importe quelle position est celui qui donne à l'adversaire la plus petite proportion de coups gagnants parmi tous les coups dont il dispose. Par définition, le joueur gagnant a toujours au moins un coup qui donne à l'adversaire zéro coup gagnant, et ce sont exactement les coups optimaux selon la définition existante.

---

Si vous disposez ou pouvez calculer une distribution de probabilités sur les coups de l'adversaire, vous pouvez également définir le jeu optimal comme la maximisation de la probabilité de se trouver dans une position gagnable, qui peut être calculée en évaluant récursivement chaque sous-arbre pour chaque coup possible. Cela correspond à la définition existante du coup optimal : si un joueur se trouve déjà dans une position gagnante, un coup gagnant le place dans une autre position gagnante avec une probabilité de 1.

Answer 3

La définition du terme "optimal" varie d'un jeu à l'autre, mais je constate des similitudes entre les différents types de jeux. D'une manière générale, un jeu "optimal" consiste à entreprendre une action de jeu qui maximise les chances de victoire dans une situation donnée, avec les ressources disponibles. Comme vous l'avez remarqué, dans les jeux qui mélangent chance et compétence (comme Magic, le poker, le backgammon), les jeux optimaux vous donnent plus d'opportunités ("outs") d'avoir de la chance et de gagner, tout en réduisant simultanément le nombre de façons d'avoir de la malchance et de perdre.

Comment cela se traduit-il dans un jeu purement déterministe comme les échecs ? Le fait que les joueurs ne jouent pas parfaitement à tout moment permet à certains coups dans des positions "perdues" d'être meilleurs que d'autres. Les coups qui obligent l'adversaire à jouer plus parfaitement sont optimaux. En d'autres termes, un jeu optimal rend plus difficile et plus fastidieux pour votre adversaire de gagner à partir de la position actuelle, même si cette position est perdante. Il est plus facile d'avoir de la "chance" si vos mouvements offrent plus d'opportunités à votre adversaire de faire une erreur. Ou si vous examinez un arbre de recherche, il y aura une plus grande proportion de "mauvaises décisions" à prendre pour votre adversaire.

Pour les joueurs d'échecs, cette analogie a beaucoup de sens. Il est bien connu que certaines fins de partie sont gagnées d'office avec un jeu parfait. Roi et Tour ( KR ) contre le roi est une victoire facile pour le camp avec la tour. Roi, Cavalier, Fou ( KNB ) contre King est une victoire forcée plus difficile à exécuter. C'est-à-dire que le pourcentage de joueurs qui peuvent faire échec et mat avec KR est beaucoup plus élevé que le pourcentage de ceux qui peuvent KNB . Ainsi, si vous vous trouvez dans une situation où vous avez le choix entre jouer un coup qui transforme la fin de partie en l'une ou l'autre des options suivantes KR o KNB vous devez choisir le mouvement qui vous permet de défendre le KNB finalité.

Answer 4

Cette question ne peut avoir de solution définie qu'en référence à un modèle particulier d'injection de fautes à appliquer à l'algorithme de sélection des mouvements du joueur en position gagnante. La manière d'optimiser contre un joueur parfait qui a 1% de chances de jouer au hasard est très différente de la manière d'optimiser contre un joueur parfait qui a 1% de chances de jouer le deuxième meilleur coup.

Je pense que ce dernier cas est plus intéressant. Voici donc une tentative de définition concernant les modèles d'injection de fautes qui aggravent le jeu sans rejeter complètement l'évaluation de base :

Le jeu optimal à partir d'une position perdante est le coup qui maximise la valeur du coup perdant de plus grande valeur que l'adversaire pourrait faire en réponse.