La mejor opción de tarjeta en el juego de cartas en C #

Question

El problema consiste en elegir la mejor opción en cada momento del juego siguiendo estas reglas:

• Solo puede elegir la tarjeta más a la izquierda o la más a la derecha.

• Tu oponente SIEMPRE elegirá primero, y SIEMPRE elegirá la carta más alta de la carta más a la izquierda o la más a la derecha. Si es un empate, elegirá el más a la derecha. Tenga en cuenta que esta no siempre es la mejor opción.

A veces es imposible ganar, pero de todos modos debes mostrar la mayor cantidad que puedas agregar jugando contra este oponente (o estrategia, digamos).

Ejemplo:

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

Aquí, elegí 1 en lugar de 4 en el segundo turno, para poder elegir el 8 más tarde. Por eso, elegir la carta más alta no siempre es lo mejor.

He intentado implementar esta solución mediante la recursividad, pero no estoy seguro de que sea la mejor opción. ¿Alguna idea sobre cómo diseñar este algoritmo?

[EDITAR] Gracias a @PengOne por su generosa ayuda. Este es el código que estoy tratando de implementar, pero desafortunadamente me está dando errores. ¿Qué debo arreglar en él? Estoy editando esto a medida que avanzo.

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

Cree la solución a partir de los casos más simples utilizando la recursividad.

Sea D la matriz de tarjetas. Deja que A sea el total de tus cartas y B el total de las cartas de tu oponente. Establezca S = A-B como el valor del juego. Usted gana si S>0, pierde si S<0 y empata si S==0.

Lo más fácil es hacer dos movimientos a la vez, tu movimiento seguido por el movimiento decidido del oponente. Hay dos casos básicos a considerar:

• Si length(D) == 0, devuelve S. El juego ha terminado.

• Si length(D) == 1, devuelve S + D[0]. Eliges la carta restante y el juego termina.

Para el caso recursivo, cuando length(D) > 1, evalúe las dos posibilidades

• Deja que L sea el resultado del juego si eliges la carta de la izquierda seguida por el oponente haciendo su movimiento determinista, es decir

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

• Deja que R sea el resultado del juego si eliges la carta correcta seguida por el oponente haciendo su movimiento determinista, es decir

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

Elija la jugada correspondiente al número mayor, es decir, tome D[0] si L>=R, de lo contrario, tome D[N-1]. Aquí N = length(D).

Answer 2

Debería consultar el algoritmo Min-Max , posiblemente con Poda alfa-beta

Min-Max es la idea de que tu oponente siempre elegirá la mejor opción por sí mismo, por lo que puedes ejecutar cada escenario posible para descubrir la mejor opción que resultará en vencer a tu oponente. "es decir, dado que hago el movimiento x, mi oponente tomará el movimiento y, luego yo tomaré ...", etc., hasta el final del juego. Por lo tanto, puede determinar quién ganará.

La poda alfa-beta es similar a la observación de posibles escenarios, pero determina si una lista de posibles escenarios alguna vez producirá un resultado ganador. Si sabe que si hace "mover x", siempre perderá sin importar qué, no necesita pasar más tiempo mirando "mover x luego mover y". Puede "podar" toda la rama de opciones de "mover x" porque sabe que nunca será útil.

Answer 3

Este es el código que realmente funcionó al final.Gracias a todos por su apoyo.

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