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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

עצי משחק ועצי מינמקס[עריכת קוד מקור | עריכה]

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

  1. המשחק הוא משחק לשני שחקנים.
  2. המשחק משוחק בתורות - המהלכים מתבצעים בצורה סדרתית, ולא בו זמנית.
  3. המשחק הוא משחק סכום אפס, היינו, הרווח של האחד הוא הפסדו של האחר.
  4. המשחק מהווה מערכת דטרמיניסטית - המשחק אינו תלוי בגורם אקראי או בלתי-קבוע, ובהינתן אסטרטגיה מסוימת על ידי שני השחקנים, תוצאת המשחק תמיד תהיה זהה.
  5. המשחק הוא משחק מידע מלא - מטרת המשחק והאפשרויות החוקיות בו ברורות לכולם.
  6. המשחק מתקיים בסביבה של מידע מושלם - כל פעולות העבר חשופות לעיני שני הצדדים, ואין מהלכים נסתרים או בלתי-חשופים.

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

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

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

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

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

אופק חישוב ומוטיבציה מעשית[עריכת קוד מקור | עריכה]

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

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

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

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

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

גיזום[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

ואריאנטים[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

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

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

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

פסאודו קוד[עריכת קוד מקור | עריכה]

עבור קודקוד v בעץ, פסאודו קוד של אלגוריתם הגיזום מעל חיפוש מינמקס קלאסי נראה כך:

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

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

 negamaxEval(node, depth, α, β, color) {
 if node is a terminal node or depth = 0
 return color * the heuristic value of node
 else
 foreach child of node {
 α := max(α, -negamaxEval(child, depth-1, -β, -α, -color))
 //the following if statement constitutes alpha-beta pruning
 if α≥β
 return α
 }//foreach
 return α
 }//negamaxEval

בעת הקריאה הראשונית לשיטה, יש להשתמש בערכי הקיצון עבור α (נמוך ביותר) ו-β (גבוה ביותר). כך למשל במשחק בו התוצאה הטובה ביותר האפשרית היא 100, יש לקרוא לשיטה באופן הבא:

 negamaxEval(nodeToEvaluate, maxSearchDepth, -100, +100, 1)

סיבוכיות[עריכת קוד מקור | עריכה]

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

בהינתן סידור קודקודים פתולוגי, לא נוכל להיעזר ב-α, β, וניאלץ לסרוק את כל העץ. סידור קודקודים פתולוגי הוא סידור כזה שבו מקס ניתקל בקודקודים בעלי ערך הולך וגדל (אלפא גדלה אחרי כל קודקוד); ומין ניתקל בקודקודים בעלי ערך הולך וקטן (ביתא קטנה).
עבור עץ משחק עם גורם-הסתעפות קבוע, b, ועומק חיפוש d, פירושו כי עלינו לסרוק O(b*b*...*b) = O(bd) קודקודים. בדיוק מה שהיינו מקבלים בחיפוש מינמקס רגיל. אם כן, החסם העליון למקרה הגרוע ביותר זהה לזה של חיפוש מינמקס.
לעומת זאת, במקרה הטוב ביותר, זה שבו מקס נתקל בערך הגבוה ביותר בתת-העץ הראשון (ומין בנמוך, באופן דואלי), הרי שמתוך b בנים שיש לקודקוד מסוים, עלינו לבחון רק את תת-העץ של הקודקוד הראשון, ולגזום את כל b-1 הענפים הנותרים. במקרה זה, מספר העלים שיש לבחון הוא O(b*1*b*1*...*1) = O(b^{d/2}) = O(\sqrt{b^d}). במקרה זה, גורם הסיעוף יהיה שורש של גורם הסיעוף המקורי, ולמעשה יאפשר לבחון פי כמה יותר מהלכים באותו זמן חישוב.

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

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