الدرس 7 من 9
تلخيص درس تطبيقات الذكاء الاصطناعي باستخدام لغة البرمجة بايثون
الدرس باختصار
في الألعاب التي يتنافس فيها لاعبان يحتاج الذكاء الاصطناعي إلى خوارزمية تختار الحركة الأفضل مع افتراض أن الخصم يلعب أفضل ما عنده. تسمى هذه الفكرة البحث التنافسي (Adversarial Search)، وأشهر خوارزمياتها (MiniMax). نتعلم كيف تُحسب قيم العقد في شجرة اللعبة، وكيف تُبرمج في بايثون (Python) للعبة (XO).
مصطلحات الدرس
- البحث التنافسي (Adversarial Search)
- بحث تتنافس فيه جهتان (وكيلان) أو أكثر، وكل جهة تحاول إفشال خطة الأخرى، كما في الشطرنج و(XO).
- شجرة اللعبة (Game Tree)
- شجرة عقدها حالات اللعبة، ويُكتب على حوافها اسم اللاعب الذي يتحرك في ذلك المستوى.
- فائدة الحالة (Utility)
- قيمة عددية تحدد نتيجة اللعبة في حالة نهائية، مثل +1 للفوز و-1 للخسارة و0 للتعادل.
- لعبة مُحصِّلتها صفر (Zero-Sum Game)
- لعبة يكون فيها مجموع نقاط اللاعبين ثابتًا في كل نتيجة، فما يربحه أحدهما يخسره الآخر.
- التقليم ألفا-بيتا (Alpha-Beta Pruning)
- تقنية تتجاهل فروعًا من الشجرة لا تؤثر في القرار النهائي لتقليل عدد العقد المفحوصة.
أهم الأفكار
MAX وMIN
يتناوب لاعبان على الحركة: (MAX) يريد أعلى قيمة فائدة، و(MIN) يريد أدنى قيمة. تفترض (MiniMax) أن كلا اللاعبين يلعب بشكل مثالي، وتقيّم شجرة اللعبة كاملة لتتخذ قرارًا مثاليًا.
حساب القيم صعودًا
نبدأ بالعقد الطرفية (النهائية) ذات الفوائد المعروفة، ثم نصعد: عقدة (MIN) تأخذ أصغر قيم أبنائها، وعقدة (MAX) تأخذ أكبرها. تشبه هذه العملية الاقترانات الراجعة (Recursive Functions) وفكّ التكرار (Backtracking)، وعند الجذر يختار (MAX) الحركة ذات القيمة الأعلى.
التعقيد والتقليم
إذا كان أقصى عمق وعدد الحركات الممكنة في العقدة ، فالتعقيد الزماني لأن الخوارزمية تستكشف الشجرة كاملة بالبحث في العمق أولًا (Depth-First Search). يزداد عدد الحالات بسرعة مع العمق، لذا يُستخدم التقليم ألفا-بيتا لإهمال فروع لا تغيّر القرار، فتنخفض الحالات المفحوصة إلى النصف أو أقل دون التأثير في صحة القرار.
برمجة (XO) في بايثون
تُمثَّل اللوحة مصفوفة ثنائية الأبعاد 3×3. تأخذ الدالة `minimax(board, depth, is_maximizing)` اللوحة والعمق ومتغيرًا منطقيًا، وتُرجع `1` إذا فاز الذكاء الاصطناعي (X) و`-1` إذا فاز المستخدم (O) و`0` للتعادل. إذا كان الدور للذكاء الاصطناعي جرّب كل خانة فارغة واحتفظ بأكبر قيمة بالدالة `max`، وإلا فبأصغر قيمة بالدالة `min`، مع إعادة الخانة فارغة بعد كل تجربة.
أمثلة محلولة
مثال 1: قيمة الجذر في لعبة بحركة واحدة لكل لاعب
الجذر A للاعب (MAX) وله ثلاثة أبناء B وC وD تخصّ اللاعب (MIN). أوراق B هي 3 و12 و8، وأوراق C هي 2 و4 و6، وأوراق D هي 14 و5 و2. ما قيمة (MiniMax) للجذر، وأيّ حركة يختار (MAX)؟
اعرض الحل
- نحسب قيمة كل عقدة لـ (MIN) بأخذ أصغر قيمة بين أبنائها: B تساوي 3، وC تساوي 2، وD تساوي 2.
- الآن دور (MAX) عند الجذر: يأخذ أكبر القيم الراجعة 3 و2 و2، فتكون 3.
- يختار (MAX) الحركة المؤدية إلى B لأنها تعطيه أعلى قيمة مضمونة.
الجواب: القيمة 3، وتُختار الحركة المؤدية إلى B
مثال 2: شجرة بمستويين
جذر (MAX) له ابنان من نوع (MIN): الأول أوراقه 3 و6، والثاني أوراقه 2 و8. أوجد قيمة الجذر.
اعرض الحل
- الابن الأول: أصغر القيمتين 3 و6 هي 3.
- الابن الثاني: أصغر القيمتين 2 و8 هي 2.
- الجذر يأخذ أكبر القيمتين 3 و2، فهي 3.
الجواب: 3
مثال 3: شجرة بأربعة مستويات
في شجرة أربعة مستويات: الجذر A (MAX)، وابناه B وC (MIN)، وأبناء B هما D وE، وأبناء C هما F وG وكلها (MAX)، وأوراق D هي -1 و4، وأوراق E هي 2 و6، وأوراق F هي -3 و-5، وأوراق G هي 0 و7. أوجد قيمة A.
اعرض الحل
- نبدأ من الأوراق صعودًا (فكّ التكرار): D=max(-1,4)=4، وE=max(2,6)=6، وF=max(-3,-5)=-3، وG=max(0,7)=7.
- المستوى التالي لـ (MIN): B=min(4,6)=4، وC=min(-3,7)=-3.
- الجذر لـ (MAX): A=max(4,-3)=4.
الجواب: 4
مثال 4: عدد الحالات التي تفحصها (MiniMax)
لعبة فيها 3 حركات ممكنة في كل عقدة وأقصى عمق للشجرة 4. ما عدد الحالات تقريبًا وفق التعقيد الزماني ؟
اعرض الحل
- التعقيد الزماني للخوارزمية حيث عدد الحركات الممكنة في العقدة و أقصى عمق.
- نعوّض و: .
الجواب: 81 حالة تقريبًا
أخطاء شائعة
أخذ الأكبر في عقدة (MIN) أو الأصغر في عقدة (MAX).
ليش غلط: القاعدة تتبع صاحب الدور في العقدة: (MIN) يريد أقل قيمة و(MAX) أعلاها.
الصح: نحدد أولًا لمن تعود العقدة، ثم نأخذ الأصغر لـ (MIN) والأكبر لـ (MAX).
حساب قيمة الجذر قبل قيم الأوراق.
ليش غلط: قيمة كل عقدة تعتمد على قيم أبنائها.
الصح: نبدأ من القيم النهائية ونصعد مستوى بعد مستوى.
الظن أن التقليم ألفا-بيتا يغيّر القرار النهائي.
ليش غلط: الفروع المقلَّمة لا تؤثر في قيمة الجذر، فهو يوفر الوقت فقط.
الصح: نتذكر أن الجذر مستقل عن قيم العقد المقلَّمة.
نسيان إعادة الخانة فارغة بعد تجربة الحركة.
ليش غلط: تبقى اللوحة معدّلة وتفسد التجارب التالية.
الصح: نكتب `board[i][j] = " "` بعد استدعاء `minimax`.
اختبر حالك
1. جذر (MAX) له ابنان من نوع (MIN): أوراق الأول 5 و8، وأوراق الثاني 7 و4 و9. أوجد قيمة الجذر.
اعرض الجواب
الجواب:
الأول: min(5,8)=5، والثاني: min(7,4,9)=4، والجذر max(5,4)=5.
2. في دالّة `minimax` بلغة بايثون، ما القيمة التي تُرجعها الدالة عندما يفوز اللاعب (O)؟
اعرض الجواب
الجواب:
القاموس `scores` يعطي `"O"` القيمة `-1` لأن فوز المستخدم سيئ للذكاء الاصطناعي (X).
3. في لعبة فيها 4 حركات ممكنة في كل عقدة وأقصى عمق 3، كم حالة تقريبًا تفحصها (MiniMax) وفق ؟
اعرض الجواب
الجواب:
.
4. أيّ لاعب يختار أعلى قيمة فائدة بين أبناء العقدة: (MAX) أم (MIN)؟
اعرض الجواب
الجواب: (MAX)
(MAX) يسعى إلى زيادة القيمة، و(MIN) إلى تقليلها.
جاهز تتدرّب؟
7 سؤال على هالدرس، بتتصحّح خطوة خطوة، ومعها تلميحات لما تعلق. أول أسئلة مجانية.
تدرّب على 7 سؤال من هالدرس مجانًا