algorithme Minimax: Fonction de coût / d'évaluation?

Question

Un projet d'école m'a écrit un jeu de date dans C ++ (exemple http://www.cut-the-knot.org/Curriculum/Games/Date.shtml ) où le joueur informatique doit mettre en œuvre un algorithme Minimax avec la taille alpha-bêta. Jusqu'à présent, je comprends ce que l'objectif est derrière l'algorithme en termes de maximisation des gains potentiels tout en assumant l'adversaire les rapetisser.

Cependant, aucune des ressources que j'ai lu m'a aidé à comprendre comment concevoir la fonction d'évaluation des bases minimax toutes ses décisions. Tous les exemples ont eu un nombre arbitraire attribués aux nœuds feuilles, cependant, je dois attribuer effectivement des valeurs significatives à ces nœuds.

Intuition me dit que ce serait quelque chose comme +1 pour un nœud feuille gagnant, et -1 pour une perte, mais comment les nœuds intermédiaires évaluent?

Toute aide serait très appréciée.

Answer 1

Le Minimax les plus élémentaires n'évalue que nœuds feuilles, victoires de marquage, des pertes et tire, et soutient ces valeurs dans l'arbre pour déterminer les valeurs de nœud intermédiaire. 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 de Minimax. Une fois que la profondeur est atteinte, vous devez exécuter une sorte de fonction d'évaluation des états incomplets.

La plupart des fonctions d'évaluation dans une recherche minimax sont domaine spécifique, trouver si l'aide pour votre jeu particulier peut être difficile. Rappelez-vous que l'évaluation doit retourner une sorte d'attente en pourcentage de la position étant une victoire pour un joueur spécifique (généralement max, mais pas lors de l'utilisation d'une mise en œuvre negamax). À peu près tous les jeux moins des recherches va ressembler étroitement un autre jeu plus de recherches. Celui-ci des liens dans de très près avec le jeu . L'utilisation Minimax et alpha bêta seulement, je suppose que le jeu est traitable.

Si vous êtes doit créer une fonction d'évaluation des postes non terminaux, voici un peu d'aide à l'analyse du jeu de bâtons, que vous pouvez décider si son utilité pour le jeu de date ou non.

Lancer la recherche d'un moyen de forcer un résultat en regardant une position terminale et tous les mouvements qui peuvent conduire à cette position. Dans le jeu de bâtons, une position terminale est de 3 ou moins bâtons restant sur le dernier mouvement. La position qui procède immédiatement cette position de terminal est donc laissant 4 bâtons à votre adversaire. Le but est maintenant laisser votre adversaire avec 4 bâtons peu importe, et qui peut être fait à partir soit 5, 6 ou 7 bâtons laissés pour vous, et que vous souhaitez forcer votre adversaire à vous laisser dans l'une de ces positions. L'endroit de votre adversaire doit être pour que vous soyez soit 5, 6 ou 7 est 8. Poursuivre cette logique sur et et un modèle est disponible très rapidement. Toujours laisser votre adversaire avec un nombre divisible par 4 et vous gagnez, tout le reste, vous perdez.

Ceci est un jeu plutôt trivial, mais la méthode de détermination de l'heuristique est ce qui est important, car il peut être appliqué directement à votre mission. Depuis le dernier à se déplacer en va d'abord, et vous ne pouvez changer 1 attribut de date à un moment, vous savez gagner il faut exactement 2 se déplace à gauche ... et ainsi de suite.

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

Answer 2

Le cas le plus simple d'une fonction d'évaluation est une pour une victoire, -1 pour une perte et 0 pour toute position non-fini. Étant donné votre arbre est assez profond, même cette fonction simple vous donnera un bon joueur. Pour tous les jeux non triviales, avec un facteur élevé de ramification, en général, vous avez besoin d'une meilleure fonction, avec quelques heuristiques (par exemple pour les échecs, vous pouvez attribuer des poids aux pièces et trouver une somme, etc.). Dans le cas du jeu de date, je voudrais simplement utiliser la fonction d'évaluation simple, avec 0 pour tous les noeuds intermédiaires.

Comme une note de côté, Minimax n'est pas le meilleur algorithme pour ce jeu particulier; mais je suppose que vous le savez 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 je me trompe).

Dans ce cas, il est seulement une question d'attribuer une valeur de 1 à une position gagnante (joueur actif obtient au 31 décembre) et une valeur de -1 aux positions perdantes (autre joueur arrive à 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