تقييم ألفا بيتا

وهي خوارزمية تعمل على تقليل عدد الأحتمالات في شجرة ميني ماكس

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

تقييم ألفا بيتا
بيانات عامّة
الصنف
المكتشف

التاريخعدل

يبدو أن تقييم الفا بيتا قد أخترع عدة مرات [2] ففي عام 1958 اخترع ألين نيويل وهربرت أ. سايمون، نظاما اسمياه ب "التقريب" [3] وكان لدى آرثر صموئيل نسخة مبتكرة لمحاكاة لعبة الداما.  كما اخترع ريتشاردز وتيموثي هارت ومايكل ليفين و / أو دانيال إدواردز تقييما مستقلا في الولايات المتحدة.[4] اقترح مكارثي أفكارًا مماثلة في ورشة عمل دارتموث في عام 1956 واقترحها على مجموعة من طلابه بما في ذلك آلان ونشرها في معهد ماساتشوستس للتكنولوجيا في عام 1961.[5]  ابتكر ألكسندر برودنو خوارزمية ألفا بيتا بشكل مستقل، ونشر نتائجه في عام 1963.[6]  قام دونالد كنوث ورونالد دبليو مور بتنقيح الخوارزمية في عام 1975.[7][8] أنها مثالية من حيث اختصار وقت الحساب المتوقع للأشجار ذات القيم المعينة عشوائيًا في ورقتين.[9][10] في عام 1986 بينما رأى مايكل ساكس وآفي ويغدرسون أن النسخة العشوائية من ألفا بيتا هي الأفضل .[11]

الفكرة الأساسيةعدل

تحتفظ الخوارزمية بقيمتين، ألفا وبيتا، والتي تمثلان على التوالي الحد الأدنى من النقاط التي يضمنها اللاعب والحد الأقصى للدرجة التي يضمنها لاعب الأصغر.  في البداية، ألفا هي لانهاية سالبة وبيتا هي لانهاية موجبة، أي  يبدأ كلا اللاعبين بأسوأ نتيجة ممكنة.  عندما تصبح بحيث تكون الحركة الناتجة اسوء من حركة وجدها اللاعب قبلها يتجاهلها ببساطة، حيث لن يلعب الخصم هذه الحركة .

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

تحسينات على النظامعدل

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

تكمن فائدة تقييم ألفا بيتا في حقيقة أنه يمكن التقليل عمن فروع شجرة البحث مما يعني بحثا أسرع.  بهذه الطريقة، يمكن أن يقتصر وقت البحث على الشجرة الفرعية "الأفضل" ، ويمكن إجراء بحث أعمق في نفس الوقت.  مثل سابقتها، تنتمي إلى فرع الخوارزميات وفئة منضم.  يقلل التحسين من العمق الفعال إلى أكثر بقليل من نصف الحد الأدنى البسيط إذا تم تقييم العقد بترتيب مثالي أو قريب من المستوى الأمثل (أفضل خيار للجانب عند الحركة مرتبة أولاً في كل عقدة).

عندما يكون أ هو عامل تفريع (متوسط أو ثابت)، و ب هو عمق البحث، فإن ج الحد الأقصى لعدد مواضع عقدة الورقة التي تم تقييمها (عندما يكون ترتيب النقل ضعيفًا) هو ج (ب × ب × ... ×ب) = ج(أ ب) - بنفس الطريقة التي تكتمل بها عملية البحث البسيطة.  إذا كان ترتيب النقل للبحث هو الأمثل (بمعنى أنه يتم دائمًا البحث عن أفضل الحركات أولاً) ، فإن عدد مواضع العقدة الورقية التي تم تقييمها يكون متساويا سواء كان لعقدة واحدة أو مجموعة من العقد ويساوي المعادلة : 

حيث b هو معدل التفريع

و d هو عمق البحث أو الحركة التي ينتهي عندها البحث

و o العدد الأقصى من المواضع التي تقيم في كل عقدة

وحين تختزل الحركات إلى جذرها التربيعي، أو، يتضاعف خعمق البحث مرتين بنفس المقدار من الوقت. [12] ويجب دراسة جميع حركات اللاعب الأول للعثور على أفضلها، ولكن لكل منها، يفترض أن اللاعب الثاني سيلعب أفضل نقلة ممكنة للحصول على النقلة الأفضل وبذلك يسهل التقييم على اللاعب الأول أتخاذ الحركة الأفضل دون الحاجة إلى أخذ حركات اللاعب الثاني الأخرى في الاعتبار.  عندما يتم النظر في العقد بترتيب عشوائي (على سبيل المثال، يتم اختيار الخوارزمية بشكل عشوائي) ، بشكل مقارب، يكون العدد المتوقع للعقد التي يتم تقييمها في أشجار موحدة ذات قيم أوراق ثنائية[11] كما في المعادلة:

 

وعندما تعين قيم الورقة بشكل مستقل عن بعضها البعض في نفس العقدة، وتعطى كلها نفس الأهمية فإن العدد المتوقع من العقد المقيم هو   وهو أصغر بكثير من العمل الذي تقوم به الخوارزمية العشوائية، المذكورة أعلاه، ومرة أخرى هو الأمثل لمثل هذه الأشجار العشوائية.[9]  عندما يتم اختيار قيم الطرف بشكل مستقل عن بعضها البعض ولكن عن طريق أختيار إحدى القيمتين   تكون النتيجة  

إذا كانت   إي أن d عدد غير منتهي[10]

وهذه الطريقة جيدة إيضا لهذه الأنواع العشوائية من الأشجار.  ومن الأفضل تقريب العدد الفعلي للقيم "الصغيرة" باستخدام .[9][10]

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

بالإضافة إلى ذلك، يمكن تعديل هذه الخوارزمية بشكل تافه لإرجاع اختلاف رئيسي كامل بالإضافة إلى النتيجة.  بعض الخوارزميات الأكثر عدوانية مثل MTD (f) لا تسمح بمثل هذا التعديل بسهولة.

تحسينات آخرىعدل

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

يمكن إجراء بحث ألفا بيتا بشكل أسرع من خلال النظر فقط في نافذة بحث ضيقة (يتم تحديدها بشكل عام عن طريق التخمين بناءً على الخبرة).  هذا هو المعروف باسم البحث عن طريق الشفط.  في الحالة القصوى، يجرى البحث باستخدام تقييم ألفا بيتا العادي ؛  تقنية تُعرف باسم البحث في النافذة الصفرية أو البحث في النافذة الفارغة أو البحث الاستكشافي.  هذا مفيد بشكل خاص لعمليات البحث عن الربح / الخسارة بالقرب من نهاية اللعبة حيث قد يؤدي العمق الإضافي المكتسب من النافذة الضيقة ووظيفة تقييم الربح / الخسارة البسيطة إلى نتيجة حاسمة.  إذا فشل بحث الشفط، فمن السهل اكتشاف ما إذا كان قد فشل في تحديد حركة عالية (كانت الحافة العليا للنافذة منخفضة جدًا) أو منخفضة (كانت الحافة السفلية للنافذة مرتفعة جدًا).  يوفر هذا معلومات حول قيم النافذة التي قد تكون مفيدة في إعادة البحث عن الموضع.

برزت فكرة أن ألفا بيتا تقييم فاشل لجون فيشبورن واعتمدت على نطاق عالمي بعد تعديلها قليلا كما اقترح وضع كتيبات لنهاية اللعبة الأمر الذي طُبِق فيما بعد.

العلاقة مع الخوارزميات الأخرىعدل

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

من ناحية أخرى، تستخدم الخوارزميات مثل SSS * استراتيجية معدة مسبقا.  هذا يجعلها أكثر كفاءة من حيث الوقت، ولكن بتضحية كبيرة نظرا لوجود احتمال وجود حركات أفضل من حركات الإستراتيجية المتبعة.[13]

انظر أيضاعدل

المراجععدل

  1. ^ "Artificial Intelligence: A Modern Approach". aima.cs.berkeley.edu. مؤرشف من الأصل في 23 فبراير 2021. اطلع عليه بتاريخ 24 فبراير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  2. ^ Newell, Allen; Simon, Herbert A. (1976-03-01). "Computer science as empirical inquiry: symbols and search". Communications of the ACM. 19 (3): 113–126. doi:10.1145/360018.360022. ISSN 0001-0782. مؤرشف من الأصل في 26 فبراير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  3. ^ "wrong-sli". www-formal.stanford.edu. مؤرشف من الأصل في 06 نوفمبر 2020. اطلع عليه بتاريخ 24 فبراير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  4. ^ Edwards, D. J.; Hart, T. P. (1961-12-01). "The Alpha-Beta Heuristic" (باللغة الإنجليزية). مؤرشف من الأصل في 06 نوفمبر 2020. الوسيط |CitationClass= تم تجاهله (مساعدة); Cite journal requires |journal= (مساعدة)
  5. ^ "MIT Artificial Intelligence Memo 41". www.kotok.org. مؤرشف من الأصل في 06 نوفمبر 2020. اطلع عليه بتاريخ 24 فبراير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  6. ^ "Wayback Machine" (PDF). web.archive.org. 2008-10-30. اطلع عليه بتاريخ 24 فبراير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  7. ^ Knuth, D.; Moore, R. (2002). "An Analysis of Alpha-Beta Priming '". مؤرشف من الأصل في 20 سبتمبر 2020. الوسيط |CitationClass= تم تجاهله (مساعدة); Cite journal requires |journal= (مساعدة)
  8. ^ Abramson, B. (1989). "Control strategies for two-player games". CSUR. doi:10.1145/66443.66444. مؤرشف من الأصل في 28 نوفمبر 2020. الوسيط |CitationClass= تم تجاهله (مساعدة)
  9. أ ب ت Pearl, J. (1982). "The solution for the branching factor of the alpha-beta pruning algorithm and its optimality". CACM. doi:10.1145/358589.358616. مؤرشف من الأصل في 28 نوفمبر 2020. الوسيط |CitationClass= تم تجاهله (مساعدة)
  10. أ ب ت Pearl, Judea (1980-09-01). "Asymptotic properties of minimax trees and game-searching procedures". Artificial Intelligence (باللغة الإنجليزية). 14 (2): 113–138. doi:10.1016/0004-3702(80)90037-5. ISSN 0004-3702. مؤرشف من الأصل في 26 فبراير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  11. أ ب Saks, M.; Wigderson, A. (1986-10). "Probabilistic Boolean decision trees and the complexity of evaluating game trees". 27th Annual Symposium on Foundations of Computer Science (sfcs 1986): 29–38. doi:10.1109/SFCS.1986.44. مؤرشف من الأصل في 09 يونيو 2018. الوسيط |CitationClass= تم تجاهله (مساعدة); تحقق من التاريخ في: |تاريخ= (مساعدة)
  12. ^ "Artificial Intelligence: A Modern Approach". aima.cs.berkeley.edu. مؤرشف من الأصل في 23 فبراير 2021. اطلع عليه بتاريخ 01 مارس 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  13. ^ Pearl, Judea; Korf, Richard E. (1987-06-01). "Search Techniques". Annual Review of Computer Science. 2 (1): 451–467. doi:10.1146/annurev.cs.02.060187.002315. ISSN 8756-7016. مؤرشف من الأصل في 6 مارس 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)