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

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

אופן הגיזום הוא פשוט: במהלך החיפוש לעומק ניתן לזנוח פתרונות חלקיים ברגע שברור שהם גרועים מפתרונות שכבר ראינו.

האלגוריתם נמצא בשימוש נרחב בתחום הבינה המלאכותית, לדוגמה בתוכנות משחק (שחמט, דמקה, איקס עיגול ועוד).

עצי משחק ועצי מינימקס

נתבונן על קבוצת המשחקים המקיימים את התכונות הבאות:

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

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

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

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

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

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

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

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

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

עבור משחקים אחרים כמו שחמט וגו, עץ המשחק המתאר אותם הוא ענף ביותר, ונמצא הרבה מעבר לאופק החישוב המעשי של חומרה קיימת כלשהי. לדוגמה, עץ המשחק של שח מכיל מעל 10⁴³ הילוכים אפשריים (לפי אומדנים שמרניים), ועץ המשחק של גו מכיל הרבה יותר הילוכים אפשריים (10³⁶⁰).

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

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

גיזום

גיזום העץ מבוצע באופן הבא:
א. גיזום אלפא (Alpha cut)

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

ב. גיזום ביתא (Beta cut)

אם הקודקוד הוא קודקוד של שחקן ה'מין' - ננקוט בפעולה ההפוכה.

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

וריאנטים

קיימם וריאנטים שונים לאלגוריתם הגיזום הקלאסי שמוצג בערך זה.

ישנם וריאנטים שקולים לחלוטין למינימקס - כדוגמת אלגוריתם ה-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^d קודקודים. בדיוק מה שהיינו מקבלים בחיפוש מינמקס רגיל. אם כן, החסם העליון למקרה הגרוע ביותר זהה לזה של חיפוש מינמקס.
לעומת זאת, במקרה הטוב ביותר, זה שבו מקס נתקל בערך הגבוה ביותר בתת-העץ הראשון (ומין בנמוך, באופן דואלי), הרי שמתוך b בנים שיש לקודקוד מסוים, עלינו לבחון רק את תת-העץ של הקודקוד הראשון, ולגזום את כל b-1 הענפים הנותרים. במקרה זה, מספר העלים שיש לבחון הוא O(b*1*b*1*...*1) = $O(b^{d/2})=O({\sqrt {b^{d}}})$ . במקרה זה, גורם הסיעוף יהיה שורש של גורם הסיעוף המקורי, ולמעשה יאפשר לבחון פי כמה יותר מהלכים באותו זמן חישוב.

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

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

קישורים חיצוניים

גיזום אלפא-ביתא, באתר MathWorld (באנגלית)