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

خوارزميات البحث التنافسي

• الحالة الأوّلية (الابتدائية) ⁦(S0)⁩: تُحدّد هذه الحالة كيفية إعداد اللعبة في بدايتها.
• اللاعب ⁦(S)⁩: يُحدّد اللاعب الذي لديه الحركة في حالة مُعيّنة.
• الإجراء ⁦(as)⁩: يعمل الإجراء ⁦(as)⁩ على إرجاع مجموعة التحركات المُحتملة (المُمكِنة) إلى حالة مُعيّنة.
• النتيجة ⁦(result (S, a))⁩: يُقصد بذلك نموذج الانتقال الذي يُحدّد نتيجة الحركة.
• اختبار المَحطَّة (اختبار المَحطّات): يُطلق على الحالات التي تنتهي فيها اللعبة اسم حالات المحطّة، وهي تُعدّ صحيحة في حال انتهاء اللعبة، وتُعدّ غير صحيحة إذا لم تنته اللعبة.
• فائدة الحالة (⁦utility (s⁩,⁦a⁩)): تُسمّى أيضًا دالة الهدف أو دالة العائد، وهي تُحدّد القيمة العددية النهائية للعبة. ففي لعبة الشطرنج مثلًا، تكون النتيجة إمّا فوزًا، وإمّا خسارةً، وإمّا تعادلًا، فتكون القيم ⁦(+1)⁩، أو (0)، أو (½)؛ إذ يُعطى اللاعب ⁦(Max)⁩ القيمة (1) في حال الفوز، ويعطى القيمة (0) في حال الخسارة، في حين يُعطى كلّ من اللاعبين (½) في حال التعادل.

آليّة عمل خوارزمية

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

التعقيد المكاني والتعقيد الزماني:

• تعمل خوارزمية ⁦(MiniMax)⁩ على استكشاف كامل شجرة اللعبة باستخدام خوارزمية البحث في العمق أولاً ⁦(Depth-First Search)⁩.
• فإذا كان أقصى عمق للشجرة هو ⁦(m)⁩، وتبين وجود ⁦(b)⁩ حركة محتملة (ممكنة) في كل عقدة، فإن التعقيد الزماني لخوارزمية ⁦(MiniMax)⁩ سيكون $O(b^m)$.
• وبالمثل، فإن التعقيد المكاني سيكون $O(b^m)$، ويقصد به عدد الحركات المحتملة (الممكنة) إذا عملت الخوارزمية على توليد جميع الإجراءات دفعة واحدة (أي احتفظت بالشجرة كاملة في الذاكرة)، أو $O(m)$ إذا ولدت الخوارزمية إجراء واحداً في كل مرة (أي احتفظت بمسار واحد فقط في الذاكرة أثناء الاستكشاف).
• تتمثل المشكلة الرئيسة عند استخدام خوارزمية ⁦(MiniMax)⁩ في أن عدد الحالات التي يجب فحصها يزداد بصورة كبيرة عند زيادة عمق شجرة اللعبة؛ ما يؤدي إلى تعقيد حسابي عالٍ جداً. بالرغم من ذلك، يمكن تقليل عدد الحالات التي يتم فحصها إلى النصف أو أكثر عن طريق حساب قرار خوارزمية ⁦(MiniMax)⁩ من دون حاجة إلى النظر في كل عقدة في شجرة اللعبة.
• تحقيقاً لهذا الهدف؛ تستخدم فكرة تقليم الأشجار ⁦(Pruning)⁩ التي تتيح استبعاد أجزاء معينة من شجرة اللعبة أثناء عملية البحث؛ لأن هذا الاستبعاد لن يؤثر في القرار النهائي.
• أما التقنية الخاصة المستخدمة لهذا الغرض فتسمى التقليم ألفا-بيتا ⁦(Alpha-Beta Pruning)⁩.
• عند تطبيق هذه التقنية على شجرة خوارزمية…