Algorithme minimax: fonction de coût / évaluation?

Le cas le plus simple d'une fonction d'évaluation est +1 pour une victoire, -1 pour une perte et 0 pour toute position non finie. Compte tenu de 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 ramification élevé, vous avez généralement besoin d'une meilleure fonction, avec certaines heuristiques (par exemple pour les échecs, vous pouvez affecter 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 la plus simple, avec 0 pour tous les nœuds intermédiaires.

Note latérale, Minimax n'est pas le meilleur algorithme de ce jeu particulier; Mais je suppose que vous le savez déjà.

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

La plupart des fonctions d'évaluation dans une recherche de minimax sont spécifiques à un domaine, il est donc difficile de trouver une aide pour votre jeu particulier. N'oubliez pas que l'évaluation doit renvoyer une sorte de pourcentage d'attente de la position d'une victoire pour un lecteur spécifique (généralement max, mais pas lors de l'utilisation d'une implémentation négamax). À peu près tout jeu moins cherché consiste à ressembler de près un autre jeu plus recherché. Celui-ci est très étroitement étroitement avec le jeu Sticks de ramassage . Utilisation de Minimax et Alpha Beta seulement, je devinerais que le jeu est traitable.

Si vous devez créer une fonction d'évaluation pour les postes non terminaux, voici un peu d'aide pour l'analyse du jeu Sticks, que vous pouvez décider si son objectif est utile ou non.

Commencez à chercher un moyen de forcer un résultat en regardant une position terminale et tous les mouvements pouvant conduire à cette position. Dans le jeu Sticks, une position terminale est avec 3 bâtons ou moins restants au dernier mouvement. La position qui procède immédiatement à ce que la position du terminal quitte donc 4 bâtons à votre adversaire. Le but est maintenant de laisser votre adversaire avec 4 bâtons quoi que ce soit, et que cela peut être fait à partir de 5, 6 ou 7 bâtons qui vous sont laissés, et vous souhaitez forcer votre adversaire à vous laisser dans l'une de ces positions. L'endroit que votre adversaire doit être pour que vous puissiez être de 5, 6 ou 7. 8. Continuez cette logique sur et sur et un motif devient disponible très rapidement. Toujours quitter votre adversaire avec un nombre divisible par 4 et vous gagnez, tout d'autre que vous perdez.

Il s'agit d'un jeu plutôt trivial, mais la méthode de détermination de la heuristique est ce qui est important car elle peut être directement appliquée à votre affectation. Étant donné que le dernier à bouger va d'abord, et vous ne pouvez modifier que 1 attribut de date à la fois, vous savez gagner, il doit y avoir exactement 2 mouvements à gauche ... et ainsi de suite.

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

De ce que je comprends du jeu de date que vous avez lié, il semble que les seuls résultats possibles pour un joueur gagnent ou perdent, il n'y a pas entre les deux (corrigez-moi s'il vous plaît si je me trompe).

Ce cas, ce n'est qu'une question d'attribution d'une valeur de 1 à une position gagnante (le joueur actuel atteint le 31 décembre) et une valeur de -1 aux positions de perte (autres joueurs deviennent au 31 décembre). P> Votre algorithme minimax (sans taille alpha-bêta) ressemblerait à ceci: P>

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