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

Question

J'écris des programmes pour jouer des variantes de jeux de société parfois. La stratégie de base est standard taille alpha-bêta ou des recherches similaires, parfois augmentée par les approches habituelles ou des ouvertures à des fins de parties. J'ai surtout joué avec des variantes d'échecs, alors quand vient le temps de choisir ma fonction d'évaluation, j'utilise une fonction d'évaluation d'échecs de base.

Cependant, maintenant je suis en train d'écrire un programme pour jouer un jeu de société tout à fait nouveau. Comment choisir une fonction d'évaluation bonne ou même décent?

Les principaux défis sont les mêmes que les pièces sont toujours sur la carte, donc une fonction de matériel habituel ne changera pas en fonction de la position, et le jeu a été joué moins d'un millier de fois ou, si les humains ne le font pas nécessairement jouer assez bien encore donner un aperçu. (PS. Je considère une approche MoGo, mais les jeux aléatoires ne sont pas susceptibles de mettre fin à.)

Détails du jeu : Le jeu se joue sur un tableau de 10 par 10 avec six pièces de chaque côté fixe. Les pièces ont certaines règles de mouvement, et interagissent à certains égards, mais aucun autre morceau est jamais capturé. Le but du jeu est d'avoir assez de vos pièces dans certaines cases spéciales sur la carte. L'objectif du programme d'ordinateur est de fournir un joueur qui est concurrentiel avec ou mieux que les joueurs humains actuels.

Answer 1

Trouvez quelques candidats pour votre fonction d'évaluation, comme la mobilité (nombre de mouvements possibles) moins la mobilité de l'adversaire, essayez de trouver le poids optimal pour chaque mesure. Les algorithmes génétiques semblent assez bien pour l'optimisation de poids dans une fonction d'évaluation.

Créer une population avec des poids aléatoires, les combattre les uns contre les autres avec une profondeur limitée et tours, remplacer les perdants avec des combinaisons aléatoires de gagnants, lecture aléatoire et répéter, l'impression de la moyenne de la population après chaque génération. Laissez courir jusqu'à ce que vous êtes satisfait du résultat, ou jusqu'à ce que la nécessité d'ajuster la plage pour certains des paramètres et essayez à nouveau, s'il semble que la valeur optimale pour une métrique peut être en dehors de votre gamme initiale.

modifier la fin: plus acceptée, étudié, compris approche que je ne savais pas à l'époque est quelque chose appelé « Evolution différentielle ». Offspring sont créés à partir de 3 parents, au lieu de 2, de telle manière à éviter le problème de la convergence prématurée vers la moyenne.

Answer 2

Je vais commencer par quelques notions de base et de passer à des choses plus difficiles plus tard.

Agent de base et un cadre de tests

Peu importe l'approche que vous vous prenez besoin de commencer avec quelque chose de vraiment simple et stupide. La meilleure approche pour un agent muet est un hasard (générer tous les mouvements possibles, sélectionnez un au hasard). Cela servira de point de départ pour comparer tous vos autres agents. Vous avez besoin d'un cadre solide pour la comparaison. Quelque chose qui prend divers agents, permet de jouer un certain nombre de jeux entre eux et renvoie la matrice de la performance. D'après les résultats, vous calculez la remise en forme pour chaque agent. Par exemple, votre tournament(agent1, agent2, agent3, 500) de fonction jouer 500 jeux entre chaque paire d'agent (lecture de la première / seconde) et vous renvoie 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 la fonction de notation de tirage au sort, et à la fin tout simplement la somme pour trouver la remise en forme. Ce tableau me dit tout de suite que agent3 est le meilleur, et agent1 est pas vraiment différent de agent2.

Donc, une fois ces deux choses importantes sont mises en place, vous êtes prêt à expérimenter avec vos fonctions d'évaluation.

---

Commençons par la sélection d'entités

1. Tout d'abord, vous devez créer la fonction d'évaluation de not a terrible. Je veux dire par que cette fonction devrait correctement identifier 3 aspects importants (victoire / nul / perte). Cela semble évident, mais je l'ai vu quantité importante de bots, où les créateurs ne sont pas en mesure de régler correctement ces 3 aspects.

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

3. Si vous n'avez pas l'expert, ou vous venez de créer, même les règles de votre jeu il y a 5 minutes, ne pas sous-estimer la capacité de l'homme à la recherche de crépite. Même après avoir joué deux jeux, une personne intelligente peut vous donner des idées comment il aurait dû jouer (cela ne signifie pas qu'il peut mettre en œuvre les idées). Utilisez ces idées caractéristiques.

4. À ce stade, vous ne avez pas vraiment besoin de savoir comment ces caractéristiques influent sur le jeu. Exemple de caractéristiques:. La valeur des pièces, la mobilité des pièces, le contrôle des positions importantes, la sécurité, le nombre total de déplacements possibles, la proximité avec une finition

5. Une fois que vous avons écrit en ces caractéristiques et les utiliser séparément pour voir ce qui fonctionne le mieux (ne pas se dépêcher de se défaire des fonctionnalités qui ne fonctionnent pas en soi raisonnable, ils pourraient être utiles en conjonction avec d'autres), vous êtes prêt d'expérimenter avec des combinaisons.

Construire de meilleures évaluations en combinant et la pondération des caractéristiques simples. Il y a deux approches standard.

1. Créer une fonction uber basée sur diverses combinaisons de vos fonctions. Il peut être eval = f_1 * a_1 + ... f_n * a_n linéaire (caractéristiques de f_i, coefficients a_i), mais il peut être quelque chose. Ensuite, de nombreux agents instancier avec des poids absolument aléatoires pour cette fonction d'évaluation et utiliser l'algorithme génétique pour les jouer contre l'autre. Comparer les résultats en utilisant le framework de test, jeter quelques perdants clairs et muter deux gagnants. Continuer le même processus. (Ceci est une ébauche, en savoir plus sur GA)

2. Utilisez l'idée back-propagation à partir d'un réseau de neurones à dos propager l'erreur de la fin du jeu pour mettre à jour les poids de votre réseau. Vous pouvez en savoir plus comment il a été fait avec backgammon (je ne l'ai pas écrit quelque chose de semblable, désolé pour la brièveté).

Vous pouvez travailler sans fonction d'évaluation! Cela peut paraître fou pour une personne qui n'entendu parler Minimax / alpha-bêta, mais il existe des méthodes qui ne nécessitent pas une évaluation du tout. L'un d'eux est appelé Monte Carlo arbre Recherche et comme Monte Carlo dans un nom l'indique utilise un beaucoup de jeu de hasard (il ne devrait pas être aléatoire, il peut utiliser vos bons agents précédents) joue pour générer un arbre. Ceci est un énorme sujet en lui-même, donc je vais vous donner la mienne vraiment explication de haut niveau. Vous commencez avec une racine, créez votre frontière, que vous essayez de développer. Une fois que vous développez quelque chose, vous allez simplement au hasard à la feuille. Obtenir le résultat de la feuille, vous backpropagate le résultat. Pour ce faire, beaucoup de fois, et de recueillir les statistiques sur chaque enfant de la frontière actuelle. Sélectionnez le meilleur. Il y a la théorie importante, il qui se rapporte à la façon dont équilibrez-vous entre l'exploration et de l'exploitation et une bonne chose à lire, il est UCT (Haute confiance Bound)

Answer 3

Je regardais un algorithme d'apprentissage machine supervisé, comme l'apprentissage de renforcement. Consultez Apprentissage par renforcement dans des jeux de société . Je pense que cela va vous donner quelques bonnes directions à examiner.

En outre, consultez Acquisition Stratégie pour le jeu d'Othello Basé sur l'apprentissage par renforcement (lien PDF) où étant donné les règles du jeu, une bonne « fonction de paiement » peut être appris. Ceci est étroitement lié à TD-Gammon ...

  

Pendant la formation, le réseau de neurones   lui-même est utilisé pour sélectionner déplace pour   les deux côtés ... Le peu surprenant   conclusion était qu'une quantité substantielle   de l'apprentissage a effectivement eu lieu, même   dans la connaissance nulle initiale   expériences utilisant un panneau brut   codage.

Answer 4

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

Vous pouvez essayer des réseaux de neurones avec des algorithmes de rétroaction ou d'apprentissage machine similaire, mais ils sucent habituellement jusqu'à ce qu'ils aient des tonnes de formation, qui dans ce cas est probablement pas disponible. Et même alors, si elles ne sucent pas, vous ne pouvez pas acquérir des connaissances de leur part.

Je pense qu'il n'y a aucun moyen à court de comprendre le jeu le mieux que vous pouvez et, pour commencer, laissez les inconnues comme au hasard 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 souhaitez partager plus d'informations sur le jeu que vous pourriez obtenir de meilleures idées de la communauté.

Answer 5

Si je comprends bien, vous voulez une bonne fonction d'évaluation statique à utiliser les feuilles de votre arbre min-max. Dans ce cas, il est préférable de se rappeler que le but de cette fonction d'évaluation statique est de fournir une note à quel point ce conseil est pour le lecteur de l'ordinateur. Donc, est

f (Board1)> f (board2)

alors il doit être vrai que commission1 est meilleur pour l'ordinateur (il est plus probable, à terme, gagner) que dans board2. Bien sûr, aucune fonction statique est toujours tout à fait correct pour toutes les cartes.

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

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

Answer 6

Alors que vous pouvez utiliser différentes méthodes d'apprentissage de la machine pour trouver une fonction d'évaluation (TD-Learning, utilisé dans de tels projets tels que gnubackgammon, est un exemple), les résultats sont certainement en fonction du jeu lui-même. Pour backgammon, cela fonctionne très bien, parce que la nature stochastique du jeu (dés roulant) oblige l'apprenant à explorer le territoire, il peut ne pas vouloir le faire. Sans un tel élément crucial, vous finirez probablement avec une fonction d'évaluation qui est bon contre elle-même, mais pas contre les autres.

Comme différence matérielle ne peut pas être applicable, est le concept de la mobilité importante - à savoir le nombre de mouvements possibles dont vous disposez? Contrôle une certaine zone de la carte habituellement mieux que pas? Parlez aux gens qui jouent le jeu pour trouver quelques indices.

Bien qu'il soit préférable d'avoir aussi bien d'une fonction d'évaluation que vous pouvez, vous devez également régler votre algorithme de recherche afin que vous pouvez effectuer une recherche 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 surclasser les recherches peu profondes avec une bonne fonction d'évaluation. Tout dépend du domaine. (Gnubackgammon joue un jeu d'experts en recherche 1 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 des résultats de recherche de cache pour avoir son élagage avant.

Je recommande fortement la recherche sur ces diapositives .

Answer 7

Vous devez également faire attention à votre choix. Si votre algorithme n'a pas de relation connue avec la valeur réelle, les fonctions standard AI ne fonctionneront pas correctement. Pour être valide, votre fonction d'évaluation ou heuristique doit être identique ou inférieure à la valeur réelle de façon uniforme ou il guidera vos décisions d'une façon bizarre (que l'on pourrait faire valoir pour les échecs, même si je pense que les points standard sont très bien ).

Ce que je fais habituellement est de savoir ce qui peut et ce qui est nécessaire. Pour certains jeux, comme Sokoban, je l'ai utilisé le nombre minimum de boîte mouvements requis pour obtenir une boîte (en vase clos) à partir de son emplacement actuel à l'un des emplacements de but. Ce n'est pas une réponse précise pour le nombre de mouvements nécessaires, mais je pense qu'il est une assez bonne heuristique car il ne peut jamais surestimer et il peut être pré-calculé pour l'ensemble du conseil. Lorsque la somme le score d'un conseil d'administration, il est juste la somme des valeurs pour chaque emplacement de la boîte actuelle.

Dans une simulation de vie artificielle que j'ai écrit à évoluer la chasse pack et la défense pack, le système de notation que j'était seulement pour guider l'évolution et de ne pas effectuer d'élagage. J'ai donné chaque créature un point pour être né. Pour chaque point d'énergie qu'ils consomment 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 chacune devait se reproduire. Dans mon cas, j'ai simplement utilisé la proportion du total des points de leur génération qu'ils avaient acquises. Si je voulais faire évoluer les créatures qui étaient super à échapper, je l'aurais marqué vers le bas pour obtenir des points consommés hors d'eux.

Vous devez également veiller à ce que votre fonction est pas trop dur d'un but de frapper. Si vous essayez d'évoluer quelque chose, vous voulez vous assurer que l'espace de solution a une pente décente. Vous voulez guider dans une direction de l'évolution, et non pas simplement déclarer une victoire si elle arrive à frapper au hasard.

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

Si vous fournissez plus d'informations, je serais heureux d'essayer de donner plus de perspicacité. Il y a beaucoup d'excellents livres sur le sujet ainsi.

Jacob

Answer 8

Prenez à l'esprit que ce n'est pas nescessarily vrai qu'une fonction d'évaluation décente existe. Pour cette déclaration, je suppose que, une fonction d'évaluation doit être de faible complexité (P).