בתחילה, נקבעים משתנים אלו להיות בעלי ערכי קיצון שרירותיים - אלפא למינוס אינסוף, וביתא לפלוס אינסוף. ערכים תחיליים אלו, מייצגים את המצב הגרוע ביותר מבחינתו של כל שחקן - לשחקן הממקסם מובטחת תוצאה גרועה ביותר (מינוס אינסוף), ולשחקן הממזער גם כן תוצאה גרועה ביותר לפי השקפתו (פלוס אינסוף). עם התקדמות החיפוש, הולך ומצטמצם המרחק בין אלפא לביתא. כאשר ביתא מקבלת ערך נמוך מאלפא, פירושו של דבר כי העמדה הנוכחית אינה תוצאה של משחק מושלם על ידי שני השחקנים (ועל-כן, לא תשוחק על ידי אחד מהם, שיכול לשפר תוך שהוא משחק באופן מושלם), ואין צורך להעמיק חקר בתת-העץ הנוכחי.
וריאנטים.
קיימם וריאנטים שונים לאלגוריתם הגיזום הקלאסי שמוצג בערך זה.
ישנם וריאנטים שקולים לחלוטין למינימקס - כדוגמת אלגוריתם ה-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) = formula_1.
במקרה זה, גורם הסיעוף יהיה שורש של גורם הסיעוף המקורי, ולמעשה יאפשר לבחון פי כמה יותר מהלכים באותו זמן חישוב.
כמובן שברוב המקרים איננו מתייצבים מול המקרה הפתולוגי, ולא מול המקרה האופטימלי. לרוב מספק האלגוריתם שיפור ממוצע בטווח הנ"ל. על-מנת לנסות להבטיח כי, בתוחלת, אנו מתמודדים עם המקרה הממוצע, ניתן לבחור את הקודקוד הבן הבא באופן אקראי מתוך כל קודקודי הבנים שטרם נסרקו. כמובן שגם שיטה זו אינה משפרת את המקרה הגרוע ביותר, אך עשויה לשפר את תוחלת המקרה הגרוע ביותר (amortised).
אחת משיטות האופטימיזציה של תוכנות שונות העושות שימוש בחיפוש א"ב, היא יצירת מנגנון בחירת מהלכים חכם. מנגנון זה מנסה לחזות מה הם המהלכים ה"מעניינים" על לוח המשחק, ולבחון אותם ראשונים. זוהי היוריסטיקה שלא מובטח כי תסייע כלל, אך לעיתים רבות היא מסייעת בגיזום מהיר של העץ. כך למשל, תוכנת שח תנסה לבחון תחילה מהלכים של הכאת חייל יריב, או מהלכים המציבים את המלך היריב בשח. מהלכים אלו נחשבים "מעניינים" בעיני התכנה, וייתכן כי הם מגלמים בחובם פוטנציאל לערך מיטבי בעיני הצד המחפש. אם כן, הרי שהדבר יסייע מאוד בהליך הגיזום.
Hewlett-Packard
Hewlett Packard
הרדמה אפידורלית
תעלת הלידה
חדר שינה בארל
חדר שינה בארל (בצרפתית: La Chambre à Arles, בהולנדית: Slaapkamer te Arles) הוא שמן של שלוש גרסאות של אותו ציור שמן על בד מעשה ידי האמן ההולנדי הפוסט אימפרסיוניסטי וינסנט ואן גוך.
ואן גוך קרא ליצירה "חדר השינה" (בצרפתית: La Chambre à coucher).
תיאור היצירה.
היצירה מתארת את חדרו של ואן גוך ברחוב לאמארטין מס' 2 (הבית הצהוב) בארל שבצרפת.
הדלת בימין היצירה מובילה לגרם המדרגות המוביל אל הקומה השנייה. הדלת משמאל היצירה מובילה אל חדר האורחים שבו נהג ללון האמן פול גוגן.
החלון במרכז היצירה פונה לעבר רחוב לאמארטין.
צורת החדר טרפזואידית בלתי רגילה, והמבט של הצופה פונה לעבר הפינה הימנית הרחוקה של החדר, ובהתאם כל החדר מוטה לעבר פינה זו. צורת החדר לא רגולרית בכך שהפינה השמאלית התחתונה של החדר מתוארת בזווית קהה, בעוד שהפינה הימנית המקבילה לה מתוארת בזווית חדה.
בימין התמונה מתוארת מיטתו של האמן ועליה שמיכה אדומה. בשמאל התמונה כיסא אחד ובמרכז התמונה, בסמוך לקיר, שולחן לילה וכיסא נוסף.
הגרסה הראשונה.