Le meilleur choix de la carte dans le jeu de cartes en C #

Question

Le problème consiste à choisir la meilleure option à tout moment du jeu suivant ces règles:

• Vous ne pouvez choisir le ou la carte à gauche à droite.

• Votre adversaire sera toujours choisir d'abord, et toujours choisir la plus haute carte soit de la gauche ou sur la carte à droite. Si c'est un lien, il choisira le plus à droite. Prendre en considération ce n'est pas toujours le meilleur choix.

Parfois, il est impossible de gagner, mais vous devez afficher de toute façon le plus haut amout vous pouvez ajouter en jouant contre cet adversaire (ou d'une stratégie, disons).

Exemple:

Cards:    1 2 4 2 8 4 3
Opponent: 3 4 2 2 = 11
Me:       1 8 4 = 13

Ici, je chosed 1 au lieu de 4 au deuxième tour, pour que je puisse choisir le 8 plus tard. C'est pourquoi choisir la meilleure carte n'est pas toujours mieux.

J'ai essayé de mettre en œuvre cette solution en utilisant récursion mais je ne suis pas sûr que c'est la meilleure option. Toutes les idées sur la façon de concevoir cet algorithme?

[EDIT] Merci à @PengOne pour elle de l'aide généreuse. Ceci est le code im essayant de mettre en œuvre, mais malheureusement, il me donne des erreurs. Que dois-je fixer en elle? Je l'édition de ce que je progresse.

static int cardGameValue(List<int> D, int myScore, int opponentScore)
{
    if (D.Count == 0) return myScore;
    else
    {
        if (D[0] <= D[D.Count - 1])
        {
            opponentScore += D[D.Count - 1];
            D.RemoveAt(D.Count - 1);
        }
        else
        {
            opponentScore += D[0];
            D.RemoveAt(0);
        }

        int left = cardGameValue(
                new List<int>(D.GetRange(1, D.Count - 1)),
                myScore + D[0],
                opponentScore);

        int right = cardGameValue(
                new List<int>(D.Take(D.Count - 2)),
                myScore + D[D.Count - 1],
                opponentScore);

        if (left >= right)
        { return left; }
        else
        { return right; }
    }
}

Answer 1

Construire la solution à partir des cas les plus simples à l'aide de la récursivité.

Soit D être le tableau de cartes. Que A soit le total de vos cartes et B soit le total des cartes de votre adversaire. Set S = A-B être la valeur du jeu. Vous gagnez si S>0, perdre si S<0 et une cravate si S==0.

Le plus simple est de faire deux mouvements à la fois, votre déménagement suivi par mouvement déterminé de l'adversaire. Il y a deux cas de base à considérer:

• Si length(D) == 0, S de retour. Le jeu est terminé.

• Si length(D) == 1, S + D[0] de retour. Vous choisissez la carte restante, et le jeu se termine.

Pour le cas récursif, lorsque length(D) > 1, évaluer les deux possibilités

• Que L soit le résultat du jeu si vous choisissez la carte à gauche suivie par l'adversaire faire son mouvement déterministe, à savoir

  L = D[0] - max(D[1],D[N-1]) + cardGameValue(newD)

• Que R soit le résultat du jeu si vous choisissez la bonne carte suivie par l'adversaire faire son mouvement déterministe, à savoir

  R = D[N-1] - max(D[0],D[N-2]) + cardGameValue(newD)

Choisissez le jeu correspondant au plus grand nombre, à savoir prendre D[0] si L>=R, sinon prendre D[N-1]. Ici N = length(D).

Answer 2

Vous devriez regarder le algorithme Min-Max , peut-être avec la taille Alpha-Beta

Min-Max est l'idée que votre adversaire toujours choisir le meilleur choix pour eux-mêmes, vous pouvez ainsi exécuter chaque scénario possible de découvrir le meilleur choix qui se traduira par vous battre votre adversaire. « -À-dire, étant donné que je fais x déplacer, mon adversaire TakeMoveTM y, alors je vais prendre ... » etc, tout le chemin jusqu'à la fin du jeu. Ainsi, vous pouvez déterminer qui va gagner.

taille Alpha-Beta est similaire qu'il se penche sur les scénarios possibles, mais il détermine si une liste de scénarios possibles sera jamais produire un résultat gagnant. Si vous savez que si vous faites « déplacer x », alors vous aurez toujours pas lâche quoi qu'il arrive, vous n'avez pas besoin de passer plus de temps à regarder « move x puis déplacez y ». Vous pouvez « pruneau » la branche entière des choix de « déplacer x » parce que vous savez que ce ne sera jamais utile.

Answer 3

Ceci est le code qui a effectivement travaillé à la fin. Merci à tous pour votre soutien.

    static int cardGameValue(List<int> D, int myScore, int opponentScore)
    {
        if (D.Count == 0) return myScore;
        else if (D.Count == 1)
        {
            opponentScore += D[0];
            return myScore;
        }
        else
        {
            if (D[0] <= D[D.Count - 1])
            {
                opponentScore += D[D.Count - 1];
                D.RemoveAt(D.Count - 1);
            }
            else
            {
                opponentScore += D[0];
                D.RemoveAt(0);
            }

            int left = cardGameValue(new List<int>(D.GetRange(1, D.Count - 1)), myScore + D[0], opponentScore);

            int right = cardGameValue(new List<int>(D.GetRange(0, D.Count - 1)), myScore + D[D.Count - 1], opponentScore);

            if (left >= right)
            {
                return left;
            }
            else
            {
                return right;
            }
        }
    }