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

نتاجات التعلّم (Learning Outcomes):

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

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

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

مثال: يُبيّن الشكل (4-2) شجرة بحث تُظهر جزءًا من لعبة (XO)، وتتضمّن عرضًا لاحتمالات اللعب بالنسبة إلى اللاعب (X) الذي ستعمل خوارزمية (Minimax) على تسميته (Max). كذلك تتضمّن شجرة البحث عرضًا لاحتمالات اللعب بالنسبة إلى اللاعب (O) الذي ستعمل هذه الخوارزمية على تسميته (Min)، ثمّ تتولّى تسجيل المواضع التي فاز فيها اللاعب (X) بقيمة موجبة، والمواضع التي فاز فيها اللاعب (O) بقيمة سالبة. بعد ذلك ستتخذ الخوارزمية قرارًا يُحدّد أفضل لعبة يُمكن ممارستها، في ما يُمثّل الدور الذي تؤدّيه خوارزمية (Minimax).

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

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

  يُشار إلى لعبة الشطرنج بمصطلح "لعبة مُحصّلتها صفر" (Zero-Sum Game)؛ أي إنّ مجموع النقاط الإجمالي لكلا اللاعبين هو نفسه لكل حالة من حالات اللعبة؛ ذلك أنّ نتائجها دائمًا إمّا (1+0)، وإمّا (1/2 + 1/2)؛ ما يعني أنّ المجموع الإجمالي في جميع الحالات يساوي (1). تعمل كلّ من الحالة الأوّلية (الابتدائية) ودالة الإجراء ودالة النتيجة على تحديد شجرة اللعبة (Game Tree) للعبة. وهذه الشجرة تحتوي على عُقد تُمثّل حالات اللعبة، وهي تختلف عن شجرة البحث التي تعرّفتها مُسبقًا في أنّ اسم اللاعب الذي يؤدّي دورًا في هذا المستوى من اللعبة يُكتب عند الحافة. مثال: الشكل (4-3) جزءًا من شجرة اللعبة في لعبة (XO)، يُبيّن الحالة الابتدائية، واسم كلّ من اللاعبين على يسار الشجرة، ودالة النتيجة.

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

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

الحلّ الأمثل في مشكلات البحث العادية يكون دائمًا سلسلة من الإجراءات، تبدأ بالحالة الأوّلية (الابتدائية)، وتنتهي بالحالة الهدف؛ وهي الحالة النهائية التي تُمثّل الفوز. أمّا في البحث التنافسي (Adversarial Search) فيتعيّن على اللاعب (MAX) إيجاد استراتيجية طارئة تُحدّد حركته للحالة الأوّلية (الابتدائية)، ثمّ التحركات الناجمة عن كل استجابة مُحتملة (مُمكِنة) من اللاعب (MIN)، وهكذا. وفي نهاية المطاف، فإنّ الاستراتيجية المُثلى ستفضي إلى نتائج جيّدة.

يعرض الشكل (4-4) مثالًا سهلًا على لعبة تُبيّن آليّة عمل خوارزمية (Minimax)؛ إذ يبدأ اللاعب (MAX) اللعب من عُقدة الجذر، وتُسمّى الحركات المُحتملة (المُمكِنة) لهذا اللاعب (a1)، و(a2)، و(a3) كما هو مُبيّن في الشكل. فإذا اختار اللاعب (MAX) الحركة (a1)، فإنّ العُقدة (B) ستنشأ، وستكون الاستجابات المُحتملة (المُمكِنة) للاعب (MIN) هي: (b1)، و(b2)، و(b3). أمّا إذا اختار اللاعب (MAX) الحركة a2، فستظهر العُقدة (C)، وستكون الاستجابات المُحتملة (المُمكِنة) للاعب (MIN) هي: (c1)، و(c2)، و(c3)، وهكذا الحال بالنسبة لبقيّة الحركات. ثمّ ستنتهي اللعبة بعد أداء كلّ من اللاعبين حركة واحدة فقط؛ إذ يقال في لغة الألعاب: "إنّ عمق الشجرة هو حركة واحدة، تتكوّن من حركتين نصفيّتين، تُسمّى كل منهما (ply)؛ أي حركة واحدة لكل لاعب". يُذكر أنّ قيمة الفائدة للحالات النهائية في هذه اللعبة تتراوح بين (2) و(14).

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

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

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

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

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

1. تعمل خوارزمية (MiniMax) على استكشاف كامل شجرة اللعبة باستخدام خوارزمية البحث في العمق أولاً (Depth-First Search).
2. فإذا كان أقصى عمق للشجرة هو (m)، وتبين وجود (b) حركة محتملة (ممكنة) في كل عقدة، فإن التعقيد الزماني لخوارزمية (MiniMax) سيكون $O(b^m)$.
3. وبالمثل، فإن التعقيد المكاني سيكون $O(bm)$، ويقصد به عدد الحركات المحتملة (الممكنة) إذا عملت الخوارزمية على توليد جميع الإجراءات دفعة واحدة (أي احتفظت بالشجرة كاملة في الذاكرة)، أو $O(m)$ إذا ولدت الخوارزمية إجراء واحداً في كل مرة (أي احتفظت بمسار واحد فقط في الذاكرة أثناء الاستكشاف).

1. تتمثل المشكلة الرئيسة عند استخدام خوارزمية (MiniMax) في أن عدد الحالات التي يجب فحصها يزداد بصورة كبيرة عند زيادة عمق شجرة اللعبة؛ ما يؤدي إلى تعقيد حسابي عالٍ جداً. بالرغم من ذلك، يمكن تقليل عدد الحالات التي يتم فحصها إلى النصف أو أكثر عن طريق حساب قرار خوارزمية (MiniMax) من دون حاجة إلى النظر في كل عقدة في شجرة اللعبة.
2. تحقيقاً لهذا الهدف؛ تستخدم فكرة تقليم الأشجار (Pruning) التي تتيح استبعاد أجزاء معينة من شجرة اللعبة أثناء عملية البحث؛ لأن هذا الاستبعاد لن يؤثر في القرار النهائي.
3. أما التقنية الخاصة المستخدمة لهذا الغرض فتسمى التقليم ألفا-بيتا (Alpha-Beta Pruning).
4. عند تطبيق هذه التقنية على شجرة خوارزمية (MiniMax)، فإنها تعمل على إزالة الفروع التي لا تؤثر في القرار النهائي للاعب (MAX) أو اللاعب (MIN)؛ ما يؤدي إلى تقليل عدد العقد التي تتم زيارتها بصورة كبيرة، ثم تحسين كفاءة الخوارزمية من دون التأثير في صحة القرار.

بالرجوع إلى الشكل (4-4)، يلاحظ أنه يمكن الاستغناء عن تقييم عقدتين ورقيتين.

ألاحظ أن قيمة الجذر مستقلة عن قيم العقد المقلمة (x، y).

نشاط فردي

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

![MAX a1 MIN b1 b2 c1 c2 3 6 2

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

1. الحالة (m state): إحدى حالات حيّز الحالة الذي يُمثّل العُقدة (m).
2. الأب (Parent): عُقدة في شجرة البحث، تفرّعت منها العُقدة (m).
3. الإجراء (Action): إجراء طُبّق على العُقدة الأب لإنشاء العُقدة (m).
4. تكلفة المسار (Path-Cost) للعُقدة (m): تكلفة المسار من الحالة الأوّلية (الابتدائية) إلى العُقدة (m)، ويُرمز إليها بالرمز g(m).

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

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

• هل تضمن الخوارزمية إيجاد الحَلّ؟
• هل تستطيع الخوارزمية إيجاد الحَلّ المثالي؟
• ما الوقت الذي تستغرقه الخوارزمية في إيجاد الحَلّ؟
• ما حجم الذاكرة اللازم لإنهاء عملية البحث؟

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

1. تعريف لوحة اللعبة بوصفها مصفوفة (3×3). أنظر الشكل (4-9) الذي يُبيّن كيف تُعرّف لوحة اللعبة بصفتها مصفوفة.

1 import math 2 3 # تعريف لوحة اللعبة كمصفوفة 3x3 4 def print_board (board ):

6 print (" | ".join (row )) 7 print ("\n") ```

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

def minimax(board, depth, ismaximizing): scores = {"X": 1, "O": -1, "draw": 0} winner = checkwinner(board)

return scores[winner]

best_score = -math.inf for i in range(3):

if board[i][j] == " ": board[i][j] = "X" score = minimax(board, depth + 1, False) board[i][j] = " " bestscore = max(score, bestscore) return best_score

best_score = math.inf for i in range(3):

if board[i][j] == " ": board[i][j] = "O" score = minimax(board, depth + 1, True) board[i][j] = " " bestscore = min(score, bestscore) return best_score ```

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

board = [[" " for in range(3)] for in range(3)]

print("Game Over! Winner: ", check_winner(board))

row, col = map(int, input("Enter your move (row and column): ").split()) if board[row][col] == " ": board[row][col] = "O"

print("Invalid move! Try again.")

if check_winner(board):

print("AI is making a move...") move = best_move(board)

board[move[0]][move[1]] = "X" if name == "main": main() ```

نشاط جماعي

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

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

1. البحث التنافسي.
2. خوارزمية (MINIMAX).

   السؤال الثاني: أوضح خطوات حساب القرار في خوارزمية (MINIMAX). المهارات: أوظف مهارات التفكير الناقد والبحث الرقمي والتواصل في الإجابة عن السؤالين الآتيين: السؤال الأول: أجد القيمة النهائية لخوارزمية (MINIMAX) بناءً على شجرة اللعبة الممثلة في الشكل الآتي:

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

بعد دراستي هذه الوحدة، اقرأ الفقرات الواردة في الجدول الآتي، ثم أضع إشارة (✓) في العمود المناسب:

إذا اخترت (لا) أو (لست متأكدًا) لأي من الفقرات السابقة، فأتبع الخطوات الآتية لتجنب ذلك:

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

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

يمكنني أن أطبق ما تعلمته في: الصعوبات التي واجهتها في أثناء عملية التعلم: ذللت هذه الصعوبات عن طريق: يمكنني مستقبلًا تحسين: تم بحمد الله تعالى