خوارزمية الحد الأدنى

Question

لدي سؤال بسيط بشأن خوارزمية Minimax: على سبيل المثال لعبة Tic-Tac-Toe ، كيف يمكنني تحديد وظيفة الأداة المساعدة لكل لاعب؟ لا يفعل ذلك تلقائيًا ، أليس كذلك؟ يجب أن أقوم بتدوين القيم المتشددة في اللعبة ، ولا يمكن أن تتعلمها بنفسها ، أليس كذلك؟

Answer 1

لا ، لا يتعلم الحد الأدنى. إنها نسخة أكثر ذكاءً من البحث عن الأشجار الغاشمة.

Answer 2

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

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

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

Answer 3

Tic-Tac-Toe صغير بما يكفي لتشغيل اللعبة حتى النهاية وتعيين 1 للفوز ، 0 للسحب و -1 لخسارة.

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

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

Answer 4

كيف تحدد وظيفة الأداة المساعدة لكل مسرحية؟

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

لا يمكن أن تتعلمهم بنفسه ، أليس كذلك؟

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

بعد تعلم هذه الطريقة الرائعة لتعليم الكمبيوتر كيفية اللعب ، قد لا نكون مهتمين بالعودة إلى Minmax كما هو مطبق على Tic-Tac-Toe. بعد كل ذلك Minmax هي وسيلة بسيطة نسبيًا لتقليم شجرة القرار, ، وهو ما لا يلزم بالكاد مع مساحة لعبة Tic-Tac-Toe الصغيرة. ولكن ، إذا كان يجب علينا ؛-) [عد إلى مينماكس] ...

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

خلاصة القول: في حالة tic-tac-toe ، يصبح Minmax أكثر إثارة للاهتمام فقط (على سبيل المثال في مساعدتنا على استكشاف فعالية وظيفة فائدة معينة) عندما نزيل الطبيعة الحتمية للعبة ، المرتبطة بالتقييم السهل الكامل شجرة. هناك طريقة أخرى لجعل اللعبة [من الناحية الرياضية] مثيرة للاهتمام هي اللعب مع خصم يرتكب أخطاء ...