كيفية إنشاء تقييم جيد وظيفة من أجل لعبة ؟

Question

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

ولكن الآن أنا أكتب برنامج للعب جديدة تماما لعبة المجلس.كيف يمكنني اختيار جيد أو حتى لائقة وظيفة التقييم ؟

التحديات الرئيسية هي أن نفس قطعة دائما على متن الطائرة ، لذلك المعتاد وظيفة المواد لن تتغير على أساس الموقف ، تم لعب لعبة أقل من ألف مرة أو حتى البشر ليس بالضرورة اللعب جيدا بما فيه الكفاية لإعطاء بعد البصيرة.(PS.تعتبر مكتوب النهج ، ولكن ألعاب عشوائية من غير المحتمل أن إنهاء.)

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

Answer 1

العثور على عدد قليل من المرشحين للتقييم الخاص بك وظيفة ، مثل التنقل (# من التحركات المحتملة) ناقص الخصم التنقل ، ثم محاولة العثور على الوزن الأمثل لكل مقياس.الخوارزميات الجينية يبدو أن تعمل بشكل جيد جدا لتحسين الأوزان في تقييم وظيفة.

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

في وقت متأخر تحرير: أكثر قبول, درس, فهم النهج الذي لم أكن أعرف في ذلك الوقت ما يسمى "التفاضلية التطور".ذرية يتم إنشاؤها من 3 الآباء بدلا من 2, في مثل هذه الطريقة التي يتجنب مشكلة المبكرة التلاقي من أجل المتوسط.

Answer 2

سأبدأ مع بعض الأساسيات والانتقال إلى أصعب الاشياء في وقت لاحق.

الوكيل الأساسي وإطار الاختبار

بغض النظر عن النهج الذي تحتاجه تحتاج إلى البدء بشيء بسيط حقا وصوم. أفضل طريقة لعامل غبي هو واحد عشوائي (توليد جميع التحركات الممكنة، حدد واحد عشوائيا). هذا سيكون بمثابة نقطة انطلاق لمقارنة جميع عواملك الآخرين. تحتاج إلى إطار قوي للمقارنة. يتيح شيئا يأخذ عوامل مختلفة، للعب بعض الألعاب بينهما وإرجاع مصفوفة الأداء. بناء على النتائج، تقوم بحساب اللياقة البدنية لكل وكيل. على سبيل المثال وظيفتك tournament(agent1, agent2, agent3, 500) سوف تلعب 500 مباراة بين كل زوج من وكيل (يلعب أول / ثانية) وإرجاع لك شيئا مثل:

  x         -0.01       -1.484   |  -1.485
0.01          x         -1.29    |  -1.483
1.484       1.29          x      |  2.774

هنا على سبيل المثال، استخدم 2 نقطة للفوز، نقطة واحدة لسحب وظيفة التسجيل، وفي النهاية مجرد تلخيص كل شيء للعثور على اللياقة البدنية. هذا الجدول يخبرني على الفور ذلك agent3 هو الأفضل، و agent1 لا يختلف حقا عن agent2.

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

---

لنبدأ باختيار الميزات

1. بادئ ذي بدء، تحتاج إلى إنشاء not a terrible وظيفة التقييم. وهذا يعني أن هذه الوظيفة يجب أن تحدد بشكل صحيح 3 جوانب مهمة (الفوز / السحب / الخسارة). هذا يبدو واضحا، لكنني رأيت كمية كبيرة من الروبوتات، حيث لم يكن المبدعون قادرين على إعداد هذه الجوانب الثلاثة بشكل صحيح.

2. ثم تستخدم براعتك البشرية للعثور على بعض ميزات حالة اللعبة. أول شيء يجب القيام به هو التحدث مع خبير اللعبة واسأله كيف يمكنه الوصول إلى الموقف.

3. إذا لم يكن لديك الخبير، أو أنك قد أنشأت فقط قواعد لعبتك قبل 5 دقائق، فلا تقلل من قدرة الإنسان على البحث عن مقاطع. حتى بعد لعب بضعة ألعاب، يمكن لشخص ذكي أن يعطيك أفكارا كيف كان ينبغي أن يلعب (لا يعني أنه يمكنه تطبيق الأفكار). استخدم هذه الأفكار كميزات.

4. في هذه المرحلة، لا تحتاج حقا إلى معرفة كيف تؤثر هذه الميزات على اللعبة. مثال على الميزات: قيمة القطع، القطع التنقل، التحكم في المناصب الهامة، السلامة، إجمالي عدد التحركات الممكنة، التقارب من أجل النهاية.

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

بناء تقييم أفضل من خلال الجمع بين الميزات البسيطة والتوزيع. هناك بضع مناهج قياسية.

1. إنشاء وظيفة Uber بناء على مجموعات مختلفة من ميزاتك. يمكن أن يكون خطي eval = f_1 * a_1 + ... f_n * a_n (f_i الميزات، a_i معاملات)، ولكن يمكن أن يكون أي شيء. ثم إنشاء مثيل للعديد من العوامل ذات الأوزان العشوائية تماما لهذه وظيفة التقييم واستخدام الخوارزمية الوراثية لتشغيلها مرة أخرى بعضها البعض. قارن النتائج باستخدام إطار الاختبار، وتجاهل اثنين من الخاسرين الواضحين وتحبين زوجين من الفائزين. مواصلة نفس العملية. (هذا مخطط تقريبي، اقرأ المزيد عن GA)

2. استخدم فكرة الانتشار الخلفي من الشبكات العصبية للعودة نشر الخطأ من نهاية اللعبة لتحديث أوزان شبكتك. يمكنك قراءة المزيد كيف تم ذلك مع طاولة الزهر (أنا لم أكتب أي شيء مماثل، لذا آسف للغاية على ضيق).

يمكنك العمل دون وظيفة التقييم! قد يبدو هذا مجنونا للشخص الذي سمع إلا عن MiniMax / Alpha-Beta، ولكن هناك طرق لا تتطلب تقييم على الإطلاق. واحد منهم يسمى بحث شجرة مونت كارلو وكما يوحي مونت كارلو في الاسم أنه يستخدم الكثير من عشوائي (لا ينبغي أن يكون عشوائيا، فيمكنه استخدام لعبة العوامل الجيدة السابقة) تلعب لعبة إنشاء شجرة. هذا موضوع ضخم بحد ذاته، لذلك سأقدم لك شرحا رفيع المستوى حقا. تبدأ بجذر، وإنشاء الحدود الخاصة بك، والتي تحاول توسيعها. بمجرد توسيع شيء ما، تذهب فقط عشوائيا إلى الورقة. الحصول على النتيجة من الورقة، أنت عودة إلى ذلك النتيجة. قم بذلك عدة مرات، وجمع الإحصاءات حول كل طفل من الحدود الحالية. حدد أفضل واحد. هناك نظرية مهمة هناك والتي تتعلق بكيفية التوازن بين الاستكشاف والاستغلال والشيء الجيد قراءتها هناك UCT (خوارزمية الثقة العليا المرتبطة)

Answer 3

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

أيضا، تحقق من الاستيفاء الاستراتيجية للعبة Othello بناء على التعلم التعزيز (رابط PDF) حيث تعطى قواعد اللعبة، يمكن تعلم "وظيفة المكافآت" جيدة. هذا يرتبط ارتباطا وثيقا TD-Gammon ...

أثناء التدريب، تستخدم الشبكة العصبية نفسها لتحديد التحركات لكلا الجانبين ... وكانت النتيجة المفاجئة إلى حد ما هي أن كمية كبيرة من التعلم حدثت بالفعل، حتى في تجارب المعرفة الأولية الصفرية باستخدام ترميز لوحة خام.

Answer 4

إذا كان لا أحد يفهم اللعبة حتى الآن، فلا توجد طريقة يمكنك الحصول على وظيفة تقييم لائقة. لا تقل لي أن ALPHA-Beta القياسي مع عدد المواد جيدة أو حتى لائقة بالنسبة لشطرنج أو متغيراتها (ربما شطرنج الخاسرين استثناء).

يمكنك تجربة الشبكات العصبية مع ردود الفعل أو خوارزميات التعلم الآلية المماثلة ولكنها عادة ما تمتص حتى يكون لديهم الكثير من التدريب، والتي في هذه الحالة ربما غير متوفر. وحتى ذلك الحين، إذا لم يتمتص، فلا يمكنك الحصول على المعرفة منهم.

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

بالطبع، إذا كنت تشارك المزيد من المعلومات حول اللعبة، فيمكنك الحصول على أفكار أفضل من المجتمع.

Answer 5

كما أفهمها، فأنت تريد استخدام وظيفة تقييم ثابتة جيدة في أوراق شجرة Min-Max الخاصة بك. إذا كان الأمر كذلك، فمن الأفضل أن نتذكر أن الغرض من وظيفة التقييم الثابتة هذه هو توفير تصنيف كمادة جيدة لاعب الكمبيوتر. لذلك هو

F (board1)> f (board2)

ثم يجب أن يكون صحيحا أن Board1 أفضل للكمبيوتر (من المرجح أن يفوز في نهاية المطاف) من Board2. بالطبع، لا توجد وظيفة ثابتة صحيحة تماما لجميع اللوحات.

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

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

Answer 6

على الرغم من أنه يمكنك استخدام طرق تعلم الآلات المختلفة للتوصل إلى وظيفة تقييم (تعلم TD، يستخدم في مثل هذه المشاريع مثل Gnubackgammon، فإن النتائج تعتمد بالتأكيد على اللعبة نفسها. بالنسبة إلى الطاولة، فإنها تعمل بشكل جيد حقا، لأن الطبيعة الستوكاستيكية للعبة (المتداول النرد) يجبر المتعلم لاستكشاف الأراضي قد لا ترغب في القيام به. بدون مثل هذا المكونات الحاسمة، فمن المحتمل أن ينتهي بك الأمر بدالة تقييم جيدة ضد نفسها، ولكن ليس ضد الآخرين.

نظرا لأن الاختلاف المادي قد لا يكون قابلا للتطبيق، فهل مفهوم التنقل مهم - أي كم عدد التحركات الممكنة المتوفرة؟ يتحكم في منطقة معينة من اللوحة عادة أفضل من عدم؟ تحدث إلى الأشخاص الذين يلعبون اللعبة لمعرفة بعض القرائن.

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

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

أنا أوصي بشدة النظر أكثر هذه الشرائح.

Answer 7

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

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

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

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

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

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

جاكوب

Answer 8

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