Comment créer une bonne fonction d'évaluation pour un jeu?

je vais commencer avec quelques bases et passer à des choses plus dures plus tard.

de Base de l'agent et d'un framework de test

peu importe l'approche que vous adoptez, vous devez commencer par quelque chose de très simple et stupide. La meilleure approche pour un agent muet est une approche aléatoire (générer tous les mouvements possibles, en sélectionner un au hasard). Ceci servira de point de départ pour comparer tous vos autres agents. Vous avez besoin d'un cadre de comparaison solide. Quelque chose qui nécessite divers agents, permet de jouer un certain nombre de jeux entre eux et retourne la matrice de la performance. En vous basant sur les résultats, vous calculez l'aptitude de chaque agent. Par exemple, votre fonction tournament(agent1, agent2, agent3, 500) va jouer 500 jeux entre chaque paire d'agent (jouant le premier / deuxième) et vous retourne quelque chose comme:

  x         -0.01       -1.484   |  -1.485
0.01          x         -1.29    |  -1.483
1.484       1.29          x      |  2.774

ici par exemple j'utilise 2 points pour une victoire, 1 point pour le tirage au sort fonction de notation, et à la fin juste Sommer tout pour trouver l'aptitude. Cette table immédiatement me dit que agent3 est la meilleure, et agent1 n'est pas vraiment différent de agent2.

ainsi, une fois ces deux choses importantes établies, vous êtes prêt à expérimenter vos fonctions d'évaluation.

commençons par sélectionner les fonctionnalités

1. tout d'Abord, vous devez créer not a terrible fonction d'évaluation. Par ceci je veux dire que cette fonction devrait identifier correctement 3 aspects importants (win/draw/loss). Cela semble évident, mais j'ai vu beaucoup de bots, où les créateurs n'ont pas été en mesure de mettre en place correctement ces 3 aspects.

2. puis vous utilisez votre ingéniosité humaine pour trouver quelques caractéristiques de l'état de jeu. La première chose à faire est de parler avec un expert de jeu et lui demander comment il accède à la position.

3. si vous n'avez pas l'expert, ou vous venez même de créer les règles de votre jeu il y a 5 minutes, ne sous-estimez pas la capacité de l'humain à chercher des empreintes. Même après avoir joué à quelques jeux, une personne intelligente peut vous donner des idées sur la façon dont elle aurait dû jouer (cela ne veut pas dire qu'elle peut mettre en œuvre les idées). Utilisez ces idées comme caractéristiques.

4. À ce stade, vous n'avez pas vraiment besoin de savoir comment ces caractéristiques affectent le jeu. Exemple de caractéristiques: valeur des pièces, mobilité des pièces, contrôle des positions importantes, sécurité, nombre total de mouvements possibles, proximité d'un terminer.

5. après avoir codé ces fonctionnalités et les avoir utilisées séparément pour voir ce qui fonctionne le mieux (ne vous hâtez pas de rejeter les fonctionnalités qui ne fonctionnent pas de manière raisonnable par elles-mêmes, elles pourraient être utiles en conjonction avec d'autres), vous êtes prêt à expérimenter des combinaisons.

construire de meilleures évaluations en combinant et en pondérant des caractéristiques simples. il y a quelques standards approche.

1. créer une fonction uber basée sur différentes combinaisons de vos fonctionnalités. Il peut être linéaire eval = f_1 * a_1 + ... f_n * a_n (f_i fonctions, a_i coefficients), mais ça peut être n'importe quoi. Puis instanciez de nombreux agents avec des poids absolument aléatoires pour cette fonction d'évaluation et utilisez l'algorithme génétique pour les jouer les uns contre les autres. Comparez les résultats en utilisant le cadre de test, écartez un couple de perdants clairs et muter un couple de gagnants. Continuer de la même processus. (C'est une ébauche, en savoir plus sur l'AG)

2. utilisez l'idée de rétro-propagation à partir d'un réseau neuronal pour rétro-propager l'erreur à partir de la fin du jeu pour mettre à jour les poids de votre réseau. Vous pouvez lire plus comment cela a été fait avec backgammon (Je n'ai rien écrit de semblable, donc désolé pour la brièveté).

Vous pouvez travailler sans fonction d'évaluation! cela pourrait sembler insensé pour un personne qui a seulement entendu parler minimax/alpha-bêta, mais il existe des méthodes qui ne nécessitent pas une évaluation. L'un d'eux est appelé Monte Carlo Tree Search et comme un Monte Carlo dans un nom suggère qu'il utilise beaucoup de hasard (il ne devrait pas être aléatoire, il peut utiliser vos bons agents précédents) jeux de jeu pour générer un arbre. C'est un sujet énorme en soi, donc je vais vous donner mon explication vraiment de haut niveau. Vous commencez avec une racine, créez votre frontière, que vous essayez d'étendre. Lorsque tu élargis quelque chose, tu vas juste au hasard à la feuille. D'obtenir le résultat de la feuille, vous backpropagate le résultat. Faites cela de nombreuses fois, et de recueillir les statistiques sur chaque enfant de la frontière actuelle. Choisir le meilleur. Il y a là une théorie significative qui se rapporte à l'équilibre entre exploration et exploitation et une bonne chose à lire il y a UCT (Upper Confidence Bound algorithm)

je regarderais un algorithme d'apprentissage machine supervisé tel que l'apprentissage de renforcement. Découvrez renforcement apprentissage dans les jeux de société. Je pense que cela vous donnera de bonnes orientations à examiner.

Aussi, découvrez acquisition de stratégie pour le jeu Othello basée sur L'apprentissage de renforcement (lien PDF) où compte tenu des règles du jeu, une bonne "fonction de paiement" peut être apprise. Cette question est étroitement liée à l' TD-Gammon ...

pendant l'entraînement, le réseau neuronal lui-même est utilisé pour sélectionner déplace pour les deux côtés ... Plutôt surprenant il a été constaté qu'un montant substantiel de l'apprentissage a effectivement eu lieu, même dans la connaissance zéro initiale expériences utilisant une planche brute encodage.

si personne ne comprend encore le jeu, il n'y a aucun moyen d'obtenir une fonction d'évaluation décente. Ne me dites pas que l'alpha-bêta standard avec le nombre de matériaux est bon ou même décent pour les échecs ou ses variantes (peut-être losers' chess est une exception).

vous pouvez essayer les réseaux neuronaux avec rétroaction ou des algorithmes d'apprentissage machine similaires, mais ils sont généralement nuls jusqu'à ce qu'ils aient des tonnes de formation, ce qui dans ce cas n'est probablement pas disponible. Et même alors, s'ils ne sont pas nuls, tu ne peux pas acquérir des connaissances à partir d'eux.

je pense qu'il n'y a aucun moyen de comprendre le jeu du mieux que vous pouvez et, pour commencer, laissez les inconnues comme aléatoire sur la fonction d'évaluation (ou tout simplement hors de l'image jusqu'à ce que les inconnues deviennent mieux connues).

bien sûr, si vous partagiez plus d'informations sur le jeu, vous pourriez obtenir de meilleures idées de la communauté.

si je comprends bien, vous voulez une bonne fonction d'évaluation statique à utiliser aux feuilles de votre arbre min-max. Si c'est le cas, il est préférable de se rappeler que le but de cette fonction d'évaluation statique est de fournir une évaluation de la qualité de ce tableau pour le lecteur d'ordinateur. Donc est

f(direction1) > f(board2)

alors il doit être vrai que board1 est meilleur pour l'ordinateur (il est plus susceptible de gagner éventuellement) que dans board2. Bien sûr, aucune fonction statique est jamais complètement correct pour toutes les planches.

donc, vous dites que "le but du jeu est d'avoir assez de vos pièces dans certains carrés spéciaux sur le plateau", donc un premier coup à f(plateau) serait simplement de compter le nombre de pièces que l'ordinateur a sur ces carrés Spéciaux. Vous pouvez alors la finesse plus.

sans connaître les spécificités du jeu, il est impossible de donner de meilleures estimations. Si vous nous avez donné les règles du jeu je suis sûr que les utilisateurs de stackoverflow seraient en mesure de venir avec des tonnes de des idées originales pour de telles fonctions.

alors que vous pourriez utiliser diverses méthodes d'apprentissage automatique pour arriver à une fonction d'évaluation (TD-Learning, utilisé dans des projets tels que gnubackgammon, en est un exemple), les résultats dépendent certainement du jeu lui-même. Pour le backgammon, cela fonctionne vraiment bien, parce que la nature stochastique du jeu (lancer des dés) force l'apprenant à explorer un territoire qu'il ne veut peut-être pas faire. Sans un tel élément crucial, vous finirez probablement avec une fonction d'évaluation qui est bonne contre elle-même, mais pas contre les autres.

comme la différence matérielle n'est peut-être pas applicable, le concept de mobilité est-il important -- c.-à-d. combien de mouvements possibles avez-vous Disponibles? Est le contrôle de certaines zones du conseil général mieux que pas? Parlez aux gens qui jouent au jeu pour trouver des indices.

bien qu'il soit préférable d'avoir une fonction d'évaluation aussi bonne que vous le pouvez, vous devez également ajuster votre algorithme de recherche afin que vous puissiez rechercher comme profondément que possible. Parfois, cela est en fait plus d'une préoccupation, car un chercheur profond avec une fonction d'évaluation medicore peut jouer recherches superficielles avec une bonne fonction d'évaluation. Tout dépend du domaine. (gnubackgammon joue un jeu d'expert avec une recherche d'un pli, par exemple)

il existe d'autres techniques que vous pouvez utiliser pour améliorer la qualité de votre recherche, plus important encore, d'avoir une table de transposition pour mettre en cache les résultats de recherche pour avoir l'avance du son tailler.

je recommande fortement la recherche sur ces diapositives.

Vous devez également faire attention à votre choix. Si votre algorithme n'a pas de relation connue avec la valeur réelle, les fonctions AI standard ne fonctionneront pas correctement. Pour être valide, votre fonction d'évaluation, ou heuristique doit être la même que, ou en dessous de la valeur réelle de manière cohérente ou il guidera vos décisions d'une manière étrange (ce que l'on pourrait plaider pour les échecs, même si je pense que les points standard sont très bien).

ce que je fais généralement est de trouver ce qui est capable et ce qui est requis. Pour certains jeux, comme sokoban, j'ai utilisé le nombre minimum de mouvements de boîte requis pour obtenir une boîte (dans l'isolement) de son emplacement actuel à l'un des emplacements de but. Ce n'est pas une réponse exacte pour le nombre de mouvements requis, mais je pense que c'est un assez bon heuristique car il ne peut jamais surestimer et il peut être pré-calculé pour l'ensemble du Conseil. Lorsque vous additionnez la note pour un tableau, c'est juste la somme des valeurs pour chaque emplacement de boîte courant.

Dans un simulation de vie artificielle que j'ai écrit pour faire évoluer la chasse aux meutes et la défense des meutes, le système de notation que j'ai utilisé était seulement pour guider l'évolution et non pour effectuer toute taille. J'ai donné à chaque créature un point pour être né. Pour chaque point d'énergie qu'ils ont consommé dans leur vie, je leur ai donné un point supplémentaire. J'ai ensuite utilisé la somme des points de leur génération pour déterminer la probabilité que chacun se reproduise. Dans mon cas, j'ai simplement utilisé la proportion des points totaux de leur génération que ils avaient acquis. Si j'avais voulu faire évoluer des créatures qui étaient douées pour l'évasion, j'aurais fait un mauvais score pour avoir obtenu des points dévorés.

vous devriez également faire attention que votre fonction n'est pas trop difficile d'un but à frapper. Si vous essayez de faire évoluer quelque chose, vous voulez vous assurer que l'espace de solution a une bonne pente. Vous voulez guider l'évolution dans une direction, pas simplement déclarer une victoire s'il arrive de frapper au hasard.

Sans en savoir plus sur votre jeu je me serait difficile de vous dire comment construire une fonction. Y a-t-il des valeurs claires de quelque chose qui indique une victoire ou une perte? Avez-vous une manière d'estimer un coût minimum pour combler l'écart?

si vous fournissez plus d'information, je serais heureux d'essayer de fournir plus de perspicacité. Il y a beaucoup d'excellents livres sur le sujet.

Jacob

gardez à l'esprit qu'il n'est pas nécessairement vrai qu'une fonction d'évaluation décente existe. Pour cet énoncé, je suppose qu'une fonction d'évaluation doit être de faible complexité (P).