خوارزمية الحد الأدنى: وظيفة التكلفة/التقييم؟

Question

مشروع مدرسي جعلني أكتب لعبة تاريخ في C ++ (مثال على http://www.cut-the-knot.org/curriculum/games/date.shtml) حيث يجب على مشغل الكمبيوتر تنفيذ خوارزمية الحد الأدنى مع تقليم ألفا بيتا. حتى الآن ، أفهم ماهية الهدف وراء الخوارزمية من حيث زيادة المكاسب المحتملة مع افتراض أن الخصم سيؤدي إلى إعدامهم.

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

يخبرني الحدس أنه سيكون شيئًا مثل +1 لعقدة أوراق الفوز ، و -1 للخسارة ، ولكن كيف يتم تقييم العقد الوسيطة؟

أي مساعدة سيكون أكثر تقدير.

Answer 1

يقوم الحد الأدنى الأساسي بتقييم العقد الورقية فقط ، والوصول إلى الفوز ، والخسائر والرسم ، ودعم تلك القيم لأعلى الشجرة لتحديد قيم العقدة الوسيطة. في حالة أن شجرة اللعبة قابلة للتحفظ ، تحتاج إلى استخدام عمق القطع كمعلمة إضافية لوظائف الحد الأدنى الخاص بك. بمجرد الوصول إلى العمق ، تحتاج إلى تشغيل نوع من وظيفة التقييم للحالات غير المكتملة.

معظم وظائف التقييم في بحث الحد الأدنى هي محددة ، لذلك قد يكون العثور على مساعدة للعبة الخاصة بك أمرًا صعبًا. فقط تذكر أن التقييم يحتاج إلى إرجاع نوع من التوقعات المئوية للموقف كونه فوزًا لاعبًا معينًا (عادةً ما يكون الحد الأقصى ، ولكن ليس عند استخدام تنفيذ Negamax). تشبه أي لعبة أقل بحثًا عن كثب لعبة أخرى أكثر بحثًا. يربط هذا واحد عن كثب مع اللعبة عصي الالتقاط. باستخدام Minimax و Alpha Beta فقط ، أعتقد أن اللعبة قابلة للمعارضة.

إذا كان يجب عليك إنشاء وظيفة تقييم للمواقف غير الطرفية ، فإليك القليل من المساعدة في تحليل لعبة العصي ، والتي يمكنك تحديد ما إذا كانت مفيدة للعبة التاريخ أم لا.

ابدأ في البحث عن وسيلة لفرض نتيجة من خلال النظر إلى موقف نهائي وجميع التحركات التي يمكن أن تؤدي إلى هذا الموقف. في لعبة العصي ، يكون وضع الطرفية مع 3 أو أقل من العصي المتبقية في الخطوة الأخيرة. الموقف الذي يستمر على الفور هذا الموقف الطرفي يترك 4 عصيًا لخصمك. الهدف هو الآن ترك خصمك مع 4 عصي بغض النظر عن ماذا ، ويمكن القيام بذلك من 5 أو 6 أو 7 عصي تترك لك ، وترغب في إجبار خصمك على تركك في أحد هذه المواقف. المكان الذي يجب أن يكون فيه خصمك حتى تكون في 5 أو 6 أو 7 هو 8. تابع هذا المنطق ويصبح نمطًا متاحًا بسرعة كبيرة. اترك دائمًا خصمك برقم قابل للقسمة بمقدار 4 وتفوز ، أي شيء آخر ، تخسره.

هذه لعبة تافهة إلى حد ما ، لكن طريقة تحديد الإرشادات هي المهم لأنه يمكن تطبيقه مباشرة على مهمتك. نظرًا لأن آخر تحرك يسير أولاً ، ويمكنك تغيير سمة تاريخ واحد فقط في وقت واحد ، فأنت تعلم أن الفوز يجب أن يكون هناك حركتان بالضبط ... وهكذا.

حظا سعيدا ، أخبرنا بما ينتهي بك الأمر.

Answer 2

أبسط حالة وظيفة التقييم هي +1 للفوز ، -1 لخسارة و 0 لأي موقف غير مملوء. بالنظر إلى شجرتك عميقة بما فيه الكفاية ، حتى هذه الوظيفة البسيطة ستمنحك لاعبًا جيدًا. بالنسبة لأي ألعاب غير تافهة ، ذات عامل متفرع عالي ، عادة ما تحتاج إلى وظيفة أفضل ، مع بعض الاستدلال (على سبيل المثال بالنسبة للشطرنج ، يمكنك تعيين أوزان إلى قطع وإيجاد مبلغ ، وما إلى ذلك). في حالة لعبة التاريخ ، أود فقط استخدام أبسط وظيفة تقييم ، مع 0 لجميع العقد الوسيطة.

كملاحظة جانبية ، ليس Minimax أفضل خوارزمية لهذه اللعبة بالذات ؛ لكني أعتقد أنك تعرف ذلك بالفعل.

Answer 3

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

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

ستبدو خوارزمية الحد الأدنى (بدون تقليم ألفا بيتا) شيئًا من هذا القبيل:

A_move(day):
   if day==December 31:
       return +1
   else:
       outcome=-1
       for each day obtained by increasing the day or month in cur_date:
           outcome=max(outcome,B_move(day))
       return outcome

B_move(day):
   if day==December 31:
       return -1
   else:
       outcome=+1
       for each day obtained by increasing the day or month in cur_date:
           outcome=min(outcome,A_move(day))
       return outcome