الصفحة الرئيسية>المتعلقة بالبرمجة>شفرة المصدر الأخرى
تنزيل

محرك الشطرنج باستخدام بايثون

يحتوي هذا المستودع على تنفيذ محرك الشطرنج باستخدام Minimax و Alpha-Beta pruning وخوارزمية البحث Quiescent . يتم استخدام دفتر Jupyter الموجود داخل حاوية Docker للترميز. جميع أجهزة Jupyter Notebook متاحة أيضًا في شكل صورة عامل إرساء.

تحقق من ورقة المشروع لرؤية التحليل التفصيلي.

الوحدة الخارجية المستخدمة

  • بايثون الشطرنج

كيفية التشغيل باستخدام عامل الإرساء 

docker pull codewithnk/chess-engine-using-python:latest
docker run -p 8888:8888 -v $( pwd ) codewithnk/chess-engine-using-python:latest

خوارزميات محرك الشطرنج

مينماكس

نظرية

جوهر الشطرنج لعب الشطرنج في مينماكس. يربط Minmax عادةً القطعة السوداء بـ MAX، والقطعة البيضاء بـ MIN، ويتم تقييمها دائمًا من وجهة النظر البيضاء.

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

تستخدم خوارزمية minmax نهج Depth First Search للعثور على النتيجة. بالإضافة إلى ذلك، فإنه يستخدم أيضًا التراجع والتكرار. سوف تعبر الخوارزمية حتى العقدة الطرفية ثم تتراجع أثناء مقارنة جميع القيم الفرعية. سيتم تحديد الحد الأدنى أو الأقصى للقيمة، بناءً على دوره. سيتم بعد ذلك نشر القيمة مرة أخرى إلى الأصل. ويستخدم وظيفة التقييم الثابتة لتحديد القيمة في كل عقدة طرفية. إنها تستفيد من لعبة Zero-Sum.


تطبيق

محرك الشطرنج باستخدام Minmax


تعقيد الوقت

يستخدم Minmax بحث العمق الأول (DFS) على Game Tree، وبالتالي فإن التعقيد الزمني لخوارزمية minmax هو O(b**m) ، حيث b هو عامل التفرع لشجرة اللعبة، وm هو الحد الأقصى لعمق الشجرة.


تعقيد الفضاء

يشبه تعقيد الفضاء لخوارزمية minmax أيضًا DFS وهو O(bm) ، حيث b هو عامل التفرع لشجرة اللعبة، وm هو أقصى عمق للشجرة.


الاكتمال

اكتملت خوارزمية Minmax. ومن المؤكد أنه سيجد الحل، إن وجد، في شجرة البحث المحدودة.


الأمثلية

تعد خوارزمية Minmax مثالية إذا كان كلا الخصمين يلعبان على النحو الأمثل.


تشذيب ألفا بيتا

نظرية

يمكن تحسين خوارزمية الحد الأدنى عن طريق تقليم بعض الفروع. الفروع المشذبة هي التي لن تؤثر على النتيجة. وسوف يحسن تعقيد الوقت. يُعرف هذا الإصدار من minmax باسم minmax مع تقليم ألفا بيتا. وتسمى أيضًا بخوارزمية ألفا بيتا.
في Alpha-Beta Pruning، هناك قيمتان، Alpha وBeta. فيما يلي بعض النقاط التي يجب مراعاتها حول ألفا وبيتا:

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

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

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

شروط تقليم ألفا بيتا: 

 α >= β

نقل الترتيب

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


أسوأ ترتيب

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


الترتيب المثالي

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


تطبيق

محرك الشطرنج باستخدام ألفا بيتا التقليم


تعقيد الوقت

تستخدم خوارزمية Alpha Beta أيضًا البحث العميق الأول (DFS) على Game Tree.

  • في حالة الترتيب الأسوأ: O(b^m)
  • في حالة الترتيب المثالي: O(b^m/2)

تعقيد الفضاء

  • في حالة الترتيب الأسوأ: O(bm)
  • في حالة الترتيب المثالي: O(b(m/2))

الاكتمال

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


الأمثلية

تعتبر خوارزمية Alpha-Beta مثالية إذا كان كلا الخصمين يلعبان على النحو الأمثل.



بحث السكون

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


تعقيد الوقت

تستخدم خوارزمية البحث الهادئ أيضًا Depth First Search (DFS) في Game Tree.

  • في حالة الترتيب الأسوأ: O(b^m)
  • في حالة الترتيب المثالي: O(b^m/2)

تعقيد الفضاء

  • في حالة الترتيب الأسوأ: O(bm)
  • في حالة الترتيب المثالي: O(b(m/2))

الاكتمال

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

الأمثلية

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



الوجبات الجاهزة الرئيسية

  • يتم تقليل العقد التي يتم استكشافها في كل حركة بمقدار 10 أضعاف في Alpha Beta مقارنةً بـ Minmax.
  • يتم أيضًا تقليل الوقت المستغرق للعثور على أفضل حركة بمقدار 10 أضعاف في Alpha Beta مقارنةً بـ Minmax.
  • يؤدي البحث الهادئ بشكل جيد في العمق الأعلى.
  • البحث الهادئ هو أسرع خوارزمية من بين الخوارزميات الثلاثة.
  • يقوم البحث الهادئ بتقييم عدد أقل من العقد.
  • قد يؤدي البحث الهادئ إلى تحركات متكررة، إذا لم يتم التعامل معه بشكل صحيح.
يوسع
معلومات إضافية
تطبيقات ذات صلة
نوصي لك
أخبار ذات صلة الكل