גיזום אלפא-ביתא (Alpha–Beta Pruning)
הגדרה
גיזום אלפא-ביתא הוא שיטת אופטימיזציה לאלגוריתם המינימקס (Minimax) בתוכנות למשחקים של שני שחקנים, כמו שחמט: היא מדלגת על ענפים בעץ המשחק שאינם יכולים להשפיע על ההחלטה הסופית, ומגיעה לאותה תוצאה בדיוק בהרבה פחות בדיקות.
💡 דוגמה
תארו לעצמכם שאתם משחקים דמקה ובוחרים בין שני מהלכים. בדקתם את מהלך א' עד הסוף, ומצאתם שהוא מבטיח לכם לפחות תיקו. עכשיו אתם בודקים את מהלך ב', ומגלים כבר בתשובה הראשונה שבדקתם שליריב יש תשובה שמביאה אתכם להפסד. אין צורך לבדוק את שאר התשובות האפשריות של היריב למהלך ב' — כבר ברור שהוא גרוע ממהלך א', ושלא תבחרו בו. זה בדיוק מה שגיזום אלפא-ביתא עושה בשביל המחשב: הוא מדלג על ענפים שכבר ידוע שלא ישפיעו על ההחלטה הסופית.
הבעיה: למה אי-אפשר פשוט לבדוק את כל המהלכים
מינימקס (Minimax) הוא אלגוריתם רקורסיבי לבחירת המהלך הבא במשחק של שני שחקנים, כמו שחמט או דמקה: כל שחקן מניח שהיריב ישחק את המהלך הגרוע ביותר עבורו, ובוחר בהתאם את המהלך שממקסם את הערך המינימלי שהיריב יכול להשאיר לו. הבעיה המעשית היא שמספר הקודקודים שצריך לבדוק בעץ המשחק צומח באופן מעריכי עם מספר המהלכים קדימה שבודקים ("פליז", Plies). לכן אי-אפשר בפועל לנתח במלואם משחקים כמו שחמט באמצעות אלגוריתם המינימקס הטהור. תוכנת שחמט מעריכה עמדות ביניים באמצעות פונקציית הערכה היוריסטית, בעומק חיפוש מוגבל, ולא על ידי סריקה מלאה של עץ המשחק עד העמדות הסופיות של ניצחון והפסד.
הפתרון: אותה תוצאה בדיוק, הרבה פחות בדיקות
גיזום אלפא-ביתא הוא אלגוריתם חיפוש בעץ שמטרתו להקטין את מספר הקודקודים שאלגוריתם המינימקס נדרש להעריך בעץ החיפוש שלו. כשמפעילים אותו על עץ מינימקס רגיל, הוא מחזיר את אותו מהלך שמינימקס היה מחזיר, אבל גוזם ענפים שאינם יכולים בשום אופן להשפיע על ההחלטה הסופית. העיקרון: האלגוריתם עוקב אחרי שני חסמים בזמן שהוא סורק את העץ — "אלפא", הציון הנמוך ביותר שכבר מובטח לשחקן הממקסם במקום אחר בעץ, ו"ביתא", הציון הגבוה ביותר שכבר מובטח לשחקן הממזער. מרגע שביתא יורד מתחת לאלפא (ובמימושים רבים, כבר כשהוא שווה לו), ברור שאחד השחקנים לא יבחר להגיע לענף הזה, כי יש לו חלופה טובה יותר. שאר הענף נחתך בלי להיבדק, כולל כל תת-הענפים שתחתיו.
כמה זה בדיוק חוסך: מיליון קודקודים מול כ-2,000
דוגמה מספרית מקובלת מעולם השחמט: תוכנת שחמט שמחפשת בעומק ארבעה "פליז" (חצאי מהלכים, כלומר שני מהלכים לכל צד), עם 36 ענפים בממוצע לכל קודקוד, מעריכה יותר ממיליון קודקודי עלה כשהיא בודקת כל אפשרות בלי גיזום. במקרה האופטימלי, כשהמהלכים הטובים נבדקים תמיד ראשונים, גיזום אלפא-ביתא היה מבטל את כל קודקודי העלה מלבד כ-2,000 מהם: ירידה של 99.8%, בלי לשנות כלל את המהלך שהאלגוריתם בוחר בסוף. בפועל סדר המהלכים אינו מושלם והחיסכון קטן יותר, אבל עדיין עצום. בזכות החיסכון הזה יכלו תוכנות שחמט לחפש עמוק הרבה יותר באותו זמן חישוב: את הזמן שנחסך אפשר להשקיע בהסתכלות של צעד או שניים נוספים קדימה, ולא רק לסיים את אותו חיפוש מהר יותר.
סיפור הגילוי: מג'ון מקארתי ועד גילויים עצמאיים נוספים
לפי התיעוד ההיסטורי, ג'ון מקארתי המציא את עקרון חיפוש אלפא-ביתא במהלך סדנת דרטמות' (Dartmouth Workshop). שם פגש את אלכס ברנשטיין מ-IBM, שכתב אז תוכנת שחמט, והמליץ לו על השיטה, אך ברנשטיין לא התרשם ולא אימץ אותה. אלן ניואל והרברט סיימון כתבו ב-1958 שהרעיון הומצא ככל הנראה כמה פעמים, באופן עצמאי. לארתור סמואל הייתה גרסה מוקדמת בסימולטור הדמקה שלו; קבוצת חוקרים אחרת בארצות הברית (ובהם טימותי הארט, מייקל לוין ודניאל אדוארדס) הגיעה לרעיון בנפרד; אלכסנדר ברודנו בברית המועצות הגיע אליו באופן עצמאי לחלוטין ופרסם אותו ב-1963; ובהמשך, ב-1975, חידדו דונלד קנות' ורונלד מור את השיטה וניתחו אותה מתמטית. יהודה פרל הוכיח שהאלגוריתם אופטימלי (מבחינת זמן הריצה הצפוי) בעצים עם ערכי עלה אקראיים, ומייקל סאקס ואבי ויגדרסון הראו ב-1986 שגם הגרסה האקראית שלו אופטימלית.
בשימוש בפועל: מדיפ בלו ועד מנועי שחמט מודרניים
דיפ בלו (Deep Blue), מחשב השחמט של IBM שניצח את אלוף העולם גארי קספרוב ב-1997, השתמש בשבבי VLSI מותאמים אישית כדי להריץ במקביל את אלגוריתם החיפוש אלפא-ביתא. כלומר, גיזום אלפא-ביתא היה חלק מהחומרה הייעודית שעליה נשענה עוצמתו, ולא רק רעיון שמיושם בתוכנה. כל שבב שחמט ייעודי במכונה הכיל, לפי התיעוד, ארבעה חלקים — מחולל מהלכים, מחסנית מהלכים חכמה, פונקציית הערכה, ובקר חיפוש — שעבדו יחד כדי להריץ את החיפוש עם הגיזום בחומרה עצמה. גיזום אלפא-ביתא ממשיך לשמש כאבן יסוד במנועי שחמט עד היום, ונלמד בקורסי מבוא לבינה מלאכותית כדוגמה מרכזית לשילוב של חיפוש שיטתי עם חיסכון ניכר בזמן חישוב.
השינוי המודרני: מינימקס קלאסי מול חיפוש בהנחיית רשת נוירונים
לפי תוצאות שפרסמה DeepMind ב-2018, AlphaZero — מערכת שלמדה לשחק שחמט מהכללים בלבד, בלי ידע שחמט אנושי שהוזן לה מראש — שיחקה סדרה של 1,000 משחקים מול Stockfish, מנוע שחמט המבוסס על גיזום אלפא-ביתא, וסיימה עם 155 ניצחונות, 6 הפסדים ו-839 תיקו. ההבדל המרכזי בשיטת החיפוש: AlphaZero מחפשת רק כ-80,000 עמדות בשנייה בשחמט, בהשוואה ל-70 מיליון ב-Stockfish, ומקזזת את ההבדל העצום הזה באמצעות הרשת העצבית העמוקה שלה, שמתמקדת באופן סלקטיבי הרבה יותר בהמשך המבטיח ביותר. זו גרסה של חיפוש עץ מונטה קרלו (Monte Carlo Tree Search, MCTS) שהרשת מנחה, במקום סריקה שיטתית של הענפים. לארי קאופמן, ממפתחי מנוע השחמט Komodo, ניבא שהמנוע החזק ביותר בעתיד יהיה ככל הנראה "מנוע היברידי עם רשתות נוירונים וחיפוש אלפא-ביתא רגיל". מהתחזית עולה שגיזום אלפא-ביתא נתפס כ"חיפוש הרגיל", הסטנדרטי, שמולו נמדדות הגישות המבוססות על למידה, ולא כשיטה שנעלמה מהתחום. ואכן, מאז 2020 Stockfish עצמו משלב רשת נוירונים קלה (NNUE) להערכת עמדות, ומ-2023 נשען רק עליה — אבל החיפוש שלו נשאר מבוסס אלפא-ביתא.
📬 הגיליון השבועי של Wiki-AI
פעם בשבוע, ביום ראשון: שלושת הדברים החשובים שקרו בעולם הבינה המלאכותית, בעברית פשוטה, וערכים חדשים באנציקלופדיה. לגיליונות
| מינימקס טהור (בלי גיזום) | מינימקס עם גיזום אלפא-ביתא | חיפוש עץ מונטה קרלו בהנחיית רשת (MCTS, כמו ב-AlphaZero) | |
|---|---|---|---|
| העיקרון | בודק את כל ענפי העץ עד עומק מוגדר, בלי לדלג על אף אחד מהם | מחשב את אותו ערך, אבל מדלג בפועל על ענפים שלא יכולים לשנות את ההחלטה הסופית | דוגם ענפים נבחרים בהנחיית רשת נוירונים שמעריכה אילו מהלכים מבטיחים, ולא עובר שיטתית על העץ |
| מחזיר בהכרח את אותה תוצאה כמינימקס טהור? | כן, לפי הגדרה | כן — מוכח שמחזיר בדיוק את המהלך שמינימקס טהור היה מחזיר | לא מובטח בחיפוש מוגבל; הבחירה נשענת על הערכות של רשת נוירונים שאומנה במשחק עצמי, לא על הוכחה |
| קודקודי עלה שנבדקים (שחמט, עומק של 4 חצאי מהלכים) | יותר ממיליון קודקודי עלה | כ-2,000 במקרה האופטימלי (ירידה של 99.8%); בפועל יותר, לפי סדר בדיקת המהלכים | לא נמדד באותה שיטה — AlphaZero בוחנת כ-80,000 עמדות בשנייה בלבד, לעומת 70 מיליון ב-Stockfish |
| דוגמה מוכרת | הגרסה שמלמדים בקורסי מבוא ל-AI, לפני המעבר לגרסה המשופרת | דיפ בלו, שניצח את גארי קספרוב ב-1997 | AlphaZero, שניצחה את Stockfish 155 פעמים בסדרה של 1,000 משחקים (תוצאות שפורסמו ב-2018) |
שאלות נפוצות ❓
מה ההבדל בין מינימקס לגיזום אלפא-ביתא?
מינימקס טהור בודק כל ענף אפשרי בעץ המשחק; גיזום אלפא-ביתא מחזיר בדיוק את אותה תוצאה, אבל מדלג על ענפים שהוכח שאינם יכולים להשפיע על ההחלטה הסופית.
כמה גיזום אלפא-ביתא חוסך בפועל?
בדוגמה מקובלת של חיפוש בשחמט בעומק ארבעה חצאי מהלכים, מספר קודקודי העלה יורד מיותר ממיליון בחיפוש רגיל לכ-2,000 במקרה האופטימלי (כשהמהלכים הטובים נבדקים ראשונים) — ירידה של 99.8%, בלי לשנות את התוצאה.
האם דיפ בלו השתמש בגיזום אלפא-ביתא?
כן. דיפ בלו, שניצח את גארי קספרוב ב-1997, השתמש בשבבי חומרה מותאמים אישית להרצה מקבילה של אלגוריתם החיפוש אלפא-ביתא.
האם מנועי שחמט מודרניים כמו AlphaZero עדיין משתמשים בגיזום אלפא-ביתא?
AlphaZero עצמה משתמשת בחיפוש עץ מונטה קרלו (MCTS) בהנחיית רשת נוירונים, לא בגיזום אלפא-ביתא — אבל מנועים כמו Stockfish ממשיכים להסתמך עליו, גם אחרי ששילבו רשת נוירונים להערכת עמדות.