الاقتران الاستدلالي (Heuristic Function)

• أُعرّف الاقتران الاستدلالي.
• أبني اقترانًا تقييميًا للألعاب.
• أُطبّق خوارزمية البحث الشامل بالأفضلية (⁦A⁩* ⁦Search⁩) على لعبة (لغز) الأرقام الثمانية ⁦(8-Puzzle)⁩ باستخدام الاقترانات التقييمية، وأُقارن بينها.

كيف يختار الحاسوب الطريق الأذكى؟

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

كيف يتحوّل النصح إلى رقم؟

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

• تُقسّم المشكلات التي تحتاج إلى هذا النوع من البحث إلى ثلاثة أنواع:

كيف يُقيّم الحاسوب لوحة الشطرنج؟

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

• بناءً على هذا التقييم يُحدّد الحاسوب أفضل الخطوات والحركات التي تزيد من قوّة موقعه النسبي على اللوحة؛ ما يُعزّز فرصه في الفوز.

ماذا يوفّر الاقتران الاستدلالي للروبوت؟

• المسألة: روبوت في شبكة مُربّعات ⁦(Grid)⁩ تُمثّل متاهة، يبحث عن أقصر طريق إلى الهدف داخل المتاهة.
• كلّ مُربّع قد يكون طريقًا مفتوحًا أو عقبة لا يُمكن المرور منها.
• في كل حركة يُمكن للروبوت الانتقال إلى أحد المُربّعات المجاورة (أعلى، أسفل، يسار، يمين).

كيف تجمع ⁦A⁩* بين التكلفة الفعلية والمُقدّرة؟

• في ما يأتي أمثلة على اقترانات التقييم ⁦(Evaluation Functions)⁩ في ثلاثة سياقات مختلفة - على الأقل - ضمن مجالات الذكاء الاصطناعي.
• أوّلًا: مشكلات العثور على المسار بوكيل واحد. من أمثلتها الكلاسيكية لعبة (لغز) الأرقام الثمانية ⁦(8-Puzzle)⁩.
• المهمة فيها إعادة ترتيب الأرقام على البلاطات (القطع) بشكل متسلسل باستخدام أقل عدد ممكن من الحركات.
• من الخوارزميات القويّة لهذا النوع خوارزمية البحث الشامل بالأفضلية (⁦A⁩* ⁦Search⁩).
• تُقلّل هذه الخوارزمية إجمالي تكلفة الحلّ المُقدّرة بالجمع بين تكلفة المسار الفعلية والتكلفة المُقدّرة للوصول إلى الهدف.

• لتطبيق الخوارزمية بالطريقة المُثلى يجب توافر شرطين: القبول والاتساق.

• يُنظر إلى القبول ⁦(Admissibility)⁩ بصورة مُتفائلة ⁦(Optimistic)⁩؛ لأنّها تفترض أنّ تكلفة الحلّ أقل مما هي عليه فعليًا.
• ومن ثمّ تحاول دائمًا إيجاد المسار الأقل تكلفة.
• فمثلاً، عند البحث عن المسار بين نقطتين، تختار الخط المستقيم؛ لأنّه المسار الأقصر بين أي نقطتين.

• الاتساق ⁦(Consistency)⁩ يُعرَّف أيضًا بشرط الاطِّراد ⁦(Monotonicity)⁩، ويُعدّ أقوى من شرط القبول.
• يُعتمد عند استخدام هذه الخوارزمية في البحث عن الرسوم البيانية.

كيف تجد ندى أرخص طريق من ⁦I⁩ إلى ⁦T⁩؟

• h(n) هي التكلفة المُقدّرة لأرخص مسار من أيّ مدينة إلى المدينة الهدف ⁦(T)⁩.
• تُحسب تكلفتها بناءً على الخط المستقيم بين المدينة الهدف والمدن الأخرى.

• الخطوة 1: نبدأ من المدينة الأوّلية (الابتدائية)، وهي ⁦(I)⁩، ويُمكن الانتقال منها إلى مدينتين، هما ⁦(A)⁩ و⁦(B)⁩.
• المدينة ⁦(A)⁩: تكلفة الوصول إليها (2)، والتكلفة المُقدّرة لأرخص مسار بينها وبين المدينة الهدف ⁦(T)⁩ نحو (10.4).

f(A) = 2 + 10.4 = 12.4

• المدينة ⁦(B)⁩: تكلفة الانتقال إليها (5)، والتكلفة المُقدّرة لأرخص مسار بين المدينة ⁦(T)⁩ والمدينة ⁦(B)⁩ نحو (8.9).

f(B) = 5 + 8.9 = 13.9

• الخطوة 2: المقارنة بين القيمتين تُبيّن أنّ تكلفة الانتقال إلى المدينة ⁦(T)⁩، مرورًا بالمدينة ⁦(A)⁩، هي أقل، فيتمّ اختيارها.
• الخطوة 3: دراسة تفرّعات المدينة ⁦(A)⁩؛ إذ توجد (3) تفرّعات لهذه المدينة؛ أوّلها للمدينة الأوّلية (الابتدائية)، ولا يوجد داع لدراسته مرّة أخرى.
• وثانيها للمدينة ⁦(B)⁩، وثالثها للمدينة ⁦(C)⁩.

f(C) = (1+2) + 6.7 = 9.7

f(B) = (2+2) + 8.9 = 12.9

• لحساب ⁦g(n)⁩ يجب جمع تكلفة المسار من المدينة ⁦(I)⁩ إلى المدينة ⁦(A)⁩، ثمّ جمع تكلفة الوصول من المدينة ⁦(A)⁩ إلى المدينة التي ستنتقل ندى إليها.

• الخطوة 4: المقارنة بين قيم ⁦f(n)⁩ التي تمّ التوصّل إليها، وهي: 12.4، 13.9، 9.7.
• أصغر قيمة من بينها هي 9.7؛ أي مرورًا بالمدينة ⁦(C)⁩؛ لذا يتمّ إكمال الحلّ من هذه المدينة.

• الخطوة 5: للمدينة ⁦(C)⁩ تفرّعات ثلاثة: المدينة ⁦(A)⁩ وقد تمّت دراستها، والمدينة ⁦(E)⁩، والمدينة ⁦(D)⁩.

g(E) = 7 = 4 + 1 + 2

f(E) = g(E) + h(E) = 11 = 7 + 4

g(D) = 8 = 5 + 1 + 2

f(D) = g(D) + h(D) = 14.9 = 8 + 6.9

• الخطوة 6: المقارنة بين قيم ⁦f(n)⁩: 13.9، 12.9، 11، 14.9، تُبيّن أنّ أصغر قيمة هي (11)؛ أي مرورًا بالمدينة ⁦(E)⁩.

• الخطوة 8: إعادة المقارنة بين القيم: 13.9، 12.9، 11، 14.9، تُبيّن أنّ أصغرها 12.9، وهي للمدينة ⁦(B)⁩، مرورًا بالمدينة ⁦(A)⁩.
• الخطوة 9: للمدينة ⁦(B)⁩ طريق واصل إلى المدينة ⁦(A)⁩ وإلى المدينة ⁦(I)⁩ تمّت دراستهما مُسبقًا، وطريق واصل إلى المدينة ⁦(D)⁩ سيتمّ العمل على دراسته.

• الحل:
• $g(D) = 6 = 2 + 2 + 2$
• $f(D) = g(D) + h(D) = 12.9 = 6 + 6.9$

في الكتاب مطبوع ⁦g(B)⁩ و ⁦f(E)⁩، والمقصود ⁦g(D)⁩ و ⁦f(D)⁩

• الخطوة 10: أصغر قيمة بينها هي القيمة 12.9، وأنّها قيمة خاصة بالمدينة ⁦(D)⁩.
• لذا يتمّ الانطلاق من هذه المدينة لدراسة المسارات المُحتملة (المُمكِنة) منها، التي لم تُدرس مُسبقًا: المسار إلى المدينة ⁦(C)⁩، والمسار إلى المدينة ⁦(F)⁩.

g(F) = 10 = 4 + 2 + 2 + 2

f(F) = g(F) + h(F) = 13 = 10 + 3

g(C) = 11 = 5 + 2 + 2 + 2

f(C) = g(C) + h(C) = 17.7 = 11 + 6.7

• الخطوة 11: المقارنة بين قيم ⁦f(n)⁩ المُحتملة (المُمكِنة)، فيُلاحَظ أنّ أصغر قيمة لها هي القيمة التي عند المدينة ⁦(F)⁩، وهي تساوي (13).
• لذا يتمّ الانطلاق من هذه المدينة إلى المدينة ⁦(T)⁩.

g(T) = 13 = 3 + 4 + 2 + 2 + 2

f(T) = g(T) + h(T) = 13 = 13 + 0

لماذا لا يكفي البحث الشامل في لغز الأرقام الثمانية؟

• المثال: تطبيق خوارزمية البحث الشامل بالأفضلية (⁦A⁩* ⁦Search⁩) على لعبة (لغز) الأرقام الثمانية ⁦(8-Puzzle)⁩ باستخدام الاقترانات التقييمية.
• الحالة الأوّلية (الابتدائية) تحوي مُربّعًا فارغًا في المنتصف.
• في إحدى الحالات الهدف رُتّبت الأرقام تسلسليًا، وتُرك الفراغ في بداية الأرقام.
• الانتقال من الحالة الأوّلية (الابتدائية) إلى الحالة الهدف يتطلّب إجراء (26) خطوة.

• تكلفة حلّ الألغاز المُكوّنة من ثماني قطع عشوائيًا هي - في المُتوسّط - (22) خطوة.
• يتحرّك المُربّع الفارغ بثلاث طرائق:
• في المنتصف: له أن يتحرّك في أربع خطوات مُحتملة (مُمكِنة)؛ أي في جميع الاتجاهات.
• في الزاوية: يستطيع أن يتحرّك حركتين فقط.
• عند الحافة: بإمكانه أن يتحرّك ثلاث حركات.
• تكلفة البحث الشامل في شجرة البحث إلى عمق (22) تتطلّب البحث في نحو $3^{22}$، وهو ما يساوي $3.1 \times 10^{10}$ حالة تقريبًا.
• وهذه القيمة كبيرة جدًا.

كيف نقدّر عدد الخطوات إلى الهدف؟

• يجب إيجاد دالة استدلالية جيّدة للتمكّن من إيجاد أقصر الحلول.
• الشرط: ألا تُبالغ هذه الدالة في تقدير عدد الخطوات إلى الهدف.
• توجد طريقتان شائعتان للاستخدام، هما: ⁦H1⁩ و⁦H2⁩.

• H1:
• بالنسبة إلى الشكل (3-9)، جميع المُربّعات في غير موضعها؛ لذا عدد الحركات التي يحتاج إليها كل مُربّع هو (8) حركات.
• وهذه الدالة الاستدلالية مقبولة؛ لأنّه يجب تحريك كل مُربّع حركة واحدة على الأقل.

• H2:
• يتمّ حساب المسافات أفقيًا أو عموديًا؛ لأنّه لا يُمكنها التحرك قطريًا.
• و⁦H2⁩ أيضًا مقبول؛ لأنّ كل مُربّع سيتحرّك حركة واحدة على الأقل.

• ومن ثمّ فإنّ مجموع الحركات للبلاطات (القطع) التي تحمل الأرقام السابقة هو:
• $H2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18$

• أُلاحظ أنّ الحلين لا يعطيان تقديرًا لتكلفة الحلّ الحقيقية التي يبلغ مقدارها (26).
• $H1 = 8 \leq 26$
• $H2 = 18 \leq 26$

من أين تأتي الاقترانات الاستدلالية؟

• اقترانات التقييم السابقة تعمل على إرجاع الحدود الدنيا للتكلفة الفعلية التي يتمّ تقديرها.
• في لعبة الأرقام الثمانية تُمثِّل كل حركة تحرُّكًا لمُربَّع واحد، ويتعيَّن على كل مُربَّع أنْ يتحرَّك مرّات عديدة بقَدْر مسافة مانهاتن من موضعه الهدف.

• الاقترانات الاستدلالية تُستمدّ من النماذج المُبسّطة للمشكلة الأصلية.
• في لعبة الأرقام الثمانية تقتصر الحركات المسموحة على تحريك مُربّع من موضع إلى آخر فقط إذا كانت المساحة الفارغة مجاورة للمُربّع.
• لو أُزيل شرط وجوب تحريك المُربّع إلى مسافة فارغة، لصار الناتج مشكلة أبسط بكثير؛ إذ يُمكن تحريك المُربّع في أي اتجاه وحدة واحدة فقط.
• أي إنّ عدد التحرّكات المطلوبة لحلّ هذه المشكلة المُبسّطة يساوي المسافة من الحالة الأوّلية (الابتدائية) إلى الحالة الهدف.

• الحالة الأوّلية (الابتدائية):

• الحالة الهدف:

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

ولكن ما حجم شجرة البحث في لعبة كبيرة كالشطرنج؟

كم كبيرة شجرة بحث الشطرنج؟

كيف تُقيَّم مواقف اللاعبين في الألعاب الثنائية؟

• من الأمثلة على الألعاب التي يمارسها اثنان من اللاعبين: لعبة الشطرنج، ولعبة ⁦(XO)⁩.
• تعتمد دوال التقييم الاستدلالية في هذا النوع من الألعاب على القِيَم الإيجابية لأحد اللاعبين.
• القيم الإيجابية الكبيرة تشير إلى موقف أحد اللاعبين، ويُسمّى ⁦(MAX)⁩.
• القيم السلبية الكبيرة الحجم تشير إلى مواقف صُلبة للخصم، ويُسمّى ⁦(MIN)⁩.
• ⁨(MAX)⁩ يحاول التحرُّك إلى مواقف تعمل على تعظيم دالة التقييم الاستدلالية.
• ⁨(MIN)⁩ يحاول التحرُّك إلى مواقف تُقلّل من تلك الدالة، وتحدّ منها.

هل فهمتُ الاقتران الاستدلالي؟

أُوضّح المقصود باقتران التقييم الاستدلالي.

في المثال الخاص بانتقال ندى من المدينة ⁦(I)⁩ إلى المدينة ⁦(T)⁩، لماذا وُضعت القيمة صفر للدالة ⁦(hT)⁩؟

فيمَ يستفاد من استخدام الدوال الاستدلالية في عملية البحث؟

أُوضّح عمل الاقتران الاستدلالي الخاص بمشكلة لعبة (لغز) الأرقام الثمانية ⁦(8-Puzzle)⁩ إذا استغنيت عن شرط الانتقال إلى مكان مجاور فقط؛ أي إمكانية الانتقال إلى أي مكان في اللعبة مع الاحتفاظ بشرط أن يكون المكان فارغًا.

أُفرّق بين دالة التقييم الاستدلالية لمسألة إيجاد المسار التي يستخدمها عميل (وكيل) واحد والدالة الاستدلالية للعبة بين لاعبين اثنين.