אלגוריתם גיזום אלפא-בטא (\\(\alpha\\)-\\(\beta\\) Pruning) ותרגילי עצי משחק
לפצח את הקסם של אלפא-בטא בלי להיבהל מהמשתנים
שלום חברים! בפרק הקודם הכרנו את עצי המינימקס, וראינו איך סוכן רציונלי יכול לחשב את המהלך המושלם מול יריב אינטליגנטי. אבל ראינו גם את נקודת התורפה הקטלנית: הפיצוץ הקומבינטורי. סריקת כל ענף וענף עד לעומק $m$ דורשת סריקה של $O(b^m)$ מצבים – מספר הגדול ממספר האטומים ביקום כבר בעומקים בינוניים!
כאן בדיוק מגיעה אחת מפריצות הדרך האלגוריתמיות המבריקות ביותר בתולדות מדעי המחשב: גיזום אלפא-בטא (\(\alpha\)-\(\beta\) Pruning).
הרבה סטודנטים נרתעים במבט ראשון מהמשתנים $\alpha$ ו-$\beta$, כי הם נתפסים כמו שתי מטרות נעות בתוך מחסנית רקורסיבית מבלבלת. אבל האמת היא פשוטה להפליא: מדובר בסך הכל בחלון הזדמנויות של שחקנים רציונליים. ברגע ששחקן גילה חלופה שמבטיחה לו תוצאה מסוימת, אין שום סיבה לבזבז אפילו מילי-שנייה אחת בבחינת מהלכי יריב שמובילים לתוצאה גרועה יותר, כי אף שחקן שפוי לא יאפשר למשחק להתגלגל לשם!
במדריך שלפניכם נפרק את האלגוריתם צעד-אחר-צעד, נבין את האינטואיציה העמוקה בעזרת אנלוגיית חיי היומיום, ננתח מתמטית תרגילי מפתח בכתב יד ונחקור את כל המקרים המיוחדים בסימולציה האינטראקטיבית. בואו נתחיל!
💡 אינטואיציה בגובה העיניים: אנלוגיית המשא ומתן להשכרת דירה
תארו לעצמכם שאתם מחפשים לשכור דירה (אתם שחקן MIN, שרוצה למזער את שכר הדירה החודשי). ביקרתם בבניין הראשון, ובעל הבית חתם אתכם על התחייבות: תוכלו לשכור אצלו דירה מעולה ב-3,000 ש"ח. זוהי תקרת הביטחון שלכם (\(\beta = 3000\)).
כעת אתם מגיעים לבניין השני. נכנסתם ללובי, והמתווך (שחקן MAX שרוצה להרוויח כמה שיותר) מציע לכם לבחון כמה דירות. הדירה הראשונה שהוא מראה לכם מוצעת ב-3,800 ש"ח. האם תטרחו להמשיך לסייר בבניין השני ולבדוק את שאר הדירות בקומה? בשום פנים ואופן לא!
⚖️ 1. מהות האלגוריתם: הגדרת חלון החסמים \((\alpha, \beta)\)
אלגוריתם אלפא-בטא הוא הרחבה של סריקת עומק-ראשון (DFS) עבור עצי מינימקס. לאורך כל ענף חיפוש, האלגוריתם מחזיק ומעדכן שני חסמים קריטיים:
הגדרה: ערך החלופה הטובה ביותר (הגבוהה ביותר) ששחקן MAX מצא עד כה בכל נקודה לאורך המסלול מהשורש ועד לצומת הנוכחי.
• ערך התחלתי: \(\alpha = -\infty\).
• מתי מתעדכן? רק בצומתי MAX, לפי: \(\alpha \leftarrow \max(\alpha, v)\).
• משמעות אינטואיטיבית: "רצפת ביטחון" – מובטח ל-MAX לקבל לפחות \(\alpha\).
הגדרה: ערך החלופה הטובה ביותר (הנמוכה ביותר) ששחקן MIN מצא עד כה בכל נקודה לאורך המסלול מהשורש ועד לצומת הנוכחי.
• ערך התחלתי: \(\beta = +\infty\).
• מתי מתעדכן? רק בצומתי MIN, לפי: \(\beta \leftarrow \min(\beta, v)\).
• משמעות אינטואיטיבית: "תקרת איום" – מובטח ל-MIN שיריבו MAX לא יקבל יותר מ-\(\beta\).
בכל רגע שבו מתקיים \(\alpha \ge \beta\) (הרצפה פגשה את התקרה או עלתה מעליה), מתבצע גיזום מידי (Cutoff) של כל שאר האחים שטרם נסרקו תחת אותו צומת! החיפוש חוזר (Backtracks) מיד לרמת האב, ומונע בדיקת מיליוני צמתים חסרי תועלת.
⚙️ 2. האלגוריתם המלא שלב-אחר-שלב (פסיאודו-קוד וזרימת נתונים)
כיצד זורם המידע בעץ? שימו לב לכלל הברזל: ערכי \(\alpha\) ו-\(\beta\) מועברים מלמעלה למטה (בירידה לעומק העץ), ואילו ערכי ההערכה המספריים \(v\) מוחזרים מלמטה למעלה (בעלייה לאחור)!
1 קריאת השורש: אתחול חלון החיפוש
הסוכן קורא לפונקציה הראשית: AlphaBetaSearch(state).
השורש (לרוב שחקן MAX) מופעל עם החסמים ההתחלתיים:
$$\alpha = -\infty, \quad \beta = +\infty$$
2 לוגיקת צומת MAX: עדכון \(\alpha\) ובדיקת גיזום \(\beta\)
בצומת MAX, עבור כל בן חוקי:
1. קוראים ברקורסיה ל-MinValue(child, \(\alpha\), \(\beta\)) ומקבלים ערך $v$.
2. מעדכנים את ערך המקסימום הזמני: $v_{max} \leftarrow \max(v_{max}, v)$.
3. אם $v_{max} \ge \beta$ – גוזמים מיד ומחזירים $v_{max}$ (נקרא גיזום בטא / \(\beta\)-Cutoff).
4. אחרת, מעדכנים את החסם התחתון: \(\alpha \leftarrow \max(\alpha, v_{max})\).
3 לוגיקת צומת MIN: עדכון \(\beta\) ובדיקת גיזום \(\alpha\)
בצומת MIN, עבור כל בן חוקי:
1. קוראים ברקורסיה ל-MaxValue(child, \(\alpha\), \(\beta\)) ומקבלים ערך $v$.
2. מעדכנים את ערך המינימום הזמני: $v_{min} \leftarrow \min(v_{min}, v)$.
3. אם $v_{min} \le \alpha$ – גוזמים מיד ומחזירים $v_{min}$ (נקרא גיזום אלפא / \(\alpha\)-Cutoff).
4. אחרת, מעדכנים את החסם העליון: \(\beta \leftarrow \min(\beta, v_{min})\).
📋 דוגמה מודרכת צעד-אחר-צעד: איך המשתנים משתנים בזיכרון שלב אחרי שלב?
נתבונן בעץ שבו השורש הוא A (MAX) עם שני בנים: B (MIN) ו-C (MIN). תחת B יש עלים 3 ו-5. תחת C יש עלה שמאלי 2 ועלה ימני 8:
• בודק תנאי גיזום: $\alpha \ge \beta \implies -\infty \ge 3$ (לא מתקיים).
• סורק עלה שני: 5 $\implies$ $\beta = \min(3, 5) = \mathbf{3}$.
• B מחזיר את הערך 3 לאביו A.
• C סורק עלה ראשון: 2 $\implies$ מעדכן: $\beta = \min(+\infty, 2) = \mathbf{2}$.
• C בודק תנאי גיזום: האם $\alpha \ge \beta$? $3 \ge 2$ – מתקיים בהחלט!
• גיזום אלפא (Cutoff)! העלה הימני של C (ערך 8) נגזם מידית ולא נבדק לעולם!
• C מחזיר את הערך 2 לשורש.
🔍 3. מאפיינים תיאורטיים קריטיים ומלכודות מבחן שכיחות
האלגוריתם מדלג לחלוטין על בחינת תתי-עצים שאינם משפיעים על השורש. בסידור מהלכים מושלם (Ideal Ordering), סיבוכיות הזמן צונחת מ-$O(b^m)$ ל-$O(b^{m/2})$. המשמעות המעשית: ניתן להכפיל את עומק החיפוש באותו זמן עיבוד בדיוק!
גיזום אלפא-בטא הוא אלגוריתם מדויק ללא פשרות. הוא מובטח מתמטית להחזיר בדיוק נמרץ את אותו ערך מינימקס ואותו מהלך בשורש כפי שהיה מחזיר חיפוש מלא שסורק את כל מיליארדי העלים!
מאחר שהחיפוש מתבצע משמאל לימין, המסלול השמאלי ביותר חייב להיסרק כולו עד העלים כדי לקבוע את חסמי ה-\(\alpha\) וה-\(\beta\) הראשוניים של העץ. לא קיים מידע קודם שמאפשר לגזום אותו!
האלגוריתם מוצא את הערך המדויק של שורש העץ, אך צמתים שנמצאים בתוך ענפים שנגזמו לעולם אינם מקבלים את ערך המינימקס האמיתי שלהם (ערכם נותר בלתי ידוע).
• רצפת הביטחון נשמרת: הניקוד ש-MAX יקבל יהיה גדול או שווה לערך המינימקס המקורי: $Score \ge v(s)$. שגיאות היריב רק עוזרות לנו!
• אבל האם מינימקס הוא האסטרטגיה הטובה ביותר מול יריב כזה? לא בהכרח! אם אנו יודעים מראש שהיריב שוגה באופן שיטתי, כדאי להפעיל אלגוריתם "ניצול חולשות" (Exploitation) שעשוי להניב רווח גבוה בהרבה ממשחק שמרני.
📝 4. ניתוח מלא של תרגילים מתקדמים בכתב יד (צעד-אחר-צעד)
תרגול מודרך ומעמיקתרגיל מודרך א': הצבת ערכי עלים לקבלת גיזום ספציפי
עומק 2 (MAX $\to$ MIN $\to$ Leaves)
נתון עץ משחק בעומק 2. השורש הוא MAX, תחתיו 3 צמתי MIN המסומנים $E_1, E_2, E_3$.
תחת $E_1$ יש 3 עלים קבועים: $5, 9, 2$.
תחת $E_2$ יש 3 עלים עם משתנים: $a, b, c$ (המסומנים כענפים $E_4, E_5, E_6$).
תחת $E_3$ יש 3 עלים עם משתנים: $d, e, f$ (המסומנים כענפים $E_7, E_8, E_9$).
צומת $E_1$ הוא צומת MIN. הוא סורק את עליו: $5, 9, 2$. $$v(E_1) = \min(5, 9, 2) = 2$$ ערך זה חוזר לשורש (MAX), ומעדכן את רצפת הביטחון שלו: $$\alpha_{\text{root}} = \max(-\infty, 2) = \mathbf{2}, \quad \beta_{\text{root}} = +\infty$$ מכאן ואילך, כל צומת שיקבל ערך קטן או שווה ל-2 ייגזם מיד!
ענף $E_7$ הוא הבן הראשון של צומת ה-MIN בשם $E_3$. כדי לבצע גיזום בצומת MIN, נדרש שערך הבן יקיים $v \le \alpha$. אולם לפני שסורקים לפחות עלה אחד תחת $E_3$, הערך הזמני של $E_3$ הוא $\beta = +\infty$, ואין שום ערך להשוות מול $\alpha=2$. לכן חובה לבקר בעלה הראשון $E_7$!
בצומת $E_2$, סורקים תחילה את $E_4$ (ערך $a$). אם $a \le 2$, ערך $E_2$ הוא לכל היותר 2. מאחר שבשורש כבר מובטח $\alpha=2$, שחקן MAX לעולם לא יבחר ב-$E_2$, ומתבצע גיזום מידי של שאר בניו ($E_5, E_6$). אותו היגיון בדיוק פועל ב-$E_3$: אם העלה הראשון $d \le 2$, נגזמים מיד $E_8, E_9$!
כדי להגיע לענף $E_5$ מבלי לגזום אותו, העלה הראשון חייב להיות גדול מ-2 ($a > 2$). כעת, כדי לגזום את $E_6$, העלה השני חייב להיות קטן או שווה ל-2 ($b \le 2$), מה שמעדכן את החסם של $E_2$ ל-2 ומפעיל גיזום של $E_6$. באופן סימטרי לחלוטין ב-$E_3$: נדרש $d > 2$ וגם $e \le 2$.
כדי שצומת שלם ייגזם מבלי להיכנס אליו כלל, היה נדרש שאביו (השורש) יבצע גיזום בטא. אולם השורש הוא MAX, ויש לו רק חסם $\alpha=2$ עם $\beta=+\infty$. תנאי גיזום $\alpha \ge \beta$ אינו מתקיים בשורש, ולכן חובה לרדת לצומת $E_3$ ולסרוק לפחות את העלה הראשון שלו.
תרגיל ב': מניעת גיזום לחלוטין בעץ משחק (Worst Move Ordering)
סריקה מלאה של כל 8 העליםנתון עץ 3 רמות: שורש MAX, רמת MIN עם צמתים $B, C$, רמת MAX עם $D, E, F, G$, ו-8 עלים ($H, I, J, K, L, M, N, O$). מהם התנאים המתמטיים הנדרשים כדי שאף עלה לא ייגזם, הן בסריקה משמאל-לימין והן בסריקה מימין-לשמאל?
D=8, E=6
F=7, G=5
תרגיל ג': עץ בינארי עם ערכים חיוביים ושליליים לסירוגין
הוכחה והפרכה לעומק זוגי ואי-זוגי
הגדרת הבעיה והטענה: נתון עץ בינארי מלא בעומק $d$ שבו השורש הוא MAX. עלי העץ מסודרים משמאל לימין עם ערכים חיוביים ושליליים לסירוגין: $+v_1, -v_2, +v_3, -v_4, \dots$
האם מובטח שערך השורש יהיה בהכרח חיובי?
נתבונן בעץ בעומק $d=2$ עם 4 עלים שערכיהם לסירוגין: $+1, -1, +1, -1$.
1. ברמה 1 (מתחת לשורש) יש שני צמתי MIN.
2. צומת MIN שמאלי מחשב: $\min(+1, -1) = \mathbf{-1}$.
3. צומת MIN ימני מחשב: $\min(+1, -1) = \mathbf{-1}$.
4. שורש MAX מחשב: $\max(-1, -1) = \mathbf{-1}$ (שלילי לחלוטין! ההנחה הופרכה).
בעומק אי-זוגי, הרמה שממנה מסתעפים העלים שייכת לשחקן MAX! כל צומת MAX מחזיק בשני עלים אחים: אחד חיובי $+v_{2k-1}$ ואחד שלילי $-v_{2k}$. מאחר ש-MAX בוחר מקסימום: $\max(+v_{2k-1}, -v_{2k}) = +v_{2k-1} > 0$. כלומר, כל הצמתים ברמה שמעל העלים מקבלים ערכים חיוביים בלבד! מכאן, כל פעולות ה-$\min$ וה-$\max$ במעלה העץ יפעלו אך ורק על קבוצות של מספרים חיוביים, ולכן ערך השורש יהיה בהכרח חיובי. מ.ש.ל!
מעבדה אינטראקטיבית 4.1: סימולטור עצי משחק ותרגול גיזום אלפא-בטא
פונקציות הערכה, אפקט האופק, עונש עומק ופתולוגיית המינימקס
כשהמחשב מסרב לתת מט מיידי וכשהחיפוש משתגע מעומק
שלום לכולם! בתיאוריה, מינימקס ואלפא-בטא נראים מושלמים: הם מבטיחים ניצחון ודאי. אבל כשאנחנו פוגשים את המציאות של משחקים אמיתיים כמו שחמט (עם פקטור סיעוף של $b \approx 35$ ועומק משחק ממוצע של 80 חצאי-מהלכים), אנחנו מגלים שאין שום סיכוי להגיע לעלים!
במציאות, חובה עלינו לבצע חיתוך עומק מוגבל משאבים (Cutoff Search) ולהחליף את ערך המשחק האמיתי בפונקציית הערכה היוריסטית (\(Eval(s)\)).
אבל כאן מתחילות הצרות המרתקות:
מדוע מנוע שחמט ללא תוספת מיוחדת עשוי להעדיף מט ב-5 צעדים על פני מט בצעד אחד בלבד?
מהו "אפקט האופק" שגורם למחשב להקריב כלי אחרי כלי כדי "לדחות את הקץ"?
ומדוע המתמטיקאי דייוויד נאו הוכיח שעצים עם רעש אקראי הופכים לגרועים יותר ככל שמעמיקים בהם (פתולוגיית המינימקס), וכיצד ג'ודיאה פרל הציל את עולם השחמט מהפרדוקס הזה?
בואו נצלול פנימה ונגלה את כל הסודות!
🧠 1. פונקציית ההערכה \(Eval(s)\) ופרדיגמות החיפוש של קלוד שאנון
בשנת 1950, אבי תורת האינפורמציה, קלוד שאנון (Claude Shannon), הציע שני מודלים יסודיים לתכנות משחקי חשיבה:
חיפוש ברוחב מלא עד עומק קשיח קבוע
סורק את כל המהלכים החוקיים ללא סינון עד עומק קבוע מראש $d$.
• יתרון: לא מפספס מהלכים טקטיים בלתי-צפויים ("הברקות").
• חיסרון: מוגבל מאוד בעומק עקב פיצוץ קומבינטורי אדיר, וסובל קשות מ"אפקט האופק".
חיפוש סלקטיבי מעמיק (Playouts & Heuristics)
מסנן מהלכים גרועים מראש ובודק רק קווים מבטיחים לעומק רב בהרבה, תוך שימוש בחיפוש שקט (Quiescence Search) בעמדות סוערות.
• יתרון: מחקה חשיבה של רב-אמן אנושי וחוסך מיליארדי צמתים חסרי טעם.
• חיסרון: סכנת עיוורון טקטי אם מנוע הסינון פספס מהלך מנצח "שקט".
📐 אנטומיה של פונקציית הערכה ליניארית משוקללת (Weighted Linear Combination)
לרוב, פונקציית ההערכה מחושבת כצירוף ליניארי של תכונות המצב: $$Eval(s) = w_1 f_1(s) + w_2 f_2(s) + \dots + w_n f_n(s) = \sum_{i=1}^n w_i f_i(s)$$
♟️ 2. באג המט המיידי בשחמט ועונש עומק (Depth Penalty)
מלכודת מינימקס קלאסיתאלגוריתם המינימקס הסטנדרטי מעריך כל מצב טרמינלי של ניצחון באותו ערך קבוע, למשל: $$v(\text{Checkmate}) = +1.0$$ מבחינת האלגוריתם: $$\text{Mate in 1 step} \implies +1.0, \quad \text{Mate in 5 steps} \implies +1.0$$ שני המצבים שקולים לחלוטין! לכן, אם ענף המט ב-5 צעדים נסרק ראשון, המנוע עשוי לבחור בו בשמחה ולהתעלם מניצחון מיידי בצעד אחד, או לשוטט בצעדים חסרי תועלת שנותנים ליריב הזדמנות להיחלץ!
🛠️ הפתרון המתמטי: פונקציית תועלת מותאמת עומק (Depth-Discounted Utility)
מפעילים מקדם דעיכה קטן \(\epsilon\) (למשל \(\epsilon = 0.01\)) התלוי בעומק הצומת בעץ ($d$):
• עבור מט בעומק 1: $1.0 - 0.01 \cdot 1 = \mathbf{0.99}$.
• עבור מט בעומק 5: $1.0 - 0.01 \cdot 5 = \mathbf{0.95}$.
מאחר ש-$0.99 > 0.95$, האלגוריתם יעדיף תמיד את הניצחון המהיר ביותר האפשרי!
• עבור תבוסה בעומק 1: $-1.0 + 0.01 \cdot 1 = \mathbf{-0.99}$.
• עבור תבוסה בעומק 5: $-1.0 + 0.01 \cdot 5 = \mathbf{-0.95}$.
מאחר ש-$-0.95 > -0.99$, כשההפסד בלתי נמנע, המנוע יעדיף את המסלול הארוך ביותר שדוחה את התבוסה ומאפשר ליריב לטעות!
🔭 3. אפקט האופק (Horizon Effect) וחיפוש שקט (Quiescence Search)
חיתוך החיפוש בעומק קבוע יוצר "אופק" מלאכותי. מה קורה כשאסון טקטי מתרחש צעד אחד בדיוק מעבר לאופק?
⚠️ התרחיש הקלאסי: הקרבות דחייה הרסניות (The Horizon Trap)
נניח שלמחשב יש מלכה לכודה שעומדת להילכד בוודאות בעומק $d=4$.
המחשב מבחין שאם יקריב רץ עם שח ($d=1$), היריב ייאלץ להכות את הרץ ($d=2$). כעת המחשב מקריב פרש עם שח ($d=3$), והיריב מכה אותו ($d=4$).
בנקודה זו, החיפוש בעומק 4 נעצר! מאחר שהמלכה עדיין לא נלכדה *בתוך חלון ה-4 צעדים*, המחשב מעריך את המצב כאילו "המלכה ניצלה", ומבצע בשמחה את הקרבות השווא, כשלמעשה הוא גם הפסיד רץ ופרש וגם יפסיד את המלכה בצעד החמישי!
🛡️ הפתרון: חיפוש שקט (Quiescence Search) – לא עוצרים באמצע קרב יריות!
כאשר האלגוריתם מגיע לעומק המקסימלי $d$, הוא אינו מפעיל את פונקציית ההערכה מיד אם המצב אינו "שקט" (Non-quiescent). אם יש על הלוח לכידות פעילות, חילופי כלים פתוחים או שח, החיפוש ממשיך הלאה (אך ורק עבור מהלכי לכידה והגנה טקטיים) עד שכל הלכידות ממוצות ומגיעים לעמדה רגועה לחלוטין.
2. אם נפעיל $Eval$ מיד: הלבן ייראה מוביל ברגלי שלם ($+1.0$).
3. אבל המצב אינו שקט (המלכה תחת איום מיידי!). מופעל
QuiescenceSearch():• מהלך שחור 1: פרש שחור מכה את המלכה הלבנה ב-d5 (לכידה!).
• מהלך לבן 2: צריח לבן מכה את הפרש השחור ב-d5 (לכידה!).
• אין עוד לכידות אפשריות $\implies$ העמדה הוגדרה כ"שקטה" (Quiet)!
4. כעת מפעילים $Eval$: המאזן האמיתי מתגלה – הלבן הפסיד מלכה וקיבל רק פרש ורגלי ($-5.0$)!
החיפוש השקט הציל את המחשב מהקרבה עיוורת ואסון טקטי!
⚡ 4. טבלאות התמרה (Transposition Tables) וגיבוב זוברסיט (Zobrist Hashing)
עץ משחק אינו עץ טהור, אלא גרף מכוון ללא מעגלים (DAG). לעיתים קרובות מאוד מגיעים לאותו מצב לוח בדיוק מסדר מהלכים שונה לחלוטין (תופעה הנקראת טרנספוזיציה).
דוגמה: המהלכים 1. e4 e5 2. Nf3 Nc6 מביאים לאותו לוח בדיוק כמו 1. Nf3 Nc6 2. e4 e5!
מאתחלים מראש טבלה של מספרים אקראיים בני 64-ביט: Table[64_squares][12_pieces].
המפתח ההתחלתי של הלוח הוא XOR של כל הכלים המוצבים עליו:
$$Hash = \bigoplus_{i=1}^n Table[\text{square}_i][\text{piece}_i]$$
• $0 \oplus Table[to][piece] = Table[to][piece] \implies$ מציב את הכלי במשבצת היעד!
ערך התמרה בטבלה: שומרים {Key, Depth, Flag (EXACT/LOWER/UPPER), Value, BestMove}. אם אותו לוח נבדק בעבר בעומק שווה או עמוק יותר, מחזירים את התוצאה בזמן $O(1)$ ללא חישוב נוסף!
🧬 5. פתולוגיית המינימקס (Nau 1979) והפתרון של Judea Pearl
פרדוקס מתמטי מרתק
בשנת 1979 פרסם החוקר דייוויד נאו (Dana Nau) מאמר שהדהים את עולם הבינה המלאכותית:
הוא הוכיח מתמטית כי בעצי משחק שבהם ערכי העלים הם משתנים מקריים בלתי-תלויים הנושאים רעש (שגיאת הערכה), ככל שסורקים עמוק יותר בעץ, ההחלטה בשורש הופכת לגרועה יותר ולאיכותית פחות!
הסיבה: פעולות ה-$\max$ וה-$\min$ פועלות כמסנני רעש א-סימטריים שמגבירים שגיאות קיצוניות ודוחפים אותן במעלה העץ.
🏆 מדוע שחמט אמיתי חסין לפתולוגיה? הפתרון של חתן פרס טיורינג Judea Pearl (1983)
ג'ודיאה פרל הוכיח כי עצי משחק אמיתיים של בני אדם אינם מקיימים את הנחות המודל של Nau, משתי סיבות מכריעות:
במשחקים אמיתיים, עמדות אחיות שנובעות מאותה עמדת אב דומות מאוד זו לזו מבחינה מבנית. ערכיהן תלויים מאוד ואינם בלתי-תלויים! תלות חזקה זו בולמת לחלוטין את התפשטות השגיאה לאחור.
במשחק אמיתי קיימים מסלולים טקטיים חדים של תבוסה או ניצחון מוחלט (מלכודות מט או נפילת כלי) הרבה לפני קצה העץ. מצבים טרמינליים אלו מעגנים את החיפוש בערכי אמת מוצקים.
מעבדה אינטראקטיבית 4.2: אפקט האופק וגיבוב Zobrist
סביבות מזל, Expectimax, אלגוריתמי Star וחיפוש מונטה קרלו (MCTS)
כשהטבע אינו שטן, אלא קובייה אקראית של מזל
שלום חברים! בכל המודלים שראינו עד כה (Minimax ו-Alpha-Beta), הנחנו הנחה קיצונית מאוד: שהיריב שלנו פועל בזדון טהור ואופטימלי נגדנו. אבל מה קורה כשאתם משחקים שש-בש, פוקר, מונופול, או מנווטים רובוט מאדים שגלגליו עלולים להחליק על סלע?
במקרים אלו, הסביבה אינה "רוצה ברעתנו" במכוון – היא פשוט סטוכסטית (אקראית), ונשלטת על ידי חוקי ההסתברות!
כאן אנו נפרדים מעצי המינימקס הדטרמיניסטיים ופוגשים שני כלים ששינו את פני הבינה המלאכותית:
1. אלגוריתם Expectimax: שמחשב תוחלת מתמטית ודורש זהירות עילאית מפני טרנספורמציות לא-ליניאריות.
2. אלגוריתם MCTS (חיפוש עץ מונטה קרלו): האלגוריתם ששבר את המחסום שנחשב לבלתי-עביר במשחק הגו (Go), הביס אלופי עולם וסלל את הדרך ל-AlphaZero! בואו נבין בדיוק איך זה עובד.
🎲 1. מודל עץ Expectimax: צומתי מקסימום, מינימום וסיכוי (Chance Nodes)
בעץ Expectimax ישנם שלושה סוגי צמתים הפועלים בתיאום:
הסוכן שלנו בוחר את המהלך הממקסם את התועלת הצפויה.
היריב (אם קיים) בוחר את המהלך הממזער את תועלתנו.
הטבע מגריל תוצאה ע"פ התפלגות הסתברות ידועה מראש.
⚠️ שאלת מבחן מכרעת: מדוע טרנספורמציה מונוטונית משנה החלטה ב-Expectimax?
דוגמה נגדית מספרית
במינימקס דטרמיניסטי, מותר להפעיל על ערכי העלים כל טרנספורמציה מונוטונית עולה (כמו $g(x) = x^3$ או $g(x) = \log x$), והמהלך הנבחר לעולם לא ישתנה כי: $\max(g(x), g(y)) = g(\max(x, y))$.
אבל ב-Expectimax – טרנספורמציה לא-ליניארית מעוותת את התוחלת והופכת את ההחלטה לחלוטין!
מסקנה מתמטית: ב-Expectimax מותר להשתמש אך ורק בטרנספורמציות אפיניות ליניאריות מהצורה: $f(x) = ax + b$ כאשר $a > 0$. כל פונקציה קעורה או קמורה משנה את יחס הסיכון (Risk Aversion / Risk Seeking) ומשמידה את נכונות המודל.
⭐ אלגוריתמי גיזום בעצי סיכוי: Star1 ו-Star2 (Ballard, 1983)
מדוע אלפא-בטא רגיל לא יכול לגזום בצומתי סיכוי? כי ללא חסמים ידועים על ערכי העלים, עלה בודד שטרם נסרק עלול להיות שווה $+\infty$, ולהקפיץ את כל התוחלת לשמיים!
הפתרון של ברוס בלארד: אם ידוע שכל התועלות בעץ חסומות בקטע סגור $[L, U]$ (למשל $[0, 100]$):
• אלגוריתם Star1: מחשב חסם עליון פסיבי לתוחלת בהנחה שכל העלים שטרם נסרקו יקבלו את הערך המקסימלי $U$. אם חסם עליון זה קטן מ-$\alpha$, גוזמים את יתרת צומת הסיכוי!
• אלגוריתם Star2: מהדק את החסמים בצורה דינמית על ידי ניצול ההסתברויות המדויקות של כל ענף, ומשיג חיסכון חישובי של עד $93\%$ מעץ החיפוש.
🚀 2. חיפוש עץ מונטה קרלו (MCTS) ונוסחת UCB1 / UCT
מהפכת הבינה המלאכותית
במשך עשרות שנים נחשב משחק הגו (Go) ל"גביע הקדוש" הבלתי-מושג של מדעי המחשב. עם פקטור סיעוף עצום של $b \approx 250$ ועומק של 150 מהלכים, עץ החיפוש מכיל $10^{360}$ מצבים – ומעולם לא נמצא אדם שהצליח לנסח עבורו פונקציית הערכה ידנית $Eval(s)$ ראויה.
בשנת 2006 פותח אלגוריתם MCTS (Monte Carlo Tree Search) שהביא למהפך: במקום להעריך עמדות באופן יוריסטי, נותנים למחשב לשחק אלפי משחקים אקראיים מהירים (Rollouts) עד הסוף, ומסיקים את איכות העמדה מתוך הסטטיסטיקה של הזכיות וההפסדים!
יורדים מראש העץ דרך צמתים שכבר קיימים בו, כאשר בכל צומת בוחרים את הבן בעל הציון הגבוה ביותר לפי נוסחת UCB1, עד שמגיעים לעלה שאינו מורחב במלואו.
יוצרים צומת בן חדש (או מספר בנים) המייצג מהלך חוקי שטרם נוסה מעמדה זו, ומוסיפים אותו כצומת רשמי לעץ החיפוש.
מהצומת החדש מריצים "משחק סימולציה מהיר" (Rollout / Play-out) עד לסיום המשחק (על פי מדיניות בחירה מהירה או אקראית) לקבלת תוצאה סופית: ניצחון ($+1$), תיקו ($0$) או הפסד ($-1$).
מעלים את תוצאת המשחק לאחור לאורך כל המסלול שנבחר עד לשורש: מעלים את מונה הביקורים ($N \leftarrow N+1$) ומעדכנים את מונה הזכיות ($W \leftarrow W + z$) בכל צומת אב.
🎰 אינטואיציה מהחיים: פרדוקס מכונות המזל בקזינו (Multi-Armed Bandit)
דמיינו שאתם נכנסים לקזינו עם שורת מכונות מזל ("שודדים חמושים").
משכתם בידית המכונה הראשונה וזכיתם ב-50 ש"ח. מה תעשו כעת?
• האם תמשיכו למשוך רק בידית הזו שוב ושוב (ניצול טהור - Exploitation)? אם כן, ייתכן שפספסתם את המכונה הסמוכה שמשלמת 500 ש"ח בכל סיבוב!
• האם תבזבזו את כל כספכם בניסיון לבדוק את כל 50 המכונות באולם (חקר טהור - Exploration)? אם כן, תפסידו את רוב כספכם על מכונות ריקות!
נוסחת UCB1 היא הפתרון המתמטי המושלם לדילמה הזו: היא מאזנת בדיוק אופטימלי בין הרצון להרוויח ממה שכבר הוכח כמוצלח, לבין הסקרנות לגלות מהלכים חדשים שאולי יתבררו כמבריקים!
אחוז הזכיות הממוצע של הצומת ($w_i$ מספר הזכיות, $n_i$ מספר הביקורים). ככל שצומת הוכיח את עצמו כיותר מוצלח בסימולציות, ערך זה גבוה יותר, והאלגוריתם ישאף לחזור אליו שוב!
איבר המודד את חוסר הוודאות. $N$ הוא סך הביקורים באב, ו-$n_i$ מספר הביקורים בבן. ככל שאנו מבקרים בצמתים אחרים אך מזניחים את בן $i$, המונה $\ln N$ גדל בעוד המכנה $n_i$ נשאר קבוע – מה שמזניק את הציון שלו ומכריח את המערכת לבדוק אותו!
מעבדה אינטראקטיבית 4.3: צמיחת עץ MCTS חי בזמן אמת
ניסוח פורמלי של CSP, גרף אילוצים וטרנספורמציות מ-n-ary לבינארי
להפסיק לחפש מסלולים, ולהתחיל לספק אילוצים!
שלום חברים! הגענו לחלק השני של הפרק – בעיות סיפוק אילוצים (Constraint Satisfaction Problems - CSP).
עד כה, בכל האלגוריתמים שלמדנו (BFS, DFS, A*, אלפא-בטא), שאלנו את עצמנו שאלה אחת מרכזית: "איך מגיעים מנקודת המוצא אל היעד?" – סדר הפעולות והמסלול היו לב העניין.
ב-CSP, תפיסת העולם משתנה ב-180 מעלות: למי אכפת מהמסלול?!
תחשבו על פתרון לוח סודוקו, צביעת מפת מדינות בצבעים שונים, או בניית מערכת שעות לאוניברסיטה עם מאות קורסים ומרצים: האם מעניין מישהו אם שיבצתם את שיעור חדו"א ביום ראשון או ביום חמישי קודם? ממש לא!
כל מה שמעניין הוא שהמצב הסופי שמתקבל מקיים את כל החוקים והאילוצים במלואם.
זוהי עוצמתה של פרדיגמת ה-Factored Representation (ייצוג מפורק): במקום להתייחס למצב כ"קופסה שחורה" עיוורת, המחשב מבין את המבנה הפנימי של המשתנים והאילוצים, ומנצל אותו כדי לחסל 99.9% ממרחב החיפוש! בואו נלמד איך למדל ולפתור בעיות כאלו כמו מקצוענים.
📐 1. ניסוח מתמטי פורמלי של בעיית CSP: השלשה \(\langle X, D, C \rangle\)
בעיית סיפוק אילוצים מוגדרת באופן פורמלי ומדויק על ידי שלושה רכיבים:
קבוצת הנעלמים שחובה לשבץ עבורם ערך סופי.
עבור כל משתנה $X_i$, קבוצת כל הערכים החוקיים המותרים להצבה.
אוסף התנאים המגדירים אילו שילובי ערכים מותרים להשמה בו-זמנית.
📋 מילון מושגי הליבה: הגדרת מצבים ופתרון ב-CSP
🗺️ 2. הדוגמה הקלאסית: צביעת מפת אוסטרליה ומשפט הרכיבים המבודדים
דוגמת הבסיס של הקורסעלינו לצבוע את 7 הטריטוריות של אוסטרליה ב-3 צבעים (אדום, ירוק, כחול) כך ששתי מדינות שכנות בעלות גבול משותף לא יחלקו את אותו הצבע:
🧩 3. סיווג סוגי אילוצים: ארנויות (Arity), אילוצים גלובליים ואילוצים רכים (WCSP)
Alldifferent(\(X_1 \dots X_9\)) בסודוקו.
בעולם האמיתי (כמו שיבוץ קורסים), חלק מהאילוצים הם העדפות רכות ולא חוקי ברזל ("רצוי שהשיעור לא יהיה ביום שישי בבוקר").
• מודל Weighted CSP (WCSP): לכל הפרת אילוץ משויך קנס מספרי $Cost(C)$.
• מטרת האלגוריתם: מציאת השמה שלמה הממזערת את סך הקנסות $\sum Cost(C)$.
• שיטת פתרון: מבוצע באמצעות חיפוש Branch and Bound עם חסמים יוריסטיים תחתונים.
🔄 4. טרנספורמציות מ-n-ary לרשת בינארית (Dual Graph מול Hidden Variable)
נושא מבחן תיאורטי מרכזיאלגוריתמי עקביות קשת (כמו AC-3) מתוכננים לפעול על אילוצים בינאריים. כיצד ממירים בעיה עם אילוצים מסדר גבוה לרשת בינארית בלבד? קיימות שתי שיטות יסוד מתמטיות:
צעד 1: כל אילוץ מקורי מסדר גבוה $C_i$ הופך למשתנה חדש בגרף הדואלי!
צעד 2: תחום הערכים של המשתנה הדואלי הוא אוסף כל הצירופים החוקיים (Tuples) המקיימים את האילוץ.
צעד 3: נמתחת קשת בינארית בין שני משתנים דואליים אם ורק אם האילוצים המקוריים שלהם חולקים משתנה משותף, והאילוץ הבינארי דורש שהם יסכימו על ערכו של המשתנה המשותף!
צעד 1: שומרים את כל המשתנים המקוריים כפי שהם.
צעד 2: עבור כל אילוץ מסדר גבוה, יוצרים משתנה עזר "מוסתר" יחיד, שתחומו הוא קבוצת כל הצירופים המותרים (Tuples).
צעד 3: מותחים קשתות בינאריות אך ורק בין המשתנה המוסתר לבין כל אחד מהמשתנים המקוריים המשתתפים בו (האילוץ הבינארי אוכף התאמה בין ערך המשתנה הבודד לערכו בתוך ה-Tuple). מתקבל גרף דו-צדדי נקי!
💡 דוגמה מוחשית צעד-אחר-צעד: איך ממירים את האילוץ המשולש \(A + B = C\)?
נניח שנתונים שלושה משתנים: \(A, B \in \{1, 2\}\) ו-\(C \in \{2, 3\}\), עם האילוץ הטרנארי: \(A + B = C\).
• קבוצת הצירופים החוקיים (Tuples): \(\{(1, 1, 2), (1, 2, 3), (2, 1, 3)\}\) (3 צירופים בלבד מתוך 8 אפשריים!).
מעבדה אינטראקטיבית 4.4: צביעת מפת אוסטרליה וטרנספורמציות גרף
אכיפת עקביות קשת (AC-3 עד AC-2001), חיפוש משולב (FC, MAC, CBJ) והיוריסטיקות זהב
לתת לאילוצים לעבוד בשבילנו ולנפות את הבלתי-אפשרי
שלום חברים! ביחידה הקודמת למדנו להגדיר בעיית CSP כשלשה פורמלית \(\langle X, D, C \rangle\).
כעת עולה שאלת מיליון הדולר: איך פותרים את זה בפועל מבלי לטבוע בחיפוש עיוור אינסופי?
תארו לעצמכם בלש משטרה שחוקר שוד בנק. יש לו 1,000 חשודים. האם הוא יביא כל חשוד למשפט מלא כדי לגלות שיש לו אליבי? ודאי שלא!
במקום זאת, הבלש מבצע ניפוי מוקדם: מי שהיה בחו"ל בזמן השוד – נמחק מיד מהרשימה.
ב-CSP, הניפוי המוקדם הזה נקרא הפצת אילוצים (Constraint Propagation), והמנגנון המרכזי שמוביל אותו הוא עקביות קשת (Arc Consistency). הרעיון הוא פשוט אך גאוני: אם לערך מסוים של משתנה אין שום בן זוג חוקי אצל המשתנה השכן, הערך הזה לעולם לא יוכל להשתתף בפתרון סופי – ולכן אפשר להעיף אותו מהתחום עוד לפני שבכלל פתחנו את עץ החיפוש!
ביחידה זו נלמד כיצד פועל אלגוריתם AC-3 הקלאסי, נבין מדוע הוא דורש סיבוכיות של \(O(ed^3)\), נראה כיצד אלגוריתם AC-2001 שיפר את הביצועים ל-\(O(ed^2)\) בעזרת "מצביעי שארית", ונבחן כיצד משלבים עקביות בתוך חיפוש בעזרת Forward Checking, MAC ו-CBJ, בליווי שלוש היוריסטיקות הזהב: MRV, Degree ו-LCV!
⚡ 1. מהות עקביות קשת (Arc Consistency): הגדרה מתמטית והא-סימטריה המכוונת
עקביות קשת בוחנת זוג משתנים הקשורים ביניהם באילוץ בינארי. שימו לב להגדרה הפורמלית המדויקת:
הקשת המכוונת \((X_i, X_j)\) היא עקבית קשתית (Arc-Consistent) אם ורק אם לכל ערך \(x \in D_i\), קיים לפחות ערך אחד \(y \in D_j\) המקיים את האילוץ הבינארי שביניהם: $$\forall x \in D_i, \quad \exists y \in D_j \quad \text{such that} \quad (x, y) \models C_{ij}$$ הערך \(y\) נקרא תומך (Support) של הערך \(x\). אם לערך \(x\) אין אף תומך ב-\(D_j\), הוא נמחק מידית מתוך \(D_i\)!
בדיקת הקשת \((X_i, X_j)\) בוחנת אך ורק את הערכים ב-\(D_i\) ומצמצמת את \(D_i\). היא אינה משנה דבר ב-\(D_j\)! לכן, ייתכן בהחלט שהקשת \((X_i, X_j)\) עקבית, אך הקשת ההפוכה \((X_j, X_i)\) אינה עקבית כלל!
⚙️ 2. אלגוריתם AC-3: פסיאודו-קוד מלא, גל ההפצה וגזירת סיבוכיות \(O(ed^3)\)
אלגוריתם היסוד (Mackworth, 1977)אלגוריתם AC-3 מנהל תור של קשתות מכוונות (\(Queue\)) ומפיץ את אפקט המחיקות לאורך הגרף כמו גל הלם:
כאשר התחום של \(X_i\) הצטמצם, מי נמצא כעת בסכנה לאבד תמיכה? השכנים שלו (\(X_k\))! אולי ערך מסוים ב-\(X_k\) נתמך אך ורק על ידי אותו ערך שהרגע מחקנו מ-\(X_i\)? לכן חובה לבדוק מחדש את הקשת \((X_k, X_i)\). לעומת זאת, העובדה ש-\(D_i\) קטן אינה יכולה לפגוע בעקביות של \(X_i\) מול שכניו האחרים (אם לערך ששרד ב-\(X_i\) היה תומך קודם, התומך הזה עדיין קיים).
📐 הוכחה מתמטית מדויקת: גזירת סיבוכיות הזמן במקרה הגרוע \(O(ed^3)\)
ננתח את מספר הפעולות המקסימלי בשלושה שלבים ברורים:
בגרף יש \(e\) קשתות בינאריות, כלומר \(2e\) קשתות מכוונות. קשת \((X_k, X_i)\) מוחזרת לתור אך ורק כאשר נמחק לפחות ערך אחד מ-\(D_i\). מכיוון שב-\(D_i\) יש לכל היותר \(d\) ערכים, קשת זו יכולה להיכנס לתור לכל היותר \(d\) פעמים!
סך כל הקשתות שיוצאות מהתור לאורך כל חיי האלגוריתם חסום על ידי: $$2e \cdot d = O(ed)$$
בכל הפעלה של Revise, סורקים עד \(d\) ערכים ב-\(D_i\), ועבור כל אחד סורקים עד \(d\) ערכים ב-\(D_j\).
עלות כל ריצה: \(O(d^2)\).
🏛️ דוגמה יישומית מלאה להרצת AC-3: שיבוץ 4 מבנים ב-6 משבצות קמפוס
תרגיל מפתחנתונה רשת של 6 מגרשים ($2 \times 3$, שורה עליונה: $\{1, 2, 3\}$, שורה תחתונה: $\{4, 5, 6\}$) ו-4 מבנים $\mathcal{X} = \{A, B, C, D\}$. התחומים ההתחלתיים: $\{1, 2, 3, 4, 5, 6\}$. האילוצים: $AllDiff$, $A \in \{1, 2, 3\}$, $B \in \{4, 5, 6\}$, $col(B) > col(A)$, $C$ צמוד ל-$A$, $D$ לא צמוד ל-$A$, ו-$col(C) \in \{2, 3\}$.
למשבצת $a=3$ אין שום משבצת ב-$D_B$ עם עמודה גדולה מ-3.
3 נמחק מ-D_A!
נותר: $D_A = \{1, 2\}$.
למשבצת $b=4$ (עמודה 1) אין שום משבצת ב-$D_A$ עם עמודה קטנה מ-1.
4 נמחק מ-D_B!
נותר: $D_B = \{5, 6\}$.
השכנים של $D_A=\{1, 2\}$ הם $\{1, 2, 3, 4, 5\}$. משבצת 6 איננה שכנה של אף אחד מהם.
6 נמחק מ-D_C!
נותר: $D_C = \{2, 3, 5\}$.
🚀 3. האבולוציה של עקביות קשת: מ-AC-3 דרך AC-4 ועד פריצת הדרך של AC-2001
חזית הטכנולוגיהמדוע AC-3 אינו אופטימלי? כי הוא גס-גרגיר (Coarse-Grained): בכל פעם שקשת נכנסת מחדש לתור, הוא בודק שוב את כל הערכים מאפס, גם עבור ערכים שהתומכים שלהם כלל לא נמחקו!
הרעיון: ניהול רשימות תמיכה מפורשות לכל ערך בנפרד: \(S_{X_j, y}\) (אילו ערכים נתמכים על ידי \(y\)) ומערך מונים \(Counter[(X_i, X_j), x]\) שסופר כמה תומכים נותרו לערך \(x\).
הרעיון הגאוני: במקום לשמור טבלאות ענק, שומרים בסך הכל מצביע בודד לערך התומך האחרון שנמצא: \(LastSupport(X_i, x, X_j)\).
| אלגוריתם | זמן גרוע | מקום בזיכרון | מנגנון ליבה | הערכה מעשית |
|---|---|---|---|---|
| AC-3 | $O(ed^3)$ | $O(e + nd)$ | בדיקה מחדש נאיבית ע"י החזרת קשתות לתור | קל למימוש אך איטי עקב בדיקות כפולות |
| AC-4 | $O(ed^2)$ | $O(ed^2)$ | רשימות תמיכה מפורשות ומערך מונים | זולל זיכרון, לא מעשי בבעיות רחבות |
| AC-2001 (AC-3.1) | $O(ed^2)$ | $O(e + nd)$ | מצביעי תומך אחרון (Residue Pointers) ללא אתחול כבד | השילוב המושלם: מהירות שיא ומינימום זיכרון! |
🔍 4. שילוב עקביות בתוך חיפוש: Look-Ahead מול Look-Back (BT, FC, MAC, CBJ)
ארבעת עמודי התווך של החיפושכיצד משלבים הסקת אילוצים תוך כדי שסורקים את עץ ההשמות? נבחן את ארבע הפרדיגמות המרכזיות:
מבצע השמה למשתנה אחד בכל פעם. בודק אילוצים אך ורק בין המשתנה הנוכחי למשתנים שכבר הושמו בעבר.
• הבעיה הקטלנית: עיוורון מוחלט לעתיד! סובל קשות מתופעת ה-Thrashing (נסיגות שווא כרוניות סביב משתנה שאינו קשור לסתירה).
בכל פעם שמשבצים משתנה \(X\), מפעילים עקביות קשת אך ורק על השכנים הישירים הבלתי-משובצים שלו ומסננים מהם ערכים סותרים.
אם תחום של שכן מתרוקן – נסוגים מיד!
• היתרון: מהיר וזול חישובית בכל צעד.
• החיסרון: אינו מפיץ אילוצים בין משתנים שטרם הושמו! (ראו דוגמת מפת אוסטרליה להלן).
לאחר כל השמה, מריצים אלגוריתם עקביות קשת מלא (כמו AC-2001) על כלל הרשת הבלתי-משובצת!
גל ההפצה ממשיך ומנקה תחומי משתנים רחוקים עד שהרשת כולה עקבית לחלוטין.
• היתרון: מזהה סתירות עמוקות הרבה לפני שהן מתרחשות ומוחק ענפי ענק בעץ. כיום השיטה המובילה בעולם לפתרון בעיות CSP קשות!
פרדיגמת Look-back חכמה. מנהלת עבור כל משתנה קבוצת סתירה: \(conf(X_i)\) – רשימת המשתנים שהשמותיהם גרמו למחיקת ערכים מתחומו. בעת הגעה למבוי סתום, האלגוריתם אינו נסוג צעד אחד כרונולוגי לאחור, אלא "קופץ" ישירות למשתנה העמוק ביותר ב-\(conf(X_i)\) שחולל את הסתירה!
🎯 5. שלוש היוריסטיקות הזהב לחיפוש CSP: מי הבא ומה להציב?
עקרונות Fail-First ו-Fail-Lastבכל צעד של עץ החיפוש, על האלגוריתם לקבל שתי החלטות קריטיות: איזה משתנה לבחור כעת? ו-איזה ערך מתוך התחום שלו לנסות קודם?
בחירת המשתנה בעל התחום המצומצם ביותר
מכונה גם "המשתנה המוגבל ביותר" (Most Constrained Variable).
• ההיגיון הפדגוגי: אם בחרנו ענף שגוי שיוביל למבוי סתום, אנחנו רוצים להיכשל מהר ככל האפשר (Fail-First) בראש העץ, במקום לגלות את הטעות בעומק 50! בנוסף, משתנה עם תחום של ערך בודד מחייב השמה מיידית ללא פיצול.
בחירת המשתנה המעורב בהכי הרבה אילוצים
משמשת כשובר שוויון כאשר ל-MRV יש כמה משתנים עם אותו גודל תחום (למשל בתחילת המשחק כשכל התחומים בגודל 3).
• ההיגיון הפדגוגי: בוחרים את המשתנה שמחובר למספר הגבוה ביותר של משתנים שטרם הושמו. שיבוץ שלו יטיל את ההגבלות החזקות ביותר על שאר הרשת ויצמצם את תחומי שכניו בחדות.
בחירת הערך שהכי פחות מגביל את השכנים
לאחר שבחרנו משתנה, באיזה ערך נתחיל?
• ההיגיון הפדגוגי: בודקים לכל ערך כמה אפשרויות הוא מוחק מתחומי השכנים הלא-משובצים שלו, ובוחרים את הערך שמשאיר לשכנים מקסימום גמישות!
מדוע כאן רוצים להצליח ולא להיכשל? כי ב-CSP אנו מחפשים פתרון אחד חוקי, ואם נבחר ערך סלחני – נגיע לפתרון מיד במורד הענף הראשון ללא נסיגות!
מעבדה אינטראקטיבית 4.5: מנוע הפצת אילוצים וקרב FC מול MAC
מילון מונחים מקצועי, טבלאות השוואה רוחביות וגשר לפרק הבא
🎓 דברי סיכום: סגירת המעגל של חיפוש ואילוצים
עשינו כברת דרך מדהימה! חיברנו בין שני עולמות מרכזיים בבינה מלאכותית: מצד אחד, חיפוש יריבותי (תורת המשחקים, מינימקס, גיזום אלפא-בטא, פתולוגיות, Expectimax ו-MCTS) שבו אנו מקבלים החלטות מול סוכן אחר או מול הטבע. מצד שני, בעיות סיפוק אילוצים (CSPs), שבהן המבנה המתמטי של האילוצים מאפשר לנו לפתור בעיות מורכבות ללא צורך בסריקה עיוורת.
📊 טבלת השוואה רוחבית: אלגוריתמי החיפוש היריבותי
| אלגוריתם | סיבוכיות זמן | סוג סביבה נדרש | רגישות לטרנספורמציות | יתרון בולט |
|---|---|---|---|---|
| Minimax | $O(b^m)$ | דטרמיניסטית, סכום-אפס | כל טרנספורמציה מונוטונית | ערבות אופטימליות מוחלטת מול יריב מושלם. |
| Alpha-Beta | $O(b^{m/2})$ עד $O(b^m)$ | דטרמיניסטית, סכום-אפס | כל טרנספורמציה מונוטונית | מכפיל את עומק החיפוש ללא שום איבוד אופטימליות. |
| Expectimax | $O(b^m \cdot n^m)$ | סטוכסטית (צומתי מזל) | אפינית ליניארית בלבד ($ax+b$) | חישוב תוחלת מתמטית מדויקת בתנאי הגרלה. |
| MCTS (עם UCB1) | Anytime (לפי תקציב זמן) | מרחבי סיעוף עצומים (Go) | דירוג זכיות סטטיסטי | צמיחה אסימטרית, עוקף פונקציות הערכה ידניות. |
⚡ טבלת השוואה רוחבית: אלגוריתמי החיפוש וההסקה ב-CSP
| אלגוריתם | סוג הסקה (Inference) | סיבוכיות זמן גרועה | מנגנון התמודדות עם כישלון | יעילות מעשית |
|---|---|---|---|---|
| Simple Backtracking (BT) | ללא הסקה (No Lookahead) | $O(d^n)$ | נסיגה כרונולוגית (צעד אחד לאחור) | איטי ביותר, סובל מ-Thrashing כרוני. |
| Forward Checking (FC) | צפייה צעד 1 קדימה (שכנים בלבד) | $O(d^n)$ | נסיגה כרונולוגית ברגע שתחום מתרוקן | מהיר בכל צעד, אך עיוור לסתירות בין שכנים. |
| Maintaining AC (MAC) | הפצה מלאה (Full Lookahead ע"י AC-2001) | $O(d^n)$ (בפועל קרוב לפולינומי) | נסיגה מוקדמת מיד בראש ענף שגוי | האלגוריתם המוביל בעולם! מנצח בעיות מורכבות. |
| Conflict Backjumping (CBJ) | הסקה לאחור (Look-back מבוסס $conf$) | $O(d^n)$ | קפיצה ישירה למקור הסתירה ההיסטורי | מדלג על ענפי סרק רבים ומונע Thrashing. |
| Min-Conflicts | אופטימיזציה מקומית (Local Search) | $O(k \cdot n)$ בממוצע | אתחול אקראי מחדש (Random Restarts) | פותר בעיות מיליון המלכות בשניות (אך אינו שלם). |
📖 מילון מונחים מקצועי דו-לשוני מורחב (עברית - אנגלית)
דילוג על ענפים בעץ שמתמטית לא יכולים להשפיע על החלטת השורש.
הקרבות דחייה חסרות תועלת עקב עצירה שרירותית של החיפוש בעומק קבוע.
הרחבת החיפוש בלכידות ושח עד להגעה לעמדה רגועה ללא איומים מיידיים.
שיטת גיבוב מבוססת XOR לעדכון מפתח לוח ב-$O(1)$ בטבלאות התמרה.
תופעה תיאורטית בעצים אקראיים שבה חיפוש עמוק מגדיל את טעות ההערכה.
הפחתת קנס קטן $\epsilon \cdot d$ מתועלת המט כדי להעדיף ניצחון מהיר בצעד אחד.
מודל עץ המשלב צומתי סיכוי (Chance) לחישוב תוחלת מתמטית בסביבות מזל.
אלגוריתם מבוסס הדמיות אקראיות (Rollouts) וצמיחה אסימטרית ע"י UCB1.
מדד המאזן אופטימלית בין ניצול ידע קיים (Exploitation) לחקר מצבים חדשים (Exploration).
אכיפה שלכל ערך במשתנה מקור קיים לפחות ערך תומך אחד במשתנה היעד.
שמירת מצביע על התומך האחרון להשגת זמן אופטימלי $O(ed^2)$ בזיכרון $O(e+nd)$.
סינון תחומי השכנים הישירים בלבד מיד לאחר ביצוע כל השמה.
אכיפת AC מלאה על כל הרשת הלא-משובצת לאחר כל השמה למניעת חיפושי סרק.
נסיגה חכמה ישירות למקור הסתירה בקבוצת $conf$ ומניעת תופעת ה-Thrashing.
בחירת המשתנה בעל התחום המצומצם ביותר במטרה להיכשל מהר בראש העץ.
שובר שוויון ל-MRV הבוחר את המשתנה המחובר להכי הרבה משתנים לא-משובצים.
בחירת הערך שמוחק הכי מעט אפשרויות משכניו במטרה למצוא פתרון ללא נסיגות.
המרה שבה כל אילוץ מקורי הופך למשתנה שתחומו הוא קבוצת הצירופים החוקיים.
המרה היוצרת גרף דו-צדדי עם משתנה עזר מוסתר המחובר בקשתות בינאריות למשתנים.
מדד לקרבת גרף אילוצים לעץ, המאפשר פתרון בזמן $O(n \cdot d^{w+1})$ ע"י פירוק עצים.
מודל המאפשר אילוצים רכים עם קנסות ע"י אלגוריתם Branch and Bound.
בפרק 4 ראינו כיצד MCTS ו-AlphaZero מחליפים פונקציות הערכה ידניות ברשתות עצביות עמוקות (Deep Neural Networks). בפרק הבא נעזוב את מרחבי החיפוש הקלאסיים וניכנס אל לב לבה של מהפכת הלמידה החישובית (Machine Learning): כיצד סוכן לומד מפונקציות תגמול, משערך הסתברויות ומאמן רשתות נוירונים לפתרון בעיות בעולם האמיתי!