Minimax algorithme Tic Tac Toe état intermédiaire

Question

J'ai essayé de comprendre le fonctionnement de l'algorithme minimax aux états intermédiaires d'un jeu de tic tac toe. Mais je suis incapable de le faire. Je comprends que l'algorithme min max renvoie le meilleur état possible pour le joueur à chaque étape. Si les États étaient comme cette

Aux dernières étapes du jeu, il est plus facile de comprendre que l'état qui conduit à un avantage ou un maximum de points pour un joueur est la meilleure configuration. Dans cet exemple, nous pouvons voir que l'état qui a le score '1', à la feuille est le meilleur état. Mais que se passe-t-il aux étapes intermédiaires ou au début du jeu?

Supposons que nous ayons 3 positions pour commencer ou le joueur pourrait aller à ces états en jouant une certaine position. Et ces positions conduisent encore à d'autres configurations de planches dans l'arbre. Chacune des trois branches du nœud initial/de départ mènera finalement à la victoire notée '1' au niveau des nœuds feuilles ou une défaite désignée par '-1' dans les nœuds feuilles ou dans certains cas un pointage noté '0'.

Qu'est-ce que l'algorithme de minimax faire ici? Quelle position ou branche le minimax retournera-t-il après le nœud initial?

Answer 1

L'algorithme minimax, comme mentionné here examine le résultat extrémal du mouvement. Pour le joueur qui vise à maximiser le score (dans le cas de Tic-Tac-Toe, le score maximum est de 1), la valeur d'un mouvement est le maximum de tous les résultats possibles et l'algorithme vise à maximiser la valeur du mouvement .

De même, pour le joueur qui vise à minimiser le score, l'algorithme vise à choisir un coup avec une valeur minimaxl (qui est -1 pour Tic-Tac-Toe). Plus formellement, la valeur d'un coup est la valeur de l'état de jeu final résultant si le coup aboutit à un état de jeu terminal (c'est-à-dire que le coup atteint une feuille de l'arbre de jeu). Si le mouvement aboutit à un nœud interne de l'arbre de jeu, cela dépend si le niveau de l'arbre de jeu est pair ou impair (car les mouvements seraient effectués par les joueurs en alternance) et est défini de manière récursive; pour un niveau encore, la valeur d'un mouvement est la valeur minimale réalisable de mouvements successifs et pour un niveau impair, la valeur d'un mouvement est la valeur maximale attainble de mouvements successifs (ou vice versa, en fonction de la définition exacte de niveau et quel joueur vise à quelle valeur).

moins formellement, l'algorithme minimax évalue l'ensemble de l'arbre de jeu basé sur le raisonnement suivant. Pour évaluer un coup, il suffit de faire le mouvement, de prendre la position de l'adversaire et de faire la même évaluation, à savoir évaluer un coup et reprendre la position de l'adversaire. Au total, cela conduit à déterminer un mouvement optimal dans l'hypothèse où l'adversaire joue également de manière optimale - ce qui est mis en œuvre par l'émulation de son choix de mouvements en utilisant également l'algorithme minimax pour évaluer ses mouvements.