J'ai du mal à obtenir une solution, mais je n'ai aucune idée de cela.
Robota et Robotb qui choisissent une permutation des n chiffres de commencer. Robota choisit d'abord et ils choisissent alternativement. Chaque tour, les robots ne peuvent choisir que n'importe quel nombre restant de la permutation. Lorsque les chiffres restants forment une séquence croissante, le jeu se termine. Le robot qui a choisi le dernier tour (après quoi la séquence devient augmentée) gagne le jeu. P>
supposer que les deux jouer de manière optimale, qui gagne? P>
Exemple 1: strong> em> p> Exemple 2: strong> EM> P> The original sequence is 8 5 3 1 2.
RobotB wins by selecting the 2, preventing any increasing sequence.
4 Réponses :
ressemble à un Minimax problème.
Je ne pense pas que c'est la bonne façon d'y aller. Cela sera très lent et très difficile à mettre en œuvre de manière à ce que le jeu soit optimal.
@IVLAD Avez-vous une meilleure suggestion? Les majuscules de minimax ou alpha-bêta sont les moyens standard d'explorer des arbres de jeu comme celui-ci.
@Nickjohnson - non ce n'est pas. Ce n'est que la norme pour les jeux qui n'ont aucune solution mathématique efficace. L'approche standard consiste à essayer de trouver une approche mathématique à l'aide de la théorie du jeu. Vous n'utiliseriez pas minimax pour le jeu NIM, n'est-ce pas? Le problème ressemble à celui-ci, mais non, je n'ai pas encore de solution réelle.
@IVLAD, je ne savais pas non plus si ceci est un minimum réel. C'est pourquoi je n'ai pas dit que c'est Minimax, j'ai dit que cela ressemble à un minimum. Cela m'a semblé que Minimax pourrait être une solution possible. Et oui, je n'ai pas non plus de solution parfaite.
@IVLAD Bien sûr, mais je ne suis pas convaincu qu'il en a un, et vous n'avez pas démontré autrement. Vous devriez sauver la critique jusqu'à ce que vous ayez une alternative concrète à offrir.
@Nick Johnson - C'était plus d'opinion que la critique depuis que je n'ai pas répondu. Si cela est attribué dans une classe ou posée dans une interview, je pense que la réponse attendue n'est pas quelque chose comme Minimax. Si vous voulez voir si un étudiant / interviewé connaît Minimax, il y a de meilleures questions à poser. Et la partie "optimale de jeu" est un cadeau mort, à mon avis. Les implémentations minimax peuvent être très intelligentes, mais je n'ai pas encore entendu parler d'une optimale. Je pense juste que c'est une mauvaise voie à prendre ici, c'est tout.
Et pourquoi devrais-je même sauver la critique si je n'ai rien de mieux? Peut-être que mes critiques aideront les autres à proposeront quelque chose. Cela ne fait certainement rien blessé ou quiconque aussi longtemps que c'est constructif et j'ai des arguments.
@IVLAD Minimax et algorithmes connexes (alpha-bêta et leurs remises) sont exactement ce qui est utilisé pour déterminer une lecture optimale. En fait, toute la base de Minimax est «Agir de la manière dont vous minimisez les pires conséquences de vos actions de votre adversaire», ce qui est précisément quel jeu optimal est.
@Nick Johnson - Minimax Utilisez une fonction de notation pour attribuer des scores à une partie de l'arborescence de jeu, puis choisit le mouvement à effectuer en fonction de ces scores. Étant donné que l'arbre de jeu est généralement très grand (oui, les méthodes de taille existent, mais l'arbre de jeu est toujours trop grand pour explorer pleinement), Minimax ne jouera jamais de manière optimale, car il est très difficile de garantir que cette fonction fonctionnera de manière optimale avec les informations. disponible pour cela. Essayez de résoudre des jeux comme NIM avec minimax. Puis résolvez-les mathématiquement, comparez avec votre minimax et voyez lequel est vraiment optimal.
@IVLAD Si vous cherchez de manière exhaustive l'arborescence de jeu - la seule façon de jouer à un jeu sans solution triviale de manière optimale - Minimax / alpha-bêta entraîne une pièce optimale. Ce n'est que lorsque vous devez limiter votre profondeur de recherche et faire des approximations que ce n'est pas le cas. Je ne suggère pas d'utiliser Minimax sur un problème qui a une solution triviale, mais vous n'avez pas démontré que c'est le cas ici.
Je suppose qu'il y a une solution plus rapide pour cette tâche. Je penserai. Mais je peux vous donner une idée de la solution avec une complexité O (n! * N ^ 2).
Au début, notez que le numéro de cueillette de N-permutation est équivalent aux éléments suivants:
Numéro de choix de N-permutation. Soit c'était le numéro x.
Réassignez les nombres à l'aide de la règle:
1 = 1
2 = 2
...
x-1 = x-1
X = rien, c'est parti.
x + 1 = x
...
n = n-1
Exemple:
1 5 6 4 2 3
Pick 2
1 5 6 4 3
réaffectation
1 4 5 3 2
Utilisez celui-ci comme boucle, à la place de choisir simplement. Il est facile de voir que les jeux sont équivalents, jouez une victoire dans ce jeu pour une certaine permutation si et seulement si elle gagne en original.
Donnons un code à toutes les permutations de n chiffres N-Numes, N-1, ... 2 chiffres.
Définir f (x) -> {0; 1} (où X est un code de permutation) est fonction qui est 1 lorsque le quai actuel
gagne et 0 si le joueur actuel échoue. Facile à voir F (1 2 .. k-1. .
f (x) = 0 si pour tout mouvement qui transforme x sur y, f (y) = 1.
afin que vous puissiez utiliser la récursivisation avec la mémorisation pour calculer: Pour chaque argument, nous calculerons cette fonction une seule fois. Il y a 1! Permutations de longueur 1, 2! Permutations de longueur 2 .. n! Permutations de longueur N. Pour une longueur de permutation K, nous devons faire une opération O (k) pour calculer. La complexité sera donc O (1 * 1! + 2 * 2! + .. n * n!) = <= O (n! * N ^ 2) = O (n! * N ^ 2) < / p>
donné une séquence puis Le jeu se termine lorsque Travailler le jeu en arrière, si sur Robotx's Tour par exemple, si retour à l'exemple précédent, Une analyse plus poussée suivant ces lignes devrait conduire à une stratégie optimale pour l'un ou l'autre des joueurs. Le jeu mathématique le plus proche que je sais est le jeu de séquence monotone. Dans un jeu de séquence monotone, deux joueurs choisissent alternativement des éléments d'une séquence à partir d'un ensemble commandé fixe (E.G. Si vous voulez en savoir plus sur la théorie des jeux en général, ou ces types de jeux en particulier, je recommande de gagner des moyens de gagner des manières mathématiques par Berlekamp, Conway and Guy. Volume 3, je crois, aborde ces types de jeux. w de nombres distincts, laisse n (w) être la longueur de w et laisse l (w ) est la longueur de la recherche croissante la plus longue dans w . Par exemple, si n (w) = 5 et l (w) = 3 . l (w) = n (w) ou, équivalent, n (w) - l (w) = 0 . N (W) - L (W) - L (W) = 1 , la lecture optimale doit supprimer la lettre unique non dans une plus longue augmentation. à la recherche de la recherche, remportant ainsi le jeu. w = 1 7 3 , puis n (w) = 3 et l (w) = 2 avec une ultérieurement plus longue d'augmentation étant 1 3 . Suppression du 7 entraîne une séquence croissante, garantissant que le joueur qui a supprimé le 7 gagne. w = 3 5 8 1 4 , si 1 ou 4 est supprimé, puis pour la permutation résultante u nous avons < Code> n (u) - l (u) = 1 , le lecteur qui a supprimé le 1 ou 4 perdra certainement à un adversaire compétent. Cependant, tout autre jeu entraîne une victoire puisque elle oblige le prochain joueur à passer à une position perdue. Ici, la lecture optimale est de supprimer n'importe lequel des 3 , 5 ou 8 , après quoi n (u) - l ( u) = 2 , mais après le déplacement suivant n (v) - l (v) = 1 .
1,2, ..., N ). Le jeu se termine lorsque la séquence résultante contient une sous-séquence ascendante de la longueur A ou une une descendre une longueur d . Ce jeu a ses origines d'un théorème d'Erdos et de Szekers, et une belle exposition peut être trouvée dans jeux de séquence monotonique , et ce Présentation de la diapositive < / a> par Bruce Sagan est également une bonne référence.
Voici le code Python pour l'algorithme du vent de la sagesse. Il imprime des victoires pour Robota.
Désolé d'avoir posté avec aucune solution réelle, mais je trouve que si vous gardez la base anglaise, plus de gens comprennent. Avoir l'anglais comme une 2e langue, je ressens également la nécessité d'utiliser de gros mots comme "permutation", mais simplement de dire "réorganiser" cela facilite la lecture et la compréhension de ce que vous recherchez.
Merci pour vos suggestions.
@ user85569 je ne suis pas d'accord. Aucune raison de mettre fin à la langue. Surtout quand la permutation est un mot commun en mathématiques et en informatique.
@ user85569, la permutation est un terme mathématique standard. Il ne peut être remplacé par la ré-arrangée.
@Yuriy Faktorovich, je n'étais pas enseigné en anglais ou en informatique en anglais. J'ai donc dû rechercher le mot dans Google pour savoir ce qu'il essayait de dire. Il entrave le processus car je suis sûr que beaucoup d'autres personnes ne parlent pas l'anglais comme langue maternelle, ni enseignée. Il s'agissait d'une suggestion de rendre plus facile à comprendre pour tout le monde ... puisque c'est Internet ...
@ Windom's Wind n Il suffit d'une condition d'entrée, lorsque la séquence est 8 5 3 1 2, signifie N est 5.
Non, quel est le max possible n?
@ Windom's Wind Je pense quel que soit le max possible n, mais ne doit pas garantir aucun élément reproductible dans la séquence.
Laissez-moi vous expliquer, je peux vous donner une solution, mais cela prend du temps. Si ça va, je peux l'écrire.
@ Wisdom'swind sûr, merci.
Je ne comprends toujours pas le jeu. Aucune des ni la séquence n'est une permutation. Voulez-vous dire que les robots choisissent chacun des nombres distincts jusqu'à une certaine longueur totale? Si tel est le cas, alors certainement la parité compte. Pouvez-vous s'il vous plaît expliquer plus clairement comment le jeu fonctionne et quelle est la condition de résiliation?
@Pengone - Je pense que ce qu'il voulait dire, c'est que les robots initialement commencent par une permutation de
{1, ..., n} . Ses exemples ne présentent pas les séquences d'origine (les permutations), mais les séquences après un certain nombre de marches dans la partie (de sorte que certains chiffres sont manquants, mais ils étaient initialement des permutations).@IVLAD Cela n'a toujours aucun sens pour moi. Voulez-vous dire qu'il tire des chiffres d'une permutation jusqu'à ce que la séquence restante soit de plus en plus ordonnée? Si tel est le cas, la solution dépend de la permutation d'origine. Un exemple réel ou une exposition claire serait utile.
@Pengone - Oui, c'est comme ça que je comprends. Vous recevez une permutation et des joueurs
A etB sont des numéros de retrait de celui-ci,A en premier. Celui qui le fait ainsi que les chiffres restants sont en augmentation de l'ordre gagnant. Par exemple:1 4 3 2 =>A supprime1 et quel que soitb supprime après cela,A va gagner dans le prochain mouvement. Donc, si les deux jouent de manière optimale,A va certainement gagner.