C# のカード ゲームで最適なカードの選択

Question

問題は、次のルールに従ってゲームのあらゆる瞬間に最適な選択肢を選択することにあります。

• 一番左または一番右のカードのみを選択できます。

• 対戦相手は常に最初にカードを選び、常に左端または右端のカードから最も高いカードを選択します。同点の場合は、一番右を選択します。これが常に最良の選択であるとは限らないことを考慮してください。

勝つことが不可能な場合もありますが、とにかくこの相手 (または戦略) と対戦して追加できる最高額を表示する必要があります。

例：

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

ここでは、後で 8 を選択できるように、2 ターン目に 4 ではなく 1 を選択しました。そのため、最高のカードを選択することが常に最善であるとは限りません。

再帰を使用してこのソリューションを実装しようとしましたが、それが最良のオプションであるかどうかわかりません。このアルゴリズムを設計する方法について何かアイデアはありますか?

編集] @Pengoneに寛大な助けをありがとう。これは実装しようとしているコードですが、残念ながらエラーが発生します。その中で何を直せばいいのでしょうか？進行に合わせてこれを編集しています。

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

再帰を使用して、最も単純なケースからソリューションを構築します。

させて D カードの配列になります。させて A あなたのカードの合計になり、 B 相手のカードの合計となります。セット S = A-B ゲームの価値になります。そうすれば勝ちます S>0, 、次の場合は負けます S<0 そして結ぶ場合 S==0.

最も簡単なのは、一度に 2 つの動きをすることです。自分の動きの後に相手の決められた動きを続けます。考慮すべき基本的なケースが 2 つあります。

• もし length(D) == 0, 、 戻る S. 。ゲームは終了しました。

• もし length(D) == 1, 、 戻る S + D[0]. 。残ったカードを選択するとゲームが終了します。

再帰的なケースの場合、 length(D) > 1, 、2 つの可能性を評価します

• させて L あなたが左のカードを選択し、その後に対戦相手が決定的な動きをした場合、ゲームの結果になります。

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

• させて R あなたが正しいカードを選択し、その後に対戦相手が決定的な動きをした場合、ゲームの結果が決まります。

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

大きい方の数字に対応するプレイを選択してください。取る D[0] もし L>=R, 、それ以外の場合はかかります D[N-1]. 。ここ N = length(D).

Answer 2

最小-最大アルゴリズムをアルファベータ法

Min-Maxは、対戦相手が常に自分にとって最良の選択を選択するという考えです。したがって、考えられる各シナリオを実行して、対戦相手を打ち負かす結果となる最良の選択を見つけることができます。 「つまり、私がxの動きをすると、対戦相手はyの動きを取り、それから私は...を取ります」など、ゲームの最後まで続きます。したがって、誰が勝つかを決めることができます。

アルファベータ法は、考えられるシナリオを調べるのと似ていますが、考えられるシナリオのリストが勝利の結果を生み出すかどうかを決定します。 「movex」を作成すると、何があっても常に緩むことがわかっている場合は、「move x thenmovey」を見るのに時間をかける必要はありません。 「movex」から選択肢のブランチ全体を「削除」することができます。これは、決して役に立たないことがわかっているためです。

Answer 3

これは実際に最終的に機能したコードです。皆様のご支援に感謝いたします。 ジェネラコディセタグプレ