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

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

خلال ورشة عمل دارتموث، التقى جون مكارثي بأليكس بيرنشتاين من شركة آي بي إم ، الذي كان يكتب برنامجًا للشطرنج. ابتكر مكارثي خوارزمية البحث ألفا-بيتا وأوصى بها بيرنشتاين، لكن بيرنشتاين لم يكن مقتنعًا بها. ^{[ 2 ]}

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

يمكن لشجرة اللعبة أن تمثل العديد من الألعاب الثنائية ذات المحصلة الصفرية ، مثل الشطرنج والداما والريفرسي. يمثل كل عقدة في الشجرة موقفًا محتملاً في اللعبة. تُخصص لكل عقدة طرفية (نتيجة) من فرع ما قيمة عددية تحدد قيمة النتيجة للاعب الذي لديه النقلة التالية. ^{[ 13 ]}

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

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

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

مع عامل تفرع (متوسط ​​أو ثابت) مقداره b ، وعمق بحث مقداره d ، فإن الحد الأقصى لعدد مواضع العقد الطرفية التي يتم تقييمها (عندما يكون ترتيب الحركة سلبيًا ) هو O ( bd ⁾ - وهو نفس حجم بحث minimax البسيط. إذا كان ترتيب الحركة للبحث مثاليًا (أي يتم البحث دائمًا عن أفضل الحركات أولًا)، فإن عدد مواضع العقد الطرفية التي يتم تقييمها يكون حوالي O ( b × 1 × b × 1 × ... × b ) للعمق الفردي و O ( b × 1 × b × 1 × ... × 1) للعمق الزوجي.${\displaystyle O\left(b^{\frac {d}{2}}\right)=O\left({\sqrt {b^{d}}}\right)}$.

في الحالة الأخيرة، حيث يكون عدد خطوات البحث زوجيًا، ينخفض ​​عامل التفرع الفعال إلى جذره التربيعي ، أو بعبارة أخرى، يمكن للبحث أن يتعمق ضعف العمق بنفس مقدار الحساب. ^{[ 14 ]} يكمن تفسير b × 1 × b × 1 × ... في أنه يجب دراسة جميع تحركات اللاعب الأول للعثور على أفضلها، ولكن لكل تحرك، لا يلزم سوى أفضل تحرك للاعب الثاني لدحض جميع تحركات اللاعب الأول باستثناء التحرك الأول (والأفضل) - يضمن خوارزمية ألفا-بيتا عدم الحاجة إلى النظر في أي تحركات أخرى للاعب الثاني. عندما تُدرس العقد بترتيب عشوائي (أي أن الخوارزمية تُجري عملية عشوائية)، يكون العدد المتوقع للعقد التي يتم تقييمها في الأشجار المنتظمة ذات القيم الثنائية للأوراق، تقاربًا، هو${\displaystyle \Theta \left(\left({\frac {b-1+{\sqrt {b^{2}+14b+1}}}{4}}\right)^{d}\right)}$ [ ^{12 ]​}

بالنسبة للأشجار نفسها، عندما تُسند القيم إلى أوراق الشجر بشكل مستقل عن بعضها البعض، ولنفترض أن الصفر والواحد لهما نفس الاحتمالية، فإن العدد المتوقع للعقد التي يتم تقييمها هو${\displaystyle \Theta \left(\left(b/2\right)^{d}\right)}$وهو أصغر بكثير من العمل الذي تقوم به الخوارزمية العشوائية المذكورة أعلاه، وهو الأمثل مرة أخرى لمثل هذه الأشجار العشوائية. ^{[ 10 ]} عندما يتم اختيار قيم الأوراق بشكل مستقل عن بعضها البعض ولكن من${\displaystyle [0,1]}$إذا تم تحديد الفاصل الزمني بشكل عشوائي منتظم، فإن العدد المتوقع للعقد التي يتم تقييمها يزداد إلى${\displaystyle \Theta \left(b^{d/\log(d)}\right)}$في${\displaystyle d\to \infty }$الحد ^{[ 11 ]} ، وهو الأمثل مرة أخرى لهذا النوع من الأشجار العشوائية. لاحظ أن العمل الفعلي للقيم "الصغيرة" لـ${\displaystyle d}$يُفضل تقريبها باستخدام${\displaystyle 0.925d^{0.747}}$[ ^{11 ] [ 10 ]​}

يقوم برنامج شطرنج يبحث في أربع نقلات بمتوسط ​​36 فرعًا لكل عقدة بتقييم أكثر من مليون عقدة طرفية. من شأن عملية تقليم ألفا-بيتا المثلى أن تزيل جميع العقد الطرفية باستثناء حوالي 2000 عقدة، أي بنسبة تخفيض قدرها 99.8%. ^{[ 13 ]}

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

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

الشفرة الزائفة لخوارزمية minimax المحدودة العمق مع تقليم ألفا-بيتا هي كما يلي: ^{[ 15 ]}

دالة alphabeta(node, depth, α, β, maximizingPlayer) تقوم بما يلي: إذا كان العمق يساوي صفرًا أو كانت العقدة طرفية، فإنها تُرجع القيمة التقريبية للعقدة. إذا كانت العقدة maximizingPlayer، فإن القيمة تُصبح -∞ . لكل ابن من أبناء العقدة ، تُحسب القيمة القصوى باستخدام alphabeta(child, depth - 1, α, β, FALSE). إذا كانت القيمة أكبر من أو تساوي β، فإنها تتوقف. (* β cutoff *) α := max(α, value) أعد القيمة وإلا القيمة := +∞ لكل فرع من العقدة، قم بما يلي : القيمة := الحد الأدنى (القيمة، ألفا بيتا (الفرع، العمق - 1، α، β، صحيح)) إذا كانت القيمة ≤ α ، فتوقف (* حد القطع α *) β := min(β, value) القيمة المُعادة

(* استدعاء أولي *) alphabeta(origin, depth, − ∞ , + ∞ , TRUE)

يمكن تصنيف تطبيقات تقليم ألفا-بيتا غالبًا إلى نوعين: "التقليم المرن" و"التقليم الصارم". يوضح الكود الزائف النوع "التقليم المرن". في هذا النوع، قد تُرجع دالة ألفا-بيتا قيمًا (v) تتجاوز حدود α و β المحددة بواسطة وسيطات استدعاء الدالة (v < α أو v > β). في المقابل، يقتصر التقليم الصارم على القيمة المُرجعة ضمن النطاق المُتضمن لـ α و β.

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

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

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

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

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

• راسل، ستيوارت جيه .؛ نورفيج، بيتر. (2021). الذكاء الاصطناعي: منهج حديث (  الطبعة الرابعة). هوبوكين: بيرسون. ISBN 9780134610993. إل سي سي إن 20190474 . 
• هاينمان، جورج ت.؛ بوليس، غاري؛ سيلكو، ستانلي (2008). "7. البحث عن المسار في الذكاء الاصطناعي". الخوارزميات باختصار . دار نشر أورايلي . الصفحات 217-223 . ISBN  978-0-596-51624-6.
• بيرل، جوديا (1984). الاستدلالات: استراتيجيات بحث ذكية لحل مشكلات الحاسوب . أديسون-ويسلي. ISBN 978-0-201-05594-8. OCLC 1035596197 . 
• فيشبورن، جون ب. (1984). "الملحق أ: بعض التحسينات على بحث α-β". تحليل تسريع الخوارزميات الموزعة (مراجعة لأطروحة دكتوراه عام 1981) . مطبعة يو إم آي للأبحاث. الصفحات 107-111 . ISBN  0-8357-1527-2.