Quels conseils généraux avez-vous pour créer un bot pour participer à un défi King of the Hill? Quelles stratégies utilisez-vous pour passer du défi à la création de votre bot? Quelles structures de données trouvez-vous les plus utiles?

Veuillez poster un pourboire par réponse.

Trouver l' équilibre de Nash

Il s'agit d'un concept très important lorsque le KOTH implique un ensemble de décisions relativement simple, n'implique que quelques acteurs (généralement 2) et est déterministe. Un équilibre de Nash décrit une position «bloquée»: si les deux joueurs ont décidé de leurs deux stratégies, alors les deux joueurs sont effectivement bloqués dans ces positions: l'un ou l'autre joueur changeant de stratégie crée simplement des vulnérabilités supplémentaires.

Des exemples de jeux où les équilibres de Nash sont importants sont:

• Rock-Paper-Scissors (-Lizard-Spock), dans lequel une stratégie "imbattable" est un jeu aléatoire
• Morra , qui a un "spectre" d'équilibres. Peter Taylor a écrit un bon exemple dans sa réponse ici .
• Prisoner's Dilemma, un jeu coopératif remarquable pour avoir un blocage "tout le monde perd"

Comment trouver un équilibre

Trouver un équilibre est en fait assez simple pour la plupart des jeux simples et est souvent assez intuitif. Une tonne de détails sur les différentes méthodes peuvent être trouvées sur Internet. Le concept de base, qui est normalement applicable, est de créer une liste de stratégies possibles que les deux joueurs peuvent utiliser (les options fournies par le jeu). Si une stratégie est "dominée" par une autre, cette stratégie peut être supprimée de la liste et le processus est répété. Par «domination», je veux dire que si la stratégie A donne toujours un résultat égal ou meilleur que la stratégie B, contre toutes les stratégies adverses restantes, alors la stratégie B peut être supprimée de la liste.

Exemple: Rock-Paper-Scissors

RPS a quelque chose appelé un équilibre "mixte", ce qui signifie qu'une distribution est impliquée. Plutôt que de jouer le même coup à plusieurs reprises (ce qui entraînera une défaite rapide), l'équilibre consiste à jouer 1/3 de pierre, 1/3 de papier et 1/3 de ciseaux dans une distribution aléatoire. Si je joue au hasard, mon adversaire ne peut rien faire pour me devancer, point final. Si mon adversaire choisit de ne pas jouer au hasard, cela ne fait que créer une vulnérabilité de sa part.

Les jeux à équilibre mixte sont probablement les plus courants sur PPCG, car ils peuvent prendre de nombreuses formes (le seul jeu intéressant auquel je peux penser avec un équilibre pur est le dilemme du prisonnier). Je dois noter que l'équilibre mixte n'a pas à être uniformément aléatoire , simplement autre chose que de jouer le même coup à chaque fois.

Utilisation de ces informations

L'équilibre Nash d'un jeu représente souvent la «ligne de base» à partir de laquelle vous devez essayer de fonctionner. En RPS, jouer au hasard garantit une place de finition au milieu du peloton. Pour passer au sommet, vous devez commencer à identifier les faiblesses des autres joueurs.

Pour ce faire, vous devez vous en tenir à l'équilibre lorsque vous n'êtes pas sûr des faiblesses de l'adversaire. Une fois que ces faiblesses ont été identifiées (vous avez détecté que votre adversaire n'est pas en équilibre), vous devez alors vous déplacer doucement hors de l'équilibre pour profiter de votre adversaire. Cette action, à son tour, crée des faiblesses de votre part. Vous devez ensuite détecter quand votre adversaire change de stratégie, afin de pouvoir ensuite arrêter l'attaque et reprendre le jeu au hasard.

Détecter la variation de l'équilibre

C'est assez difficile et je ne suis pas un expert. Les variations peuvent prendre plusieurs formes:

• Privilégier certaines options au-dessus / en dessous d'autres sans aucune raison, comme un lecteur RPS qui joue du rock deux fois plus souvent que des ciseaux, ou qui évite de jouer au papier. Certaines statistiques relativement simples peuvent le détecter.
• Baser un mouvement actuel sur les mouvements passés, selon un schéma prévisible. Cela inclut les "copie-chats", les bots "bat ce qui bat votre dernier coup" ou les bots "à vélo". Cela nécessite une logique supplémentaire pour détecter, car la distribution globale des mouvements peut être également répartie, même si les mouvements ne sont pas aléatoires. Vous devriez essayer de prendre le dossier des coups et trouver des corrélations comme "le coup que j'ai fait il y a 2 tours et le coup que mon adversaire a fait maintenant" et "le coup qu'il a fait il y a 1 tour, et le coup qu'il a fait maintenant", etc.
• Les bots dont la répartition des déplacements est basée sur la vôtre. La vulnérabilité de ces robots n'est souvent pas créée (en quantité mesurable) tant que vous ne vous êtes pas écarté d'une distribution aléatoire. Généralement, votre propre bot entre dans cette catégorie.

Soyez précis sur les exigences pour exécuter votre bot

Les bots peuvent être écrits dans une variété de langues (et versions de ces langues), donc cela aide tout le monde lorsque vous:

1. Testez-le dans l'environnement spécifié par l'OP (ou aussi près que possible de lui).
2. Testez-le dans une variété d'autres environnements si possible (pour aider ceux qui veulent l'exécuter).
3. Soyez précis sur la langue et la version que vous utilisez et expliquez comment exécuter votre bot.

En prime: si vous utilisez une langue moins connue, faites un lien vers l'endroit où les gens peuvent télécharger le binaire / la source pour l'exécuter.

Si vous travaillez en équipe, travaillez avec votre équipe

Bien que vous puissiez généralement écrire un bot qui travaille en solo pour effectuer des tâches pour aider votre équipe, il y a un avantage beaucoup plus important lorsque vous vous coordonnez à la fois dans et hors du jeu. Un exemple parfait de cela peut être vu dans Red vs Blue - Pixel Team Battlebots .

Pendant le développement, les équipes ont pu discuter et discuter de la façon de coordonner leurs robots pour mieux fonctionner que seuls. Bien que techniquement le même bot, SphiNotPi3000 a été écrit pour fonctionner en tandem avec un autre, et a pu évoluer de manière à expliquer les faiblesses auxquelles il aurait été confronté s'il avait été seul. Le résultat final était qu'ils étaient capables de dominer presque complètement le champ de bataille, même quand ce n'était que les deux contre toute l'autre équipe .

Donc, en dehors du jeu, planifiez et coordonnez avec vos coéquipiers les stratégies à couvrir. Peut-être que quelqu'un a un bot qui scanne la carte en diagonale? Faites scanner le vôtre horizontalement (juste un exemple). À l'intérieur du jeu, si le défi permet la communication d'équipe, profitez-en. Dans le jeu de robots de combat par exemple, vous pouvez envoyer un message à vos coéquipiers sur la position des robots en dehors de leur champ de vision, puis les encourager à écrire leurs robots de manière compatible pour utiliser ces signaux.

Utilisez une méta-stratégie

Pour presque toutes les stratégies intelligentes, il y a une autre stratégie qui la bat: par exemple, votre adversaire pourrait utiliser exactement le même raisonnement que vous pour anticiper votre prochain mouvement, puis le contrer. Maintenant, vous pouvez essayer de deviner votre adversaire, mais il est difficile de savoir quand s'arrêter .

Un autre problème est qu'une stratégie qui est bonne pour deviner un adversaire intelligent pourrait être loin d'être optimale contre des adversaires plus simples.

Comment pouvez-vous résoudre ce problème? Vous laissez votre bot décider à la volée de la stratégie à utiliser!

Pour cela, vous commencez par donner à votre bot un répertoire de différentes stratégies. Ensuite, avant chaque mouvement, votre bot regarde l'historique enregistré du jeu jusqu'à présent et évalue comment ces différentes stratégies se seraient déroulées. Il illustre ensuite celui qui aurait été le plus réussi.

Inclure des stratégies solides en premier lieu vous aidera à donner à votre bot de bonnes options. Mais vous devez également en inclure de très simples, car ils fonctionnent souvent mieux contre des adversaires stupides.

Vous pourriez envisager de mettre un biais sur certaines stratégies, soit pour éviter le sur-ajustement (par exemple, essayer de battre un schéma où l'adversaire agit simplement au hasard) ou pour favoriser certaines stratégies au début quand il n'y a pas encore beaucoup d'informations.

Bien sûr, cette approche ne fonctionnera que pour certains types de défis du roi de la colline. Cela a très bien fonctionné pour moi dans un match Rock-Paper-Scissors-Lizard-Spock . Dans d'autres jeux, il peut être presque impossible d'évaluer comment une certaine stratégie aurait réussi si elle n'avait pas été réellement jouée.

Une forme extrême de cette méta-approche (qui frise la tricherie) serait d'inclure le comportement connu de tous les autres bots dans votre propre bot, de sorte qu'il puisse parfaitement anticiper leurs mouvements.