قم بإنشاء لعبة شطرنج بسيطة: 5 خطوات سهلة

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

يمكن إنشاء الذكاء الاصطناعي البسيط الذي يمكن أن يلعب الشطرنج على أساس أربعة مفاهيم:

1. 1. تتحرك ؛
2. 2. تقييم المجلس.
3. 3. الحد الأدنى ؛
4. 4. ألفا بيتا لقطة . في كل مرحلة من مراحل العمل باستخدام الخوارزمية ، سيتم استخدام واحدة منها ، مما يؤدي إلى تحسين إمكانات اللعب في الذكاء الاصطناعي تدريجياً.

توصي Skillbox بما يلي: تطبيق Python Data Analyst على الإنترنت.

نذكرك: لجميع قراء "Habr" - خصم بقيمة 10،000 روبل عند التسجيل في أي دورة تدريبية في Skillbox باستخدام الرمز الترويجي "Habr".

يمكن الاطلاع على شفرة المصدر الجاهزة على جيثب .

المرحلة 1. التصور من رقعة الشطرنج مع جيل من التحركات

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


عند النقر فوق الصورة ، سيتم فتحها بدقة كاملة.

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

var calculateBestMove =function(game) { //generate all the moves for a given position var newGameMoves = game.ugly_moves(); return newGameMoves[Math.floor(Math.random() * newGameMoves.length)]; }; 

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


الأسود يتحرك بشكل عشوائي. ( المصدر واللعبة عبر الإنترنت )

المرحلة 2. تقييم الموقف

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



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

 var calculateBestMove = function (game) { var newGameMoves = game.ugly_moves(); var bestMove = null; //use any negative large number var bestValue = -9999; for (var i = 0; i < newGameMoves.length; i++) { var newGameMove = newGameMoves[i]; game.ugly_move(newGameMove); //take the negative as AI plays as black var boardValue = -evaluateBoard(game.board()) game.undo(); if (boardValue > bestValue) { bestValue = boardValue; bestMove = newGameMove } } return bestMove; }; 

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


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

المرحلة 3. شجرة البحث مع minimax

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

هنا يتم تحليل شجرة العودية مع عرض جميع التحركات الممكنة على عمق معين. ويقدر الموقف من أوراق شجرة لدينا.

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


هنا ، يعد b2-c3 أفضل حركة بالنسبة لـ White ، حيث إنه يضمن وصول اللاعب إلى المركز برصيد -50 درجة.

 var minimax = function (depth, game, isMaximisingPlayer) { if (depth === 0) { return -evaluateBoard(game.board()); } var newGameMoves = game.ugly_moves(); if (isMaximisingPlayer) { var bestMove = -9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } else { var bestMove = 9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } }; 

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

Minimax مع عمق 2 (المصادر واللعبة هنا )

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

المرحلة 4. ألفا بيتا لقطة

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

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

لا يؤثر التحسين على نتيجة الحد الأدنى ، ولكن كل شيء يبدأ في العمل بشكل أسرع.

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


تُظهر الصورة التحركات التي تصبح غير ضرورية عند استخدام لقطة ألفا بيتا.

كما ترون ، مع لقطة ألفا بيتا ، فإن minimax هو الأمثل ، وبشكل كبير للغاية.


عدد المواضع التي تريد تقييمها في حالة البحث بعمق 4 وموضع البداية ، الموضح أعلاه. (المصدر واللعبة متوفرة هنا )

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

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

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



والآن لدينا خوارزمية تلعب بالفعل بشكل جيد ، بطبيعة الحال ، بالمقارنة مع اللاعب العادي.


المصادر واللعبة متوفرة هنا.

الخاتمة

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

تطبيق خوارزمية لدينا هو 200 سطر فقط من التعليمات البرمجية ، وبالتالي فإن المبادئ الأساسية بسيطة للغاية. يمكن مشاهدة الإصدار الأخير من البرنامج <a href= target github.com/lhartikk/simple-chess-ai'> على GitHub.

يمكن إضافة وحدات أخرى إلى الخوارزمية ، بما في ذلك:

• تبسيط التحركات .
• تسريع جيل من التحركات .
• والنتيجة النهائية .

يمكن الاطلاع على المزيد حول خوارزميات الشطرنج على Chiki Programming Wiki .

توصي Skillbox بما يلي:

• دورة عملية "Mobile Developer PRO"
• دورة عبر الإنترنت "Web Developer Profession"
• دورة تدريبية لمدة عامين "أنا مطور ويب للمحترفين . "