أفضل خيار بطاقة في لعبة بطاقة في ج#

Question

تكمن المشكلة في اختيار الخيار الأفضل في كل لحظة من اللعبة باتباع هذه القواعد:

• يمكنك فقط اختيار أقصى اليسار أو أقصى اليمين بطاقة.

• سيختار خصمك دائما أولا ، وسيختار دائما أعلى بطاقة من أقصى اليسار أو أقصى اليمين.إذا كان التعادل ، فإنه سيتم اختيار أقصى اليمين.تأخذ في الاعتبار هذا ليس دائما الخيار الأفضل.

في بعض الأحيان يكون من المستحيل الفوز ، ولكن يجب عليك على أي حال عرض أعلى مستوى يمكنك إضافته من خلال اللعب ضد هذا الخصم (أو الإستراتيجية ، دعنا نقول).

مثال:

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

هنا ، اخترت 1 بدلا من 4 في المنعطف الثاني ، حتى أتمكن من اختيار 8 لاحقا.هذا هو السبب في اختيار أعلى بطاقة ليست دائما أفضل.

لقد كنت أحاول تنفيذ هذا الحل باستخدام العودية ولكني لست متأكدا من أنه الخيار الأفضل.أي أفكار حول كيفية تصميم هذه الخوارزمية?

[عدل] بفضل @ بينغون لأنها مساعدة سخية.هذا هو رمز إم تحاول تنفيذ ، ولكن للأسف انها تعطيني أخطاء.ما الذي يجب أن أصلحه فيه?أنا تحرير هذا وأنا التقدم.

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.

الأسهل هو القيام بحركتين في وقت واحد ، تحركك متبوعا بحركة الخصم المحددة.هناك نوعان من الحالات الأساسية للنظر فيها:

• إذا length(D) == 0, عودة S.انتهت اللعبة.

• إذا length(D) == 1, عودة S + D[0].اخترت البطاقة المتبقية ، وتنتهي اللعبة.

بالنسبة للحالة العودية ، عندما length(D) > 1, ، تقييم الاحتمالين

• دعونا 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 Algorithm ، ربما باستخدام تقليم Alpha-Beta

Min-Max هي فكرة أن خصمك سيختار دائمًا الخيار الأفضل لأنفسهم ، وبالتالي يمكنك تشغيل كل سيناريو محتمل لاكتشاف الخيار الأفضل الذي سينتج عنه هزيمة خصمك. "على سبيل المثال ، نظرًا لأنني أقوم بحركة x ، فإن خصمي سيأخذ الحركة y ، ثم سآخذ ..." إلخ ، حتى نهاية اللعبة. وبالتالي ، يمكنك تحديد من سيفوز.

يتشابه تقليم Alpha-Beta في النظر إلى السيناريوهات المحتملة ، ولكنه يحدد ما إذا كانت قائمة السيناريوهات المحتملة ستؤدي إلى نتيجة رابحة. إذا كنت تعلم أنك إذا قمت بحركة "س" ، فستفقد دائمًا بغض النظر عن السبب ، فلن تحتاج إلى قضاء المزيد من الوقت في البحث عن "حرك س ثم تحرك ص". يمكنك "تقليم" فرع الخيارات بأكمله من "move x" لأنك تعلم أنه لن يكون مفيدًا أبدًا.

Answer 3

هذه هي الشفرة التي عملت بالفعل في النهاية.شكرا للجميع على دعمكم. Genacodicetagpre