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

بيانات عامّة
الصنف	خوارزمية بحث
المكتشف	Alexander Brudno (en) — آرثر صموئيل

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

التاريخ

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

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

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

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

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

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

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

عندما يكون أ هو عامل تفريع (متوسط أو ثابت)، وب هو عمق البحث، فإن ج الحد الأقصى لعدد مواضع عقدة الورقة التي تم تقييمها (عندما يكون ترتيب النقل ضعيفًا) هو ج (ب × ب × ... ×ب) = ج (أ ب) - بنفس الطريقة التي تكتمل بها عملية البحث البسيطة. إذا كان ترتيب النقل للبحث هو الأمثل (بمعنى أنه يتم دائمًا البحث عن أفضل الحركات أولاً)، فإن عدد مواضع العقدة الورقية التي تم تقييمها يكون متساويا سواء كان لعقدة واحدة أو مجموعة من العقد ويساوي المعادلة: $O(b^{d/2})=O({\sqrt {b^{d}}})$

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

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

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

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

$\Theta (((b-1+{\sqrt {b^{2}+14b+1}})/4)^{d})$

وعندما تعين قيم الورقة بشكل مستقل عن بعضها البعض في نفس العقدة، وتعطى كلها نفس الأهمية فإن العدد المتوقع من العقد المقيم هو $\Theta ((b/2)^{d})$ وهو أصغر بكثير من العمل الذي تقوم به الخوارزمية العشوائية، المذكورة أعلاه، ومرة أخرى هو الأمثل لمثل هذه الأشجار العشوائية.^[9] عندما يتم اختيار قيم الطرف بشكل مستقل عن بعضها البعض ولكن عن طريق أختيار إحدى القيمتين $[0,1]$ تكون النتيجة $\Theta (b^{d/log(d)})$

إذا كانت $d\to \infty$ إي أن d عدد غير منتهي^[10]

وهذه الطريقة جيدة إيضا لهذه الأنواع العشوائية من الأشجار. ومن الأفضل تقريب العدد الفعلي للقيم «الصغيرة» باستخدام $0.925d^{0.747}$ .^[9]^[10]

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

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

تحسينات آخرى

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

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

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

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

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

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

انظر أيضا

شطرنج باربع لاعبين

شطرنج ثلاثي

شطرنج اوميغا

تعادل (شطرنج)

بيدق (شطرنج)

شطرنج (حاسوب)

المراجع

^ "Artificial Intelligence: A Modern Approach". aima.cs.berkeley.edu. مؤرشف من الأصل في 2021-02-23. اطلع عليه بتاريخ 2021-02-24.
^ Newell، Allen؛ Simon، Herbert A. (1 مارس 1976). "Computer science as empirical inquiry: symbols and search". Communications of the ACM. ج. 19 ع. 3: 113–126. DOI:10.1145/360018.360022. ISSN:0001-0782. مؤرشف من الأصل في 2021-02-26.
^ "wrong-sli". www-formal.stanford.edu. مؤرشف من الأصل في 2020-11-06. اطلع عليه بتاريخ 2021-02-24.
^ Edwards, D. J.; Hart, T. P. (1 Dec 1961). "The Alpha-Beta Heuristic" (بالإنجليزية الأمريكية). Archived from the original on 2020-11-06. {{استشهاد بدورية محكمة}}: الاستشهاد بدورية محكمة يطلب |دورية محكمة= (help)
^ "MIT Artificial Intelligence Memo 41". www.kotok.org. مؤرشف من الأصل في 2020-11-06. اطلع عليه بتاريخ 2021-02-24.
^ "Wayback Machine" (PDF). web.archive.org. 30 أكتوبر 2008. مؤرشف من الأصل (PDF) في 2008-10-30. اطلع عليه بتاريخ 2021-02-24.
^ Knuth، D.؛ Moore، R. (2002). "An Analysis of Alpha-Beta Priming '". مؤرشف من الأصل في 2020-09-20. {{استشهاد بدورية محكمة}}: الاستشهاد بدورية محكمة يطلب |دورية محكمة= (مساعدة)
^ Abramson، B. (1989). "Control strategies for two-player games". CSUR. DOI:10.1145/66443.66444. مؤرشف من الأصل في 2020-11-28.
^ ^ا ^ب ^ج Pearl، J. (1982). "The solution for the branching factor of the alpha-beta pruning algorithm and its optimality". CACM. DOI:10.1145/358589.358616. مؤرشف من الأصل في 2020-11-28.
^ ^ا ^ب ^ج Pearl, Judea (1 Sep 1980). "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. Archived from the original on 2021-02-26.
^ ^ا ^ب 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. مؤرشف من الأصل في 2018-06-09. {{استشهاد بدورية محكمة}}: تحقق من التاريخ في: |تاريخ= (مساعدة)
^ "Artificial Intelligence: A Modern Approach". aima.cs.berkeley.edu. مؤرشف من الأصل في 2021-02-23. اطلع عليه بتاريخ 2021-03-01.
^ Pearl، Judea؛ Korf، Richard E. (1 يونيو 1987). "Search Techniques". Annual Review of Computer Science. ج. 2 ع. 1: 451–467. DOI:10.1146/annurev.cs.02.060187.002315. ISSN:8756-7016. مؤرشف من الأصل في 2021-03-06.

[1] "Artificial Intelligence: A Modern Approach". aima.cs.berkeley.edu. مؤرشف من الأصل في 2021-02-23. اطلع عليه بتاريخ 2021-02-24.

[2] Newell، Allen؛ Simon، Herbert A. (1 مارس 1976). "Computer science as empirical inquiry: symbols and search". Communications of the ACM. ج. 19 ع. 3: 113–126. DOI:10.1145/360018.360022. ISSN:0001-0782. مؤرشف من الأصل في 2021-02-26.

[3] "wrong-sli". www-formal.stanford.edu. مؤرشف من الأصل في 2020-11-06. اطلع عليه بتاريخ 2021-02-24.

[4] Edwards, D. J.; Hart, T. P. (1 Dec 1961). "The Alpha-Beta Heuristic" (بالإنجليزية الأمريكية). Archived from the original on 2020-11-06. {{استشهاد بدورية محكمة}}: الاستشهاد بدورية محكمة يطلب |دورية محكمة= (help)

[5] "MIT Artificial Intelligence Memo 41". www.kotok.org. مؤرشف من الأصل في 2020-11-06. اطلع عليه بتاريخ 2021-02-24.

[6] "Wayback Machine" (PDF). web.archive.org. 30 أكتوبر 2008. مؤرشف من الأصل (PDF) في 2008-10-30. اطلع عليه بتاريخ 2021-02-24.

[7] Knuth، D.؛ Moore، R. (2002). "An Analysis of Alpha-Beta Priming '". مؤرشف من الأصل في 2020-09-20. {{استشهاد بدورية محكمة}}: الاستشهاد بدورية محكمة يطلب |دورية محكمة= (مساعدة)

[8] Abramson، B. (1989). "Control strategies for two-player games". CSUR. DOI:10.1145/66443.66444. مؤرشف من الأصل في 2020-11-28.

[:1-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. مؤرشف من الأصل في 2020-11-28.

[:2-10] ا ^ب ^ج Pearl, Judea (1 Sep 1980). "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. Archived from the original on 2021-02-26.

[:0-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. مؤرشف من الأصل في 2018-06-09. {{استشهاد بدورية محكمة}}: تحقق من التاريخ في: |تاريخ= (مساعدة)

[12] "Artificial Intelligence: A Modern Approach". aima.cs.berkeley.edu. مؤرشف من الأصل في 2021-02-23. اطلع عليه بتاريخ 2021-03-01.

[13] Pearl، Judea؛ Korf، Richard E. (1 يونيو 1987). "Search Techniques". Annual Review of Computer Science. ج. 2 ع. 1: 451–467. DOI:10.1146/annurev.cs.02.060187.002315. ISSN:8756-7016. مؤرشف من الأصل في 2021-03-06.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]