La migliore scelta di carte nel gioco di carte in C #

Question

Il problema consiste nello scegliere la migliore opzione in ogni momento del gioco seguendo queste regole:

• Puoi scegliere solo la carta più a sinistra o più a destra.

• Il tuo avversario sceglierà SEMPRE per primo e sceglierà SEMPRE la carta più alta tra quella più a sinistra o quella più a destra. Se è un pareggio, sceglierà il più a destra. Tieni presente che questa non è sempre la scelta migliore.

A volte è impossibile vincere, ma devi comunque mostrare l'importo più alto che puoi aggiungere giocando contro questo avversario (o strategia, diciamo).

Esempio:

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

Qui, ho scelto 1 invece di 4 al secondo turno, quindi ho potuto scegliere l'8 in seguito. Ecco perché scegliere la carta più alta non è sempre la migliore.

Ho provato a implementare questa soluzione usando la ricorsione ma non sono sicuro che sia l'opzione migliore. Qualche idea su come progettare questo algoritmo?

[MODIFICA] Grazie a @PengOne per il suo generoso aiuto. Questo è il codice che sto cercando di implementare, ma sfortunatamente mi dà degli errori. Cosa dovrei aggiustare? Lo sto modificando man mano che procedo.

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

Crea la soluzione partendo dai casi più semplici utilizzando la ricorsione.

Lascia che D sia l'array di carte. Lascia che A sia il totale delle tue carte e B sia il totale delle carte del tuo avversario. Imposta S = A-B come valore del gioco. Vinci se S>0, perdi se S<0 e pareggio se S==0.

Il modo più semplice è fare due mosse contemporaneamente, la tua mossa seguita dalla mossa determinata dell'avversario. Ci sono due casi base da considerare:

• Se length(D) == 0, restituisce S. Il gioco è terminato.

• Se length(D) == 1, restituisce S + D[0]. Scegli la carta rimanente e il gioco finisce.

Per il caso ricorsivo, quando viene generato un codice tag, valuta le due possibilità

• Lascia che length(D) > 1 sia il risultato del gioco se scegli la carta a sinistra seguita dall'avversario che esegue la sua mossa deterministica, ovvero

  L

• Lascia che L = D[0] - max(D[1],D[N-1]) + cardGameValue(newD) sia il risultato del gioco se scegli la carta giusta seguita dall'avversario che esegue la sua mossa deterministica, ovvero

  R

Scegli il gioco corrispondente al numero più grande, ad esempio prendi R = D[N-1] - max(D[0],D[N-2]) + cardGameValue(newD) se D[0], altrimenti prendi L>=R. Qui D[N-1].

Answer 2

Dovresti esaminare l ' algoritmo min-max , possibilmente con Potatura Alpha-Beta

Min-Max è l'idea che il tuo avversario sceglierà sempre la scelta migliore per se stesso, quindi puoi eseguire ogni possibile scenario per scoprire la scelta migliore che ti porterà a battere il tuo avversario. "cioè, dato che faccio la mossa x, il mio avversario prenderà la mossa y, poi prenderò ..." ecc. fino alla fine della partita. Quindi, puoi determinare chi vincerà.

La potatura Alpha-Beta è simile in quanto esamina i possibili scenari, ma determina se un elenco di possibili scenari produrrà mai un risultato vincente. Se sai che se fai "muovi x", perderai sempre qualunque cosa accada, non hai bisogno di passare più tempo a guardare "muovi x poi muovi y". Puoi "eliminare" l'intero ramo delle scelte da "sposta x" perché sai che non sarà mai utile.

Answer 3

Questo è il codice che ha effettivamente funzionato alla fine.Grazie a tutti per il vostro supporto.

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