تطبيقات الذكاء الاصطناعي باستخدام لغة البرمجة بايثون

• أُوضّح خوارزمية ⁦(MiniMax)⁩.
• أبرمج خوارزمية ⁦(MiniMax)⁩ لتطوير لعبة ⁦(XO)⁩ باستخدام لغة البرمجة بايثون ⁦(Python)⁩.
• أُوضّح الاقترانات التقييمية، وأستخدمها.

ماذا سنفعل في هذا الدرس؟

الفكرة الرئيسة: سأتعرَّف في هذا الدرس خوارزميات البحث التنافسية التي تُستخدَم في المسائل التي يتنافس فيها أكثر من عميل (وكيل)، مثل الألعاب الثنائية. كذلك سأتعرَّف خوارزمية ⁦(MiniMax)⁩، وكيف تُستخدَم هذه الخوارزمية في لعبة ⁦(XO)⁩ لتحديد أفضل الحركات المُحتمَلة (المُمكِنة) لكل لاعب.

• التقليم ألفا-بيتا:
• بعد ذلك سأتعرَّف خوارزمية التقليم ⁦(Alpha-Beta)⁩ التي تُستخدَم مع خوارزمية ⁦(MiniMax)⁩ لزيادة كفاءة البحث وتقليل عدد العُقَد التي يجب تقييمها.
• التطبيق العملي:
• في نهاية الدرس، سأُطبِّق هذه المفاهيم عمليًّا عن طريق برمجة خوارزمية ⁦(MiniMax)⁩ باستخدام لغة البرمجة بايثون ⁦(Python)⁩، ثمَّ توظيف هذه الخوارزمية في تطوير لعبة ⁦(XO)⁩ بشكل حاسوبي.

• المفاهيم والمصطلحات: البحث التنافسي ⁦(Adversarial Search)⁩، لعبة مُحصِّلتها صفر ⁦(Zero-Sum Game)⁩، شجرة اللعبة ⁦(Game Tree)⁩، فائدة الحالة (⁦Utility (s⁩,⁦a⁩))، التقليم ألفا- بيتا ⁦(Alpha-Beta Pruning)⁩.

نشاط تمهيدي: أمسح الرمز السريع الاستجابة المجاور، ثمَّ ألعب لعبة الشطرنج مع جهاز الحاسوب:

هل فكَّرتُ يومًا في آليَّة اختيار جهاز الحاسوب لحركاته؟

بعد ذلك أدوِّن الإجابة التي أتوصَّل إليها، ثمَّ أُشارِكها مع الزملاء/ الزميلات في الصف، ونتبادل معًا التغذية الراجعة.

البحث التنافسي: لاعبان كل منهما يريد الفوز

• تختلف خوارزميات البحث التنافسي عن خوارزمية البحث الشامل بالأفضلية (⁦A⁩* ⁦Search⁩)، التي تبحث دائمًا عن أفضل مسار للحلّ، في أنّها تعتمد المواجهة والتغلّب على الخصم الذي يحاول دائمًا إفشال خطط اللاعب والسعي إلى الفوز.
• من أشهر الأمثلة على خوارزميات البحث التنافسي: خوارزمية ⁦(MiniMax)⁩، وخوارزمية التقليم ⁦(Alpha-Beta)⁩، وخوارزمية ⁦(Monte Carlo)⁩.

• ولكي تتمكّن هذه الخوارزمية من اتخاذ قرار مثالي؛ يجب أن تُقيّم شجرة اللعبة كاملة.
• الجذر:
• تبدأ شجرة البحث - كما هو معتاد - بالحالة الأوّلية (الابتدائية). وهذه العُقدة تُمثّل جذر شجرة البحث،
• المستوى الأول:
• يتمّ الانتقال إلى المستوى الأوّل من شجرة البحث، حيث توضع فيه جميع الحركات المُحتملة (المُمكِنة) للاعب الأوّل ضمن مجموعة من العُقد، وتُعامل معاملة الأبناء للعُقدة الجذرية.
• المستوى الثاني:
• أمّا في المستوى الثاني فيتمّ تمثيل كل حركة يُحتمل أن يلعبها اللاعب الثاني بناءً على حركات اللاعب الأوّل، وعلى أساس أنّه يلعب لعبًا مثاليًا، وتكون هذه العُقد أبناءً للعُقد في المستوى السابق.
• المحصلة:
• في المُحصّلة، ستُبنى شجرة بحث تحتوي على جميع الحالات المُحتملة (المُمكِنة) ضمن ⁦(N)⁩ عُقدة كما هو مُبيّن في الشكل (4-1).

• تُحسَب قيمة لكل عُقدة بناءً على اقتران تقييمي سيتمّ توضيحه في هذا الدرس؛ إذ يسعى اللاعب ⁦(MAX)⁩ إلى زيادة قيمة نتيجة الاقتران التقييمي بناءً على الحالة الحالية، في حين يسعى اللاعب ⁦(MIN)⁩ إلى تقليل قيمة نتيجة الاقتران التقييمي.
• بناءً على هذه القيم، يُمكن معرفة إذا كان هذا الموضع جيّدًا للاعب مُعيّن أم لا.

لنرَ الفكرة على لعبة إكس أو.

• يُبيّن الشكل (4-2) شجرة بحث تُظهر جزءًا من لعبة ⁦(XO)⁩، وتتضمّن عرضًا لاحتمالات اللعب بالنسبة إلى اللاعب ⁦(X)⁩ الذي ستعمل خوارزمية ⁦(MiniMax)⁩ على تسميته ⁦(Max)⁩.

• اللاعب ⁦(O)⁩:
• كذلك تتضمّن شجرة البحث عرضًا لاحتمالات اللعب بالنسبة إلى اللاعب ⁦(O)⁩ الذي ستعمل هذه الخوارزمية على تسميته ⁦(Min)⁩، ثمّ تتولّى تسجيل المواضع التي فاز فيها اللاعب ⁦(X)⁩ بقيمة موجبة، والمواضع التي فاز فيها اللاعب ⁦(O)⁩ بقيمة سالبة.
• القرار:
• بعد ذلك ستتخذ الخوارزمية قرارًا يُحدّد أفضل لعبة يُمكن ممارستها، في ما يُمثّل الدور الذي تؤدّيه خوارزمية ⁦(MiniMax)⁩.

• استنادًا إلى الشكل (4-2)، فإنّ اللاعب ⁦(MAX)⁩ يتحرّك أوّلًا، يليه اللاعب ⁦(Min)⁩، ثمّ يتناوب اللاعبان على التحرك إلى حين انتهاء اللعبة، حتّى تُمنح نقاط للاعب الفائز.

تعريف اللعبة: ستة عناصر وشجرة

• يُمكن تعريف اللعبة بأنّها مشكلة بحث مع العناصر الآتية:

• الحالة الأوّلية (الابتدائية) ⁦(S0)⁩: تُحدّد هذه الحالة كيفية إعداد اللعبة في بدايتها.
• اللاعب ⁦(S)⁩: يُحدّد اللاعب الذي لديه الحركة في حالة مُعيّنة.
• الإجراء ⁦(as)⁩: يعمل الإجراء ⁦(as)⁩ على إرجاع مجموعة التحركات المُحتملة (المُمكِنة) إلى حالة مُعيّنة.
• النتيجة ⁦(result (S, a))⁩: يُقصد بذلك نموذج الانتقال الذي يُحدّد نتيجة الحركة.
• اختبار المَحطَّة (اختبار المَحطّات): يُطلق على الحالات التي تنتهي فيها اللعبة اسم حالات المحطّة، وهي تُعدّ صحيحة في حال انتهاء اللعبة، وتُعدّ غير صحيحة إذا لم تنته اللعبة.

• في لعبة الشطرنج مثلًا، تكون النتيجة إمّا فوزًا، وإمّا خسارةً، وإمّا تعادلًا، فتكون القيم ⁦(+1)⁩، أو (0)، أو (½)؛
• إذ يُعطى اللاعب ⁦(Max)⁩ القيمة (1) في حال الفوز، ويعطى القيمة (0) في حال الخسارة، في حين يُعطى كلّ من اللاعبين (½) في حال التعادل.

• ذلك أنّ نتائجها دائمًا إمّا ⁦(0+1)⁩، وإمّا ⁦(1+0)⁩، وإمّا (½ + ½)؛ ما يعني أنّ المجموع الإجمالي في جميع الحالات يساوي (1).

• تختلف عن شجرة البحث التي تعرّفتها مُسبقًا في أنّ اسم اللاعب الذي يؤدّي دورًا في هذا المستوى من اللعبة يُكتب عند الحافة.
• الشكل (4-3) جزءًا من شجرة اللعبة في لعبة ⁦(XO)⁩، يُبيّن الحالة الابتدائية، واسم كلّ من اللاعبين على يسار الشجرة، ودالة النتيجة.

• اللاعب ⁦(MAX)⁩:
• بالنظر إلى الشكل السابق، يُلاحظ أنّ اللاعب ⁦(MAX)⁩ الذي كتب حرف ⁦(X)⁩ في الحالة الأوّلية (الابتدائية) له (9) حركات مُحتملة (مُمكِنة).
• نهاية اللعبة:
• يأتي دور اللاعب ⁦(Min)⁩ الذي وضع حرف ⁦(O)⁩، ثمّ تناوب اللاعبان على وضع الإشارات، لتنتهي اللعبة بالوصول إلى الحالة النهائية؛ وهي وضع أحد اللاعبين (3) إشارات له على خط مستقيم، أو امتلاء جميع المُربّعات في اللعبة.
• القيم النهائية:
• أمّا القيم في أسفل الشكل فتشير إلى قيم الحالة النهائية من وجهة نظر اللاعب ⁦(MAX)⁩، وهي: ⁦(+1)⁩ في حال فوزه، و(-1) في حال خسارته، و(0) في حال تعادله مع اللاعب ⁦(Min)⁩.

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

كيف تختار الخوارزمية حركتها؟

• يعرض الشكل (4-4) مثالًا سهلًا على لعبة تُبيّن آليّة عمل خوارزمية ⁦(MiniMax)⁩؛ إذ يبدأ اللاعب ⁦(MAX)⁩ اللعب من عُقدة الجذر، وتُسمّى الحركات المُحتملة (المُمكِنة) لهذا اللاعب ⁦(a1)⁩، و⁦(a2)⁩، و⁦(a3)⁩ كما هو مُبيّن في الشكل.

• الاستجابات المحتملة:
• فإذا اختار اللاعب ⁦(MAX)⁩ الحركة ⁦(a1)⁩، فإنّ العُقدة ⁦(B)⁩ ستنشأ، وستكون الاستجابات المُحتملة (المُمكِنة) للاعب ⁦(MIN)⁩ هي: ⁦(b1)⁩، و⁦(b2)⁩، و⁦(b3)⁩.
• أمّا إذا اختار اللاعب ⁦(MAX)⁩ الحركة ⁦a2⁩، فستظهر العُقدة ⁦(C)⁩، وستكون الاستجابات المُحتملة (المُمكِنة) للاعب ⁦(MIN)⁩ هي: ⁦(c1)⁩، و⁦(c2)⁩، و⁦(c3)⁩، وهكذا الحال بالنسبة لبقيّة الحركات.

• ثمّ ستنتهي اللعبة بعد أداء كلّ من اللاعبين حركة واحدة فقط؛ إذ يقال في لغة الألعاب:

• يُذكر أنّ قيمة الفائدة للحالات النهائية في هذه اللعبة تتراوح بين (2) و(14).

• تكتب القيمة التقييمية لكل عقدة باستخدام ⁦(MINIMAX) (n)⁩، وهذه القيمة تعد الفائدة للاعب ⁦(MAX)⁩ على أساس أن كلا اللاعبين يلعبان بشكل مثالي.
• عند منح اللاعبين الخيار، فإن اللاعب ⁦(MAX)⁩ يفضل دائماً التحرك نحو العقدة التي تملك أعلى قيمة للفائدة، في حين يفضل اللاعب ⁦(MIN)⁩ التحرك في اتجاه العقدة التي لها أقل قيمة للفائدة.

• العقدة ⁦(B)⁩:
• في الشكل (4-5)، تمثل العقدة ⁦(B)⁩ أول عقدة للاعب ⁦(MIN)⁩. ولهذه العقدة ثلاثة أبناء يحملون القيم الآتية: (3)، و(12)، و(8).
• لأن هذه العقدة تخص اللاعب ⁦(MIN)⁩؛ فإنه سيختار المسار الذي يعطي أقل قيمة محتملة (ممكنة)، وهي (3) في هذه الحالة.
• العقدة ⁦(C)⁩:
• أما بالنسبة إلى العقدة ⁦(C)⁩، فعند المقارنة بين قيم أبنائها (العقد الناتجة منها)، وهي: (2)، و(4)، و(6)، يتبين أن (2) أقل قيمة من هذه القيم،
• العقدة ⁦(D)⁩:
• في ما يخص العقدة الأخيرة ⁦(D)⁩، فإن أقل قيمة بين أبنائها الثلاثة (2، 5، 14) هي أيضاً (2). ومن ثم، فإن اللاعب ⁦(MIN)⁩ سيختار هذه القيمة.
• يذكر أن القيم الراجعة من حركات اللاعب ⁦(MIN)⁩ تظهر في الشكل، وقد ظللت باللون الوردي لتمييزها.

• العقدة ⁦(A)⁩:
• بعد الانتهاء من تقييم حركات اللاعب ⁦(MIN)⁩، يأتي دور اللاعب ⁦(MAX)⁩ الذي يسعى دائماً إلى اختيار المسار الذي له أعلى قيمة محتملة (ممكنة).
• ففي هذا المثال، أول عقدة للاعب ⁦(MAX)⁩ هي ⁦(A)⁩.
• عند المقارنة بين القيم الناتجة من أبنائها، وهي: (3)، و(2)، و(2)، يتبين أن أعلى قيمة هي (3)؛ لذا سيختار اللاعب ⁦(MAX)⁩ الحركة ⁦(a1)⁩

• الحسابات:
• ألاحظ أن خوارزمية ⁦(MiniMax)⁩ تعمل على إيجاد القرار المناسب انطلاقاً من الحالة الحالية للعبة؛ إذ تعتمد اللعبة على الحسابات المكررة البسيطة لقيم خوارزمية ⁦(MiniMax)⁩ الخاصة بكل حالة لاحقة في شجرة اللعبة، علماً بأن إجراء هذه الحسابات يتم عن طريق التطبيق المباشر للمعادلات المحددة.
• التكرار:
• يستمر هذا التكرار حتى الوصول إلى العقد الطرفية (نهاية شجرة اللعبة)، بعد ذلك تنسخ قيم خوارزمية ⁦(MiniMax)⁩ أثناء عملية فك التكرار ⁦(Backtracking)⁩ في شجرة اللعبة.
• التشبيه بالبرمجة:
• هذه الآلية تشبه فكرة الاقترانات الراجعة ⁦(Recursive Functions)⁩ في عمليات البرمجة.

نشاط فردي: أجد قيمة خوارزمية ⁦(MINIMAX)⁩ للعبة المُبيَّنة في الشكل (4-7)، علمًا بأنَّ قيمة الفائدة لكل حالة ظاهرة في الشكل.

كم يكلّف البحث في الوقت والذاكرة؟

• إذا كان أقصى عمق للشجرة هو ⁦(m)⁩، وكانت توجد حركة مسموحة في كل نقطة،
• فإن التعقيد الزماني لخوارزمية ⁦(MiniMax)⁩ هو $O(b^m)$، في حين يكون التعقيد المكاني $O(b^m)$
• لخوارزمية تُولِّد جميع الإجراءات دفعة واحدة، أو $O(m)$ لخوارزمية تولد إجراء واحداً في كل مرة.

• الاستكشاف:
• تعمل خوارزمية ⁦(MiniMax)⁩ على استكشاف كامل شجرة اللعبة باستخدام خوارزمية البحث في العمق أولاً ⁦(Depth-First Search)⁩.
• التعقيد الزماني:
• فإذا كان أقصى عمق للشجرة هو ⁦(m)⁩، وتبين وجود ⁦(b)⁩ حركة محتملة (ممكنة) في كل عقدة، فإن التعقيد الزماني لخوارزمية ⁦(MiniMax)⁩ سيكون $O(b^m)$.

• تتمثل المشكلة الرئيسة عند استخدام خوارزمية ⁦(MiniMax)⁩ في أن عدد الحالات التي يجب فحصها يزداد بصورة كبيرة عند زيادة عمق شجرة اللعبة؛ ما يؤدي إلى تعقيد حسابي عالٍ جداً.
• بالرغم من ذلك، يمكن تقليل عدد الحالات التي يتم فحصها إلى النصف أو أكثر عن طريق حساب قرار خوارزمية ⁦(MiniMax)⁩ من دون حاجة إلى النظر في كل عقدة في شجرة اللعبة.

• أما التقنية الخاصة المستخدمة لهذا الغرض فتسمى التقليم ألفا-بيتا ⁦(Alpha-Beta Pruning)⁩.
• بالرجوع إلى الشكل (4-4)، يلاحظ أنه يمكن الاستغناء عن تقييم عقدتين ورقيتين.

أحسب قيمة ⁦MiniMax(root)⁩ لشجرة البحث المُبيّنة في الشكل (4-8).

كيف نخزّن شجرة البحث في البرنامج؟

• يُمكن لخوارزميات البحث تتبّع شجرة البحث في حال توافر بنية بيانات تُنشأ بحسب الخوارزمية المُستخدمة، ولكن يجب أن تتوافر في هذه البنية أربعة مُكوّنات رئيسة لكل عُقدة ⁦(m)⁩ من شجرة البحث، وهي:

• الحالة ⁦(m state)⁩: إحدى حالات حيّز الحالة الذي يُمثّل العُقدة ⁦(m)⁩.
• الأب ⁦(Parent)⁩: عُقدة في شجرة البحث، تفرّعت منها العُقدة ⁦(m)⁩.
• الإجراء ⁦(Action)⁩: إجراء طُبّق على العُقدة الأب لإنشاء العُقدة ⁦(m)⁩.

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

• يعتمد استخدام خوارزمية البحث على ضوابط ومعايير وأسس عِدّة، يتمثّل أبرزها في الأسئلة الآتية:

هل تضمن الخوارزمية إيجاد الحَلّ؟

هل تستطيع الخوارزمية إيجاد الحَلّ المثالي؟

ما الوقت الذي تستغرقه الخوارزمية في إيجاد الحَلّ؟

ما حجم الذاكرة اللازم لإنهاء عملية البحث؟

نبرمج لعبة إكس أو بثلاث خطوات

• في ما يأتي الخطوات اللازمة لبرمجة لعبة ⁦(XO)⁩ في لغة البرمجة بايثون ⁦(Python)⁩:

• الغاية:
• تعريف دالّة خوارزمية ⁦(MINIMAX)⁩؛ إذ تُستخدم هذه الدالّة في تحديد أفضل حركة للذكاء الاصطناعي ⁦(X)⁩ في لعبة ⁦(XO)⁩،
• المدخلات:
• مُدخلاتها هي مصفوفة ثنائية الأبعاد تُمثّل لوحة اللعب ⁦(board)⁩، وعمق الشجرة ⁦(depth)⁩، ومُتغيّرا منطقياً ⁦(is_maximizing)⁩ يُرجع قيمة منطقية مقدارها ⁦(true)⁩ إذا كان الدور في اللعب للذكاء الاصطناعي، و⁦(false)⁩ إذا كان الدور في اللعب للمُستخدم.
• المخرجات:
• أمّا مُخرجات هذه الدالّة فهي (1) إذا فاز الذكاء الاصطناعي، و(-1) إذا فاز المُستخدم، و(0) إذا تعادل المُستخدم مع الذكاء الاصطناعي.
• يُذكر أنَّ القيمة التي تتراوح بين (-1) و(1) أثناء عملية البحث تُعبّر عن جودة الحركات المُحتملة (المُمكِنة)، وهي مُبيّنة في الشكل (4-10).

3. تعريف الجزء الرئيس من البرنامج كما هو مُبيّن في الشكل (4-11).

أكتب دالّة باستخدام لغة البرمجة بايثون ⁦(Python)⁩، أُطلق عليها اسم ⁦(check_winner)⁩، وهي تأخذ اللوحة بوصفها مُدخلاً، وتُرجع القيمة ⁦(X)⁩ إذا فاز الذكاء الاصطناعي، وتُرجع القيمة ⁦(O)⁩ إذا فاز المُستخدم، وتعتمد القيمة ⁦(draw)⁩ إذا انتهت اللعبة بالتعادل، وتعتمد القيمة ⁦(none)⁩ إذا كانت بعض الخانات لا تزال فارغة، ولا يوجد فائز حتّى ذلك الوقت.

نشاط فردي: أكتب دالَّة باستخدام لغة البرمجة بايثون ⁦(Python)⁩ لتحديد أفضل حركة للعبة؛ على أنْ تكون مُدخَلات هذه الدالَّة هي اللوحة ⁦(board)⁩، ومُخرَجاتها هي إرجاع زوج يُمثِّل الصف والعمود لأفضل حركة.

نشاط فردي: أُفكِّر في خطوات برمجة لعبة (لغز) الأرقام الثمانية ⁦(Puzzle-8)⁩ باستخدام لغة البرمجة بايثون ⁦(Python)⁩، علمًا بأنَّه يُمكِنني الاستعانة ببرامج الذكاء الاصطناعي لكتابة المقطع البرمجي (الكود)، ثمَّ تطبيقه في جهاز الحاسوب للتحقُّق من فعّاليته.

أقيّم تعلّمي: أسئلة الدرس

المعرفة: أستخدم ما تعلمته من معارف في هذا الدرس للإجابة عن السؤالين الآتيين:

السؤال الأول: أوضح المقصود بكل مما يأتي:

البحث التنافسي.

خوارزمية ⁦(MINIMAX)⁩.

السؤال الثاني: أوضح خطوات حساب القرار في خوارزمية ⁦(MINIMAX)⁩.

• المهارات: أوظف مهارات التفكير الناقد والبحث الرقمي والتواصل في الإجابة عن السؤالين الآتيين:

السؤال الأول: أجد القيمة النهائية لخوارزمية ⁦(MINIMAX)⁩ بناءً على شجرة اللعبة الممثلة في الشكل الآتي:

السؤال الثاني: أتتبع خوارزمية التقليم ألفا-بيتا ⁦(Alpha-Beta Pruning)⁩ على شجرة اللعبة الوارد ذكرها في السؤال الأول.

أسئلة الوحدة: اختبر نفسك

• السؤال الأول: أضع إشارة (✓) بجانب العبارة الصحيحة، وإشارة (✗) بجانب العبارة غير الصحيحة في ما يأتي:

3. تتمثَّل خطوة صياغة الهدف في تنظيم الأهداف، ثمَّ تنظيم الإجراءات التي يجب اتِّباعها للوصول إلى الهدف. ( )

4. العُقْدة والحالة في شجرة البحث هما وجهان لعملة واحدة. ( )

5. تعمل خوارزمية البحث في العمق أوَّلًا على استكشاف جميع العُقَد التي في المستوى، بَدْءًا باليسار، وفي اتجاه اليمين. ( )

6. يحاول اللاعب في خوارزمية ⁦(MINIMAX)⁩ اختيار القيمة العظمى فقط في كل مستوى من مستويات الشجرة. ( )

7. يهدف اللاعب في المستوى ⁦(Min)⁩ إلى تعظيم النتيجة لمصلحته. ( )

• السؤال الثاني: أوضِّح المقصود بكلٍّ ممّا يأتي:

1. مشكلة البحث في الذكاء الاصطناعي.

2. البحث الاستدلالي في الذكاء الاصطناعي.

• السؤال الثالث: أحُلُّ المسألة الآتية باستخدام الاقتران الاستدلالي، ثمَّ أرسم حيِّز الحالة لهذه المسألة.

• السؤال الرابع: أدرس الشكل الآتي، ثمَّ أُجيب عن الأسئلة التي تليه:

1. ما الحالة الأوَّلية (الابتدائية) لشجرة البحث؟

2. ما جذر هذه الشجرة؟

3. أُعدِّد حالات فضاء البحث التي يُمثِّلها هذا الشكل.

4. ما المسار بين النقطة ⁦(E)⁩ والنقطة ⁦(M)⁩.

5. أُعدِّد النقاط الميتة في الشكل.

6. أذكر مثالًا على نقطة تُمثِّل علاقة (الأب – الأبناء).

7. أُعدِّد الأبناء للنقطة ⁦(H)⁩ في الشكل.

8. ما مسار الحَلِّ، علمًا بأنَّ الحالة الهدف تُمثِّل فوز أحد اللاعبَيْنِ باستخدام خوارزمية البحث في العمق أوَّلًا؟

10. أيُّ المسارين أقصر لإيجاد الحَلِّ؟

• السؤال الخامس: أُعلِّل ما يأتي:

1. يعتمد مقدار البحث الفعلي على دِقَّة الدالَّة الإرشادية.

2. يُطلَق على خوارزميات البحث الاستدلالية اسم خوارزميات البحث الأفضل أوَّلًا.

3. تسمية خوارزمية التقليم ألفا–بيتا (⁦Alpha⁩–⁦Beta Pruning⁩) بهذا الاسم.

• السؤال السادس: أُعدِّد مزايا كل نوع من خوارزميات البحث في ما يأتي:

1. البحث بالشبكة العصبية.

2. البحث الجشع.

السؤال السابع: أتتبَّع خوارزمية ⁦(MINIMAX)⁩ في الشكل الآتي، ثمَّ أُحدِّد الأجزاء التي ستُقلَّم باستخدام خوارزمية التقليم ألفا–بيتا (⁦Alpha⁩–⁦Beta Pruning⁩).