L'IA aux échecs est-elle vraiment inapplicable dans les jeux de stratégie au tour par tour?

Évidemment, essayer d'appliquer l'algorithme min-max sur l'arborescence complète des mouvements ne fonctionne que pour les petits jeux (je m'excuse auprès de tous les amateurs d'échecs, par "petit" je ne veux pas dire "simpliste"). Pour les jeux de stratégie au tour par tour typiques où le plateau est souvent plus large que 100 tuiles et toutes les pièces d'un côté peuvent se déplacer simultanément, l'algorithme min-max est inapplicable.

Je me demandais si un algorithme partiel min-max qui se limite à N configurations de carte à chaque profondeur ne pouvait pas être assez bon? En utilisant un algorithme génétique, il pourrait être possible de trouver un certain nombre de configurations de carte qui conviennent bien à la fonction d'évaluation. Espérons que ces configurations pourraient également être adaptées aux objectifs à long terme.

Je serais surpris si cela n'avait pas été pensé auparavant et essayé. A-t-il? Comment ça marche?

Cela dépend de la mécanique du jeu. L'arbre de jeu min-max peut être inapplicable dans l'ensemble, mais peut-être qu'il s'applique dans certaines régions. Il est courant que certains emplacements sur une carte soient stratégiquement importants. Min-max peut s'appliquer à un niveau stratégique pour lequel de ces emplacements à contrôler. Au niveau tactique, pour les x carrés autour de chaque emplacement stratégique, min-max peut être utilisé pour décider comment les unités se déploient pour le capturer et le défendre.

Ce n'est pas un algorithme minimax, mais les gars responsables de l'IA Killzone ont publié un document basé sur les fonctions d'évaluation de position que certaines IA d'échecs utilisent également.

C'est très simple en ce qu'il ne fait que choisir un poste au conseil en fonction des connaissances actuelles de l'agent. Donc, si l'agent a peu de points de vie, les positions plus éloignées de son ennemi recevront un score plus élevé car il est plus souhaitable d'être hors de portée de l'ennemi.

Le document se trouve dans AI Game Programming Wisdom 3 et a pour titre Dynamic Tactical Position Evaluation.

Une ébauche du document peut être consultée en ligne ici:
http://www.cgf-ai.com/docs/straatman_remco_killzone_ai.pdf

J'espère que cela pourra aider.

Je ne pense pas que ce serait suffisant. Choisir les configurations N spécifiques, combien et lesquelles, serait pratiquement impossible dans quelque chose d'aussi complexe. N'oubliez pas que si votre jeu comporte des ressources infinies ou quelque chose de similaire, il peut y avoir des cercles dans la façon dont il peut être joué, ce qui rend l'exploitation d'une telle IA relativement facile.

Je suggère au moins d'implémenter min-max avec un élagage alpha-bêta.

Sans l'essayer et décider qu'il n'est pas pratique (c'est-à-dire des performances terribles), et sans plus d'informations sur les mécanismes du jeu, je ne vois pas pourquoi vous pensez que min-max est inapplicable.

La taille de la carte est potentiellement un problème, mais avec l'élagage, la suppression des chemins perdus permet une recherche plus approfondie avec la même quantité de calcul, donc peut-être que les zones de carte plus grandes ne seront pas un problème lors de l'élagage? De plus, en supposant que la taille de la planche elle-même est un problème peut être prématuré, ce n'est pas tant la taille de la planche que la complexité de la mécanique et le nombre de mouvements possibles depuis chaque position de planche. Si votre jeu a une zone large mais peu peuplée, le nombre de mouvements possibles depuis chaque état du plateau peut ne pas être très différent de celui si le plateau était juste assez grand pour contenir toutes les pièces. Bien sûr, si vous avez une gigantesque planche remplie à 90% et que tout peut bouger n'importe où à chaque tour, cela va nécessiter beaucoup de recherches.

Je ne sais pas non plus pourquoi le mouvement simultané est intrinsèquement un problème. Tant que vous passez d'un état de carte discret à un autre et que vous avez une fonction d'évaluation, l'algorithme doit s'appliquer.

Je suppose que vous devez de toute façon avoir une fonction d'évaluation, et quelle que soit la recherche que vous utilisez, la fonction d'évaluation est l'endroit où la plupart du travail est susceptible d'aller. L'algorithme min-max avec élagage est lui-même très simple à implémenter, quelque chose que vous pouvez probablement faire en une heure ou deux et une grande partie du travail d'infrastructure comme le stockage de l'état de la carte, l'évaluation, la génération de déplacement, sera probablement la même quel que soit le recherche sur laquelle vous vous installez.

Le gagnant du défi Google AI 2011 a utilisé min-max (de profondeur 1). Un autre candidat de haut niveau a utilisé un échantillonnage aléatoire . Ce candidat a mentionné qu'un mélange d'échantillons min-max et aléatoire, qui est fondamentalement ce que j'ai décrit dans ma question, fonctionnait mal. Cela règle cela, je suppose.

D'un autre côté, cela montre qu'il est possible d'utiliser min-max dans les grands jeux. Il semble cependant nécessaire de le limiter à de petits groupes de fourmis, travailler avec l'ensemble complet de toutes les fourmis aurait probablement été trop lent. Une autre observation intéressante est qu'une profondeur de 1 était suffisante. Nous (les humains) sommes devenus assez bons pour jouer aux échecs, et une IA pour ce jeu a besoin d'arbres de recherche beaucoup plus profonds pour être difficiles. De nouveaux jeux plus complexes n'ont pas été joués et étudiés depuis si longtemps, et les IA plus bêtes peuvent avoir une valeur de divertissement suffisante.

L'idée de base d'une IA d'échecs est de faire une liste de tous les coups possibles à partir du meilleur coup actuellement estimé, puis de les évaluer et de répéter le processus. Il laisse tomber ceux qui ont trop peu de chance car ils ne seront pas pris (ou peuvent être supposés ne pas être pris car ils ne semblent pas donner un avantage).

L'idée de base vous oblige à faire une liste de tous les coups possibles, et à répéter ce processus pour tous ces coups, etc. Ceci est possible dans les échecs (où la liste des prochains coups probables est effectivement énumérable; un échiquier de départ a 20 coups possibles ) et jusqu'à un certain point pour d'autres choses telles que le backgammon, les dames et la résolution d'un cube Rubik.

Si je prends un simple jeu au tour par tour (Civilization 2) comme exemple, chacun de vos gars peut passer à un total de 8 cases (ou 24) en un seul tour. Si vous avez 10 gars (ce qui n'est pas beaucoup, vous en avez généralement plus au moment où cela commence à devenir quelque peu intéressant), le nombre total de "mouvements" possibles depuis l'état actuel (donc un seul niveau) est déjà de 8 ^ 10 soit environ 4 milliards. Même si vous élaguez 99,99% de ceux-ci, vous ne pouvez toujours pas aller profondément dans l'arbre car le nombre de mouvements possibles explose très rapidement.

Ajoutez à cela que le jeu est un peu comme le problème du cube de Rubik, où vous ne voyez de progrès qu'après 10 ou 12 mouvements, le problème explose à un point où les avantages d'un min / max standard ne sont répandus qu'à une capacité de mémoire de plus que votre ordinateur typique n'aura.

En d'autres termes, les stratégies qu'il trouvera seront reproductibles mais mauvaises.

Pour le problème réel, comment faire une IA décente, j'irais dans le sens d'un mouvement aléatoire essentiellement dirigé (déplacer chaque gars avec un peu d'intelligence de base), de l'évaluation et du réglage. Faites-le en parallèle pour 100 ou 1000 différents et choisissez celui qui finit par être le meilleur. Vous pouvez transmettre les résultats de cette opération dans la direction intelligente d'origine pour la régler à nouveau. Un peu comme la simulation de monte-carlo.

Pour appliquer avec succès min / max à un jeu de stratégie au tour par tour, vous devez appliquer correctement toutes les techniques d'échecs disponibles ...

Fonction d'évaluation

Même les moteurs d'échecs ont une très mauvaise force, si vos fonctions d'évaluation sont mauvaises. La version la plus simple d'une fonction d'évaluation est: 1 = partie gagnée par les blancs, -1 = partie gagnée par les noirs, 0 = tous les autres cas; Mais cela vous donnerait une très mauvaise performance. Il en va de même pour votre jeu au tour par tour! Si vous voulez utiliser min / max (avec élagage alpha / beta et autres) comme aux échecs, vous devez également implémenter une fonction d'évaluation raisonnable! Sinon, vous ne pouvez pas comparer les performances de ces algorithmes lorsqu'ils sont appliqués à votre jeu de stratégie au cas où il est appliqué aux échecs.

Ce que font les fonctions d'évaluation des moteurs d'échecs, c'est d'évaluer des choses comme:

• Quelle est la position d'une pièce sur le plateau?
• Combien de fois une pièce est-elle attaquée?
• Combien de fois la pièce est-elle protégée?
• Dans quelle mesure chaque pièce peut-elle "bouger" librement sur la planche? (ou: combien de tuiles contrôle-t-elle?)

Les parties de la fonction d'évaluation doivent d'abord être "traduites" dans votre jeu:

• Position de la pièce: est-ce par exemple sur une colline qui étend son champ de tir?
• Attaqué: combien chaque pièce est-elle en danger? (par exemple, somme des valeurs d'attaque des unités capables d'attaquer une unité spéciale multipliée par une probabilité d'être attaqué par elle; la probabilité augmente, si l'unité est déjà endommagée; diminue si de nombreuses autres unités sont à portée de l'unité attaquante)
• Propre attaque: combien d'unités peuvent être attaquées par cette unité?
• Protection: combien de pièces sont à côté (pour aider)? Peut-être qu'une unité ne peut pas attaquer des unités à une distance minimale et il est préférable de la protéger par une unité ayant la possibilité d'attaquer des unités proches.
• Mobilité: dans quelle mesure votre unité est-elle mobile? (peut-il fuir?)

Les différentes notations doivent être résumées par fonction de pondération (factor_a * rating_a + factor_b * ranting_b + ...) pour toutes les unités ...

Dans les jeux de stratégie, les ressources (or, bois, ...) doivent également être prises en compte.

Si votre fonction d'évaluation est assez bien, vous n'avez pas besoin de chercher vraiment "profondément" dans l'arborescence pour la plupart des cas. Vous n'avez donc probablement qu'à regarder de plus près les 3 ou 10 choix les plus prometteurs. Voir le chapitre suivant ...

Mouvements possibles à chaque position

La chose la plus problématique à propos de l'utilisation de min / max pour les jeux de stratégie est que vous pouvez commander plusieurs unités en un tour, alors qu'aux échecs, vous ne pouvez commander qu'une seule unité (sauf pour le roque, mais c'est une combinaison de mouvements clairement définie). Cela provoque 5 ^ N mouvements possibles pour N unités pour chaque "position" (terme d'échecs), si vous décidez seulement entre "se déplacer vers le nord, le sud, l'ouest, l'est ou l'arrêt" pour chaque unité. Vous pouvez résoudre ce problème en décomposant la commande complexe en commandes de bas niveau: par exemple, choisissez l'action pour l'unité A, allez en profondeur et décidez pour l'unité B .... décidez pour l'unité N ... puis terminez ce tour. Mais cela ne change pas à lui seul la complexité! Vous devez optimiser l'ordre dans lequel les actions sont affectées aux unités (par exemple, la première unité B, C, D puis l'unité A). Vous pouvez enregistrer l'impact de la décision pour chaque unité lors du dernier calcul, puis trier par importance. De cette façon, l'élagage alpha-bêta peut être utilisé pour supprimer très tôt toute mauvaise combinaison de l'arbre de recherche. La priorité la plus élevée doit toujours être "ne rien faire de plus et terminer votre tour" (élagage à mouvement nul) à chaque itération. De cette façon, vous pouvez "ignorer" l'attribution de la plupart des tâches à la plupart des unités et les laisser simplement continuer ce qu'elles ont fait auparavant. De cette façon, la recherche ira en profondeur rapidement en jetant simplement un œil aux unités "critiques" (par exemple celles qui sont vraiment en combat en ce moment). Assurez-vous de ne commander chaque unité qu'une seule fois ... Vous pouvez également utiliser un caractère aléatoire pour vous assurer que les unités "importantes" reçoivent également une commande de temps en temps. Surtout, les unités qui terminent un travail (par ex.

Approfondissement itératif + mise en cache / table de hachage

Ensuite, vous pouvez "approfondir l'interaction" pour aller de plus en plus en profondeur jusqu'à ce qu'une certaine limite de temps soit atteinte. Vous chercherez donc plus en profondeur s'il y a moins d'unités, et vous aurez toujours un "résultat" si vous arrêtez de chercher une meilleure solution. L'approfondissement itératif nécessiterait l'utilisation d'une table de hachage pour mettre en cache les anciens résultats des recherches. Cela permet également de réutiliser certains des résultats de la recherche des derniers tours (la branche de l'arbre de recherche qui couvre les commandes qui ont été réellement exécutées au dernier tour). Pour implémenter cela, vous avez besoin d'une très bonne fonction de hachage (jetez un œil à la "clé zobrist"), qui peut être mise à jour de manière itérative. La mise à jour de la clé de hachage signifie que vous pouvez simplement prendre la clé de hachage de l'ancienne "position" et que vous pouvez simplement activer le changement de position (par exemple, retirer l'unité en position x et la placer en position y). De cette façon, le calcul de la clé de hachage est rapide et vous n'avez pas besoin de traiter la situation de la carte entière pour la calculer, juste pour vérifier si le hachage contient une ancienne entrée pour cette position. D'une certaine manière, vous devez vous assurer qu'aucune collision de hachage ne se produit.

Comportement non déterministe

Le comportement non déterministe est un problème pour les recherches min / max. Cela signifie qu'il n'est pas sûr que vous atteigniez une cible attaquée (par exemple, la probabilité est de 10%). Ensuite, vous ne pouvez pas simplement planifier que cela se produise. Dans ce cas, vous devez modifier l'algorithme et mettre une couche "probabilty" entre les deux. C'est un peu comme "ses probabilités tournent". Chaque résultat indépendant doit être considéré séparément. L'évaluation à travers cette "couche" de profondeur doit ensuite être échantillonnée (échantillonnage de Monte Carlo) et le résultat de l'évaluation approfondie doit être pondéré par la probabilité d'occurrence. Différents résultats de la couche de probabilité doivent être considérés comme différents mouvements de l'adversaire (mais au lieu de min / max, la "moyenne" doit être calculée). Cela augmentera bien sûr la complexité de l'arbre de recherche.

Sommaire

Lorsque vous appliquez toutes ces techniques (qui sont toutes utilisées par les moteurs d'échecs actuels) à une partie déterministe, vous serez certainement en mesure d'obtenir des résultats raisonnables pour une partie également. Pour les jeux non déterministes, ce sera probablement plus compliqué, mais je pense toujours gérable.

Une bonne ressource pour expliquer ces techniques (pour les échecs) est http://chessprogramming.wikispaces.com/

Vous pouvez même implémenter une sorte d'aléatoire dirigé dans les recherches min / max. Au lieu d'étudier de manière déterministe les meilleurs résultats en premier dans chaque itération, vous pouvez simplement randomiser cela et laisser son ordre être décidé par une distribution de probabilité basée sur les évaluations actuelles ...