المهارات الرقمية 12 فصل ثاني

 

 

 

اقتران البحث الاستدلالي:

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

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

1.  المشكلات التي تتعلَّق بإيجاد مسار بوساطة عميل (وكيل) واحد (أي لاعب واحد). وفيها يكون الهدف هو الوصول من الحالة الأوَّلية (الابتدائية) إلى الحالة الهدف باستخدام أقصر مسار.
2.  المشكلات التي يكون فيها طرفان مُتنافِسان، يحاول كل منهما الفوز على الآخر.
3.  مشكلات إرضاء القيود التي تكون فيها المهمة هي إيجاد حالة تفي بمجموعة من القيود.

 

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

 

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

المثال ( 1):

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

 

المثال (2):

أفترض وجود روبوت في شبكة مُربَعات( Grid )تُمثِل متاهة، وأنَ الروبوت يبحث عن أقصر طريق إلى الهدف داخل المتاهة. أفترض أيضًا أنَ كل مُربَع قد يكون طريقًا مفتوحًا أو عقبةً لا يُمكِن المرور منها، وأنَه يُمكِن للروبوت - في كل حركة - الانتقال إلى أحد المُربَعات الأربعة المجاورة (أعلى، أسفل، يسار، يمين).

 

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

 

اقترانات التقييم في البحث الاستدلالي:

في ما يأتي عرض لأمثلة على اقترانات التقييم( Evaluation Functions ) في ثلاثة سياقات مختلف-على الأقل- ضمن مجالات الذكاء الاصطناعي: أوَّلًا : مشكلات العثور على المسار بوكيل واحد (Single-Agent Path-Finding Problems) من الأمثلة الكلاسيكية على هذا النوع من المشكلات، لعبة (لغز) الأرقام الثمانية ( 8-Puzzle )؛ ففيها تتمثَّل المهمة في إعادة ترتيب الأرقام على البلاطات (القطع) بشكل مُتسلسِل باستخدام أقل عدد مُمكِن من الحركات. ومن الخوارزميات القويَّة لهذا النوع من المشكلات، خوارزمية البحث الشامل بالأفضلية ( A* Search )؛ إذ يُمكن بهذه الخوارزمية تقليل إجمالي تكلفة الحل المُقدَّرة عن طريق الجمع بين تكلفة المسار الفعلية والتكلفة المُقدَّرة للوصول إلى الهدف.

دالَّة التقييم المُستخدَمة في خوارزمية البحث الشامل بالأفضلية  (A* Search ):

(f(n) = h(n) + g(n

حيث:

(n)g : تكلفة المسار من النقطة الأوََّلية(الابتدائية) أي الجذر إلى العُقْدة (n)

h(n) : التكلفة المُقدَّرة لأرخص مسار من العُقْدة (n) إلى العُقْدة الهدف.

f(n) : التكلفة المُقدَّرة لأرخص مسار، مرورًا بالعُقْدة (n)

 

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

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

2. الاتِّساق Consistency): يُعرَف أيضًا بشرط الاطِّراد (Monotonicity )، ويُعَدُّ أقوى من شرط القبول، وهو مُعتمَد عند استخدام هذه الخوارزمية في البحث عن الرسوم البيانية. ومن ثَم ، فإنَّ القاعدة الاستدلالية h(n) تُعَدُّ متسقة إذا كانت التكلفة المُقدَّرة للوصول إلى الهدف من العُقْدة ( n)،مرورًا بالعُقْدة الابن(n_i ) التي تنشأ عن الإجراء ( a)،لا تزيد على التكلفة المُقدَّرة للوصول إلى الهدف من العُقْدة( n). 

 

المثال (1):
تحاول ندى الانتقال من المدينة ( I) إلى المدينة (T) باستخدام أفضل مسار، عملًا بأنَّ الشكل (1-3) يُبين المسارات من المدينة ( I) إلى المدينة ( T)، وتكلفة الانتقال بين المدن. ما أفضل مسار يُمكن لندى أن تسلكه باستخدام خوارزمية البحث الشامل بالأفضلية A* Search؟

 

 

 

 

 

 

 

لإيجاد أفضل مسار يُمكِن لندى أن تسلكه باستخدام خوارزمية البحث الشامل بالأفضلية A* Search ، أستخدم التكلفة المُقدَّرة لأرخص مسار من من المدن إلى المدينة الهدف (T) الذي يُطلَق عيله اسم (n)h ، ويُمكِن حساب تكلفته بناءً على الخطِّ المستقيم بين المدينة الهدف والمدن الأُخرى. أنظر الشكل(3- 2) .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

لحساب تكلفة أفضل مسار، أستخدم الاقتران الآتي وشجرة البحث:
(f(n) = h(n) + g(n

 

خطوات الحَلِ:
1. بَدْء الحَلِّ من المدينة الأوَّلية (الابتدائية)، وهي ( I). ومن المُلاحَظ أنَّه يُمكِن الانتقال من هذه المدينة إلى مدينتين أُخريين، هما:

أ. المدينة ( A) : تبلغ تكلفة الوصول إليها ( 2)، في حين تبلغ التكلفة المُقدَّرة لأرخص مسار بين المدينة( A) والمدينة الهدف ( T) نحو (10.4).

بتطبيق القانون، فإنَّ:

f(A) = 2+10.4 = 12.4

ب. المدينة ( B) : تبلغ تكلفة الانتقال إليها ( 5) ، في حين تبلغ التكلفة المُقدَّرة لأرخص مسار بين المدينة( T) والمدينة (B) نحو ( 8.9 ). أنظر الشكل ( 3- 3).

بتطبيق القانون، فإنَّ

f(B) = 5 + 8.9 = 13.9

 

 

2. المقارنة بين القيمتين، ليتبين أنَّ تكلفة الانتقال إلى المدينة ( T)، مرورًا بالمدينة( A)، هي أقل، فيتم اختيارها.

3. دراسة تفرُّعات المدينة (A)؛ إذ توجد ( 3) تفرُّعات لهذه المدينة؛ أوَّلها للمدينة الأوَّلية (الابتدائية)، ولا يوجد داعٍ لدراسته مَرَّة أُخرى؛ فقد سبقت دراسته في الخطوة الأولى،  وثانيها للمدينة (B)، وثالثها للمدينة (C). يلي ذلك حساب (f(n لكل منهما، فيظهر الناتج الآتي كما هو مُبين في الشكل ( 3- 4):
f(C)= (1+2) + 6.7 = 9.7
f(B) = (2+2) + 8.9 = 12.9

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

 

 

 

 

 

 

 

 

 

 

 

 

4. المقارنة بين قِيَم (f(n التي تم التوصُّل إليها، وهي: 12.4 ، 13.9 ، 9.7 ، وملاحظة أنَّ أصغر قيمة من بينها هي 9.7 ؛ أيْ مرورًا بالمدينة ( C)؛ لذا يتم إكمال الحَلِّ من هذه المدينة.

5. ملاحظة أنَّ المدينة ( C)  لها ( 3) تفرُّعات؛ أوَّلها للمدينة ( A)، وقد تمتَّ دراسته في الخطوة السابقة، وثانيها للمدينة (E)، وثالثها للمدينة ( D). يلي ذلك حساب ( f(n لكل منهما، فيظهر الناتج الآتي كما هو مُبين في الشكل ( 3- 5):
g(E) = 7 = 4 + 1 + 2
f(E) = g(E) + h(E)
         4+7=11
g(D) = 8 = 5 + 1+2
f(D) = g(D) + h(D)
 6.9 +8= 14.9

 

 

 

 

 

 

 

 

 

 

 

 

6. المقارنة بين قِيَم (f(n التي تم التوصُّل إليها، وهي: 13.9 ، 12.9 ،11، 14.9 ،وملاحظة أنَّ أصغر قيمة لـ (n ) f من بينها هي ( 11)؛ أيْ مرورًا بالمدينة ( E)؛ لذا يتم إكمال الحَلِّ من هذه المدينة.

7. ملاحظة أنَّ المدينة ( E)متصلة فقط بالمدينة ( C) - تمتَّ زيارتها آنفًا، وأنَّ العُقْدة ( E) هي عُقْدة ميتة لا يوجد لها أبناء. ومن ثَم فلا توجد مدينة أُخرى يُمكِن الانطلاق إليها من المدينة(E)

8. إعادة المقارنة بين قِيَم ( f(n لإيجاد أصغر قيمة لها. وهذه القِيَم هي: 13.9 ، 12.9 ، 11 ، 14.9 ، فيتبين أنَّ أصغر قيمة لـ (n) f من بينها هي 12.9 . وبالنظر إلى الشكل (3- 5)، فإنَّ هذه القيمة هي للمدينة ( B)، مرورًا بالمدينة ( A)، فيت إكمال الحَلِّ من هذه المدينة.

9. بالنظر إلى الشكل ( 3- 1)، يُلاحَظ أنَّ للمدينة ( B) طريقًا واصلًا إلى المدينة ( A) - تمت دراسته مُسبّقا-، وطريقا واصلًا إلى المدينة (I) - تمت دراسته مُسبّقا، وطريقًا واصلًا إلى المدينة ( D) سيتم العمل على دراسته كما هو مُبين في الشكل ( 3- 6):
g(B) = 6 = 2 + 2 + 2
f(E) = g(E) + h(E)
6.9+ 6= 12.9

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10. بالنظر إلى قِيَم (f(n ، يُلاحَظ أنَّ أصغر قيمة بينها هي القيمة 12.9 ، وأنَّها قيمة خاصة بالمدينة (D)؛ لذا يت الانطلاق من هذه المدينة لدراسة المسارات المُحتمَلة (المُمكِنة) منها، التي لم تُدْرس مُسبَّقًا، على امتداد هذا المسار: المسار إلى المدينة( C)، والمسار إلى المدينة  ،(F) فتكون القِيَم الناتجة كما هو مُبيّن في الشكل ( 3- 7):
g(F) = 10 = 4 + 2 + 2 + 2
f(F) = g(F) + h(F)
10+3=13
g(C) = 11 = 5+2+2+2
f(C) = g(C) + h(C)
11 + 6.7 = 17.7 =

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

11. المقارنة بين قِيَم (n) f المُحتمَلة (المُمكِنة)، فيُلاحَظ أنَّ أصغر قيمة لها هي القيمة التي عند المدينة ( F)، وهي تساوي (13)؛ لذا يتم الانطلاق من هذه المدينة إلى المدينة ( T) كما هو مُبين في الشكل ( 3- 8):
g(T) = 13 = 3+ 4+2+2+2
f(T) = g(T) + h(T)
 13 + 0= 13

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

إذن، أقل تكلفة مُحتمَلة (مُمكِنة) لانتقال ندى من المدينة ( I) إلى المدينة ( T) هي ( 13 )

 

 

 

 

 

 

إجابة محتملة :

المزايا:

1. قادرة على إيجاد الحل ِ الأمثل إذا كان التقدير Heuristic صحيحًا ومتقبلاً .

2. تجمع بين البحث في العمق والتقدير الاسترشادي ِ (موازنة بين كلفة الوصول والتقدير).

3. تُستخدم عادةً في الذكاء الاصطناعيِ وتطبيقات المسارات (الروبوتات، وألعاب الفيديو، ونظم المالحة)

 العيوب:

1. تستهلك ذاكرة كبيرة؛ لأنَها تحتفظ بالعُقَد المفتوحة والمغلقة جميعها.

2. البطء إذا كان فضاء البحث واسعًا جدًا.

3. غير عملية للمسائل الضخمة جدًا

المثال ( 2):
تطبيق خوارزمية البحث الشامل بالأفضلية ( A* Search ) على لعبة (لغز) الأرقام الثمانية ( 8-Puzzle) باستخدام الاقترانات التقييمية.

يُبين الشكل ( 3- 9) الحالة الأولية(الابتدائية) للعبة (لغز) الأرقام الثمانية ( 8-Puzzle ) التي تحوي مُربَّعًا فارغًا في المنتصف. وعلى الجانب الأيسر من هذا الشكل، تظهر إحدى الحالات الهدف، حيث رُتبت الأرقام تسلسليًّا، وتُرك الفراغ في بداية الأرقام، علمًا بأنَّ الانتقال من الحالة الأوَّلية (الابتدائية) إلى الحالة الهدف (الظاهرة في الشكل) يتطلَّب إجراء ( 26) خطوة.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

إنَّ تكلفة حَل الألغاز المُكوَّنة من ثماني قطع عشوائيًّا - في المُتوسط - هي ( 22) خطوة؛ إذ يتحرَّك فيها المُربَّع الفارغ بثلاث طرائق؛ الأولى: إذا كان هذا المُُربَّع في المنتصف، فله أن  يتحرَّك في أربع خطوات مُحتمَلة (مُمكِنة)؛ أي في جميع الاتجاهات. والثانية: إذا كان هذا المُربَّع في الزاوية، فإنَّه يستطيع أن  يتحرَّك حركتين فقط. والثالثة: إذا كان هذا المُربَّع عند الحافة، فإنَّ بإمكانه أن يتحرَّك ثلاث حركات. ومن ثََمَّ، فإنَّ تكلفة البحث الشامل في شجرة البحث إلى عمق( 22) تتطلَّب البحث في نحو ( 322)، وهو ما يساوي 1010 ×3.1 حالة تقريبًا. وهذه القيمة كبيرة جدًّا.

طريقة الحل :

الاقترانات الثلاث  باختصار:

(n)g: عدد الخطوات التي تحركناها من البداية حتى نصل إلى الحالة الحالية.

(n)h: تقديـر المسـافة المتبقِيـة للوصـول إلـى الهـدف (مثـل عـدد المربعات غيـر الموضوعة فـي مكانهـا الصحيح، أو المسـافة المنتهية لـكل مربع).

f(n)=g(n)+h(n): القيمة المستخدمة لترتيب الأولويات في البحث.

 أن اختيار (n)h الجيد يجعل البحث أسرع (لأنه  يقلِل عدد الحالات المولَدة). 

 الحـركات الممكنـة مـن الحالـة الابتدائية (الفراغ في الوسـط ⇒  يمكنـه التحـرك 4 اتِجاهـات).  (g – h – f ) يمثل  كلَ حالة جديدة في جدول (حركة A* Search، وقرر أيُ حالـة يفضِلهـا f(n) قارن بيـن قيـم .البحث الشامل تابع الخطوات مرتين أو ثلاثا فقط (  دون الدخول  في 26 خطـوة كاملة) لـو اسـتخدمنا بحثًـا شـامل يتوسـع إلـى عمق 22 مع متوسـط تفرع يقارب 3، فسـنحتاج إلـى عدد حالات يقارب: 10^10×3.1≈322  أنَ دور(n)h يتمثَـل فـي تقليص فضاء البحث بشـكل هائـل مقارنة بالبحث الشـامل

أن الغـرض ليـس حـلَ اللُغـز كاملًا (26 خطـوة)  ،بل كيـف تعمل خوارزمية َ(A * Search) عمليـا  ، وكيف يقلل  اختيار (n)h المناسـب عـدد الحـالات  التـي يجـب استكشـافها مقارنة بالبحث الشـامل.

 

بناءً على العدد السابق لعدد الحالات التي يُمكِن بها إيجاد الحَل، يجب إيجاد دالة استدلالية جيدة للتمكُّن من إيجاد أقصر الحلول؛ شرط ألّا تُبالغ هذه الدالَّة في تقدير عدد الخطوات إلى الهدف.

يوجد طريقتان شائعتان للاستخدام، هما:

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

H2. 2 : مجموع مسافات المُربَّعات من مَواضِع هدفها. في هذه الطريقة، سيتم حساب المسافات
أفقيًّا أوعموديًّا؛ لأنَّه لا يُمكِنها التحرُّك قُطْريًّا. و H2 أيضًا مقبول؛ لأنَّ كل مُربَّع سيتحرَّك حركة واحدة على الأقل. أمّا بالنسبة إلى الشكل( 3- 9) والحالة الهدف، فإنَّ عدد الحركات التي يحتاج إليها كل مُربَّع للوصول إلى الحالة الهدف سيكون على النحو الآتي:

•  عدد الحركات التي سيحتاج إليها المُربَّع الذي يحمل الرقم ( 1) هو ( 3).
•  عدد الحركات التي سيحتاج إليها المُربَّع الذي يحمل الرقم ( 2) ليصل إلى موقعه الهدف هو(1)
• عدد الحركات التي سيحتاج إليه المُربَّع الذي يحمل الرقم ( 3) ليصل إلى موقعه الهدف هو(2)
• عدد الحركات التي سيحتاج إليها المُربَّع الذي يحمل الرقم ( 4) ليصل إلى موقعه الهدف هو(2)
• عدد الحركات التي سيحتاج إليها المُربَّع الذي يحمل الرقم ( 5) ليصل إلى موقعه الهدف هو(2)
• عدد الحركات التي سيحتاجها المُربَّع الذي يحمل الرقم ( 6) ليصل إلى موقعه الهدف هو( 3)
• عدد الحركات التي سيحتاج إليها المُربَّع الذي يحمل الرقم ( 7) ليصل إلى موقعه الهدف هو( 3)
•  عدد الحركات التي سيحتاج إليها المُربَّع الذي يحمل الرقم ( 8) ليصل إلى موقعه الهدف هو(2)

ومن ثَمَّ، فإ مجموع الحركات للبلاطات (القطع) التي تحمل الأرقام السابقة هو:

H2 = 3+1+2+2+2+3+3+2 = 18

أُلاحِظ ممّا سبق أن الحَلَّين لا يعطيان تقديرًا لتكلفة الحَلِّ الحقيقية التي يبلغ مقدارها ( 26).

 

تعمل اقترانات التقييم السابقة على إرجاع الحدود الدنيا للتكلفة الفعلية التي يتمُّ تقديرها؛ ففي لعبة (لغز) الأرقام الثمانية ( 8-Puzzle )، تُمثل حركة تحرُّكًا لمُربَّع واحد، ويتعيَّن على كل مُربَّع أن يتحرَّك مَرّات عديدة بقَدْر  مسافة مانهاتن من موضعه الهدف، علما بأنَّ مسافة   مانهاتن تُمثِّل الحَد الأدنى لعدد الحركات الفعيلة المطلوبة لحَلِّ مشكلة مُعيَّنة

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

 

 

 

 

 

 

 

إجابة محتملة:

1. (H): عدد الأرقام  التي في المكان الخطأ = 8 حركات.

2. (H): عدد الحركات التي يحتاج إليها كل مربع للوصول إلى الحالة الهدف سيكون على النحو الآتي :

عدد الحركات التي سيحتاج إليها المربع الذي يحمل الرقم (1) ليصل إلى موقعه الهدف هو (1).

عدد الحركات التي سيحتاج إليها المربع الذي يحمل الرقم (2) ليصل إلى موقعه الهدف هو (1).

عدد الحركات التي سيحتاج إليها المربع الذي يحمل الرقم (3) ليصل إلى موقعه الهدف هو (3).

عدد الحركات التي سيحتاج إليها المربع الذي يحمل الرقم (4) ليصل إلى موقعه الهدف هو (1).

عدد الحركات التي سيحتاج إليها المربع الذي يحمل الرقم (5) ليصل إلى موقعه الهدف هو (2).

عدد الحركات التي سيحتاج إليها المربع الذي يحمل الرقم (6) ليصل إلى موقعه الهدف هو (2).

عدد الحركات التي سيحتاج إليها المربع الذي يحمل الرقم (7) ليصل إلى موقعه الهدف هو (2).

عدد الحركات التي سيحتاج إليها المربع الذي يحمل الرقم (8) ليصل إلى موقعه الهدف هو (3).

ومن ثَمَ ، فإن َ مجموع الحركات للبلاطات (القطع) التي تحمل الأرقام  السابقة هو:

H2 = 1 +1+3+1+2+2+2+3 = 15

لوحظ من أن الحلين لا يعطيان تقديرًا لتكلفة الحَل ِالحقيقية التي يبلغ متوسطها(22) حركة.

 

 

 

 

 

 

 

إجابة محتمَلة:

1- 

•   يصعب إيجاد خوارزمية إرشادية جيدة؛ إذ يتطلَب معرفة عميقة ببنية المسألة، حيث يجب على الوكيل:
• تقسيم المسألة، واشتقاق Heuristic من مشكلات  فرعية أبسط.
• تحتاج إلى تعلُم الآلة لتوليد الاقتران الاجتهادي ِ بالتدريب

2- 

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

 

 

 

 

 

 

 

 

 

إجابة مُحتمَلة:

• تشير معظم المراجع الموثوقة إلى أنَّ متوسِّط عامل التفرُّع ( Branching Factor ) في لعبة الشطرنج يتراوح بين 35 و 40 حركة تقريبًا في كلِّ نقلة، وغالبًا ما يُستخدم العدد(≈ 35 ) كقيمة تقديريَّة.

 

• أما بالنسبة إلى عدد العُقَد المحتمل لشجرة البحث ( Game Tree Nodes )، فقد قُدِّر بما يقارب 120 ^ 10 عُقدة، الذي يوضِّح ضخامة فضاء الحالات وتعقيده في لعبة الشطرنج.

 

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

نشاط :

1.  تتبُّع حركة مربَّع الرقم 5، وحساب عدد الحركات في لوحة لغز الثمانية مع مربَّع واحد ليس في مكانه وحساب مسافة مانهاتن لهذا المربَّع فقط ، و كم خطوة يحتاج للوصول إلى الهدف؟

 

 

 

 

 

 

 

 

حساب الخطوات (مسافة مانهاتن):

• الخطوة الأولى: نحرك الرقم 5 "خطوة واحدة للأعلى" ليصبح في الصف الأوسط.

• الخطوة الثانية: نحرك الرقم 5 "خطوة واحدة لليمين" ليصبح في المركز (مكانه الصحيح).

إذن، مجموع الخطوات هو 2 (خطوة للأعلى + خطوة لليمين).

2.  تتبُّع حركة مربَّع الرقم 7، وحساب عدد الحركات في لوحة لغز الثمانية مع مربَّع واحد ليس في مكانه وحساب مسافة مانهاتن لهذا المربَّع فقط ، و كم خطوة يحتاج للوصول إلى الهدف؟

حساب الخطوات (مسافة مانهاتن):

للوصول من المركز السفلي إلى الزاوية اليسرى، يحتاج الرقم 7 إلى: خطوة واحدة فقط باتجاه اليسار. إذن، مسافة مانهاتن للرقم 7 هي 1.

 

ثانيًا: الألعاب التي يمارسها لاعبان اثنان(Two-Player Games)

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

 

 

البحث المستمر: أبحث في المواقع الإلكترونية الموثوقة في شبكة الإنترنت عن المعلومات المطلوبة، وأعمل على تبسيطها واستخدامها بصورة فاعلة.
المسؤولية الرقمية: أُبادِر دائمًا إلى إيجاد الحلول التي تعمل على توفير الذاكرة والوقت.