Je sais que ce n'est pas exactement le bon endroit pour poser cette question, mais peut-être qu'un gars sage entre et a la solution.
J'essaie d'écrire un jeu d'ordinateur et j'ai besoin d'un algorithme pour résoudre cette question:
Le jeu est joué entre 2 joueurs. Chaque côté a 1 000 dollars. Il y a trois "cases" et chaque joueur écrit la quantité d'argent qu'il va placer dans ces boîtes. Ensuite, ces montants sont comparés. Quiconque a placé plus d'argent dans une boîte score 1 point (si tire une demi-point chacun). Quiconque marque plus de points remporte ses adversaires 1.000 dollars. Exemple de jeu:
joueur A: [500, 500, 0] Joueur B: [333, 333, 334]
Le joueur A gagne parce qu'il a gagné une boîte A et une boîte B (mais une boîte perdue C).
Question: Quelle est la stratégie optimale de placer l'argent?
J'ai plus de questions à poser (algorithme liée, non liée aux mathématiques) mais j'ai besoin de connaître la réponse à celle-ci d'abord.
3 Réponses :
C'est donc en fait une question de théorie du jeu (économie) et non un problème de mathématiques discrete, la ré-marquage de votre question pourrait attirer le genre d'attention que vous souhaitez. Dans la théorie du jeu, l'idée d'une "solution" est généralement Nash Equilibrium . Pour les jeux de somme zéro, il éteint l'algorithme que vous souhaitez résoudre est un problème de programmation linéaire. Voir cette wikipedia page pour un exemple de comment le configurer.
Il me semble que ce serait assez facile de prouver que ce jeu n'a pas d'équilibre pure Nash. Une stratégie pure est une solution fixe, comme [333 333 334]. Mon croquis d'une preuve est la suivante:
pour toute stratégie pure jouée par le joueur Un joueur B peut trouver un autre pur stratégie qui obtient B 2 points. Pour Exemple, si une pièce de théâtre [500 500,0] puis b joue [501,0,499], ou si une pièce de théâtre [333 333 334] Puis B joue [500 500,0], et ainsi de suite. Il y a Toujours un moyen d'obtenir 2 points. De bien sûr, cela signifie que le joueur A serait Obtenez 1 point.
De même, pour toute stratégie jouée par joueur B, joueur A peut trouver un autre stratégie pure qui l'obtient 2. Ainsi, aucune nash pure existe.
En outre, je pense que cela peut être prouvé que la stratégie (pour les deux) de
1/3 [500 500,0], 1/3 [500,0 500], 1/3 [0.500.500]
(Lecture [500.500,0] avec probabilité 1/3 et [500,0 500] avec probabilité 1/3 et [0 500 500] avec probabilité de 1/3) est un équilibre mélangé Nash pour ce jeu. Dans cette stratégie, leur gain attendu (#points) est 3/2. La preuve me semble laborieuse. Peut-être que quelqu'un d'autre aura une simple preuve.
Un Nash mixte est aussi fermé à "optimal" que nous pouvons obtenir. Il y a probablement d'autres équilibres mélangés Nash pour ce jeu.
Une permutation aléatoire de [500 500,0] a une valeur attendue négative contre une permutation aléatoire de [998,1,1].
D'accord avec Userover9000. La solution de stratégie mixte que vous proposez n'est pas un équilibre Nash.
J'ai trouvé une stratégie optimale dans cet article: http: // www. rand.org/pubs/research_memoranda/2006/rm408.pdf
Appelons cette stratégie de Blotto.
Regardez le diagramme ci-dessus. Tout mouvement que vous faites peut être représenté par un point sur le triangle. La stratégie dans le document dit de choisir un point au hasard dans l'hexagone. Choisissez des points plus proches du bord de l'hexagone avec une probabilité plus élevée (probabilité pour le centre de l'hexagone et une échelle linéaire jusqu'à la probabilité maximale au contour hexagone. Chaque point du contour hexagone a une probabilité égale.)
Cette solution est réservée à la blotto "continue", mais je suppose que vous êtes intéressé par l'affaire discrète (divisant n troupes en 3 groupes). L'application de la stratégie de Blotto à l'affaire discrète fonctionne parfaitement bien, lorsque n est un multiple de 3. Pour d'autres valeurs de N, j'ai pu faire un petit ajustement sur la frontière hexagone qui fonctionne très bien, mais pas parfaitement. .
S'il y a une stratégie qui peut vaincre celle-ci, il doit y avoir un déménagement statique qui gagne contre la stratégie de Blotto. Il n'y en a aucun, à l'exception du moment où N n'est pas un multiple de 3, il semble que cela semble être un mouvement sur la ligne où le grand triangle et l'hexagone se rencontrent (par exemple, le déplacement <0, .5 ,.5>) va gagner contre la stratégie de Blotto légèrement plus que perdre. Pour n = 100, la différence semble être inférieure à 1% et continue de se rétrécir pour plus grand n. Code pour mettre en œuvre la stratégie de Blotto:
En outre, tout mouvement au sein de l'hexagone est également susceptible de gagner, car il est de perdre contre la stratégie de Blotto. Les mouvements à l'extérieur de l'hexagone sont plus susceptibles de perdre que de gagner contre la stratégie de Blotto.
Merci d'économiser votre temps, Tom. Je ne comprends toujours pas pourquoi cette stratégie est optimale, mais je ferai de mon mieux pour l'absorber.
Pas de problème, celui-ci était très intéressant. Essayez ceci: choisissez un point sur le triangle. Maintenant, trouvez tous les points sur le triangle que votre point choisi défait et les colorier en rouge. Vous devriez voir que vous avez attiré le logo «Mitsubishi», centré sur votre point choisi. Notez que vous perdez à tous les points non colorés.
Maintenant, faites plutôt que votre stratégie choisie parmi 2 points, avec un problème égal. Vous devriez être capable d'identifier quel adversaire vous déplace vous gagnera contre 100%, 50% et 0%. Une stratégie optimale gagnera au moins 50% du temps contre tout mouvement / point. Au lieu de choisir parmi quelques points distincts, nous pourrions choisir un point sur la frontière de l'hexagone au hasard. Cela semble gagner 50% du temps contre tout mouvement dans l'hexagone, mais gagne seulement ~ 33% du temps contre tout mouvement à peine à l'extérieur de l'hexagone (trouvé par programme informatique). J'espère que cela donne une idée!
Tom: Est-ce que je manque quelque chose ici? Si je comprends bien, choisir des points sur le contour de l'hexagone est une stratégie supérieure. Juste pour faire une classe de test simple "très", j'ai défini ce tableau [(200, 100, 0), (200, 0, 100), (100, 200, 0), (100, 0, 200), (0 , 100, 200), (0, 200, 100)] et l'ordinateur fabriquent des troupes aléatoires (ajoutant jusqu'à 300). Je courais le jeu pour, disons, 1000 fois et le score est généralement de 450 pour une stratégie supérieure et 550 pour choisir aléatoire. Comme je l'ai dit, je dois manquer quelque chose.
Cueillir au hasard parmi ces 6 points n'est pas une bonne stratégie. Il perd à un point aléatoire ou à (120,120,60) 2 sur 3 fois, par exemple. Si vous souhaitez simplement vaincre la stratégie "point aléatoire", choisissez (100 100 100 100) à chaque fois (vous gagnerez 2 sur 3 fois). Si vous souhaitez mettre en œuvre la stratégie de Blotto, vous devez choisir un point dans l'hexagone, mais vous préférez les points plus proches du bord de l'hexagone (de manière spécifique). J'ai inclus le code pour mettre en œuvre la stratégie de Blotto dans mon poste.
Est-ce EN.Wikipedia.org/wiki/war_of_atrition_(Game) ?
Le lien est cassé (je ne peux pas le réparer). Copiez et collez-la si vous souhaitez visiter le site, car ces dernières parenthèses ne font pas partie de l'URL lorsque vous l'avez posté.
Nous pouvons éliminer la solution «mettre tous les œufs dans un panier»
Il suffit de vérifier ce lien en.wikipedia.org/wiki/war_of_atrition_%28game%29. Ne vois pas comment cela concerne ma question.
Orbite: oui, bien sûr. De plus, il n'y a pas de meilleure stratégie. Ces types de jeux sont appelés non transitifs - quelle que soit votre stratégie, il y a toujours un meilleur. Ainsi, le (s) joueur (s) devrait adopter ce qu'on appelle «stratégie mixte».
J'ai goûté avec un solveur LP et l'équilibre Nash ne semble pas avoir une description évidente et agréable. Où allez-vous avec cela?
Ceci est une question amusante. Mon impulsion serait d'essayer de trouver deux stratégies dans lesquelles une solution qui bat un 2/3 du temps perdrait de manière égale à l'autre. Puis choisissez entre eux au hasard ...
@blackened permettez-moi de vous souhaiter la bienvenue à Stackoverflow et de rappeler trois choses que nous faisons ici ici: 1) Lorsque vous recevez de l'aide, essayez de le donner aussi Répondre à des questions dans votre domaine d'expertise 2)
Lisez les FAQ3) Lorsque vous voyez de bons Q & A, votez-lesà l'aide des triangles grises, car la crédibilité du système est basée sur la réputation gagnant par les utilisateurs par partager leurs connaissances. N'oubliez pas non plus d'accepter la réponse qui permet de mieux résoudre votre problème, le cas échéant,en appuyant sur le signe de coche < / code>Un lien vaut la peine d'ajouter: - en.wikipedia.org/wiki/nash_quilibrium - et avant personne Demande, oui, une relation distante très . Comme c'est pour un match, je vous suggérerais d'expérimenter, disons d'abord de 10 $ et de trouver ce que les stratégies décentes ressemblent à un joueur qui distribue les 10 articles de manière aléatoire (c'est-à-dire également susceptible de choisir l'un des, je pense que , 66 distributions possibles). Cela pourrait être assez bon.
Je pense qu'il y a peu de point à ce jeu (c'est trop aléatoire) s'il est joué sur un seul tour. Une stratégie gagnante pourrait être conçue pour un match de plusieurs tours, mais ce serait probablement un comme ceux du poker: cela dépend de ce que fait l'adversaire.