Melhor escolha de cartas em jogos de cartas em C #

Question

O problema consiste em escolher a melhor opção em cada momento do jogo seguindo estas regras:

• Você só pode escolher o cartão mais à esquerda ou mais à direita.

• Seu oponente SEMPRE escolherá primeiro, e SEMPRE escolherá a carta mais alta da mais à esquerda ou da mais à direita. Se for um empate, escolherá o mais à direita. Leve em consideração que nem sempre é a melhor escolha.

Às vezes, é impossível vencer, mas você deve, de qualquer maneira, mostrar o valor mais alto que pode agregar ao jogar contra esse oponente (ou estratégia, digamos).

Exemplo:

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

Aqui, escolhi 1 em vez de 4 na segunda curva, para poder escolher o 8 mais tarde. É por isso que escolher a carta mais alta nem sempre é a melhor.

Tenho tentado implementar essa solução usando recursão, mas não tenho certeza se é a melhor opção. Alguma ideia de como projetar este algoritmo?

[EDITAR] Obrigado a @PengOne por sua ajuda generosa. Este é o código que estou tentando implementar, mas infelizmente está me dando erros. O que devo consertar? Estou editando conforme avanço.

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

Construa a solução a partir dos casos mais simples usando recursão.

Seja D a matriz de cartões. Deixe A ser o total de suas cartas e B ser o total de cartas de seu oponente. Defina S = A-B como o valor do jogo. Você ganha se S>0, perde se S<0 e empata se S==0.

O mais fácil é fazer dois movimentos ao mesmo tempo, o seu movimento seguido pelo movimento determinado do oponente. Existem dois casos básicos a serem considerados:

• Se length(D) == 0, retorne S. O jogo terminou.

• Se length(D) == 1, retorne S + D[0]. Você escolhe a carta restante e o jogo termina.

Para o caso recursivo, ao length(D) > 1, avalie as duas possibilidades

• Deixe L ser o resultado do jogo se você escolher a carta da esquerda seguida pelo oponente fazendo seu movimento determinístico, ou seja,

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

• Deixe R ser o resultado do jogo se você escolher a carta certa seguida pelo oponente fazendo seu movimento determinístico, ou seja,

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

Escolha a reprodução correspondente ao número maior, ou seja, use D[0] se L>=R, caso contrário, use D[N-1]. Aqui, N = length(D).

Answer 2

Você deve olhar para o Algoritmo Min-Max , possivelmente com Poda alfa-beta

Min-Max é a ideia de que seu oponente sempre escolherá a melhor escolha para si, assim você pode rodar cada cenário possível para descobrir a melhor escolha que resultará em você derrotar seu oponente. "ou seja, dado que eu faço o lance x, meu oponente vai fazer o lance y, então eu vou ..." etc, até o final do jogo. Assim, você pode determinar quem vencerá.

A poda alfa-beta é semelhante, pois olha para cenários possíveis, mas determina se uma lista de cenários possíveis produzirá um resultado vencedor. Se você sabe que se fizer "mover x", sempre perderá, não importa o que aconteça, você não precisa perder mais tempo olhando para "mover x depois mover y". Você pode "podar" todo o ramo de opções de "mover x" porque sabe que nunca será útil.

Answer 3

Este é o código que realmente funcionou no final.Obrigado a todos pelo apoio.

    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;
            }
        }
    }