algorithme Minimax

Question

J'ai une question simple concernant l'algorithme Minimax: par exemple pour le jeu tic-tac-toe, comment puis-je déterminer la fonction de l'utilité pour chaque joueur joue? Il fait, ne le fait pas automatiquement? Je dois coder en dur les valeurs dans le jeu, il ne peut pas les apprendre par lui-même, il fait?

Answer 1

Non, MiniMax ne pas apprendre. Il est une version plus intelligente d'une recherche d'arbres par la force brute.

Answer 2

Généralement, vous mettre en œuvre la fonction d'utilité directe. Dans ce cas, l'algorithme ne serait pas apprendre à jouer le jeu, il utiliserait les informations que vous avez explicitement codé en dur dans la mise en œuvre.

Toutefois, il serait possible d'utiliser de programmation génétique (GP) ou une technique équivalente pour dériver automatiquement une fonction d'utilité. Dans ce cas, vous ne pas avoir à coder une stratégie explicite. Au lieu de cela l'évolution découvrirait sa propre façon de jouer le jeu bien.

Vous pouvez soit combiner votre code minimax et le code de GP en un seul (probablement très lent) programme d'adaptation, ou vous pouvez exécuter le GP d'abord, trouver une bonne fonction d'utilité, puis ajoutez cette fonction à votre code minimax comme vous serait une fonction codée à la main.

Answer 3

Tic-Tac-Toe est assez petit pour lancer le jeu à la fin et attribuer 1 pour gagner, 0 pour tirage et -1 pour lose.

Sinon, vous devez fournir une fonction qui détermine la valeur d'une position heuristically. Aux échecs par exemple un facteur important est la valeur de la matière, mais aussi qui contrôle le centre ou la facilité avec laquelle les pièces peuvent se déplacer.

En ce qui concerne l'apprentissage, vous pouvez ajouter des facteurs de pondération aux différents aspects de la position et essayer d'optimiser les jeux par la lecture en boucle.

Answer 4

Comment déterminer la fonction d'utilité pour chaque jeu?

article montre comment une fonction d'évaluation erronée légèrement (un ex. qui soit ne va pas assez « profond » dans la perspective de l'arbre de plys possibles, ou celui qui ne parvient pas à capter l'strengh relative de certains postes du conseil d'administration) se traduit par un algorithme faible dans l'ensemble (celui qui perd le plus souvent).

il ne peut pas les apprendre par lui-même, est-il?

Non, il ne fonctionne pas. Il existe des moyens, cependant, pour que l'ordinateur apprend la force relative des postes du conseil d'administration. Par exemple, en regardant dans Donald Mitchie et son programme MENACE vous verrez comment un processus stochastique peut être utilisé pour apprendre le conseil sans a priori connaissances mais les règles du jeu. La partie drôle est que même si cela peut être mis en œuvre dans les ordinateurs, quelques centaines de perles colorées et des boîtes d'allumettes sont tout ce qui est nécessaire, grâce à la taille relativement petite de l'espace de jeu, et aussi grâce à diverses symétries.

Après avoir appris une telle façon cool d'enseigner l'ordinateur à jouer, nous ne pouvons pas être aussi intéressé à retourner à MinMax appliquée aux Tic-Tac-Toe. Après tout MinMax est un moyen relativement simple de la taille d'un arbre de décision , qui est à peine nécessaire avec un petit espace de jeu de tic-tac-toe. Mais, si nous devons ;-) [revenir à MinMax] ...

Nous pouvons examiner la « Matchbox » associée à la prochaine pièce (ce ne va pas en profondeur du tout), et utiliser le pourcentage de perles associées à chaque carré, comme un facteur supplémentaire. On peut alors évaluer un arbre traditionnel, mais seulement aller, dire 2 ou 3 se déplace en profondeur (une profondeur d'anticipation qui se terminent généralement en général des pertes ou nuls) et le taux de chaque mouvement suivant sur la base du simple -1 ( perte), 0 (tirage au sort / inconnu), +1 (victoire) note. En combinant ensuite le pourcentage de perles et de la notation simple (par addition de dire, certainement pas par la multiplication), nous sommes en mesure d'utiliser efficacement MinMax d'une manière qui est plus proche de la façon dont il est utilisé dans les cas où il est impossible d'évaluer l'arbre de jeu à sa fin.

Bottom line: Dans le cas de Tic-Tac-Toe, MinMax ne devient plus intéressant (par exemple pour nous aider à explorer l'efficacité d'une fonction d'utilité particulière) lorsque nous enlevons la nature déterministe du jeu, associé à la facilité évaluation l'arbre complet. Une autre façon de rendre le jeu [mathématiquement] est intéressant de jouer avec un adversaire qui fait des erreurs ...