Algorithme minimax: fonction coût/évaluation?

Question

Un projet d'école m'a écrit un jeu de Date en C++ (exemple à http://www.cut-the-knot.org/Curriculum/Games/Date.shtml) où le joueur de l'ordinateur doit implémenter un algorithme Minimax avec l'élagage alpha-bêta. Jusqu'à présent, je comprends quel est l'objectif derrière l'algorithme en termes de maximisation des gains potentiels en supposant que l'adversaire les minimisera.

Cependant, aucune des ressources que j'ai lues m'a aidé à comprendre comment concevoir la fonction d'évaluation sur laquelle le minimax fonde toutes ses décisions. Tous les exemples ont eu des nombres arbitraires assignés aux noeuds de feuille, cependant, je dois réellement assigner des valeurs significatives à ces noeuds. L'intuition me dit que ce serait quelque chose comme +1 pour un nœud feuille gagnante, et -1 pour une perte, mais comment les nœuds intermédiaires évaluent-ils?

Toute aide serait grandement appréciée.

Answer 1

Le minimax le plus élémentaire n'évalue que les nœuds feuille, en marquant les gains, les pertes et les tirages, et les sauvegarde dans l'arbre pour déterminer les valeurs de nœud intermédiaires. Dans le cas où l'arbre de jeu est intraitable, vous devez utiliser une profondeur de coupure comme un paramètre supplémentaire à vos fonctions minimax. Une fois la profondeur atteinte, vous devez exécuter une sorte de fonction d'évaluation pour les états incomplets.

La plupart des fonctions d'évaluation d'une recherche minimax sont spécifiques à un domaine, il peut donc être difficile de trouver de l'aide pour votre jeu en particulier. Rappelez-vous juste que l'évaluation doit renvoyer une certaine espérance de pourcentage de la position étant une victoire pour un joueur spécifique (typiquement max, mais pas en utilisant une implémentation de negamax). À peu près tout jeu moins recherché va ressembler à un autre jeu plus recherché. Celui-ci s'attache de très près au jeu [sticks] [1]. En utilisant le minimax et l'alpha beta seulement, je suppose que le jeu est traitable.

Si vous devez créer une fonction d'évaluation pour des positions non terminales, voici un petit peu d'aide pour l'analyse du jeu de bâtons, que vous pouvez décider si c'est utile pour le jeu de date ou non. Commencez à chercher un moyen de forcer un résultat en regardant une position terminale et tous les mouvements qui peuvent mener à cette position. Dans le jeu de bâtons, une position terminale est avec 3 bâtons ou moins restant sur le dernier coup. La position qui continue immédiatement cette position terminale laisse donc 4 bâtons à votre adversaire. Le but est maintenant de laisser votre adversaire avec 4 bâtons quoi qu'il arrive, et cela peut être fait à partir de 5, 6 ou 7 bâtons qui vous sont laissés, et vous voudriez forcer votre adversaire à vous quitter dans l'une de ces positions. L'endroit où votre adversaire doit être dans l'ordre pour que vous soyez dans 5, 6 ou 7 est 8. Continuez cette logique encore et encore et un modèle devient disponible très rapidement. Toujours laisser votre adversaire avec un nombre divisible par 4 et vous gagnez, toute autre chose, vous perdez.

Ceci est un jeu plutôt trivial, mais la méthode pour déterminer l'heuristique est ce qui est important car elle peut être directement appliquée à votre mission. Puisque le dernier à se déplacer va en premier, et que vous ne pouvez changer qu'un seul attribut de date à la fois, vous savez que pour gagner il doit y avoir exactement 2 coups restants ...etc.

Bonne chance, faites-nous savoir ce que vous finissez par faire.

[1]: http://emkay.unpointless.com/Blog/?p=42

Answer 2

Le cas le plus simple d'une fonction d'évaluation est +1 pour un gain, -1 pour une perte et 0 pour une position non terminée. Étant donné que votre arbre est assez profond, même cette fonction simple vous donnera un bon joueur. Pour tous les jeux non triviaux, avec un facteur de branchement élevé, vous avez généralement besoin d'une meilleure fonction, avec quelques heuristiques (par exemple, pour les échecs, vous pouvez assigner des poids aux pièces et trouver une somme, etc.). Dans le cas du jeu Date, j'utiliserais simplement la fonction d'évaluation la plus simple, avec 0 pour tous les nœuds intermédiaires.

En note, minimax n'est pas le meilleur algorithme pour ce jeu en particulier; mais je suppose que tu le sais déjà.

Answer 3

D'après ce que je comprends du jeu Date vous avez lié, il semble que les seuls résultats possibles pour un joueur sont gagner ou perdre, il n'y a pas entre les deux (s'il vous plaît me corriger si J'ai tort).

Dans ce cas, il suffit d'attribuer une valeur de 1 à une position gagnante (le joueur actuel arrive à Dec 31) et une valeur de -1 aux positions perdantes (l'autre joueur atteint 31 décembre).

Votre algorithme minimax (sans taille alpha-bêta) ressemblerait à quelque chose comme ceci:

A_move(day): 
    if day==December 31: 
     return +1 
    else: 
     outcome=-1 
     for each day obtained by increasing the day or month in cur_date: 
      outcome=max(outcome,B_move(day)) 
     return outcome 

B_move(day): 
    if day==December 31: 
     return -1 
    else: 
     outcome=+1 
     for each day obtained by increasing the day or month in cur_date: 
      outcome=min(outcome,A_move(day)) 
     return outcome