גיזום אלפא-ביתא

גיזום אלפא-ביתא היא שיטת אופטימיזציה עבור עצי-חיפוש מסוג מינימקס. מטרת השיטה לצמצם את מספר תתי העצים עליהם יש להלך בעת הערכת מהלך אפשרי בעץ מינימקס. שמה של השיטה ניתן לה כאנלוגיה לגיזום עצים. אלגוריתם הגיזום הוא אלגוריתם אופטימיזציה קלאסי, במובן שאינו משנה את התוצאה שהיה מחזיר האלגוריתם המקורי (חיפוש מינימקס), אלא רק מחזיר אותה תוצאה בזמן קצר יותר. במקרה הגרוע ביותר, האלגוריתם עובד בסיבוכיות זהה לזו של חיפוש מינימקס רגיל. עם זאת, באופן פרקטי ותוך שימוש בשיטות משלימות, מספק האלגוריתם את התוצאה המקורית של מינימקס, בזמן קצר בהרבה.
אופן הגיזום הוא פשוט: במהלך החיפוש לעומק ניתן לזנוח פתרונות חלקיים ברגע שברור שהם גרועים מפתרונות שכבר ראינו.
האלגוריתם עצמו נמצא בשימוש נרחב בתוכנות משחק רבות (שחמט, דמקה, איקס עיגול ועוד), ובתחום של בינה מלאכותית.

אופק חישוב ומוטיבציה מעשית

ישנם משחקי שני שחקנים רבים, הנופלים תחת הקטגוריה של משחק פתור. משחק פתור, הוא משחק שניתן לנבא את תוצאתו בהינתן משחק מושלם של שני היריבים. איקס עיגול, ארבע בשורה, נים, דמקה ועוד משחקים רבים, הם משחקים פתורים. פירושו של דבר שניתן ליצור תוכנה המסוגלת להעריך בדייקנות כל מהלך אפשרי במשחקים אלו. עבור משחק הדמקה, למשל, קיימת תוכנה בשם צ'ינוק, המסוגלת להעריך את כל המהלכים האפשריים מכל לוח דמקה חוקי נתון. עובדה זו הופכת תוכנות כגון צ'ינוק לבלתי מנוצחות. באופן דומה, ישנן תוכנות בלתי מנוצחות, המסוגלות לרוץ על המחשבים הביתיים הפשוטים ביותר, המשחקות איקס עיגול נגד שחקן אנושי.
עם זאת, ישנם משחקים רבים אשר טרם נפתרו. שחמט וגו הן שתי דוגמאות בולטות למשחקים מסוג זה. פירוש הדבר כי גם תוך שימוש בחומרה הטובה ביותר הקיימת כיום, אין תכנת שחמט שלא ניתן (תאורטית) להביסה. גם מחשבי שחמט חזקים ביותר כדוגמת כחול עמוק, הם תאורטית ברי הבסה על ידי שחקן אנושי מעולה, או על ידי מערכת מחשב אחרת.
עבור עץ המשחק של איקס עיגול קיימות כמה עשרות אלפי בחירות מהלכים אפשריות, למן הפתיחה ועד הסיום. עבור משחק מורכב יותר כמו ארבע בשורה, מדובר בסדר גודל של 10¹³ הילוכים אפשריים; עבור משחק הדמקה מדובר כבר בסדר גודל של 10³¹ עצי החלטה אפשריים.
עבור משחקים אחרים כמו שחמט וגו, עץ המשחק המתאר אותם הוא ענף ביותר, ונמצא הרבה מעבר לאופק החישוב המעשי של חומרה קיימת כלשהי. לדוגמה, עץ המשחק של שח מכיל מעל 10⁴³ הילוכים אפשריים (לפי אומדנים שמרניים), ועץ המשחק של גו מכיל הרבה יותר הילוכים אפשריים (10³⁶⁰).
כאן מגיע התמריץ המעשי לשימוש בגיזום אלפא-ביתא, ובשיטות ייעול נוספות. אנו מעוניינים "למצות" את שלל ההילוכים האפשריים על עץ משחק, מבלי להצטרך לבצע כל הילוך והילוך בפועל. הרעיון בשימוש בחיפוש אלפא-ביתא, הוא לבצע גיזום (חריף ככל הניתן) של ענפי העץ, מבלי לפגוע באיכות התוצאה המוחזרת. למעשה, גם תוך שימוש בגיזום אלפא-ביתא, לא נצליח בדרך-כלל להעריך כל מהלך בצורה דטרמיניסטית ונאלץ לבצע הערכה של מהלכי ביניים הנמצאים בקצה אופק החישוב שלנו. הערכה זו תבוטא בניקוד המביע את חוזקה המשוער של כל עמדה ועמדה.
ברור כי כל פונקציית הערכה לא דטרמיניסטית, מספקת רק ניקוד משוער של הקודקוד אותו היא מעריכה. אם לא כן, אזי היינו יכולים להעריך כל קודקוד וקודקוד למין תחילת המשחק, ללא הצורך בשימוש בגיזום א"ב, או בכל שיטת חיפוש אחרת. כל שהיה עלינו לעשות, הוא להזין את קודקוד הפתיחה של המשחק לפונקציה, ולקבל תוצאה עליו. מאחר שפונקציות הערכה, בסך הכל מספקות "ניחוש מושכל" (בדרך כלל, מושכל מאוד), נשארת המוטיבציה שבשימוש בחיפוש בכלל וגיזום א"ב בפרט. מקובל להניח, שככל שאנו רואים רחוק יותר באופק המשחק, כך פונקציית ההערכה שלנו מספקת מידע מדויק יותר.

ואריאנטים

קיימם ואריאנטים שונים לאלגוריתם הגיזום הקלאסי שמוצג בערך זה.
ישנם ואריאנטים שקולים לחלוטין למינימקס - כדוגמת אלגוריתם ה-NegaMax המהווה כתיבה יותר קומפקטית ואסתטית לאלגוריתם הגיזום אלפא-ביתא. שניהם יחזירו בדיוק את אותה תוצאה, באותו זמן חישוב.
ישנם ואריאנטים מקבילים לגיזום א"ב, במובן שיחזירו את אותה תוצאה בדיוק, אך לעיתים מהר יותר, ולעיתים לאט יותר - כדוגמת אלגוריתם ה-NegaScout. אלגוריתם ה-Negascout, מתבסס על סידור מהלכים יעיל (מהלכים מועילים קודם). על-מנת לגלות מראש סידור כזה, הוא משקיע זמן לא מבוטל בסידור המהלכים. בדרך כלל הליך זה יבוצע בשיטה של "השלכת חכה". האלגוריתם מבצע חיפוש א"ב רגיל, לעומק רדוד יחסית, על-מנת לקבל איזושהי אינדיקציה ראשונית לטיב המהלכים. לפי אינדיקציה זו, הוא מסדר את המהלכים בתור עדיפויות, מן המהלך שנראה מיטבי ביותר, ועוד לזה שנראה גרוע ביותר. 
ייתכן כי האינדיקציות הראשוניות אכן היו נכונות, ומהלכים שנראו מבטיחים בתחילה אכן התבררו ככאלה. במקרה כזה יבוצע גיזום חריף ביותר בעץ, והפסדנו בשכרנו - הזמן שהושקע בסידור המהלכים הוא זניח לעומת הזמן שנחסך על ידי הגיזום החריף, וסך הכל חסכנו זמן.
לעומת זאת, ייתכן כי האינדיקציות שקיבלנו בתחילה, היו מטעות. למעשה חייבים להיות מקרים בהם כך הדבר, שאם לא כן - היינו תמיד מסתפקים בחיפוש האינדיקטיבי בלבד, ולא משתמשים בחיפוש העמוק והיקר יותר. כאשר זה המקרה אזי כי הפסדנו זמן. השקענו זמן לא מבוטל בסידור המהלכים, ולבסוף נאלצנו גם לסרוק את רוב או כל המהלכים עד לעומק מרבי.
באופן פרקטי, אלגוריתם ה-Negascout בדרך-כלל יחזיר תוצאה מהר יותר מגיזום א"ב קלאסי, ונמצא בשימוש רב במשחקי מחשב.
ואריאנט מקביל נוסף לגיזום הקלאסי, הוא חיפוש *SSS, שאף על-פי שהוא בדרך-כלל מהיר מ-Negascout, נחשב בזבזני במונחי זיכרון ותחזוקה ועל-כן לא נמצא בשימוש רחב.

באותו אופן, ישנו גם אלגוריתם ה-MTD-f שגם כן נזנח מסיבות טכניות כאלו ואחרות.
נוסף על כל אלו, קיימם גם ואריאנטים שמשנים את האלגוריתם באופן שבו התוצאה המוחזרת תהיה שונה מזו שמוחזרת על ידי חיפוש א"ב.

נפוצים במיוחד בהקשר זה ואריאנטים העושים שימוש בהיוריסטיקת מהלך ריק (Null move heuristics). בבסיסה של היוריסטיקה זו, עומדת ההנחה כי האפשרות לבצע מהלך תורמת בהכרח לצד המשחק. ישנם משחקים בהם היוריסטיקה זו היא תמיד נכונה - כדוגמת איקס עיגול. במשחקים אלו הוספת תור לשחקן, תמיד משפרת את מצבו, ולעולם לא גורעת ממנו. לעומת זאת, ישנם משחקים (כמו שח ודמקה), בהם תיתכנה עמדות שכל מהלך היוצא מהן, גורע מן השחקן המשחק. למשל, ייתכן סידור כלים מסוים, בו המלך הלבן אינו מאוים, אך כל תזוזה של לבן תכניס את מלכו לשח. 

בכל אופן, המשתמשים בהיוריסטיקה זו - מקבלים על עצמם את ההנחה כי תזוזה תמיד משפרת את מצבו של הצד המשחק.

בהינתן הנחה זו, מבצע האלגוריתם חיפוש רדוד, אינדיקטיבי, תוך שהוא "מוותר" על תור השחקן הנוכחי. האלגוריתם מחפש כאילו זה כבר תורו של השחקן היריב, והשחקן הנוכחי "הפסיד" תור. לפני ההנחה, ויתור על תור, מגלם בחובו הפסד.

החיפוש כאמור, מבוצע מנקודת השקפתו של השחקן היריב, 'מין'. במידה ובמהלך החיפוש האינדיקטיבי, אנו נתקלים בענף ש'מין' ביקש לגזום (חיתוך ביתא), פירושו כי ענף זה הוא גרוע יותר ליריבנו, מענף שהוא נתקל בו קודם. מההנחה, אנו מסיקים כי גם בחיפוש רגיל היינו גוזמים ענף זה, שכן תחת ההנחה מובטח לנו כי בחיפוש רגיל המצב רק משתפר מבחינתנו (ולכן בהיות המשחק סכום-אפס, גרוע יותר ליריבנו). ענף שיריבנו ביקש לגזום לאחר שאנחנו ויתרנו על תור, ודאי ייגזם אם לא היינו מוותרים על תור.

באופן זה, אנו גוזמים ענפים לאחר חיפוש רדוד ביותר. לאחר שלב גיזום ראשוני זה, ירוץ האלגוריתם עד לעומק מלא, על כל שאר העץ שטרם נגזם.
לעיתים משיגה היוריסטיקה זו תוצאה טובה ומהירה יותר מזו שהייתה מושגת באופן קלאסי. עם זאת, ישנן פעמים בהן חיפוש זה פשוט משיג תוצאה שגויה. ייתכנו מצבים בהם חיפוש זה, ינקד עמדה מנצחת כמפסידה, ולהפך. על-כן, בעת שימוש בשיטה זו, יש להשתמש בכמה כללי זהירות נוספים, בהתאם למשחק בו מתעסקים.

פסאודו קוד

בעת הקריאה הראשונית לשיטה, יש להשתמש בערכי הקיצון עבור α (נמוך ביותר) ו-β (גבוה ביותר).
עבור קודקוד v בעץ, פסאודו קוד של אלגוריתם הגיזום מעל חיפוש מינמקס קלאסי נראה כך:
Eval(v, α, β) {
   if (v is a terminal node)
      return (the heuristic value of node) //using some STATIC (that is, non-iterative) helper method
   if (v is a min-node) {
      current:=β;
      for (each son of v, u) {
         val:=Eval(u, α, current);
         current:=minimum(val, current);
         if (current ≤ α)
            return α;
      }
      return current;
   }
   else { /**v is a max-node*/
      /**כנ"ל דואלי - להחליף אלפא בביתא, ומינימום במקסימום*/
   }}
לרוב, יעשה שימוש בגיזום א"ב, מעל אלגוריתם ה-Negamax השקול לחלוטין לאלגוריתם המינימקס, אך אסתטי וקל יותר לתכנות ממנו. בנוסף, משיקולים מעשיים, יבוצע בדרך-כלל החיפוש עד לעומק מקסימלי כלשהו בעץ החיפוש.

במקרה זה, יראה הקוד כך כאשר color מאותחל כ1:
 negamaxEval(node, depth, α, β, color) {
    if node is a terminal node or depth = 0
       return color * the heuristic value of node
    foreach child of node {
       α := max(α, -negamaxEval(child, depth-1, -β, -α, -color))
       //the following if statement constitutes alpha-beta pruning
       if α≥β
          return α
    }
    return α
 }

סיבוכיות

כאמור, אלגוריתם האלפא-ביתא, נעזר במידע קודם (השמור במשתני העזר α, β) על-מנת להחליט האם יש לרוץ על תת-עץ מסוים או לא.
בהינתן סידור קודקודים פתולוגי, לא נוכל להיעזר ב-α, β, וניאלץ לסרוק את כל העץ. סידור קודקודים פתולוגי הוא סידור כזה שבו מקס נתקל בקודקודים בעלי ערך הולך וגדל (אלפא גדלה אחרי כל קודקוד); ומין נתקל בקודקודים בעלי ערך הולך וקטן (ביתא קטנה).

עבור עץ משחק עם גורם-הסתעפות קבוע, b, ועומק חיפוש d, פירושו כי עלינו לסרוק (O(b*b*...*b) = O(bᵈ קודקודים. בדיוק מה שהיינו מקבלים בחיפוש מינמקס רגיל. אם כן, החסם העליון למקרה הגרוע ביותר זהה לזה של חיפוש מינמקס.

לעומת זאת, במקרה הטוב ביותר, זה שבו מקס נתקל בערך הגבוה ביותר בתת-העץ הראשון (ומין בנמוך, באופן דואלי), הרי שמתוך b בנים שיש לקודקוד מסוים, עלינו לבחון רק את תת-העץ של הקודקוד הראשון, ולגזום את כל b-1 הענפים הנותרים.
במקרה זה, מספר העלים שיש לבחון הוא O(b*1*b*1*...*1) = . 
במקרה זה, גורם הסיעוף יהיה שורש של גורם הסיעוף המקורי, ולמעשה יאפשר לבחון פי כמה יותר מהלכים באותו זמן חישוב.
כמובן שברוב המקרים איננו מתייצבים מול המקרה הפתולוגי, ולא מול המקרה האופטימלי. לרוב מספק האלגוריתם שיפור ממוצע בטווח הנ"ל. על-מנת לנסות להבטיח כי, בתוחלת, אנו מתמודדים עם המקרה הממוצע, ניתן לבחור את הקודקוד הבן הבא באופן אקראי מתוך כל קודקודי הבנים שטרם נסרקו. כמובן שגם שיטה זו אינה משפרת את המקרה הגרוע ביותר, אך עשויה לשפר את תוחלת המקרה הגרוע ביותר (amortised).
אחת משיטות האופטימיזציה של תוכנות שונות העושות שימוש בחיפוש א"ב, היא יצירת מנגנון בחירת מהלכים חכם. מנגנון זה מנסה לחזות מה הם המהלכים ה"מעניינים" על לוח המשחק, ולבחון אותם ראשונים. זוהי היוריסטיקה שלא מובטח כי תסייע כלל, אך לעיתים רבות היא מסייעת בגיזום מהיר של העץ. כך למשל, תכנת שח תנסה לבחון תחילה מהלכים של הכאת חייל יריב, או מהלכים המציבים את המלך היריב בשח. מהלכים אלו נחשבים "מעניינים" בעיני התכנה, וייתכן כי הם מגלמים בחובם פוטנציאל לערך מיטבי בעיני הצד המחפש. אם כן, הרי שהדבר יסייע מאוד בהליך הגיזום.