بعد الطفرة الحقيقية لألعاب الطاولة في أواخر القرن العشرين ، تركت الأسرة العديد من الصناديق مع الألعاب. واحد منهم هو لعبة "Hare and Hedgehog" في النسخة الألمانية الأصلية. تفوز لعبة للعديد من اللاعبين ، حيث يتم تقليل عنصر العشوائية إلى الحد الأدنى ، ويفوز الحساب الرصين وقدرة اللاعب على "التطلع إلى الأمام" بعدة خطوات.

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

قواعد اللعبة هير والقنفذ

يوجد في ساحة اللعب في 65 خلية العديد من رقائق اللاعبين ، من 2 إلى 6 مشاركين (رسوماتي ، غير الكنسي ، تبدو بالطبع ، إلخ):



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

"الوقود" للمضي قدمًا هو الجزرة - " عملة اللعبة". في البداية ، يتلقى كل لاعب 68 جزرة ، وهو ما يعطيه (وأحيانًا يستلمها) وهو يتحرك.

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

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

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

يمكن للاعب تخطي هذه الخطوة ، والبقاء على القفص مع صورة الجزر وتلقي أو إعطاء 10 جزر لهذا الإجراء. لماذا يجب أن يعطي اللاعب "الوقود"؟ الحقيقة هي أنه لا يمكن للاعب إنهاء 10 جزرة إلا بعد انتقاله الأخير (20 إذا أنهيت الثانية ، 30 إذا حصلت على المركز الثالث ، إلخ).

أخيرًا ، يمكن للاعب الحصول على 10 × جزر من الجزر عن طريق اتخاذ خطوات N على أقرب قنفذ مجاني (إذا كان أقرب قنفذ مشغول ، فهذه الخطوة مستحيلة).

يتم حساب تكلفة التحرك للأمام بشكل غير متناسب مع عدد الحركات ، وفقًا للصيغة (مع التقريب لأعلى):

$$$\ frac {N + N ^ 2} {2}$ ،
حيث N هو عدد الخطوات للأمام.

للتقدم إلى الأمام في خلية واحدة ، يعطي اللاعب 1 جزرة و 3 جزرات لخليتين و 6 جزرة ل 3 خلايا و 10 لل 4 و ... و 210 جزرة لتحريك 20 خلية للأمام.

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

التنفيذ بدون الذكاء الاصطناعى

في أول تطبيق ، والذي سيصبح بعد ذلك أساسًا لتطوير اللعبة "intellect" ، قصرت نفسي على الخيار الذي يقوم به كل لاعب بالتحرك - أي شخص.

قررت تطبيق اللعبة كعميل - موقع ثابت من صفحة واحدة ، يتم تطبيق كل "المنطق" على JS والخادم - تطبيق WEB API. تمت كتابة الخادم في .NET Core 2.1 وتنتج قطعة أثرية واحدة للتجميع - ملف dll ، والذي يمكن تشغيله في نظام Windows / Linux / Mac OS.

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

الخادم هو آلة مور الكلاسيكية. يفتقر منطق الخادم إلى مفاهيم مثل "العميل المتصل" و "جلسة اللعب" ، إلخ.

كل ما يفعله الخادم هو معالجة الأمر المتلقي (HTTP POST). يتم تطبيق نمط "الأمر" على الخادم. قد يطلب العميل تنفيذ أحد الأوامر التالية:

• بدء لعبة جديدة ، أي "ضع" رقائق لعدد معين من اللاعبين على لوحة "نظيفة"
• قم بإجراء الخطوة المشار إليها في الأمر

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

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

لا يحتاج الخادم إلى إرسال معلومات إضافية - على سبيل المثال ، معلومات حول الملعب. تمامًا كما هو الحال في تسجيل رسم الشطرنج ، ليس من الضروري رسم ترتيب الخلايا السوداء والبيضاء على السبورة - فهذه المعلومات تعتبر ثابتة.

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

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

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

بدوره لاعب

يتم تشفير دور اللاعب على شكل عدد صحيح:

1. 0 ، إذا اضطر اللاعب إلى البقاء في الخلية الحالية ،
   1 ، 2 ، ... N لـ 1 ، ... N خطوات للأمام ،
2. -1 ، -2 ، ... -M لنقل 1 ... خلايا M مرة أخرى إلى أقرب القنفذ الحر ،
3. 1001 ، 1002 - رموز خاصة للاعب الذي قرر البقاء في خلية الجزرة واستلام (1001) أو إعطاء (1002) 10 جزر لذلك.

تنفيذ البرامج

يستقبل الخادم JSON للأمر المطلوب ، ويقوم بتوزيعه في أحد فئات الطلب المقابلة ، ويقوم بتنفيذ الإجراء المطلوب.

إذا طلب العميل (المشغل) التحرك برمز CMD من الموضع (POS) المنقول إلى الفريق ، فإن الخادم ينفذ الإجراءات التالية:

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

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

عند إدخال طرق الفحص / التنفيذ ، يتلقى TurnChecker كائنًا من فئة موضع اللعبة (التخلص). يحتوي كائن Disposition على صفيف به بيانات اللاعب (Haze [] hazes) ، وهو مؤشر اللاعب الذي يقوم بنقل + بعض معلومات الخدمة التي تم تعبئتها أثناء تشغيل كائن TurnChecker.

يصف ميدان اللعب فئة FieldMap ، والتي يتم تنفيذها كحالة مفردة . يحتوي الفصل على مجموعة من الخلايا + بعض المعلومات العامة المستخدمة لتبسيط / تسريع العمليات الحسابية اللاحقة.

التنفيذ مع منظمة العفو الدولية

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

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

تقييم الموقف التجريبي

على سبيل المثال ، في لعبة الشطرنج ، يعد إجراء تقييم (دون الزحف إلى براري الفتحات) أمرًا بسيطًا للغاية: على الأقل ، يمكنك حساب "التكلفة" الإجمالية للقطع من خلال أخذ قيمة الفارس / الأسقف بثلاثة رهن ، وقيمة رهان البيدق 5 ، البيدق ، والملكة 9 .MaxValue البيدق . من السهل تحسين التقدير ، على سبيل المثال ، الإضافة إليه (مع عامل تصحيح - عامل / الأس أو وظيفة أخرى):

• عدد التحركات المحتملة من الوضع الحالي ،
• نسبة التهديدات لشخصيات العدو / تهديدات العدو.

يتم إعطاء تقييم خاص لموضع حصيرة: int.MaxValue ، إذا وضع الشيك على جهاز الكمبيوتر ، int.MinValue إذا كان الشيك وضع الشخص.

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

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

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

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

في الحالة العامة ، في لعبة Hare and the Hedgehog ، هناك مبدأ مكشوف إلى حد ما يعمل: " من الأفضل أن نمضي قدمًا أكثر مع المزيد من الجزر وسلطة أقل ". ومع ذلك ، ليس كل شيء واضح جدا. لنقل أنه إذا كان لدى اللاعب بطاقة سلطة واحدة في منتصف اللعبة ، فقد يكون هذا الخيار جيدًا. لكن من الواضح أن اللاعب الذي يقف عند خط النهاية ببطاقة السلطة سيكون في موقف خاسر. بالإضافة إلى خوارزمية التقييم ، أود أيضًا أن أكون قادرًا على "إلقاء نظرة خاطفة" على خطوة إلى الأمام ، تمامًا مثلما يمكن حساب التهديدات على القطع في تقييم إرشادي لموقف الشطرنج. على سبيل المثال ، تجدر الإشارة إلى مكافأة الجزر التي يتلقاها اللاعب الذي يترك خلية / موضع الخس (1 ... 4) ، مع مراعاة عدد اللاعبين الموجودين في المقدمة.

استنتجت الصف النهائي كدالة:

E = Ks * S + Kc * C + Kp * P ،

حيث يتم احتساب الدرجات S و C و P باستخدام بطاقات السلطة (S) والجزر © بين يدي اللاعب ، P هي الدرجات الممنوحة للاعب للمسافة المقطوعة.

Ks و Kc و Kp هي عوامل التصحيح المقابلة (سيتم مناقشتها لاحقًا).

أسهل طريقة هي تحديد العلامة للمسار الذي تم الانتقال إليه :
P = i * 3 ، حيث i هو مؤشر الخلية التي يقع عليها اللاعب.

التصنيف C (الجزر) أصعب بالفعل.

للحصول على قيمة C محددة ، اخترت واحدة من 3 وظائف $$$C_0 ، C_1 ، C_2$ من حجة واحدة (عدد الجزر على اليدين). يتم تحديد مؤشر الوظيفة C ([0 ، 1 ، 2]) حسب الموضع النسبي للاعب في ساحة اللعب:

• [0] إذا أكمل اللاعب أقل من نصف الملعب ،
• [2] إذا كان لدى اللاعب ما يكفي من الجزر (ميغابايت ، بل وفيرة) حتى النهاية ،
• [1] في حالات أخرى.

وظائف 0 و 1 متشابهة: "القيمة" لكل جزرة في يد اللاعب تتناقص تدريجيا مع زيادة عدد الجزر في اليدين. نادرا ما تشجع اللعبة Plyushkins. في الحالة 1 (تم تمرير نصف الحقل) ، تنخفض قيمة الجزر بشكل أسرع قليلاً.

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

قبل حساب كمية الجزر على أيدي اللاعب ، مع مراعاة الجزر لكل خطوة من خلية الخس / رقم الخلية 1 ... 4.

يتم استنتاج درجة " الخس " من الدرجة S بطريقة مماثلة. اعتمادًا على مقدار السلطة على أيدي اللاعب (0 ... 3) ، يتم تحديد وظيفة $$$S_0 ، S_1 ، S_2$ او $$$S_3 دولا$ . حجة وظيفة $$$S_0 - S_3$ . - مرة أخرى ، المسار "النسبي" الذي يسلكه اللاعب. وهي عدد الخلايا التي تحتوي على سلطة في الجبهة (بالنسبة للخلية التي يشغلها اللاعب):



المنحنى $$$S_0 دولا$ - وظيفة التقييم (S) على عدد خلايا الخس أمام اللاعب (0 ... 5) ، للاعب الذي يحتوي على 0 بطاقات من الخس ،
المنحنى $$$S_1$ - نفس الوظيفة للاعب مع بطاقة سلطة واحدة في متناول اليد ، إلخ.

تأخذ الدرجة النهائية (E = Ks * S + Kc * C + Kp * P) في الاعتبار:

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

وهنا كيف يلعب الكمبيوتر ، واختيار الخطوة التالية مع أقصى درجات الاستدلال:



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

شجرة القرار و Minimax خوارزمية

نستخدم خوارزمية صنع القرار في لعبة Minimax العدائية. جيد جدا ، في رأيي ، الخوارزمية موصوفة في هذا المنشور (ترجمة) .

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



لنفترض أن اللعبة تنتهي بعد الحركة الثانية للكمبيوتر ويتم تقييم كل موقع من المواضع المستلمة من وجهة نظر اللاعبين الأول والثاني. وقمنا بالفعل بتنفيذ خوارزمية التقييم. دعونا تقييم كل من المواقف النهائية (أوراق الشجرة 9 ... 18) في شكل ناقل $$$[v_0، v_1]$ ،
اين $$$v_0$ - النتيجة محسوبة لأول لاعب ، $$$v_1$ - درجة اللاعب الثاني:



نظرًا لأن الكمبيوتر يتخذ الخطوة الأخيرة ، فمن الواضح أنه سيختار الخيارات في كل من الأشجار الفرعية ([9 ، 10] ، [11] ، [12 ، 13] ، [14 ، 15 ، 16] ، [17 ، 18]) مما يعطيه تصنيف أفضل. السؤال الذي يطرح نفسه على الفور: من أي مبدأ ينبغي للمرء اختيار "أفضل" الموقف؟

على سبيل المثال ، هناك حركتان ، وبعد ذلك لدينا مواقف مع تصنيفات [5 ؛ 5] و [2 ؛ 1]. يقيم اللاعب الأول. بديلان واضحان:

• اختيار الموضع مع الحد الأقصى للقيمة المطلقة لدرجة i-th للاعب i. وبعبارة أخرى ، المتسابق النبيل ليزلي ، حريصة على النصر ، دون النظر إلى المنافسين. في هذه الحالة ، موقف مع تقدير [5 ؛ 5].
• إن اختيار المنصب ذي الحد الأقصى من التصنيف بالنسبة لتقديرات المنافسين هو الأستاذ الماهر فيث ، الذي لا يفوت فرصة لإحداث حيل قذرة على العدو. على سبيل المثال ، تخلف عن عمد وراء لاعب يخطط للبدء من المركز الثاني. عنصر مع تصنيف [2؛ 1].

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


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



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

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



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

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

لكن لعبة نموذجية للاعبين تدوم في المتوسط ​​حوالي 30 إلى 40 خطوة (لثلاثة لاعبين - حوالي 60 حركة ، إلخ). من كل موقف ، يمكن للاعب عادةً إجراء حوالي 8 حركات. وبالتالي ، فإن شجرة كاملة من المواقف المحتملة لمدة 30 خطوة تتكون من تقريبا
$$$8 ^ {30}$ = 1237940039285380274899124224 قمم!

في الممارسة العملية ، يستغرق بناء و "تحليل" شجرة مؤلفة من حوالي 100000 موقع على جهاز الكمبيوتر الخاص بي حوالي 300 مللي ثانية. مما يعطينا حدًا لعمق الشجرة من 7 إلى 8 مستويات (حركات) ، إذا كنا نريد أن نتوقع استجابة كمبيوتر لا تزيد عن ثانية.

ضبط منظمة العفو الدولية

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

• تحسين البناء / اجتياز شجرة القرار ،
• تحسين الاستدلال.

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

في المثال أعلاه ، يمكننا رفض النظر في الموضع 8 و "حفظ" 2 - 3 رؤوس الشجرة:



نسير حول الشجرة من أعلى إلى أسفل ، من اليسار إلى اليمين. بعد تجاوز الشجرة الفرعية بدءًا من الموضع 2 ، استنتجنا أفضل تقدير للحركة 1 -> 2: [3 ، 2]. بتجاوز الشجرة الفرعية مع الجذر في الموضع 7 ، حددنا التصنيف الحالي (الأفضل للحركة 3 -> 7): [2 ، 4]. من وجهة نظر الكمبيوتر (اللاعب الأول) ، تكون النتيجة [2 ، 4] أسوأ من النتيجة [3 ، 2]. ونظرًا لأن خصم الكمبيوتر يختار الانتقال من الموضع 3 ، أيا كانت درجة الموضع 8 ، فإن النتيجة النهائية للموضع 3 ستكون أولية أسوأ من النتيجة التي تم الحصول عليها للمركز الثالث. وفقا لذلك ، لا يمكن بناء الشجرة الفرعية مع الجذر في الموضع 8 ولا تقييمها.

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

تحسين لقطة ألفا بيتا الثانوية

مع تمكين خيار القطع في إعدادات AI ، تم تقليل عدد القمم في شجرة الموضع بمعدل 3 مرات في المتوسط. هذه النتيجة يمكن تحسينها إلى حد ما.

في المثال أعلاه:



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

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

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


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

في إعدادات الذكاء الاصطناعى ، قمت بضبط متجه "لقطة لأسوأ الخيارات". على سبيل المثال ، يعني متجه النموذج [0 ، 0 ، 8 ، 8 ، 4] أن:

• بالنظر إلى خطوة واحدة [0] وخطوتين [0] إلى الأمام ، سينظر البرنامج في جميع التحركات المحتملة ، لأن 0 ,
• بالنظر إلى ثلاث [8] وأربع خطوات [8] إلى الأمام ، سينظر البرنامج في ما يصل إلى 8 حركات "أفضل" مؤدية من الموضع التالي ، شاملة ،
• بالنظر إلى خمس خطوات أو أكثر للأمام [4] ، سيقوم البرنامج بتقييم أكثر من 4 خطوات "أفضل".

مع تشغيل الفرز لخوارزمية لقطة ألفا بيتا وناقل مشابه في إعدادات القطع ، بدأ البرنامج في إنفاق حوالي 300 مللي ثانية لاختيار خطوة شبه مثالية ، "التقدم أعمق" 8 خطوات للأمام.

الاستدلال الأمثل

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

عوامل التصحيح

في وقت سابق ، مع إعطاء صيغة لتقدير مجريات الأمور للوضع الحالي
E = Ks * S + Kc * C + Kp * P ،
ذكرت ، ولكن لم أصف ، عوامل التصحيح.

والحقيقة هي أن كل من الصيغة نفسها ومجموعات من الوظائف$$C 0 . . C 2 ، ق 0 . . S 5 ، تم استنباطها من حدسي ، على أساس ما يسمى "الحس السليم". على الأقل ، أود تحديد معاملات Ks و Kc و Kp بحيث يكون التقدير مناسبًا قدر الإمكان. كيف يتم تقييم "كفاية" التقييم؟ التقييم هو كمية بدون أبعاد ، ولا يمكن مقارنته إلا بتقدير آخر. تمكنت من الوصول إلى الطريقة الوحيدة لتحسين معاملات التصحيح:وضعت في البرنامج عددًا من "الدراسات" المخزنة في ملف CSV مع بيانات النموذج$C_0 .. C_2, S_0 .. S_5$

  45;26;2;f;29;19;0;f;2 ... 

يعني هذا السطر حرفيًا ما يلي:

• اللاعب الأول في المربع 45 ، لديه 26 بطاقة من الجزر وبطاقتي سلطة في يده ، لا يفوت اللاعب أي تحرك (f = false). حق التحرك هو دائما اللاعب الأول.
• اللاعب الثاني في الخلية 29 مع 19 بطاقة من الجزر وبدون بطاقات سلطة ، لا يفوتك أي تحرك.
• الرقم الثاني يعني أنه "عند تحديد" الدراسة ، افترضت أن اللاعب الثاني في وضع رابح.

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

بعد تقييم 20 etudes (بالطبع ، سيكون من المجدي تحليل المزيد منها) ، قمت بتقييم كل من etudes بواسطة البرنامج. في التقييم ، قيم كل من عوامل التصحيح ، من 0.5 إلى 2 في الزيادات من 0.1 - المجموع$$16 3 = 4096 المتغيرات الثلاثية من المعاملات. إذا تبين أن درجة اللاعب الأول أعلى من درجة اللاعب الثاني ، وتم تخزين تعليمة مماثلة في سطر سجل etude (القيمة الأخيرة للخط هي 1) ، يتم حساب "ضرب". وبالمثل لحالة المرآة. خلاف ذلك ، تم حساب زلة. نتيجةً لذلك ، اخترت تلك الثلاثية التي كانت فيها نسبة "الزيارات" الحد الأقصى (16 من أصل 20). خرج حوالي 250 من بين 4096 متجهًا ، اخترت منها "الأفضل" ، مرة أخرى ، "بالعين" ، وقمت بتثبيته في إعدادات AI.$16^3$

ملخص

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

على سبيل المثال ، في منطق اختيار التصنيفات (الحد الأقصى المطلق أو الأقصى بالنسبة للاعبين الآخرين) ، سأحاول بالتأكيد خيارًا متوسطًا. كحد أدنى ، إذا كانت القيمة المطلقة لنتائج اللاعب ith مساوية ، فمن المعقول اختيار خطوة تؤدي إلى موقع ذي قيمة نسبية أعلى من النتيجة (مزيج من Leslie النبيل و Feith الغادر).

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

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

→ رابط إلى مستودع مع مصدر