بسم الله الرحمن الرحيم، المحاضرة هذه إن شاء الله
سنكمل آخر كلمتين وقفنا عندهما في المحاضرة الماضية
ونبدأ في موضوع جديد، موضوع جديد صحيح، لكن تحت موضوع
الكبير الذي هو Hill Search. في المحاضرة الماضية كنا
حكينا عن الـ Hill Climbing، كان هذا المحور الأساسي
للمحاضرة الماضية. الـ Hill Climbing والـ Simulated
Annealing. كان معنا سلايد ثانية نطلع
عليها سريعاً، ونراجع فيها، من خلالها بدأنا
نحكي أن الموضوع الأساسي الذي هو Beyond the
Classical Search. حكينا الذي هو الـ Local Search
Algorithms، والـ Hill Climbing، والـ Simulated
Annealing، ووقفنا عند الـ Local Beam Search. ما
حكيناش فيه، لكن هذا آخر مخطط الذي حكيناه بالـ Hill
Climbing، الذي هو الـ Basics تبع الـ Algorithm نفسها.
الـ Hill Climbing Algorithm، وأسلوبها في البحث
عن الـ Goal أو الـ Solution، أو الـ Goal أو الـ State.
وإن مشكلتها الأساسية التي حكيناها، هي وقوعها
فيما يسمى بالـ Local Minima أو الـ Local Maxima، التي
هي أنها توجد نفسها في وضع، هي على State أفضل من كل
الذي حولها، أو أفضل من كل الذي ممكن يتفرع منها.
ولكن هذا الـ Local State، أو هذا الـ State ليس
ليس الـ Issue، ليس الـ Solution، ليس الـ
Global Maxima أو الـ Minima. الذي سنحكي عن مخارج
أو حلول، أو Alternatives، أو Modifications للـ Hill
Climbing التي ممكن تخرجها من هذه الـ Minimum. أيش
قلنا ثلاث حلول، خلينا نطلع عليهم سريعاً، الذي هو
الـ Variants، كلنا سميناهم Variants of Hill Climbing.
الـ Stochastic Hill Climbing، الـ First Choice Hill
Climbing، والـ Random Restart Hill Climbing. نبدأ من
الآخر. Restart ببساطة أنه عندما الـ Algorithm تجد
بمعنى أيش بتجد… بتعلق في State، وكل المحاولات
بعدها أسوأ منها، معنى ذلك وهذا الـ State ليس
الجيد، معنى ذلك هي… فبدها تعمل Restart with a
New Random Initial State. مظبوط الكلام؟ صحيح. الـ
First Choice، كانت الفكرة التي هي أنها تختار
States من التي حولها at random، وتفحص الـ Value
تبعها. مش تفحصها جورياً، لا تفحص الـ Value. If الـ
Value أحسن، تنتقل إليها. مش أحسن، تختار واحدة أخرى.
أول واحدة أفضل منها تنتقل إليها. هذا الـ First
Choice. الـ Stochastic Hill Climbing، الذي هو
Select Random from Up Hill Moves. يعني تيجي لكل
الـ Children، و تشوف أيش فيه أفضل منها، وتختار
أفضل واحد. هذا الكلام من الأساس، أسلوبه في
البحث أنه لا تختار الأفضل على الإطلاق. يعني عندي
عشرة Children، لا أختار أفضل واحد فيهم، لا أختار…
أشوف التي… التي أفضل منها. الـ Node تشوف التي
أفضل منها. إذا هذه العشرة، فيه سبعة أو خمسة أو أربعة
أو ثلاثة أفضل منها، تروح تختار at random واحد من
هذه الأفضل. يعني ليس دائماً تختار أفضل الأفضل، صح؟
هذا من البداية، لأن كل هذه عبارة عن Variations على
أساس أن الـ Algorithm تستبعد احتمالية الوقوع في الـ
Local Minima. بعد ذلك، حكينا في Simulated Annealing،
ببساطة شديدة.
الـ Algorithm تختار Random، وتفحص الـ Child. إذا الـ
Child أفضل منها، على State واحد من الـ Child States
أفضل الـ Evaluation تبعه، على طول تنتقل إليه بدون
أي تفكير. إذا أسوأ، ممكن تأخذه أو ممكن لا تأخذه
depending on
الـ Probability. الـ Probability هذه واقفة على أساس
الـ Exponent of ΔE على T. الـ ΔE هي الفرق، تمام؟
نحن افترضنا أنه أسوأ، وبالتالي فيه فرق في الجودة
ما بين الـ Current وما بين هذا الـ Child. فهذا الفرق
يقسم على T، T هذا عبارة عن Function of Time، عبارة
عن الـ Temperature، أسميها في الـ Algorithm
Temperature. تتناقص مع الوقت، تتناقص مع الوقت، تتناقص مع
الوقت، تتناقص مع الوقت، تتناقص مع الوقت، تتناقص مع الوقت
الوقت، تتناقص مع الوقت، تتناقص مع الوقت، تتناقص مع
الوقت
الـ Algorithm يختاره، صح؟ If Child is Worse، أسوأ،
May Select It. الـ Algorithm May Select It، قد، Based
on Probability. وهذه الـ Probability Based on الـ
Ratio of الـ Error Over الذي هو الـ Temperature، والـ
Temperature هذه Decreases as a Function of Time.
ماشي، أنا كان عندي Illustration سريعاً.
بس أديكم أنتم تجربوا فيه لوحدكم، الملف موجود على
الـ Folder.
تمام، فيه هنا على الـ Folder الرئيسي، تبع الـ Dropbox
فيه ملف Excel. ملف الـ Excel هذا أديكم تجربوا فيه
أنتم، أنتم. العمود الأولاني هذا T، التي قلنا تتناقص
By Time. فأنا عملتها بثلاثين، بعدين تتناقص شوية شوية
حتى تصل إلى الصفر. هذا على فرض أنهم عشرون
Iteration فقط، لكن عملياً هم لم يبقوا أكثر بكثير من
هذا العدد من Iterations، بس أنا جعلتهم هذا للتوضيح
فقط. الآن هنا 0.2 هذه افترضت أنها الـ Error، تمام. الـ
Error 0.2 يعني الفرق ما بين الـ Current State و Other
State. 0.2، هنا 0.4، أكبر، هنا أكبر، هنا أكبر، هنا Error.
هنا الخطوط هذه بتوريك، الخط الأحمر Delta E1 مكتوب
عليه، صح؟ Delta E1 هو هذا العمود. E1 هو الـ Error. جيد. أيش
0.2، 0.2. فإذا كان الـ Error، مفترض أن عندي أنا
الـ Algorithm واقف على الـ State، وفحصت أن الـ Child
وجدت أن الـ Error جيداً 0.2، أيش احتمالية أن
تأخذه؟ أيش احتمالية أن تأخذه؟ لو كانت في
الـ Iteration الأولى؟ أيش احتمالية أن تأخذه لو كانت
في الـ Iteration الثالثة، الرابعة؟ الاحتمالية
الاحتمالية… لا… أيش الذي يحصل بناء على
الـ Chart هذا؟ الاحتمالية تزيد. الاحتمالية في الأول
منخفضة، وبعدها ترتفع، منخفضة، وبعدها ترتفع، ترتفع. كلما
ما استمرينا في الـ Iterations، كل ما تقدمنا في الـ
Iterations، تصبح الـ Probability أعلى أن تأخذه. هذا
ال… أنتم ممكن تغيروا هنا الـ Values هذه، تغير الـ
Errors، تخلوها مثلاً 0.5، وتشوفوا أثر ذلك على الـ
Curve. طبعاً كل عمود له هنا خط يقابله. طيب،
نحن في هذه الحالة نكون أيش؟ نكون حكينا عن الـ
Hill Climbing، والـ Simulated Annealing. في البند الذي هو
أيضاً؟ الـ Local Beam، مظبوط. الـ Local Beam باختصار
شديد، هي يعني شبيهة بالـ Stochastic، بمعنى أن نحن الـ
Node أو الـ Algorithm وهي واقفة على الـ Node، وتروح
تأخذ الـ K Best Successors. K هنا بمعنى خمسة، وأربعة،
وأربعة، وهذا Constant تبدأ فيه الـ Algorithm، يستمر
معها ثابت، خمسة أو أربعة أو سبعة أو ما إلى ذلك.
تروح تأخذ أفضل سبعة، هذه الأفضل سبعة، أو أفضل
خمسة أو أفضل ثلاثة. ليس ضرورياً يكونوا كلهم أفضل منها.
Okay. المهم هو أفضل المتاح، أفضل عدد من، أفضل عدد K من
المتاح. ماشي، الحل في هذا الحل أيش بتسوي بعدها؟
بتأخذهم، وتختبرهم، وتستمر في تفحصهم كلهم. الآن كل
واحد بتفحصه، كل واحد بتفحصه من هذه الأربعة، ممكن
يكون له Successors، صح ولا لا؟ يبقى هذه الأربعة لو
الـ Branching Factor ثلاثة، لو الـ Branching Factor
ثلاثة، ونحن عندنا أربعة، يمكننا نتوقع أن الأربعة
دول يولدوا اثنا عشر، أربعة في ثلاثة، اثنا عشر، مظبوط صح؟
الأربعة كلهم يولدوا اثنا عشر. الآن من الاثنا عشر هذه الـ
Children، زي الآن نحن أخذنا الأربعة Best، أفضل Best،
K Best Successors، وفحصناهم، و عمل لهم الـ Goal الذي
هم. نبص على من… هذا الـ Children تبعهم، لهم الـ 12. الـ
12 هذه لا نبص عليهم كلهم، نأخذ أحسن K منهم. K
افترضنا أربعة، نأخذ أحسن أربعة من هذه الـ 12. كيف هذه
يعرف أحسن أربعة؟ نعم، كيف هذه يعرف أحسن أربعة؟ نعم.
نعم. الـ Evaluation هذا، قضية الـ Evaluation هذا. كل
الكلام تبعنا نحن نحكي Under الذي هو الـ Informer
كله Under… لأن فيه Evaluation للـ Nodes. تمام؟ وبهذا
القليل أن الـ Algorithm تبقى ماشية كأنها ماشية على
أربعة خطوط في واحد، كأنها بتفحص أربعة احتمالات في
واحد، مظبوط؟ لا تأخذ Single Successor، و تفحصهم
تأخذ أربعة من الـ Available، و تفحصهم. ربما واحد
منهم يكون الـ Goal. إذا ولا واحد منهم Goal، تروح تأخذ
كمان مجموعة، أربعة جدد، أفضل أربعة من ال… من الـ
Children. وبعد ذلك تستمر في هذا ال… في هذا الـ
Strategy، واضحة؟ فالآن نحن صار فيه عندنا بالأساس
ال… ال… الـ Hill Climbing Algorithm، والـ
Variants تبعها، وعندنا ال… الـ Simulated
Annealing Algorithm، وعندنا الـ Local Beam، وكلهم
متشابهين، قريبين من بعض، لأنهم يشاركون ببعض الخصائص
المشتركة، زي الذي هو Random Selection. الـ Local
Beam Algorithm تتشابه مع الـ Genetic Algorithm.
الـ Genetic Algorithm موجودة في الـ Section هذا، بس
أنا أخليها، لأنه نحن فصلناها… نحن فصلناها موضوع
لحالها. قداماً، نحن عاملين هكذا نكون أخذنا الذي نريده
من هذا الـ Section. أربعة، واحد من هذا الـ Chapter.
بعد ذلك ننتقل الآن إلى الـ Chapter الذي بعده، خمسة،
الذي هو Chapter خمسة، ونأخذ برضه منه Topic واحد،
الذي هو الـ Adversarial Search.
بالتفصيل أن نحن لازلنا تحت بند Problem Solving، يعني
هنا Chapter 5 يحكي في الـ Adversarial Search.
ويتفرع من Chapter خمسة هذا، الذي هو الذي حكى عن
الـ Games، والـ Optimal Decision Games، وبعد ذلك الـ
Alpha Beta Pruning. نحن سنأتي عند الـ Alpha Beta
Pruning الآن. بس نأخذ الـ Slide من الملف غير عن
الـ Edition الذي عندنا على الـ Folder. هنا الـ Game
Playing جاي في Chapter ستة في السلايدات. يعني أنا في
الكتاب هو في الخمسة. طيب الآن نحن
سيكون
تركيزنا في الـ Adversarial Search على الـ Minimax، الـ
Minimax Decision، والـ Alpha Beta
بس بالأول نفهم الأساسيات، الذي هو Adversarial
Search. Adversarial جاي من Adversary. الـ Adversary
الذي هو الشخص المعادي أو الخصم. يعني Adversarial
Search، الذي هو الـ Search الذي يكون فيه Problems و
مسائل التي يكون فيها اثنان خصمان، كل واحد يحاول
يغلب الآخر، بأنه يعظم مكاسبه ويقلل مكاسب الطرف
الآخر. هو يعظم خسارة الطرف الآخر. زي لعبة
الشطرنج، زي لعبة الـ Tic-Tac-Toe، للـ X والـ O، تحاول 175 00:15:31,
evaluation وناخد الـ best على أي أساس؟ إيش هي الـ
evaluation function أو الـ fitness function أو الـ
objective function اللي ممكن احنا نتبناها في حالة
زي هذه الحالة، في هذه اللعبة، هذا
الوضع، لو أنا حطيت الـ X هنا، هل أفضل من هذا؟ واللي
أفضل، واللي هذا أفضل؟ مين الأفضل؟ إيش القاعدة اللي
على أساسها بنقيم؟ من القواعد السابقة اللي تمثل
دول؟ لا، هذه لعبة جديدة، بدها قواعدها الخاصة، ميني ماكس
ما أقدرش أجيب قواعد الـ rules، هيورستيك تبع الـ .. أنا
ما بقولهاش أشهر أخرى، تبقى ميني ماكس، جابنا لسه احنا
ما نحكيش في ميني ماكس، بس احنا بنحكي الآن على
الـ fitness function اللي نعطيها لميني ماكس اللي على
أساسها تشتغل، إيش الـ fitness function اللي بدنا
نستخدمها في تقييم في وضع إيش؟ أنه هذه والله اللي
بتقربني، ولا هذه بتقربني أكتر، ولا هذه بتقربني
أكتر؟ للإيش؟ للـ winning، عرف أنا كل واحدة لما أحطها
في المصر، إيش هو؟ يعني إيش احتمالاته عشان ينجح؟ أيوة
أيوة، إيش عدد، إيش ممكن أقصى، إيش ممكن يعمل؟ يعني وأنت
الصادق، بتقدر تقول إيش عدد المناورات أو الاحتمالات
اللي أنا لازالت مفتوحة أمامي اللي أفوز منها يعني
مثلا أنا هنا بقدر أفوز في هذا الاتجاه، بقدر أفوز
هيك، بقدر أفوز هيك، صح؟ احتمالات للفوز، لو أنا حطيت
الـ X هنا، وهو ما انتبهش، وغمض عينه، ولا كده، وحط لي
مثلا هنا، ولا هنا؟ أنا بقدر أحط هذه هيك، وفي اللي
بعدها أحط هيك، فهذا الوضع، وهو عبارة عن مبتدأ أو بداية
لاحتتمالي أن أنا أفوز، لاحتمالي أن أنا أفوز، إذا أبيت
هذا الاتجاه، وبرضه إذا أبيت هذا الاتجاه، وبرضه
فهذا الوضع فتح لي تلات احتمالات للفوز، هذا الوضع
فتح لي كم احتمال؟ هاي واحد، هاي اتنين، بس، تمام، وكده
بحط هنا تلاتة، وبحط هنا اتنين، على أساس يعني، إيش هذه
الـ evaluation أو الـ fitness value تبع كل واحد من
الـ students، طب هذا تلاتة، تلاتة، تلاتة، تلاتة، تلاتة،
تلاتة، تلاتة، تلاتة، تلاتة، تلاتة، تلاتة، أربع، أربع، أربع،
أربع، أربع، أربع، أربع، أربع، أربع، أربع، أربع، أربع، أربع،
أربع، أربع، أ
لو أنا هنا، والخصم تبعي، لو أنا افترض أن الخصم تبعي
أنا بعد ما لعبت X، الخصم تبعي بحط الـ O هنا، صرت أنا
في هذا الوضع، أنا Max، صرت في هذا الوضع، لأن كم؟ كم
خيار متاح لي؟ طبعا متاح لي، لسه واحد، اتنين، تلاتة، أربع،
خمس، ستة، سبعة، سبع احتمالات أني أ العب، هدول بس
تلاتة منهم، لكن هذا الخيار الآن، أنا بقدر أفوز بهذا
الاحتمال، أو هذا الاحتمال فقط، أي حركة أخرى مافيها
مجال لأفوز، بالعكس ممكن تكون ضرر، اللي يعطي مجال
الخصم تبعي النفوذ، فاحنا في كل الأحوال، في كل الـ
states، هي strategy أو قايمة واحدة، أو heuristic
واحدة، اللي بنتبعها في تقييم الـ states اللي هم عدد
الـ possibilities أو احتمالات الفوز من الوضع تبع
هذا الـ state، طيب، بعدين، لسه ما حكيناش في الـ minimax
procedure، الـ minimax procedure، تقص على أنه احنا ما
زال صار في عندنا، ما زال عندنا الـ initial state، و
عارفين كل الخيارات اللي بتطلع منها، وعارفين إيش
الاحتمالات تبع كل هذا الخيار، كل واحد من هذه
الخيارات، إيش ممكن الخصم يعمل؟ بقدر أنا أتعمق في الـ
tree لأخره، لأخره، وأحط تقييم للـ leaf
nodes، للـ end states، أحط تقييم للـ leaf states، يعني
أيه؟ دي أخش depth first، وأقول هذه الـ state إيش
المنطلق منها، خيار، خيارين، تلاتة، فمن أحسن واحد فيهم، وأسجل
الخيار، كل واحد منهم إيش الـ value تبعه،
وبعدين أنا أشوف هذه الـ state، في دور من، إذا في دور
من، أنا أعلم أن من هيبحث عن الخيار الأقل، لأن الأقل
هو أقل، إلي هو مكسب إله، الأقل هنا يعني هنا هذا أحسن
إلي، لكن هذا أحسن لمن؟ للـ Min، صح؟ هذا يعني الرقم
العالي، هو كويس لـ Max، والمقام المنخفض هو كويس لـ Min،
فإذا كان هي قيم، ومن أنا أعلى منه، إذا افترض هذه
تلاتة، وهذه واحد، أنا أعلى منه، منه هياخد واحد، هياخد
الخيار هذا، هيمشي في هذا الاتجاه، لأنه سيء لي، صح؟ أو
لا، أنا؟ يبقى، إذا هذا خيار، كمان كان فيه خيارين
ثانيين، والتلاتة هدول لهم parent state، نفترض هذا
واحد، وهذا تلاتة، وهذا سبعة، طيب، okay، هدول كلهم
الخيارات المتاحة لـ Min، وMin حتما هياخد هذا، لأنه أسوأ
لي، طيب، أنا هكون دلوقتي قبله، أي خيار هاخد؟ سبعة، صح؟
فالعملية بتسمح أن احنا نقدر نيجي نفكر في الأمر
كالتالي، نبسط بس القضية بتلاتة levels، التلاتة
levels هدول، فتوضح أن هدول ليش الـ leaf nodes، leaf
states، Max بيلعب أول خطوة، بعدين Min، بعدين بيكون دور
Max، الآن في دور Max، هدول التلاتة، والثمانية، والثمانية،
والاتنين، هدول عبارة عن ليش الـ heuristic values أو
الـ evaluations تبع الـ states، إذا أنا أعلم أن هذا
الـ node هو 12، وهذا 8، أنا أعلم أن Min حتما هيختار
الأقل،
وهنا
نفس الشيء، هيختار الأقل، وهنا نفس الشيء، هيختار
الأقل،
لو أنا عملت حركة، action one، action two، action
تلاتة، action one أعطاني هذه، و action two أعطاني
هذه، و action three أعطاني هذه، أعمل أي action فيهم؟
إذا أنا عندي تلاتة possible، أنا واحد، واحد في
هنا، لسه اللحظة فاضية، ومعايا تلاتة possible
actions، وأنا أعلم كل action كده مدى ضرره عليا، الأقل
ضرر، فأنا
الآن بدي آخد الأقل ضرر، اللي هو الأعلى قيمة لي،
تلاتة، تلاتة، هنا القيمة الأعلى لي، صح؟ فأنا حتما هاخد
الـ action number one، مظبوط الكلام ولا لأ؟ هتمثل الـ
minimum، نعم، هتمثل القيمة الأعلى في الـ minimum، صح؟
طبعا، كيف؟ الـ values هذه هي القيمة تبع الـ state، أنا
كـ Max ببحث عن القيم العليا، Min ببحث عن القيم
المنخفضة، خلاص؟ فأنا الآن عندي الـ state الابتدائية،
وأمامي possible one، two، three actions، وأنا أهم
أن هذا الـ action هيدخلني على state الـ value تبعها
تلاتة، وهذا هيدخلني على state الـ value تبعها اتنين،
وهذا على state الـ value تبعها اتنين، يبقى أنا لازم
اختار الـ action اللي هيدخلني على state، صح؟ فهذا
ببساطة هي الـ minimax procedure أو الـ minimax
algorithm، فببساطة شديدة، أن احنا أول step في هذا الـ
procedure، إيش؟
expand
فأقدر أقول هيك، إن أنا بدي أفرد أو generate الفضاء
الاحتمالات كله، وإلا كيف بدي أعمل evaluation للـ
leaf nodes؟ كيف بتوصل لها؟ لازم أبجأ غصبا إلى نهاية
اللي هو الـ search space، بعدين أفردت الفضاء
الاحتمالات كله، أفرد، بعدين تفرع، تفرع، تعمل
evaluation في الأول،
leaf nodes، اللي يعني leaf states، عملنا evaluation،
عملنا إيش؟ عملنا evaluation؟ حطينا الاقيمة دي، صح؟
حطيناها بناء على إيش؟ مانحطها evaluation function أو
heuristic rule، صح؟ تلاتة هتقطع، نعم؟ بدنا نروح، نحل
نرحل الـ values إلى الـ parent nodes، الـ parent تبعه،
في دور مين؟ في دور Min؟ إذا في دور Min، يبقى بيرحل الـ
minimum value،
propagate، يعني نرحلها، بعدين
خلاص، ما ضلش شيء، خلاص، الآن الكمبيوتر بيلعب هنا، مغمض،
ليش؟ لأن هذه التلاتة بتقول له خد الـ node رقم، لأ، لأ، رقم
تلاتة، الـ limit، التلاتة، يعني كل node لها value، صح؟
صح؟ والمعروف من الـ action اللي بيوصل إليه الـ
system الآن، وهو مغمض، بدي آخد الـ action المرتبط
بالـ value، خلاص، إنت صار عنده من البداية، صار عنده من
البداية أن أحسن state، وأنت واقف هنا، أحسن state هي
الـ state اللي الـ value تبعها تلاتة، طيب، ماشي، الحل
وين الـ action؟ الـ action أي واحد هو اللي بيوديني
عليه، خلاص، وبعد هيك، بعد ما يلعب هذا، بعد ما يصير في
state تلاتة، تلقائيا احنا فاهمين أن الخصم يلعب بنفس
العقلية، فبيروح ياخد هذه، مش لأنها تلاتة أفضل، لأ،
لأنها تلاتة أقل، هيدور هنا الآن، هذه إيش الـ
children، تفرع منها، فأنا باخد الـ child اللي بس هو ..
هو عمليا، لو ولا واحد فيهم غلط، وواحد منهم ضال يختار
الـ minimax، وضال يختار الـ minimax، النهاية الحتمية
أن اللعب اتسكر، وما حدا فوز، أي بالظبط، أن أنت بتركز
على أن هناك يطلع أن الخصم تبعك يخرج عن تفكير الـ
minimax، إذا نفس الـ system لعب، اتحاله أقل نتيجة
ممكن ياخدها، تعادلها، بنتبهنا أنه ممكن لو أخد الأفضل،
لو أنا أخدت الأربعة اللي في النص، هذه مستحيل يبقى
خسارة فيه، زي في الـ .. في الـ XO، يعني مثلا لو أنا
أخذت الأربعة اللي في النص، أنا مستحيل أخسر فيها،
نيارية، الأربعة في النص، ماشي، قصدك الأربعة في النص؟
لو أنا أخدت الأربعة، الـ value أربعة، كانت في الـ XO،
مستحيل خسارة فيها، يعني أنت ممكن مش two goals ورا
بعض، لأ، فاهم، لأ، أنا فاهم، يطلع عندي أربعة، الـ value
أربعة، يعني في الـ X، ولو نرجع احنا، لو احنا، لو احنا،
لو احنا، لو احنا، لو احنا، لو احنا، لو احنا، لو احنا، لو
احنا، لو احنا، لو احنا، لو احنا، لو احنا، لو احنا، لو
احنا، لو احنا، لو احنا، لو احنا،
لو
احنا
الاستراتيجية، هي تحط هنا ولا تحط هنا، وجذبه على two win
possibility، إذا جيت الـ X اللي في النص، مع أي X على
الزاوية، تمام، لما يحط X في أي مكان، بيصير عنده احتمال
ينفوز، يعني احتمال ينفوز مؤكد، بيصير، إذا حط X هنا، في 38
إنه في دور منيّع، هياخد الـ minimum من هدول الـ
children، فحتماً هياخد التلاتة، صح؟ طيب، الآن خلصنا من
هذا الطريق، بما نشوف إذا في child ثاني، و هل الـ
child الثاني بتفرع منه الـ children ولا لأ. الآن أنا
لَجِئتُ أن الـ child هذا بتفرع منه ثلاثة. أول راح أُحدد
منهم، مفحصته، وجدت الـ heuristic value أو الـ fitness
function value تبقى 2 (اتنين). هذه ماشي، خلينا نحطها
هنا مؤقتاً بس. فاكر معايا إنت الاتنين هذه، وهي مؤقتة.
إحنا لسه بدنا نشوف قدام الـ children الآخرين، نطلع
عليهم عشان نعملهم evaluation. طيب، إذا كان الـ value
سبعتهم أكبر من 2، بِلزِم، أو بلزم أن، بالضبط أن أنا
أُطَلِّع لهم الـ min هذا، الـ max.
لما شاف التلاتة هذه، لما شاف الـ node هذه، الـ value
تبعها تلاتة، هو محتاج يستمر في البحث، آملاً على أمل
أن يجد شيئاً أفضل من التلاتة، صح؟ صح؟ طيب، الآن هو دخل
على هذا، ولِجِلْ الـ child تبعه، اتنين. نخش على هذا الـ
chart ولا على هذا الـ chart؟ تبقى 2. طيب أكمل عشان
أبحث عن شيء أقل من الاتنين. ما هو أنا في دور من
الاتنين هذه، مش هتتبدّل إلا إذا في شيء أقل منها. طب، و
ليش أصلاً أخش أدوّر على شيء أقل من الاتنين، إذا كان
الـ parent بتاعه ببحث عن شيء أكبر من التلاتة؟ شو
معناه هذا؟ معناه هذا كان أن أنا بقدر أوقف البحث،
أوقف عملية استكشاف الـ children، ومجرّد ما إني أنا
لجيت الـ child هذا، وعرفت أن الـ value تبعه اتنين، الـ
heuristic value تبعه اتنين، والاتنين هذه مبدئياً
بدأت تترشّح للـ parent اللي هو في دور الـ min، و
بنستمر في البحث، ونشوف إذا في children أخرى، وأخرى، و
هذا الـ children، إذا واحد منهم أقل من الاتنين، بدنا
نبدّل الاتنين بهذا الـ value. طب، و ليش أخش في العملية
هذه، إذا كان أنا أعلم أن الـ parent تبعي، الـ parent
اللي هو في دور الـ max، بيدوّر على state، الـ value
تبعها أكبر من تلاتة، وأنا ببدأ أخش أعمل search، أدوّر
على state قيمتها تبقى على قدم اتنين، ما لوش لازم هذا
الكلام. يبقى بوقف الوقف هذا، أو توقيف الـ search اسمه
Pruning. Pruning يعني إحنا كأنّا بنجرّد في شجرة، شجرة
بنجَسِّخ في الفروع اللي مش لازم، تمام؟ هنا نفس الشيء.
عن هذا الكلام، بنفصل في المحاضرة الجاية إن شاء الله.
بس إنت بدّك تستبعد أن عملية الـ search ممكن تختزل
بشكل كبير من خلال الـ pruning. طيب، يعطيكم العافية.