دليل خطوة بخطوة لبناء لعبة شطرنج بسيطة AI

دعنا نستكشف بعض المفاهيم الأساسية التي ستساعدنا في إنشاء لعبة شطرنج بسيطة AI:

  • جيل الحركة
  • تقييم المجلس
  • مينيماكس
  • وتقليم ألفا بيتا.

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

يمكنك عرض خوارزمية الذكاء الاصطناعي النهائية هنا على GitHub.

الخطوة 1: تحريك التوليد وتصور اللوحة

سنستخدم مكتبة chess.js لتوليد الحركة ، و chessboard.js لتصور اللوحة. تطبق مكتبة الجيل المتحرك بشكل أساسي جميع قواعد الشطرنج. بناءً على ذلك ، يمكننا حساب جميع الحركات القانونية لحالة لوحة معينة.

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

سنبدأ بإنشاء دالة تقوم فقط بإرجاع حركة عشوائية من كل الحركات الممكنة:

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

الخطوة 2: تقييم الموقف

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

من خلال وظيفة التقييم ، يمكننا إنشاء خوارزمية تختار الخطوة التي تعطي أعلى تقييم:

التحسين الملموس الوحيد هو أن خوارزميتنا ستلتقط الآن قطعة إذا أمكن ذلك.

الخطوة 3: البحث في الشجرة باستخدام Minimax

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

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

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

مع تطبيق minimax ، بدأت خوارزميتنا في فهم بعض التكتيكات الأساسية للشطرنج:

تعتمد فعالية خوارزمية minimax بشكل كبير على عمق البحث الذي يمكننا تحقيقه. هذا شيء سنقوم بتحسينه في الخطوة التالية.

الخطوة 4: تقليم ألفا بيتا

تقليم Alpha-beta هو طريقة تحسين لخوارزمية minimax التي تسمح لنا بتجاهل بعض الفروع في شجرة البحث. يساعدنا هذا في تقييم شجرة بحث minimax بشكل أعمق بكثير ، أثناء استخدام نفس الموارد.

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

لا يؤثر تقليم alpha-beta على نتيجة خوارزمية minimax - بل يجعلها أسرع فقط.

خوارزمية ألفا-بيتا هو أيضا أكثر كفاءة إذا كان لنا أن يحدث لزيارة أول تلك المسارات التي تؤدي إلى تحركات جيدة.

باستخدام alpha-beta ، نحصل على دفعة كبيرة لخوارزمية minimax ، كما هو موضح في المثال التالي:

اتبع هذا الرابط لتجربة الإصدار المحسن ألفا بيتا من لعبة الشطرنج AI.

الخطوة 5: تحسين وظيفة التقييم

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

سنستخدم نسخة معدلة قليلاً من الجداول المربعة الموصوفة في الأصل في chess-program-wiki.

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

الاستنتاجات

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

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

بعض التحسينات الإضافية التي يمكننا إجراؤها على الخوارزمية ستكون على سبيل المثال:

  • ترتيب الحركة
  • جيل حركة أسرع
  • وتقييم محدد لنهاية اللعبة.

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

شكرا للقراءة!