بسم الله الرحمن الرحيم المحاضرة هاد ان شاء الله
بنكمل اخر كلمتين وقفنا عندهم المحاضرة الماضية
ونبدأ في موضوع جديد موضوع جديد صحيح لكن تحت موضوع
الكبير اللي هو hill search المحاضرة الماضية كنا
حكينا عن ال hill climbing كان هذا المحور الأساسي
للمحاضرة الماضية ال hill climbingو ال simulated
ending كان في معانا slide تانية نطلع
عليها السريع و نراجع فيها من خلالها بدينا
نحكي إن كان الموضوع الأساسي اللي هو 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 Height Climbing اللي هو
Select Random from Up Height Moves يعني تيجي لكل
ال children و شوف إيش فيه كل الأفضل منها و بتختار
أفضل واحد هذا الكلام من الأساس من الأساس أسلوبة في
البحث انه مش بتختار الأفضل على الإطلاق يعني عندي
عشرة children مش بختار أفضل واحد فيهم لا بنختار ..
بنشوف اللي .. اللي أفضل منها ال node بتشوف اللي
أفضل منها إذا ده العشرة فيه سبعة أو خمسة أو أربعة
أو تلاتة أفضل منها تروح تختار at random واحد من
هدول الأفضل يعني مش دايما بتختار أفضل الأفضل صح
هذا من البداية علشانكل هذه عبارة عن variations على
أساس ان ال algorithm تستبعد احتمالية الوقوع في ال
local minima بعد ذلك حكينا في simulated annealing
ببساطة شديدة
الأدجوريثم تختار تراندم و تفحص ال 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 فانا عملها بتلاتين بعدين بتتناقص شوية شوية
لحدين لتصل ال zero هذا على فرض ان هم عشرين
iterations فقط لكن عمليا هم لم يبقوا اكتر بكتير من
هيك العدد ال iterations بس انا جلالتهم ده التوضيح
فقط الان هنا 0.2 هذه افترضت انها ال error تمام ال
error 0.2 يعني الفرق ما بين ال current stateother
state 0.2 هنا 0.4 اكبر هنا اكبر هنا اكبر هنا error
هنا الخطوط هذه بتوريك الخط الأحمر Delta E1 مكتوب
عليه صح Delta E1 هو هذا العمود E1 هو ال error جديش
0.2 0.2 فإذا كان ال error مفترض ان في عندي انا
الألجوريث موقف على الـ state وفحصت ان الـ child
دولجت انه الـ error جديش الـ 0.2 إيش احتمالية انها
تخدها إيش احتمالية انها تخدها لو كانت في ال
iteration الأولى إيش احتمالية انها تخدها لو كانت
في ال iteration التالتة الرابعة الاحتمالية
الاحتمالية بصي .. لا بصي .. ايش اللي بصير بناء على
ال chart هذاالاحتمالية تزيد احتمالية في الأول
منخفضة وبعدها ترتفع منخفضة وبعدها ترتفع ترتفع كل
ما استمرنا في ال iterations كل ما تقدمنا في ال
iterations بصي ال probability أعلى انها تاخدها هذا
ال .. انت ممكن تغير هنا ال values هذه تغير ال
errors تخليها مثلا point five وتشوف أثر ذلك على ال
curveطبعا كل عمود له هنا خط يقابله طيب
احنا في هذا الحالة بنكون ايش؟ بنكون حاكينا عن ال
head warming وال simulated انيليا في الفضل اللي هو
ايش؟ ال local beam مظبوط ال local beam باختصار
شديد هي يعني شبيهة بال Stochasticبمعنى ان نحن ال
node او ال algorithm وهي واقفة على ال node وبتروح
تاخد ال K best successors K هنا بمعنى و الخمسة و
الأربعة وهذا constant بتبدأ فيه ال algorithm بستمر
معاها ثابت و الخمسة او أربعة او سبعة او ما إلى ذلك
بتروح تاخد أفضل سبعة الأفضل سبعة هدولة او أفضل
خمسة او أفضل تلاتة مش مضرورة يكونوا كلهم أفضل منها
okayالمهم هو افضل المتاح افضل عدد من افضل عدد K من
المتاح ماشي الحل في هذا الحل ايش بتسوي بعدها
بتاخدهم و بتختبرهم و بتستمر في تفحصهم كلهم الان كل
واحد بتفحصه كل واحد بتفحصه من هدول الأربعة ممكن
يكون له successors صح ولا لأ يبقى الأربعة هدولة لو
ال branching factor تلاتةلو ال branching factor
تلاتة و احنا عندنا اربعة يمكننا نتوقع ان الاربعة
دول يولدوا اتناش اربعة في تلاتة اتناش مظبط صح
الاربعة كلهم يولدوا اتناش الان من الاتناش هدول ال
children زي الآن احنا اخدنا الاربعة best افضل best
key best successes و فحصناهم و اعملهم ال goal اللي
هم نبص على مينهذا ال children تبعهم لهم ال 12 ال
12 هدولة مابنبصش عليهم كلها مابناخد أحسن K منهم K
اتفاجنا أربعة ناخد أحسن أربعة من هذي ال 12 كيف دي
يعرف أحسن أربعة؟ نعم كيف دي يعرف أحسن أربعة؟ نعم
نعم ال evaluation هذا قضية ال evaluation هذا كل
الكلام تبعنا احنا بنحكي under اللي هو ال informer
كله under .. لأن في evaluation للناستمام؟ وبهذا
القليل انه ال algorithm تبقى ماشية كأنها ماشية على
أربع خطوط في أن واحد كأنها بتفحص أربع احتمالات في
أن واحد مظبوط؟ مش بتاخد single successor و بتفحصهم
بتكبش أربع من ال available و بتفحصهم ربما واحد
منهم يكون ال goalإذا و لا واحد منهم جول تروح تاخد
كمان capture أربعة اجداد أفضل أربعة من ال .. من ال
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 بيحكي في ال Adverb Serial Search
وبتفرع من ال chapter خمسة هذا اللي هو اللي حكى عن
ال games و ال optimal decision games و بعد هيك ال
alpha beta pruning احنا هنجى فى عند ال alpha beta
pruning الان بس بدنا ناخد ال slide من الملف غير عن
ال edition اللى عندنا على ال folderفهنا ال game
playing جاي في شطر ستة في السلاي دات يعني أنا في
الكتاب هو في الخمسة طيب الآن احنا
هيكون
تركيزنا ال adversarial search على ال mini max ال
mini max decision و ال alpha data
بس بالأول نفهم الأولاء الأساسي اللي هو adversarial
search adversarial جاي من adversary ال adversary
اللي هو الشخص المعادي أو الخصم يعني adversarial
search اللي هو ال search اللي بيكون فيه problems و
مسائل اللي بيكون فيها اتنين خصوم كل واحد بيحاول
يغلب الآخر بإنه يعظم مكاسبه و يقلل مكاسب الطرف
الآخرهو يعظم الخاسر الطرف الآخر زي لعبة
الشاطراليجي زي لعبة ال tic-tac-toe لل X والO تحاول
أنت أنت
تبدأ مثلا بال O وخصوصا بيحط لك ال X عشان يسكّل
عليك أنت بتحط هنا و يسكّل عليك فهي اللعبة أن أنت
يشعرالهدف في أعوان اللعبة أن انت هي لعبة طرفين
بتخاصموا أو بتنافسوا فيها وكل واحد بده يعظم مكاسبه
و يقل المكاسب للآخر ففي هذا النوع من ال problems
أو في هذا النوع من ال games عملية ال search بتختلف
شويه صغيرة بصير أنا معنى بأنهأجد ال goal .. أجد ال
goal state اللي بت .. اللي فيها أعلى value إلي و
أقل value ليش هو الخصم تبعك، انت افترض انه انت
بتلعب مع ال computer، ال computer هو الخصم، مش هو
ضرورة اتنين بين أدمين اللي بيلعبوها يعنيفالان انت
بدك تفترض انت ال computer بمعنى ان انت بدك تحط
playing technique او playing strategy اللي تلعب مع
بنا آدم و تغلب البنا آدم فمثال على هذا او واحدة من
ال algorithms او ال techniques اللي ممكن تستخدم في
مثل هذا النوع من ال problem اللي هي ال minimaxالـ
Minimax أحيانا بيسميها procedure أحيانا بيسميها
decision وأحيانا مجازا بيسميها algorithm معينة هي
بس مجرد strategy مش algorithm بالمعنى التفصيلي
يعني ال minimax ببساطة شديدة احنا خلينا نطلع على
example عليها اللي هو
ال
tic-tac-toe
عندك انت في لعبة ال tic-tac-to في الأول بتنبدأ
اللحظة فاضية صح فانت عندك كلاب أول كل تمام مربعات
خيارات إليك تحط فيها القطعة تبعتك انت راح تفترض
انك تبدأ بال X انت تبدأ بال X فعاملك تمام خيارات 1
,2,3,4,5,6,7,8,9,10,11,12,13,13,13,13,13,13,13,13
,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13
,13,13,13,13,13,13,13,13,13,13الان اللاعب اللى بده
يكسب اللعبة اللى بنسميه max والطرف التانى اللى
بنسميه min max معها ال x و ال min معها ال o فهذه
خيارات التسعة اللى فى البداية الان الان
ال min بده ياخد كل واحد من خيارات هذوله و يشوف ايش
اللى ممكن متاح اللهم و يشوف ايش الأفضل لهفهذا
الخيار في منه ان هو يحط ال O على طول هنا او يحط ال
O هنا او يحط ال O هنا كل واحد من هذه الخيارات بده
يقيم عمله تقييم على اساس ان ال algorithm تختار ال
state الأفضل اللى بده توصل في الآخر إلى فوز ل Xأما
هك أو بأي شكل آخر من الأشكال ممكن يصل إلى النهاية
و ممكن ما يصلش هى ممكن يصل انه تبقى 9 خيارات فهي
تطلع منهم اتنين و يبقى 7 خيارات مش اتنين لإن فى او
بتلحق كده ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا
ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا ا
ا ا ا ا ا ا ا ا ا ا ا ا ا
يعني max انا عنده 9 خيارات و بدنا نيجي نعملهم
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 ايش
الانضال منها خيار خيارين تلاتة فمن احسن واحد فيهمو
أسجل الخيارة كل واحد منهم إيش ال valley تبعه
وبعدين أنا أشوف هذه ال state في دور من إذا في دور
من أنا أعلم إن من هيبحث عن الخيار الأقل لأن الأقل
هو أقل إلي هو مكسب إله الأقل هنا يعني هنا هذا أحسن
إلي لكن هذا أحسن لمن مصبوط صح هذا يعني الرقم
العاليهو كويس ل max و المقام المنخفض هو كويس ل min
فإذا كان هى فضوع من انا اعلى منه اذا افترض هذه
تلتة و هذه واحد انا اعلى منه منه هياخد واحد هياخد
الخيار هذا هيمشي في هذا الاتجاه لأنه سيء لي صح او
لا انا؟ يبكى اذا هذا خيار كمان كان فيه خيارين
تانينوالتلاتة هدولة لهم parent state نفترض هذا
واحد وهذا تلاتة وهذا سبعة طيب okay هدولة كلهم
الخيارات المتاحة لمن ومن حتما هياخد هذا لأنه أسوأ
لي طيب انا هكون دلوقت قبله اي خيار هاخد سبعة صح
فالعملية بتسمح ان احنابنقدر نيجي نفكر في الأمر
كالتالي نبسط بس القضية بتلاتة levels التلاتة
levels هدولة فتوضح أن هدولة ليش ال leaf nodes leaf
states Max بيلعب أول خطوة بعدين من بعدين بيكون دور
Max الآن في دور Max هدى التلاتة والاثمان والاثمان
والاثنين هدولة عبارة عن ليش ال heuristic values او
ال evaluations تباركة ال statesاذا انا اعلم ان هذا
ال node هو 12 وهذا 8 انا اعلم ان من حتما هيختار
الأقل
وهنا
نفس الشيء هيختار الأقل و هنا نفس الشيء هيختار
الأقل
لو انا عملت حركة action one action two action
تلاتة action one اعطاني هذه و action two اعطاني
هذه و action three اعطاني هذه اعمل اي action فيهم
اذا انا عندي تلاتة possible if انا واحد واحد في
هنا لسه اللحظة فاضية و معايا تلاتة possible
actions و انا اعلم كل action كده مدى ضرر علياالأقل
ضرران فانا
الأن بدي أاخد الأقل ضرران اللي هو الأعلى قيمة لي
تلاتة تلاتة هنا القيمة الأعلى لي صح فانا حتما هاخد
ال action number one مظبوط الكلام ولا لأ هتمثل ال
minimum نعم هتمثل القيمة الأعلى في ال minimum صح
طبعا كيف ال values هذه هي القيمة تبعت ال stateأنا
ك max ببحث عن القيم العليا، من يبحث عن القيم
المنخفضة، خلاص؟ فانا الآن عندي ال 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 تبعه
في دور مين؟ في دور من؟ اذا في دور من يبقى بيرحل ال
minimum value
propagate يعني نرحلها بعدين
خلاص مضلش الشيء خلاص الان الكمبيوتر بيلعب هون غامض
ليش؟ لأن هذه التلاتة بتقوله خد ال node لأ لأ رقم
تلاتة ال limit التلاتة يعني كل node لها value صح؟
صح؟ و المعروف من ال actionاللي بيوصل إليها ال
system الآن و هو مغمض بدي أخد ال action المرتبط
بال value خلاص انت صار عنده من البداية صار عنده من
البداية أن أحسن state و أنت واقف هنا أحسن state هي
ال state اللي ال value تبعها تلاتة طيب ماشي الحل
وين ال action؟ ال action اي واحد هو اللي بيودين
عليه خلاص و بعد هيك بعد ما يلعب هذابعد ما يصير في
stay تلاتة تلقائيا احنا فاهمين ان الخصم يلعب بنفس
العقلية فهيروح ياخد هادي مش لأنها تلاتة افضل لأ
لأنها تلاتة اقل هيدكدي هنا الان هادي ايش ال
children تفرع منها فانا باخد ال child الليبس هو ..
هو عمليا لو ولا واحد فيهم غلط و واحد منه ضال يختار
ال minima و ضال يختار ال minimax النهاية الحتمية
ان اللعب اتسكر و ما حدا فوز اي بالظبط ان انت بتركز
على ان هناك يطلع ان الخصم تبعك يخرج عن تفكير ال
minimax اذا نفس ال system لعب اتحاله اقل نتيجة
ممكن ياخدها تعادأنا بنتبهت أنه ممكن لو أخد الأفضل
لو أنا أخدت الأربعة اللي في النص هذه مستحيل يبقى
خسارة فيه زي في ال .. في ال XO يعني مثلا لو أنا
أخدت الأربعة اللي في النص أنا مستحيل أخسر فيها
نيارية الأربعة في النص ماشي قصدك الأربعة في النص
لو أنا أخدت الأربعة ال value أربعة كانت في ال XO
مستحيل خسارة فيهايعني انت ممكن مش two goals ورا
بعض لأ فاهم لأ انا فاهم يطلع عندي اربع ال value
اربع يعني في ال X و لو نرجع احنا لو احنا لو احنا
لو احنا لو احنا لو احنا لو احنا لو احنا لو احنا لو
احنا لو احنا لو احنا لو احنا لو احنا لو احنا لو
احنا لو احنا لو احنا لو احنا
لو
احنا
سلابك هي تحط هنا و لا تحط هنا و جذبه على two win
possibility إذا جيت ال X اللي في النص مع أي X على
الزاوية تمام لما يحط X في أي مكان بصير عنده احتمال
ينفوذ يعني احتمال ينفوذ مؤكد بيصير إذا حط X هنا في
الزاوية في الزاوية صحيح تمام بصير في عنده إيش هذا
أي واحد احتماله و حط X في أي مكانحط X في أي مكان
تاني في أي مكان تاني
عمليا لو حد بدأت .. لو حد بدأت بيحط هنا و بعدين
بيحط في اي مكان تاني اه صحيح زي كده اه و سنعمله
هذا و سنعمله هذا بس في حاجة هو عمليا .. هو الخصم
تبعك مش حاسيبك طبعا هو الخصم تبعك و انت حاططها في
النص و هيروح يسكر عليك الزوايا او بحاجة هيعملها
يسكر الزوايا بالظبط ده هيك نفسي ثالث صحيح؟ اه
بتاخدش اتنين roles و اربعة صحيح بس انا بقول يعني
هو بالنسبة لسيس .. الموضوع .. الموضوع ال minimaxزي
ما قلنا في الأول أن الطرفين
لازم هيتعادلوا إلا إذا واحد ارتكب خطأ خارج عن نص
ال minimax procedure طبعا احنا بنفترض أن هذا وارد
لأن واحد منهم هيكون computer و التاني human human
الخطأ هيجي من ال human او ضعيف ييجي من ال system
زي ما كانت الـ idea to choose the move to position
with the highest minimax value best available
payoff against the best play طيب،
أيش بدنا نطلع الأن؟ نطلع على أن ال properties
تبعتها، حتى واحدة اللي كنا بنحكي فيه، إيه علاقة
بال properties؟ المعنى أن مثلا ال completeness، هل
هي complete؟ هل هي بتجد حل دائما؟
هل تجد حل دائما؟ طبعا تجد بشرط ان ال search space
ي define it مايبقاش ال هذا لنهيه و الأصل مامش هقدر
اشتغل شرط مصمم لازم اصل ال leaf nodes طبعا انا
ممكن اذا infinite اجسم الشغل by iterative
deepeningiterative deepening بس هذا عشان اقدر
اشتغل يعني اجي ال tree تتمدد
فانا مش هقدر اقوس deep first او deep first
فبالتالي اجي اقول بدي اشتغل على L بالسبب ستة واطبع
على هدول ال notes علي ان هم ايش هم leaf notes مع
انه انا اعلم انه لسه في بتفرع منهم children بس انا
عشان اقدر اشتغل اعمل هدول ايشleaf nodes و اقيمهم
اعتبرهم يعني leaf nodes و اقيمهم و اشتغل على هذا
الأساس طبعا وصلت لمقطة اللي لابا لسه مستمرة المقطة
اللي لابا فيها بشوف ايش ال tree اللي بتتفرع منها و
باخد برضه و باخد depth limited ماشي بس هذا عبارة
عن مخرج من عملية ال infinite depth
طبعا صح مخرج ولكن لا يضمن لي ان انا اجد solution
او اجد يعني ال best move لان اللي انا حسبته بناء
على هذا المستوى قد يكون خاطئ وممكن يهزمني القصم
لان انا اشتغلت على جزء من الصورة طيب ال optimality
نعم بيكون optimal طبعا برضه كمان ياشهر في ظل اللي
هو ان تبقى limited و برضه بيكون optimal على أساس
ان القسم تبعك بيحاول يسعى الى لا تمام ال time
complexity P to the M و ال space complexity P O of
P M
مضطرين نوقف هنا بس في ضايل شغلة بسيطة بنحاول نحكي
فيها الآن وإذا كافل معانا الوقت إذا ما كفاش وقت
بنكملها المرة الجاية وهي أنه في هذا النوع من ال
search ال minimax procedure ممكن أنا محتاجش أعمل
evaluation لكل ال tree evaluationبمعنى ايش انه انا
الان في دور ال max وفردت ال children لسه مش عارف
اكمل child بس طلعت لجيت في عندي child و ال child
هذا بده اخش اشوف ايش بتفرع منه فخشيت و اتفرع و
لجيت انه في تلتة children الان انا هنا في هذا ال
level في دور ال max قبل هي كده في دور مني انا اعلم
انه في دور منيأه من هياخد ال minimum من هدول ال
children فحتما هياخد التلاتة صح طيب الآن خلصنا من
هذا الطريق بما نشوف إذا في child تاني و هل ال
child تاني بتفرع منه ال children ولا لأ الآن أنا
لجيت أن ال child هذا بتفرع منه تلاتةأول راح احد
منهم مفهزته وجدت الـ heuristic value او ال fitness
function value تبقى 2 اتنين هذه ماشي خلينا نحطها
هنا مؤقتا بس فاكر معايا انت الاتنين هذه و هي مؤقتة
احنا لسه بدنا نشوف جدام ال children الأخرين نطلع
عليهم عشان نعملهم evaluation طيب اذا كان ال value
سبعتهم اكبر من 2 بلزمه او بلزم ان انابالظبط ان انا
اطلع لهم الـ min هذا ال max
لما شاف التلاتة هذه لما شاف النود هذه ال value
تبعها تلاتة هو محتاج يستمر في البحث املا على امل
ان يجد شيء افضل من التلاتة صح؟ صح؟ طيب الان هو خرش
على هذا و لجل ال child تبعه اتنينخش على هذا الـ
chart و لا على هذا الـ chart تبقى 2 طيب أكمل عشان
أبحث عن إشي أقل من الإتنين ما هو أنا في دور من
الإتنين هذي مش هتتبدل إلا إذا في إشي أقل منها طب و
ليش أصلا أخش أدور على إشي أقل من الإتنين إذا كان
ال maths جاعة ببحث عن إشي أكبر من التلاتة؟ شو
معناه هذا؟ معناه هذا كان إن أنا بقدر أوقف البحث
أوقف عملية استكشاف ال children و مجرد ما اني انا
لجيت ال child هذا و عرفت ان ال value تبع اتنين ال
linguistic value تبع اتنين و الاتنين هذه مبدئيا
بدأت تترحل ال parent اللي هو في دور ال man و
بنستمر في البحث وشوف اذا في children اخرى اخرى و
هذا ال children اذا واحد منهم اقل من الاتنين بدنا
نبدل الاتنينبهذا ال value طب و ليش اخش في العملية
هذه اذا كان انا اعلم ان ال parent تبعي ال parent
اللي هو في دور ال max بيدور على state ال value
تبعها اكبر من تلاتة و انا بدأ اخش اعمل search ادور
علىState الفئة تبقى على قدم اتنين مالوش لازم هذا
الكلام يبقى بقف الوقف هادي او توقيف ال search اسمه
Pruning Pruning يعني احنا كأننا بنجلم في شجرة شجرة
بنجسكس في الأفروع اللي مش لازم تمام هنا نفس الشيء
عن هذا الكلام بنفصل في المحاضرة الجاية ان شاء الله
بس انت بدك تستبعد انه عملية ال searchممكن تختزل
بشكل كبير من خلال ال proning طيب يعطيكم العافية