Beste Kartenauswahl im Kartenspiel in C #

Question

Das Problem besteht darin, zu jedem Zeitpunkt des Spiels die beste Option nach folgenden Regeln auszuwählen:

• Sie können nur die Karte ganz links oder ganz rechts auswählen.

• Ihr Gegner wählt IMMER zuerst aus und wählt IMMER die höchste Karte entweder ganz links oder ganz rechts aus. Wenn es ein Unentschieden ist, wird es ganz rechts auswählen. Beachten Sie, dass dies nicht immer die beste Wahl ist.

  Manchmal ist es unmöglich zu gewinnen, aber Sie müssen trotzdem den höchsten Betrag anzeigen, den Sie hinzufügen können, indem Sie gegen diesen Gegner (oder eine Strategie, sagen wir) spielen.

  Beispiel:

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

  Hier habe ich in der zweiten Runde 1 statt 4 gewählt, damit ich später die 8 auswählen kann. Deshalb ist die Auswahl der höchsten Karte nicht immer die beste.

  Ich habe versucht, diese Lösung mithilfe von Rekursion zu implementieren, bin mir jedoch nicht sicher, ob dies die beste Option ist. Irgendwelche Ideen zum Entwerfen dieses Algorithmus?

  [BEARBEITEN] Vielen Dank an @PengOne für die großzügige Hilfe. Dies ist der Code, den ich zu implementieren versuche, aber leider gibt er mir Fehler. Was soll ich daran beheben? Ich bearbeite dies im Laufe der Zeit.

  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

Erstellen Sie die Lösung mithilfe von Rekursion aus den einfachsten Fällen.

D sei das Array von Karten. Lassen Sie A die Summe Ihrer Karten und B die Summe aller Karten Ihres Gegners sein. Setzen Sie S = A-B auf den Wert des Spiels. Sie gewinnen, wenn S>0, verlieren, wenn S<0 und binden, wenn S==0.

Am einfachsten ist es, zwei Züge gleichzeitig zu machen, gefolgt von dem entschlossenen Zug des Gegners. Es sind zwei Basisfälle zu berücksichtigen:

• Wenn length(D) == 0, geben Sie S zurück. Das Spiel ist beendet.

• Wenn length(D) == 1, geben Sie S + D[0] zurück. Sie wählen die verbleibende Karte und das Spiel endet.

  Bewerten Sie für den rekursiven Fall beim length(D) > 1 die beiden Möglichkeiten

  • Lassen Sie L das Ergebnis des Spiels sein, wenn Sie die linke Karte auswählen, gefolgt vom Gegner, der seinen deterministischen Zug ausführt, d. h.

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

  • Lassen Sie R das Ergebnis des Spiels sein, wenn Sie die richtige Karte auswählen, gefolgt vom Gegner, der seinen deterministischen Zug ausführt, d. h.

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

    Wählen Sie das Spiel, das der größeren Zahl entspricht, d. h. nehmen Sie D[0], wenn L>=R, andernfalls D[N-1]. Hier N = length(D).

Answer 2

Sie sollten sich den Min-Max-Algorithmus ansehen, möglicherweise mit Alpha-Beta-Bereinigung

Min-Max ist die Idee, dass Ihr Gegner immer die beste Wahl für sich selbst wählt. Sie können also jedes mögliche Szenario ausführen, um die beste Wahl zu finden, die dazu führt, dass Sie Ihren Gegner schlagen. "dh wenn ich Zug x mache, wird mein Gegner Zug y machen, dann werde ich ..." usw. bis zum Ende des Spiels machen. So können Sie bestimmen, wer gewinnt.

Alpha-Beta-Bereinigung ähnelt der Betrachtung möglicher Szenarien, bestimmt jedoch, ob eine Liste möglicher Szenarien jemals zu einem erfolgreichen Ergebnis führen wird. Wenn Sie wissen, dass Sie bei "Verschieben x" immer verlieren, egal was passiert, müssen Sie nicht mehr Zeit damit verbringen, "Verschieben x dann Verschieben y" zu betrachten. Sie können den gesamten Zweig der Auswahlmöglichkeiten von "move x" "abschneiden", da Sie wissen, dass dies niemals hilfreich sein wird.

Answer 3

Dies ist der Code, der am Ende tatsächlich funktioniert hat.Vielen Dank an alle für Ihre Unterstützung.

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