מבוא לבינה מלאכותית - פרק 3: חיפוש מקומי מתקדם ומשחקים יריבותיים

יחידה 3.1 אופטימיזציה מקומית סטוכסטית (Local Search & Optimization)

אלגוריתמים גנטיים ופתרון בעיית 10 הקלפים

💡 דברי פתיחה מהמורה הפרטי: כשדרווין פוגש את מדעי המחשב

שלום חברים! בפרקים הקודמים התרגלנו לראות את עולם החיפוש כסדרה של צעדים בתוך עץ או גרף: מתחילים במצב התחלתי $s_0$, פותחים מסלולים ומנסים להגיע אל היעד. אבל מה עושים כאשר מרחב המצבים מכיל מיליארדי קונפיגורציות אפשריות, ואין שום משמעות ל"מסלול" שהוביל אליהן – אלא רק לאיכות הפתרון הסופי עצמו?

כאן בדיוק מגיעה פרדיגמת ה-Complete-State Formulation (ניסוח מצב שלם), ואחד הכלים המרתקים ביותר בתוכה הוא האלגוריתם הגנטי (Genetic Algorithm). הרעיון שואב השראה מבריקה מתהליך הברירה הטבעית והאבולוציה הביולוגית: במקום לתכנן מהלך בודד, אנחנו מנהלים אוכלוסייה שלמה של פתרונות המתחרים זה בזה, מולידים צאצאים, מחליפים ביניהם מידע גנטי מוצלח, ומשתבחים מדור לדור. בואו נצלול למבנה המתמטי של המנגנון הזה ונפתור באמצעותו את תרגיל 10 הקלפים הקלאסי של הקורס!

🧬 1. מהות האלגוריתם הגנטי: חיפוש אלומה מקומי סטוכסטי

מבחינה אלגוריתמית טהורה, אלגוריתם גנטי הוא מקרה פרטי מתקדם של חיפוש אלומה מקומי סטוכסטי (Stochastic Local Beam Search). בחיפוש אלומה רגיל, המערכת שומרת $k$ מצבים בכל שלב, בוחנת את כל שכניהם ובוחרת דטרמיניסטית את $k$ הטובים ביותר.
האלגוריתם הגנטי משכלל את הרעיון הזה בשני היבטים מהפכניים:

חיפוש אלומה דטרמיניסטי (Standard Beam)

התכנסות מוקדמת לפסגות נפרדות

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

אלגוריתם גנטי (Genetic Algorithm)

שיתוף מידע (Crossover) וחקירה אקראית (Mutation)

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

🗺️ מילון המונחים: המיפוי בין עולם הביולוגיה למדעי המחשב

ביולוגיה גן (Gene) משתנה בודד / ביט בפתרון

ביולוגיה כרומוזום / פרט מצב שלם במרחב ($s \in S$)

ביולוגיה התאמה (Fitness) פונקציית תועלת $u(s)$ למקסום

ביולוגיה אוכלוסייה (Population) קבוצת $N$ מצבים מקבילים

⚙️ 2. ארבעת שלבי מחזור החיים של האלגוריתם הגנטי

האלגוריתם מתנהל בלולאה מחזורית המתקדמת מדור לדור ($t \to t+1$) על פי ארבעה שלבים קבועים ומוגדרים היטב:

1 אתחול (Initialization)

מגרילים אוכלוסייה התחלתית של $N$ כרומוזומים באורך קבוע $L$ באופן אקראי לחלוטין (בדרך כלל מערכי ביטים של 0 ו-1).
כלל אצבע: גודל האוכלוסייה $N$ הוא היפר-פרמטר קריטי. $N$ קטן מדי (למשל 5) יגרום לחוסר מגוון גנטי; $N$ ענק (למשל 10,000) יהפוך את האלגוריתם לחיפוש ממצה איטי. לרוב בוחרים $N \in [30, 100]$.

2 הערכת התאמה (Fitness Evaluation)

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

3 תהליך הברירה והולדת דור חדש (Reproduction Loop)

חוזרים על שלושת תתי-השלבים הבאים בלולאה עד שמייצרים $N$ צאצאים חדשים המרכיבים את הדור הבא במלואו:

א. בחירת הורים (גלגל הרולטה)

ההסתברות של פרט $i$ להיבחר כהורה היא ביחס ישר לכושר שלו: $$p_i = \frac{Fitness(C_i)}{\sum_{j=1}^N Fitness(C_j)}$$ פרט מוצלח עשוי להיבחר מספר פעמים; פרט נחות עלול לא להיבחר כלל.

ב. הצלבה (Crossover)

בהסתברות קבועה $P_c$ (לרוב $0.7 \le P_c \le 0.9$), בוחרים נקודת חיתוך אקראית $k \in \{1 \dots L-1\}$ ומחליפים מקטעים בין שני ההורים. אם אין הצלבה – הצאצאים מועתקים שלמים מההורים.

ג. מוטציה (Mutation)

בהסתברות קטנה מאוד $P_m$ (לרוב $0.001 \le P_m \le 0.05$), הופכים ביט אקראי ($0 \leftrightarrow 1$) בגנום הצאצא. מוטציה מספקת חקירה (Exploration) ומונעת קיפאון מוחלט.

4 תנאי עצירה (Termination Condition)

חוזרים לשלב 2 עם האוכלוסייה החדשה. התהליך נעצר באחד משני מקרים: (1) נמצא פתרון מושלם העונה על כל אילוצי הבעיה ($Fitness \ge Target$), או (2) הגיעו למספר דורות מקסימלי שנקבע מראש ($MaxGenerations$).

🃏 3. התרגיל המרכזי מהשיעור: חלוקת 10 הקלפים

שאלת מבחן קלאסית

הגדרת הבעיה:

נתונים 10 קלפים ממוספרים: $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$.
עלינו לחלק את 10 הקלפים לשתי קבוצות שוות בנות 5 קלפים בדיוק כל אחת, כך ש:

🎯 יעד קבוצה 1: סכום = 36 סכום הקלפים בקבוצה הראשונה יהיה קרוב ככל האפשר ל-36.

🎯 יעד קבוצה 2: מכפלה = 360 מכפלת הקלפים בקבוצה השנייה תהיה קרובה ככל האפשר ל-360.

📐 מידול הבעיה באלגוריתם גנטי שלב-אחר-שלב

1. ייצוג הכרומוזום (Chromosome Encoding)

כרומוזום מיוצג על ידי וקטור בינארי באורך 10: $C = (c_1, c_2, \dots, c_{10})$.
הגן במקום ה-$i$ (המסומן $c_i$) מייצג את הקלף שערכו $i$:

$c_i = 0 \implies \text{קלף } i \text{ שייך לקבוצה 1 (סכום)}$ | $c_i = 1 \implies \text{קלף } i \text{ שייך לקבוצה 2 (מכפלה)}$

2. אילוץ הגודל (Size Constraint)

כל קבוצה חייבת להכיל 5 קלפים במדויק. מאחר שערכי $c_i \in \{0,1\}$, מספר האחדים בכרומוזום חייב להיות בדיוק 5:

$$\text{Size}_2 = \sum_{i=1}^{10} c_i = 5 \iff |\text{Size}_2 - 5| = 0$$

3. פונקציית הכושר (Fitness Function)

נחשב את הסכום של קבוצה 1 ואת המכפלה של קבוצה 2:

$$Sum_1 = \sum_{i=1}^{10} i \cdot (1 - c_i)$$

$$Prod_2 = \prod_{i=1}^{10} [i \cdot c_i + (1 - c_i)]$$

(הערה: הביטוי $i \cdot c_i + (1 - c_i)$ מבטיח שאם הקלף לא בקבוצה 2, כלומר $c_i=0$, נקבל כופל ניטרלי של 1).

פונקציית הכושר המוצעת למקסום (המענישה על סטיות מהיעדים ועל חריגה מאילוץ הגודל):

$$Fitness(C) = \frac{1}{|Sum_1 - 36| + |Prod_2 - 360| + \beta \cdot |Size_2 - 5| + \epsilon}$$

• $\beta$ (מקדם עונש גבוה): גורם לכך שכרומוזום שאינו מחלק את הקלפים ל-5 ו-5 יקבל ציון כושר אפסי, ויסולק מהאוכלוסייה.

• $\epsilon$ (קבוע קטן, למשל 0.001): מונע חלוקה באפס ומבטיח שכאשר מוצאים את הפתרון המושלם, ערך ה-Fitness יזנק ל-$1/\epsilon = 1,000$!

🌟 הפתרון המושלם היחיד בעולם (Global Optimum)

שגיאה = 0

קיים פירוק יחיד ומדויק הפותר את הבעיה באופן מושלם ללא שום סטייה:

קבוצה 1 (סכום 36): קלפים: $\{2, 7, 8, 9, 10\}$
חישוב: $2 + 7 + 8 + 9 + 10 = \mathbf{36}$ ✔️

קבוצה 2 (מכפלה 360): קלפים: $\{1, 3, 4, 5, 6\}$
חישוב: $1 \times 3 \times 4 \times 5 \times 6 = \mathbf{360}$ ✔️

וקטור הכרומוזום המנצח: $C^* = (1, 0, 1, 1, 1, 1, 0, 0, 0, 0)$

🎮 מעבדה אינטראקטיבית 3.1: סימולטור אלגוריתם גנטי חי

התנסו בשינוי הסתברויות המוטציה וההצלבה, הריצו דורות וצפו בהתכנסות לאופטימום הגלובלי

סימולציה פעילה 3.1

יחידה 3.2 טופולוגיית מרחב המצבים ומשפט No Free Lunch

טופולוגיות תועלת והשוואת אלגוריתמי חיפוש מקומי

💡 דברי פתיחה מהמורה הפרטי: משפט No Free Lunch בחיפוש מקומי

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

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

⛰️ 1. ארבעת המכשולים הטופולוגיים במרחבי חיפוש מקומי

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

🏔️

מקסימום מקומי (Local Max)

פסגה שכל שכניה נמוכים ממנה, אך היא נחותה מהאופטימום הגלובלי המרוחק.

🏞️

מישור שטוח (Plateau)

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

⚡

רכס תלול (Ridge)

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

🏰

חפיר עמוק (Moat)

עמק בעל ערך נמוך במיוחד המקיף את המטרה ומחייב צעדים מרעים לחצייתו.

🎯 2. תרגיל ההשוואה מהשיעור: פונקציות תועלת מותאמות שמבטיחות ניצחון

נתונה קבוצה של $N$ איברים, וקיימת תת-קבוצה אידיאלית יחידה $G$. ברצוננו להציע לכל אחד מארבעת האלגוריתמים הבאים פונקציית תועלת ייחודית $u(s)$, אשר תגרום לו למצוא את המטרה $G$ לפני כל שאר האלגוריתמים בהסתברות גבוהה:

🔍 א. חיפוש ממצה (Exhaustive Search)

סיבוכיות: $O(2^N)$

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

$$u(s) = \begin{cases} 1 & s = G \\ 0 & s \neq G \end{cases}$$

💡 הנימוק המתמטי לניצחון המוחלט: פונקציה זו יוצרת מרחב של "מחט בערמת שחת" – שטח שטוח לחלוטין (ערך 0) בכל מקום במרחב, למעט נקודת שיא בודדת ב-$G$.
כל אלגוריתם מקומי (Hill Climbing, Simulated Annealing, Beam Search) יתחיל במצב אקראי שערכו 0. מאחר שכל שכניו יהיו בעלי ערך 0, אין לו שום שיפוע ושום כיוון שיפור, והוא יקפא מיד במקסימום מקומי חסר תוחלת. לעומת זאת, החיפוש הממצה אינו נשען על שיפוע, סורק באופן עיוור ושיטתי, ויגיע בהכרח אל $G$!

➡️ ב. טיפוס גבעה עם מהלכי צד (SAHC with Sideways Moves)

חסם מהלכי צד: Limit

מהות האלגוריתם: טיפוס גבעות המסוגל לצעוד על מישורים שטוחים שבהם ערך התועלת אינו משתנה ($u(s') = u(s)$), עד לרף צעדים מוגדר.

$$u(s) = \begin{cases} 2 & |G \oplus s| < \frac{N}{2} \\ 1 & \text{אחרת} \end{cases}$$

💡 הנימוק המתמטי לניצחון המוחלט: הפונקציה מייצרת "מישור שטוח" רחב בעל ערך קבוע 2 סביב המטרה $G$.
אלגוריתם טיפוס גבעות רגיל ללא מהלכי צד נבלם מיד בכניסה למישור, כי אין אף שכן שמגדיל את הערך מעל 2. חישול מדומה בטמפרטורה גבוהה עלול להתפזר ולהתרחק מהמישור. רק SAHC עם מהלכי צד מנצל את יכולתו לצעוד במישור השטוח, סורק אותו בהתמדה ומוצא את המטרה $G$ המצויה בתוכו!

🔄 ג. טיפוס גבעה עם אתחולים אקראיים (SAHC with Random-Restarts)

תוחלת: $E = 1/p$

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

$$u(s) = N - \min_k |G_k \oplus s| \quad \text{כאשר } G_1 \dots G_k \text{ הן מטרות דמה, ו-} G_{real}=G_1$$

💡 הנימוק המתמטי לניצחון המוחלט: הפונקציה מייצרת מרחב זרוע "גבעות דמה" רבות בעלות אגני משיכה חזקים. כל אלגוריתם בעל סוכן בודד (SAHC רגיל או חישול מדומה) ייפול לתוך אחת מגבעות הדמה הללו, יטפס לפסגתה וייתקע בה לנצח מבלי לדעת שזו מטרה שגויה. לעומת זאת, אלגוריתם Random-Restarts ממשיך לאתחל מנקודות חדשות. הסתברותית, באחד האתחולים הוא ייפול באגן המשיכה של הפסגה האמיתית $G$ ויטפס ישירות אליה!

🔥 ד. חישול מדומה (Simulated Annealing)

בולצמן: $P = e^{\Delta E / T}$

מהות האלגוריתם: מאפשר לבצע צעדים המרעים את המצב הנוכחי בהסתברות יורדת התלויה בטמפרטורה $T$, וכך מחלץ את עצמו ממלכודות.

יצירת "חפיר" (Moat) – עמק עמוק בעל ערך נמוך במיוחד המקיף את המטרה $G$ מכל עבריה.

💡 הנימוק המתמטי לניצחון המוחלט: סביב המטרה קיים אזור שערכו צונח בעוצמה ("חפיר"). שום אלגוריתם ממשפחת ה-Hill Climbing (כולל מהלכי צד או אתחולים) אינו מאפשר צעדים מרעים ($\Delta E < 0$). לכן, גם אם יגיעו לשפת החפיר, הם יסרבו בתוקף לרדת לתוכו ולעולם לא יחצו אותו! לעומת זאת, חישול מדומה בטמפרטורה גבוהה מקבל צעדים מרעים, צולל לתוך החפיר, חוצה אותו, ומעפיל אל היעד $G$ שמעברו השני!

📊 טבלת השוואה מסכמת: טופולוגיות ומנצחים

אלגוריתם	הטופולוגיה המנצחת	הסיבה לעליונותו	נקודת התורפה הקטלנית
חיפוש ממצה	מחט בערמת שחת (0 בכל מקום, 1 ב-$G$)	אינו תלוי בשיפוע; סורק שיטתית ומגיע בהכרח	מרחבים גדולים ($O(2^N)$ פיצוץ קומבינטורי)
טיפוס גבעה + מהלכי צד	מישור שטוח רחב (ערך קבוע סביב $G$)	יודע לצעוד על המישור השטוח מבלי להיתקע	סכנת כניסה ללולאה אינסופית במישור ללא חסם
אתחולים אקראיים	ריבוי פסגות דמה ומקסימומים מקומיים	נוטש מלכודות ומבטיח הסתברותית הגעה לפסגת האמת	איטי ביותר כשאגן המשיכה של המטרה מזערי ($p \to 0$)
חישול מדומה	חפיר עמוק / עמק תלול המקיף את $G$	מסכים לבצע צעדים מרעים, חוצה עמקים ונחלץ	קירור מהיר מדי (Quenching) לוכד אותו במקום

🎮 מעבדה אינטראקטיבית 3.2: זירת מרוץ הטופולוגיות

בחרו טופולוגיה, הריצו את 4 האלגוריתמים במקביל וצפו במשפט No Free Lunch מתממש מול עיניכם

סימולציה פעילה 3.2

יחידה 3.3 מידול אילוצים והוכחות מתמטיות (Constraint Modeling)

בעיית הצבת הפרשים בשחמט ומלכודות מקסימום מקומי

💡 דברי פתיחה מהמורה הפרטי: כשהאלגוריתם נלכד בלוח השחמט

בעיית הפרשים בשחמט היא דוגמה מופתית לאופן שבו מידול מתמטי מדויק של בעיה חושף תובנות עמוקות שחיפוש עיוור לעולם לא היה מגלה.

בבעיה זו אנו מתבקשים להציב מספר מרבי של פרשים על לוח $n \times n$ כך שאף זוג פרשים אינו מאיים זה על זה. מצד אחד, נראה כיצד הוכחה תיאורטית מבריקה המבוססת על צביעת הלוח פותרת את שאלת החסם התחתון ברגע ($\lceil n^2/2 \rceil$). מצד שני, נחקור כיצד אלגוריתם חיפוש מקומי מבוסס טיפוס גבעות (Hill Climbing) עלול להילכד במלכודת מקסימום מקומי אכזרית בתצורת 8 פרשים בלבד (בלוח $5 \times 5$), ונסביר מתמטית מדוע מקדם העונש $\alpha$ מונע ממנו לבצע כל צעד פשוט!

⚙️ 1. ניסוח הבעיה במצב-שלם (Complete-State Formulation)

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

א. מרחב המצבים ($S$)

מטריצה בינארית $n \times n$

כל תא $(i, j)$ מכיל ביט:
• $1$ – מוצב פרש במשבצת.
• $0$ – המשבצת פנויה.
גודל המרחב הכולל: $2^{n^2}$ מצבים אפשריים!

ב. מודל המעברים (Operators)

3 פעולות מקומיות

מעבר ממצב $s$ לשכן $s'$ ע"י:
1. הוספת פרש: הפיכת $0 \to 1$.
2. הסרת פרש: הפיכת $1 \to 0$.
3. הזזת פרש: העברת פרש קיים למשבצת פנויה.

ג. פונקציית הערכה למקסום

תועלת עם קנס קונפליקטים

$$f(s) = \text{Knights}(s) - \alpha \cdot \text{Conflicts}(s)$$

כאשר $\text{Knights}(s)$ הוא מספר הפרשים בלוח, $\text{Conflicts}(s)$ הוא מספר זוגות הפרשים המאיימים הדדית, ו-$\alpha$ הוא מקדם עונש.

🔍 ניתוח רגישות של מקדם העונש $\alpha$: מדוע דרוש $\alpha \ge 2$?

אם $\alpha < 1$: הוספת פרש היוצר קונפליקט בודד תעלה את ערך הפונקציה נטו ($+1 - \alpha > 0$). האלגוריתם "ישתולל", יוסיף פרשים בלי חשבון, ויציף את כל הלוח בפרשים מאיימים!
אם $\alpha = 1$: הוספת פרש עם קונפליקט יחיד היא ניטרלית ($+1 - 1 = 0$), מה שמייצר מישורים שטוחים חסרי מוטיבציה לפתרון הקונפליקט.
כאשר $\alpha \ge 2$ (למשל $\alpha = 2$): כל קונפליקט גורע 2 נקודות, בעוד הפרש מוסיף רק נקודה אחת. השינוי נטו הוא $-1$. לכן האלגוריתם מעדיף תמיד לפתור קונפליקטים על פני הוספת פרשים שמאיימים זה על זה!

📐 2. המשפט המרכזי והוכחת צביעת השחמט

$\lceil n^2 / 2 \rceil$ פרשים

THEOREM

לכל $n$ טבעי, ניתן להציב לפחות $\lceil \frac{n^2}{2} \rceil$ פרשים על לוח $n \times n$ באופן שכל זוג פרשים אינו מאיים זה על זה.

✍️ מהלך ההוכחה המתמטית המלאה (Proof by Bipartite Graph Coloring)

צביעת הלוח: נצבע את לוח המשבצות מסדר $n \times n$ בצביעת שחמט דו-צבעונית קלאסית (שחור ולבן לסירוגין). משבצת $(i, j)$ תיצבע בלבן אם $i + j$ זוגי, ובשחור אם $i + j$ אי-זוגי.
תכונת תנועת הפרש: על פי חוקי השחמט, פרש נע שתי משבצות בכיוון אחד ומשבצת אחת בכיוון ניצב (תנועת L). שינוי הקואורדינטות מקיים: $$(\Delta i, \Delta j) \in \{(\pm 1, \pm 2), (\pm 2, \pm 1)\} \implies \Delta i + \Delta j \in \{\pm 3, \pm 1\}$$ בכל המקרים, סכום השינויים הוא מספר אי-זוגי! המשמעות היא שזוגיות הסכום $i+j$ מתהפכת תמיד. לפיכך, תנועת הפרש מעבירה אותו תמיד ממשבצת בצבע אחד למשבצת בצבע הנגדי (מלבן לשחור, או משחור ללבן).
גרף דו-צדדי (Bipartite Graph): נבנה גרף שבו הקודקודים הם משבצות הלוח, וקשת מחברת שני קודקודים אם פרש יכול לאיים מאחת על השנייה. מכיוון שפרש מאיים רק על משבצות מהצבע הנגדי, כל הקשתות בגרף מחברות אך ורק בין קודקוד לבן לקודקוד שחור. אין אף קשת בין שני קודקודים לבנים, ואין אף קשת בין שני קודקודים שחורים!
הצבה על צבע הרוב: נציב את כל הפרשים שלנו אך ורק על המשבצות הלבנות (קבוצת צבע הרוב). מאחר שאין שום קשת בין שתי משבצות לבנות, קבוצת המשבצות הלבנות מהווה תת-קבוצה בלתי-תלויה (Independent Set) בגרף האיומים. לפיכך, אף פרש אינו יכול לאיים על שום פרש אחר!
חישוב הכמות: בלוח $n \times n$ ישנן $n^2$ משבצות בסך הכל. בצביעת שחמט, מספר המשבצות בצבע הרוב הוא לפחות מחצית מהלוח, כלומר מעוגל כלפי מעלה: $\lceil \frac{n^2}{2} \rceil$.
מסקנה: על ידי הצבת פרשים בכל משבצות צבע הרוב, קיבלנו סידור חוקי של לפחות $\lceil \frac{n^2}{2} \rceil$ פרשים ללא שום איום הדדי. Q.E.D. / מ.ש.ל.

לוח 4x4 (16 משבצות) $\lceil 16/2 \rceil = 8$ פרשים

לוח 5x5 (25 משבצות) $\lceil 25/2 \rceil = 13$ פרשים

לוח 8x8 (64 משבצות) $\lceil 64/2 \rceil = 32$ פרשים

🛑 3. ניתוח מלכודת המקסימום המקומי בלוח $5 \times 5$

מלכודת קלאסית

בלוח $5 \times 5$ המקסימום הגלובלי הוא 13 פרשים (על פי הנוסחה המוצהרת). אולם, אלגוריתם טיפוס גבעות פשוט (Hill Climbing) עלול להגיע לתצורת 8 פרשים בלבד ולהיתקע בה לחלוטין!

🕸️ מדוע זוהי מלכודת מקסימום מקומי שממנה אי אפשר לצאת?

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

1. ניסיון להוסיף פרש חדש:

כל משבצת פנויה כבר מאוימת. לכן, הצבת פרש נוסף תיצור מיד קונפליקט אחד לפחות!
השינוי בפונקציית התועלת: $$\Delta f = +1 - \alpha \times 1 = 1 - 2 = -1 < 0$$ ערך הפונקציה יורד, ולכן טיפוס גבעות מסרב לבצע את המהלך!

2. ניסיון להסיר פרש קיים:

הסרת פרש מפחיתה ישירות את מספר הפרשים מ-8 ל-7. מאחר שטרם ההסרה לא היו קונפליקטים, אין קונפליקטים שנפתרים.
השינוי בפונקציית התועלת: $$\Delta f = -1 - 0 = -1 < 0$$ גם כאן ערך הפונקציה יורד, וטיפוס גבעות מסרב לבצעו!

מסקנה: אין אף שכן מקומי המשפר את ערך $f(s)$. המצב מהווה מקסימום מקומי חסר מוצא עבור Hill Climbing!

💡 כיצד מחלצים את האלגוריתם ממלכודת 8 הפרשים?

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

🎮 מעבדה אינטראקטיבית 3.3: לוח שחמט דינמי ומלכודת פרשים

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

סימולציה פעילה 3.3

יחידה 3.4 תורת המשחקים בבינה מלאכותית (Adversarial Search & Games)

מבוא לחיפוש בתנאי יריבות ומאפייני משחקים

💡 דברי פתיחה מהמורה הפרטי: כשהסביבה הופכת לעוינת ואינטליגנטית

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

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

📋 1. שבעת המרכיבים הפורמליים של בעיית משחק

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

מרכיב 1 $A_1 \dots A_n$

קבוצת הסוכנים (Agents)

רשימת כל השחקנים המשתתפים במשחק. במשחק 2 שחקנים: $\{MAX, MIN\}$.

מרכיב 2 $S, s_0$

מרחב המצבים והמצב ההתחלתי

קבוצת כל התצורות החוקיות של המשחק ($S$), והקונפיגורציה שבה המשחק נפתח ($s_0$).

מרכיב 3 $\text{Turn}(s)$

פונקציית התור

$\text{Turn}: S \to \{1 \dots n\}$. מחזירה את אינדקס השחקן שזהו תורו לפעול במצב $s$.

מרכיב 4 $\text{Succ}(s, i)$

פונקציית המצבים העוקבים

מחזירה את קבוצת כל המצבים החוקיים הבאים שהשחקן $i$ יכול להעביר אליהם מהמצב $s$.

מרכיב 5 $G(s) \in \{T, F\}$

בדיקת סיום (Terminal Test)

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

מרכיב 6 $U(s, i)$

פונקציית התועלת / ערך (Utility)

$U: S_G \times \{1 \dots n\} \to \mathbb{R}$. מחזירה את הציון/הרווח המספרי של שחקן $i$ במצב הסופי $s$.

⚖️ תכונות יסוד מרכזיות של משחקים אדברסריים

1. תור מתחלף (Alternating Turns) בכל צעד תורו של השחקן משתנה בהכרח: $$\forall q \in \text{Succ}(s, \text{Turn}(s)): \text{Turn}(s) \neq \text{Turn}(q)$$

2. משחק 2 שחקנים סכום אפס (Zero-Sum) הרווח של שחקן 1 שווה בדיוק להפסד של שחקן 2: $$\forall s \in S_G: \quad U(s, 1) = -U(s, 2)$$ ציונים נפוצים: $+1$ לניצחון, $-1$ להפסד, $0$ לתיקו.

3. משחק K שחקנים סכום אפס סכום הרווחים של כל $K$ השחקנים מתאפס: $$\forall s \in S_G: \quad \sum_{i=1}^K U(s, i) = 0$$

📊 2. סיווג משחקים לפי רמת המידע והאקראיות

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

סוג המשחק	דטרמיניסטי (Deterministic)	אי-דטרמיניסטי / אקראי (Chance)
אינפורמציה מלאה Full Information (כל השחקנים רואים את כל המצב תמיד)	שחמט, דמקה, איקס-עיגול, גו (Go) אין שום קוביות ואין שום קלפים מוסתרים. כל הלוח גלוי ב-100%. תוצאת כל מהלך ידועה מראש ללא שום אי-ודאות. נפתר ישירות בעזרת Minimax ו-Alpha-Beta.	שש-בש (Backgammon), מונופול לוח המשחק ומיקום כל הכלים גלויים לחלוטין לכולם, אך הצעדים האפשריים נקבעים על פי הטלת קוביות אקראית. מחייב שילוב צמתי סיכוי באלגוריתם (Expectiminimax).
אינפורמציה חלקית Partial Information (מידע נסתר מעיני חלק מהשחקנים)	צוללות (Battleship), סטרטגו (Stratego) אין קוביות ואין אקראיות במהלכים, אך מיקומי כלי היריב מוסתרים. הסוכן נדרש לבצע היקשים הסתברותיים ובייסיאניים על מצב הלוח הנסתר.	פוקר, ברידג', רמי, ריסק (Risk) פסגת המורכבות! שילוב של קלפים מוסתרים בידי היריבים (מידע חלקי) יחד עם ערבוב חפיסה אקראי והטלות קוביות בקרבות. דורש בלוף (Bluffing) ומודלים של תורת המשחקים.

🌳 3. עץ משחק (Game Tree) לעומת עץ אסטרטגיה (Strategy Tree) של MAX

לעיתים קרובות סטודנטים מבלבלים בין עץ המשחק השלם לבין עץ האסטרטגיה של שחקן נתון. ההבדל ביניהם עקרוני וקריטי למבחן:

עץ משחק (Game Tree)

מרחב מלא

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

עץ אסטרטגיה (Strategy Tree) של MAX

תוכנית פעולה

מייצג מדיניות בחירה ספציפית (Policy) עבור שחקן MAX בלבד:
• בצמתי MAX (צמתי OR): נבחר ענף בודד (המהלך המועדף האופטימלי ש-MAX מתכוון לבצע).
• בצמתי MIN (צמתי AND): נשמרים כל הענפים החוקיים! שחקן MAX אינו שולט ביריב, ולכן תוכנית הפעולה שלו חייבת להחזיק מענה מוכן לכל תגובה אפשרית ש-MIN יבחר.

המחשה ויזואלית: עץ אסטרטגיה של שחקן MAX OR Nodes vs AND Nodes

שורש: צומת MAX (צומת OR) MAX בוחר בענף שמאל בלבד!

│ (מהלך נבחר: שמאלה)

צומת MIN (צומת AND) שומרים את כל תגובות MIN האפשריות!

תגובה 1 (שמאל) | תגובה 2 (ימין)

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

יחידה 3.5 קבלת החלטות אופטימלית במשחקי סכום אפס

אלגוריתם מינימקס (Minimax Algorithm)

💡 דברי פתיחה מהמורה הפרטי: לחשוב קדימה כמו רב-אמן

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

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

📐 1. ההגדרה הרקורסיבית הפורמלית של מינימקס

ערך המינימקס של מצב $s$ מוגדר ברקורסיה על פי שלושה מקרים:

$$Minimax(s, k) = \begin{cases} U(s, k) & \text{אם } G(s) \text{ (מצב סופי / עלה בעץ)} \\ \max_{c \in \text{Succ}(s)} Minimax(c, k) & \text{אם } \text{Turn}(s) = k \text{ (תור שחקן MAX)} \\ \min_{c \in \text{Succ}(s)} Minimax(c, k) & \text{אם } \text{Turn}(s) \neq k \text{ (תור היריב MIN)} \end{cases}$$

הסבר האינטואיציה: החיפוש צולל לעומק העץ עד למצבי הסיום (העלים), שם מחושבת התועלת הפיזית $U(s)$. לאחר מכן, הערכים מתחילים לחלחל כלפי מעלה:
• צומת של MAX לוקח את המקסימום מבין כל בניו (כי MAX שואף להרוויח כמה שיותר).
• צומת של MIN לוקח את המינימום מבין כל בניו (כי MIN רוצה להוריד את הרווח של MAX למינימום).

📜

משפט המינימקס המרכזי והבטחת התועלת (The Central Minimax Theorem)

משפט ג'ון פון נוימן לתורת המשחקים והבטחת התועלת

$$\text{אם שחקן MAX משחק לפי אסטרטגיית מינימקס לעומק } D, \text{ אזי מובטחת לו תועלת של לפחות } M$$ $$\forall \pi_{MIN}: \quad V(MAX) \ge M = Minimax(s_0, D)$$

משמעות המשפט ופרשנות אסטרטגית מקיפה:

חסינות מוחלטת ללא תלות באסטרטגיית היריב: ההבטחה לתועלת $M$ (ערך המינימקס של מצב ההתחלה) מתקיימת ללא תלות באסטרטגיה שיבחר היריב MIN! היריב אינו מסוגל בשום תרחיש להוריד את התועלת של MAX מתחת ל-$M$.
יריב רציונלי ואופטימלי: אם היריב MIN משחק ללא רבב ומממש את המהלכים הממזערים ביותר בכל צעד, המשחק יסתיים בתועלת של בדיוק $M$.
יריב שוגה או תת-אופטימלי: אם היריב MIN שוגה או בוחר מהלך פחות מאידיאלי, התועלת שתתקבל עבור MAX רק תעלה מעבר ל-$M$ ($V > M$)! שגיאות היריב לעולם אינן פוגעות ב-MAX כשהוא משחק מינימקס.
עקרון המשחק הבטוח ביותר (Worst-Case Guarantee / Maximin): אלגוריתם מינימקס אינו מהמר ואינו מסתמך על "מזל" או קריאת מחשבות. הוא מתוכנן מול תרחיש היריב המסוכן ביותר (Pessimistic Worst-Case), ולכן מספק רשת ביטחון מתמטית מוחלטת.

🔍 2. מעקב חישוב שלב-אחר-שלב: עץ עומק 3 מהשיעור

12 עלי תועלת

נתון עץ משחק בעומק 3 (השורש הוא MAX, מתחתיו 3 צמתי MIN, מתחתיהם 6 צמתי MAX, ובתחתית 12 עלים).
ערכי התועלת של העלים (משמאל לימין) הם:

[+3, +5, -1, +2, -3, -2, -4, +1, -5, -1, -4, +5]

תרשים פריסת עץ המשחק וזרימת התועלות Minimax Flow Trace

רמה 0: שורש MAX ערך: +2 max(+2, -2, -1)

↙ (שמאל: +2) ↓ (אמצע: -2) ↘ (ימין: -1)

MIN ענף שמאל +2 min(+5, +2)

MIN ענף אמצע -2 min(-2, +1)

MIN ענף ימין -1 min(-1, +5)

MAX 1 +5

MAX 2 +2

MAX 3 -2

MAX 4 +1

MAX 5 -1

MAX 6 +5

+3 +5 -1 +2 -3 -2 -4 +1 -5 -1 -4 +5

שלב 1: חישוב רמת ה-MAX התחתונה (6 צמתים)

• תת-עץ 1: $\max(+3, +5) = \mathbf{+5}$
• תת-עץ 2: $\max(-1, +2) = \mathbf{+2}$
• תת-עץ 3: $\max(-3, -2) = \mathbf{-2}$
• תת-עץ 4: $\max(-4, +1) = \mathbf{+1}$
• תת-עץ 5: $\max(-5, -1) = \mathbf{-1}$
• תת-עץ 6: $\max(-4, +5) = \mathbf{+5}$

שלב 2: חישוב רמת ה-MIN האמצעית (3 צמתים)

• ענף שמאלי של MIN: $\min(+5, +2) = \mathbf{+2}$
• ענף אמצעי של MIN: $\min(-2, +1) = \mathbf{-2}$
• ענף ימני של MIN: $\min(-1, +5) = \mathbf{-1}$

שלב 3: חישוב שורש ה-MAX (החלטת המשחק הסופית)

$$\text{Root} = \max(+2, -2, -1) = \mathbf{+2}$$

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

⚖️ 3. ארבע התכונות הפורמליות של אלגוריתם המינימקס

שלמות (Completeness) כן (בעץ סופי)

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

אופטימליות (Optimality) כן (מול יריב אופטימלי)

מבטיח את תוצאת המינימום הגבוהה ביותר (Worst-case guarantee). אם היריב שוגה, מינימקס ישיג תוצאה טובה אף יותר!

סיבוכיות זמן (Time) $O(b^m)$

מעריכית קטסטרופלית! כמו BFS, האלגוריתם חייב לסרוק את כל העלים בעץ כדי למצוא את המקסימום/מינימום.

סיבוכיות מקום (Space) $O(bm)$

לינארית בעומק העץ! מכיוון שמינימקס ממומש ברקורסיית DFS, מחסנית הקריאות שומרת רק את המסלול הפעיל.

🎮 מעבדה אינטראקטיבית 3.4: חוקר עץ מינימקס ועריכת עלים

לחצו על כל עלה בעץ לשנות את ערכו, וצפו בזמן אמת בשינוי חלחול התועלות ובבחירת האסטרטגיה

סימולציה פעילה 3.4

יחידה 3.6 אופטימיזציית חיפוש יריבותי (Optimization in Games)

גיזום אלפא-בטא ($\alpha-\beta$ Pruning) וחיפוש מוגבל משאבים

💡 דברי פתיחה מהמורה הפרטי: כשהאלגוריתם לומד "לחתוך" את המיותר

במשחקים אמיתיים כמו שחמט, גורם הסיעוף הממוצע הוא $b \approx 35$, ואורך משחק טיפוסי הוא כ-50 מהלכים לכל צד (עומק $m \approx 100$). עץ המשחק המלא מכיל $35^{100} \approx 10^{154}$ צמתים – מספר הגדול ממספר האטומים ביקום הנראה כולו! אפילו מחשב-העל המהיר ביותר בעולם לא יוכל לחשב מינימקס מלא אפילו עד עומק 10 בזמן סביר.

כאן נכנסת לתמונה אחת מפריצות הדרך המבריקות בתולדות מדעי המחשב: אלגוריתם גיזום אלפא-בטא ($\alpha-\beta$ Pruning). הרעיון הוא פשוט ואלגנטי להפליא: במהלך הסריקה לעומק (DFS), אנחנו שומרים שני חסמים מתמטיים ($\alpha$ ו-$\beta$). ברגע שאנו מגלים ענף שהיריב בחיים לא יאפשר לנו להגיע אליו (או שאנחנו כבר מחזיקים בחלופה טובה ממנו בהרבה), אנחנו גוזמים את כל שאר הענף מיד ללא חישוב! והקסם הגדול ביותר: הגיזום אינו פוגע באופטימליות ההחלטה אפילו באלפית האחוז! בואו נלמד את חוקי הגיזום ואת הכללים המעשיים להגבלת משאבים.

✂️ 1. הגדרת החסמים $\alpha$ ו-$\beta$ וחוקי הגיזום הפורמליים

במהלך הסריקה לעומק (DFS) של עץ המשחק, אנו מעבירים מטה במורד הענף שני משתנים המהדקים את חלון הבדיקה:

החסם α (אלפא)

מאתחל: $-\infty$

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

• מעודכן אך ורק בצמתי MAX: $\alpha = \max(\alpha, v)$.
• אלפא תמיד עולה בערכה (או נשארת קבועה).

החסם β (ביתא)

מאתחל: $+\infty$

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

• מעודכן אך ורק בצמתי MIN: $\beta = \min(\beta, v)$.
• ביתא תמיד יורדת בערכה (או נשארת קבועה).

🛑 שני חוקי הגיזום: מתי עוצרים את החישוב?

1. גיזום בצומת MAX (מכונה "גיזום ביתא" - Beta Cutoff): תנאי: $v \ge \beta$

אם צומת MAX מחשב את אחד מבניו ומגלה ערך $v$ הגדול או שווה לחסם $\beta$ של אב קדמון מסוג MIN:
מדוע גוזמים? שחקן MIN שנמצא מעלינו כבר מצא חלופה בעלת ערך $\beta$. מאחר שצומת MAX הנוכחי שלנו יבחר ערך של לפחות $v$ (הגדול מ-$\beta$), שחקן MIN לעולם לא יאפשר למשחק להגיע לצומת שלנו! אין שום טעם להמשיך לבדוק את שאר הבנים של MAX – עוצרים וגוזמים מיד!

2. גיזום בצומת MIN (מכונה "גיזום אלפא" - Alpha Cutoff): תנאי: $v \le \alpha$

אם צומת MIN מחשב את אחד מבניו ומגלה ערך $v$ הקטן או שווה לחסם $\alpha$ של אב קדמון מסוג MAX:
מדוע גוזמים? שחקן MAX שנמצא מעלינו כבר מחזיק בחלופה מובטחת בעלת ערך $\alpha$. מאחר שצומת MIN יבחר ערך של לכל היותר $v$ (הקטן מ-$\alpha$), שחקן MAX לעולם לא יבחר לרדת לצומת זה! כל שאר בניו של MIN נגזמים מיד!

🛡️

שמירה מוחלטת על אופטימליות: גיזום אלפא-בטא אינו אלגוריתם קירוב! הוא מבוסס על הוכחה מתמטית מדויקת שהענפים הנגזמים מעולם לא היו יכולים להשפיע על ערך השורש. ההחלטה המוחזרת זהה ב-100% למינימקס מלא!

⚡ 2. השפעת סדר פתיחת הבנים (Move Ordering): מכפיל העומק וגורם הסיעוף האפקטיבי

$O(b^{d/2})$

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

סדר אופטימלי (Perfect Ordering)

$O(b^{d/2})$

בצמתי MAX אנו בודקים קודם את המהלכים הטובים ביותר ל-MAX, ובצמתי MIN אנו בודקים קודם את המהלכים הטובים ביותר ל-MIN.
התוצאה: החסמים מתהדקים בשיא המהירות, ורוב הענפים המיותרים נגזמים מיד. סיבוכיות הזמן יורדת בחצי במעריך!
💡 המשמעות המעשית: המחשב מסוגל לחקור עמוק פי שניים באותו תקציב זמן ריצה! (למשל, עומק 12 במקום עומק 6 בשחמט!).

סדר גרוע ביותר (Worst Ordering)

$O(b^d)$

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

📐 הניתוח המתמטי של מספר העלים וגורם הסיעוף האפקטיבי

1. סדר בנים אידיאלי

$$N_{leaves} = b^{\lceil d/2 \rceil} + b^{\lfloor d/2 \rfloor} - 1 \approx 2 \cdot b^{d/2}$$ $$b_{eff} = \sqrt{b}, \quad O(b^{d/2})$$

במקום $b$ בנים, כאילו לכל צומת יש רק $\sqrt{b}$ בנים!

2. סדר בנים אקראי (ממוצע)

$$O\left( \left(\frac{b}{\ln b}\right)^d \right)$$ $$b_{eff} \approx \frac{b}{\ln b}$$

שיפור משמעותי גם ללא יוריסטיקה מושלמת.

3. סדר בנים גרוע ביותר

$$N_{leaves} = b^d$$ $$b_{eff} = b, \quad O(b^d)$$

אין שום גיזום, שקול למינימקס מלא.

המחשה מספרית לשחמט ($b \approx 35, d = 10$):
• במינימקס מלא נדרש לחשב $35^{10} \approx 2.75 \times 10^{15}$ צמתים.
• באלפא-בטא אידיאלי גורם הסיעוף צונח ל-$\sqrt{35} \approx 5.91$, ומספר העלים הצפוי הוא רק $2 \cdot 35^5 \approx 105,000,000$ צמתים – חיסכון בלתי נתפס של פי $26,000,000$ בזמן הריצה!

🎯 חמש היוריסטיקות מעשיות לסידור מסעים במשחקי לוח (Move Ordering Hierarchy)

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

1. לכידות כלים (MVV-LVA)

Most Valuable Victim - Least Valuable Attacker: מכה של כלי בעל ערך גבוה עם כלי זול (למשל רגלי מכה מלכה) נבדקת ראשונה, לפני הכאת רגלי עם צריח.

2. שח ואיומים טקטיים ישירים

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

3. טבלאות טרנספוזיציה (TT)

מטמון (Hash Table) הזוכר עמדות שכבר נותחו בענף קודם. אם העמדה נראתה, המהלך הטוב ביותר שנרשם נבדק ראשון מיד.

4. היוריסטיקת מהלכי רוצח (Killer Move)

מהלך שקט (לא לכידה) שגרם לגיזום ביתא בעומק $d$ בענף שכן זוכה לעדיפות בדיקה ראשונה בכל שאר הצמתים באותו עומק.

5. היוריסטיקת היסטוריה (History Heuristic)

שמירת מונה הצלחות לכל צמד משבצות $(from, to)$. מהלכים שיצרו גיזומים תכופים בכל רחבי העץ נבדקים מוקדם.

6. העמקה איטרטיבית (Iterative Deepening)

הרצת חיפוש לעומק $1, 2, 3 \dots$ תוך שימוש בסדר המהלכים המנצח של איטרציה $k-1$ כסדר הבדיקה הראשי של איטרציה $k$.

⏱️ 3. שיקולים מעשיים, הגבלת משאבים ופונקציות הערכה יוריסטיות

בעולם האמיתי, לא ניתן להגיע לעלים של עץ המשחק בגלל מגבלות זמן (למשל 3 דקות למהלך). לכן מיישמים חיפוש מוגבל משאבים (Resource-Limited Search):

א. חיתוך עומק ופונקציית הערכה (Cutoff & Evaluation Function)

עוצרים את החיפוש בעומק קבוע $D$ (למשל $D=8$). במקום ערך תועלת אמיתי של סיום משחק, מעריכים את המצב באמצעות פונקציית הערכה יוריסטית $h(s)$ (למשל בשחמט: ספירת שווי הכלים + שליטה במרכז הלוח + הגנת המלך).

⚠️ חוק ברזל קריטי לעיצוב ערכי תועלת במצבי סיום!

ערכי התועלת האמיתיים של ניצחון והפסד במצבי סיום ($U(s) \in \{+\infty, -\infty\}$ או מספר עתק כמו $+1,000,000$) חייבים להיות קיצוניים וגבוהים משמעותית מכל ציון יוריסטי אפשרי של מצב ביניים!
הסכנה באשליה טקטית: אם ניצחון מוחלט יקבל ערך $+100$, ומצב ביניים עם יתרון כלים יקבל ערך $+120$, האלגוריתם עלול להעדיף מצב ביניים שנראה "מבטיח" על פני מהלך שמוביל ישירות לניצחון ודאי ולסיום המשחק!

🦤 ב. אפקט האופק ("תופעת בת-היענה" - The Horizon Effect) וחיפוש השקט (Quiescence Search)

תופעת בת-היענה (The Ostrich Effect):

בת-היענה טומנת ראשה בחול מתוך אשליית שווא שאם אינה רואה את הסכנה – הסכנה אינה קיימת! באופן דומה, כאשר אסון טקטי בלתי-נמנע (כגון לכידת מלכה על ידי היריב) עומד להתרחש בדיוק צעד אחד מעבר לעומק החיתוך $D$ ($d = D+1$), אלגוריתם חיתוך עיוור אינו "רואה" את האסון.

מלכודת מהלכי ההשהיה: האלגוריתם מגלה שאם יבצע מהלכי סרק חסרי ערך – כגון מתן סדרת שחים חסרי תוחלת או הקרבת רגלים ופרשים – הוא יכול לדחות את לכידת המלכה אל מעבר לאופק החיתוך (לעומק $D+2$). כתוצאה מכך, בעומק $D$ המלכה עדיין על הלוח, והאלגוריתם "שמח" ובוחר במסלול ההרסני שבו בזבז את כל כליו, במקום להשלים עם לכידת המלכה מוקדם ולשמור על שאר צבאו!

הפתרון: חיפוש השקט (Waiting for Quiescence / Quiescence Search):

במקום לחתוך את העץ באופן נוקשה ושרירותי בעומק $D$, האלגוריתם בודק האם המצב בעומק $D$ הוא מצב סוער (Turbulent State) – למשל: קיים שח פעיל, כלי יקר מאוים, או בעיצומה של החלפת כלים (שרשרת לכידות).

אם המצב אינו שקט ($\text{Quiescent}(s) = \text{False}$), האלגוריתם מרחיב באופן דינמי את עומק החיפוש.
במהלך חיפוש השקט נחקרים אך ורק מהלכים טקטיים (לכידות כלים ושחים), ללא הרחבת מהלכים עיוורים.
רק כאשר מגיעים למצב שקט ויציב שבו אין לכידות פעילות, מופעלת פונקציית ההערכה היוריסטית $h(s)$ ומחזירה ציון אמין המשקף שיווי משקל אמיתי על הלוח.

שאלת דגל ממבחני הקורס מעקב חישוב אלפא-בטא מלא ומדויק

🌳 מעקב שלב-אחר-שלב: עץ משחק שלם בן 31 עלים, 18 נבדקים ו-13 נגזמים

נתון עץ משחק אדברסרי מלא בעומק 3. השורש הוא צומת MAX (צומת A). מ-A יוצאים 3 ענפים לצמתי MIN (צמתים B, C, D). מתחת לכל צומת MIN נמצאים צמתי MAX, ומתחתם עלי תועלת סופיים. בסך הכל, עץ המשחק השלם מכיל 31 עלי תועלת (משמאל לימין).
אלגוריתם גיזום אלפא-בטא סורק את העץ בסדר עומק משמאל לימין (DFS), תוך עדכון חסמי $[\alpha, \beta]$. בסיום הסריקה, נבדקים בדיוק 18 עלים ונחתכים 13 עלים באמצעות 4 אירועי גיזום (2 גיזומי אלפא ו-2 גיזומי ביתא)!

סה"כ עלים בעץ מלא 31

עלים שנבדקו בפועל 18 (58% מהעץ)

עלים שנחתכו (נגזמו) 13 (42% חיסכון!)

ערך המינימקס בשורש A V = 6 ענף נבחר: B

שרטוט טופולוגי: מבנה עץ המשחק ומוקדי הגיזום 3 Branches: B (Left), C (Center), D (Right)

[MAX] שורש A: [α = 6, β = +∞] ⟵ מקבל ערך 6 מענף B

[MIN] צומת B: β = 6

בנים: MAX1, MAX2

• MAX1: עלים [5, 6, 2] ⟹ v = 6

• MAX2: עלים [7, 4, 8, 3] ⟹ עלה ראשון 7 $\ge \beta=6$

✂️ גיזום ביתא! נחתכים 3 עלים: [4, 8, 3]

נבדקו: 4 | נגזמו: 3

[MIN] צומת C: α = 6

בנים: MAX3, MAX4, MAX5

• MAX3: עלים [3, 4, 1, 2] ⟹ v = 4

• מכיוון ש-v = 4 $\le \alpha = 6$:

✂️ גיזום אלפא! נחתכים ענפי MAX4 ו-MAX5

נחתכים 6 עלים של MAX4 ו-MAX5

נבדקו: 4 | נגזמו: 6

[MIN] צומת D: α = 6

בנים: MAX6, MAX7

• MAX6: עלים [2, 5, 4, 3, 1] ⟹ v = 5

• מכיוון ש-v = 5 $\le \alpha = 6$:

✂️ גיזום אלפא! נחתך ענף MAX7 (4 עלים)

• במקום 14 עלים נבדקים 10 בלבד בענף הימני

נבדקו: 10 | נגזמו: 4

צעד	צומת / עלה	סוג צומת	ערך מחושב	חלון [α, β]	פעולה אלגוריתמית, עדכון חסמים וגיזום
1-3	MAX1 (עלים 1, 2, 3)	MAX	v = 6	[-∞, +∞]	נבדקים עלים 5, 6, 2. המקסימום הוא 6. ערך 6 מוחזר לצומת האב MIN ב-B.
4	עדכון צומת B	MIN	β = 6	[-∞, 6]	צומת B מעדכן את חסם ביתא: $\beta = \min(+\infty, 6) = 6$. החלון מועבר לבן הבא MAX2.
5	MAX2 (עלה 4)	MAX	v = 7	[-∞, 6]	אירוע גיזום 1 (Beta Cutoff): נבדק עלה ראשון בעל ערך 7. מאחר ש-$v = 7 \ge \beta = 6$, מתקיים תנאי גיזום ביתא! ✂️ 3 עלים נגזמים מיד ב-MAX2 [עלים 5, 6, 7]!
6	עדכון שורש A	MAX	α = 6	[6, +∞]	ענף B סיים והחזיר 6 לשורש A. שורש A מעדכן את חסם אלפא שלו: $\alpha = \max(-\infty, 6) = 6$.
7-10	ענף C: MAX3	MAX	v = 4	[6, +∞]	נבדקים 4 עלים מתחת ל-MAX3 שערכיהם [3, 4, 1, 2]. ערך המקסימום המוחזר הוא 4.
11	בדיקת צומת C	MIN	v = 4	[6, +∞]	אירוע גיזום 2 (Alpha Cutoff): צומת C מקבל ערך 4 ומעדכן $\beta = \min(+\infty, 4) = 4$. כעת מתקיים $\beta = 4 \le \alpha = 6$! ✂️ גיזום אלפא ענקי! נחתכים כל שאר בניו של C (הצמתים MAX4 ו-MAX5 המכילים 6 עלים)!
12-16	ענף D: MAX6	MAX	v = 5	[6, +∞]	נבדקים 5 עלים מתחת ל-MAX6: [2, 5, 4, 3, 1]. ערך המקסימום הוא 5.
17-18	בדיקת צומת D	MIN	v = 5	[6, +∞]	אירוע גיזום 3 (Alpha Cutoff): צומת D מעדכן $\beta = \min(+\infty, 5) = 5$. מתקיים שוב $\beta = 5 \le \alpha = 6$! ✂️ גיזום אלפא! נחתך הבן MAX7 (המכיל 4 עלים נוספים)!
סיום	הכרעת שורש A	MAX	V = 6	[6, 6]	החלטת MAX: מהלך שמאלה אל צומת B! ערך התועלת המובטח לשחקן MAX הוא לפחות 6. נבדקו בסך הכל: 3+1+4+5+5 = 18 עלים בלבד. נגזמו: 3+6+4 = 13 עלים.

💡 תובנות מפתח לפתרון שאלות גיזום אלפא-בטא במבחן:

העברת חסמים כלפי מטה: כאשר יורדים לצומת בן, הוא תמיד יורש במדויק את חלון $[\alpha, \beta]$ של האב שהוליד אותו.
חזרת ערכים כלפי מעלה: צומת MAX מעדכן אך ורק את החסם $\alpha = \max(\alpha, v)$. צומת MIN מעדכן אך ורק את החסם $\beta = \min(\beta, v)$.
זיהוי מידי של גיזום: בכל צומת (MAX או MIN), ברגע שמתקיים $\alpha \ge \beta$, עוצרים מיד את בדיקת שאר הבנים וגוזמים את התת-עץ כולו!
עלים שלא נבדקו: ערכם המספרי של העלים הנגזמים אינו ידוע ואינו רלוונטי כלל – אפילו אם בעלה הנגזם היה רשום $+1,000,000$, היריב (או אנחנו) לעולם לא היינו מגיעים לשם!

🎮 מעבדה אינטראקטיבית 3.5: גיזום אלפא-בטא חי וסדר מהלכים

השוו הרצה בסדר אופטימלי מול סדר גרוע, צפו בענפים הנגזמים בזמן אמת ועקבו אחר חסמי [α, β]

סימולציה פעילה 3.5

יחידה 3.7 אינדקס מסכם, טיפים למבחן וגשר קדימה

מילון מושגים, סיכום וגשר לפרק 4

💡 דברי סיכום מהמורה הפרטי: השלמת אבן דרך קריטית בקורס

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

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

📚 1. מילון מונחי מפתח דו-לשוני (Bilingual Key Terms)

12 המונחים המרכזיים של פרק 3 שחובה לשלוט בהם במדויק לקראת הבחינה:

1. Chromosome / Individual כרומוזום / פרט

ייצוג וקטורי של מצב שלם בעולם הפתרונות של אלגוריתם גנטי (לרוב מחרוזת ביטים).

2. Fitness Function פונקציית כשירות / התאמה

פונקציה המקצה ציון הישרדות מספרי לכל כרומוזום; מהווה בסיס לסיכויי הבחירה ברבייה.

3. Crossover & Mutation הצלבה ומוטציה

הצלבה משלבת מקטעים מההורים (Exploitation), בעוד מוטציה הופכת ביט אקראי למניעת קיפאון (Exploration).

4. Roulette Wheel Selection בחירת גלגל הרולטה

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

5. Zero-Sum Game משחק סכום אפס

משחק שבו רווח של שחקן אחד שווה במדויק להפסדו של השחקן היריב ($U_1 = -U_2$).

6. Strategy Tree עץ אסטרטגיה של MAX

תת-עץ שבו ל-MAX נבחר ענף יחיד מועדף (צומת OR), ואילו ל-MIN נשמרות כל התגובות האפשריות (צומת AND).

7. Minimax Algorithm אלגוריתם מינימקס

אלגוריתם רקורסיבי הקובע את ההחלטה האופטימלית ע"י מקסום תועלת MAX ומזעור תועלת MIN.

8. Beta Cutoff גיזום ביתא (בצומת MAX)

מתבצע בצומת MAX כאשר נמצא ערך $v \ge \beta$. שחקן MIN שנמצא מעלינו לעולם לא יאפשר זאת!

9. Alpha Cutoff גיזום אלפא (בצומת MIN)

מתבצע בצומת MIN כאשר נמצא ערך $v \le \alpha$. שחקן MAX שנמצא מעלינו כבר מחזיק בחלופה טובה יותר!

10. Move Ordering סדר פתיחת מהלכים

סדר בחינת הבנים. סדר אופטימלי מוריד סיבוכיות ל-$O(b^{m/2})$ ומאפשר לחקור עמוק פי 2 באותו זמן!

11. Horizon Effect אפקט האופק

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

12. Quiescence Search חיפוש שקט

המשך החיפוש מעבר לסף העומק במצבים לא יציבים (הכאות כלים) כדי להעריך את המצב רק כשהוא רגוע.

⚖️ 2. טבלת השוואה כוללת: אלגוריתמי פרק 3

אלגוריתם	סוג הבעיה	זמן	מקום	שלם?	אופטימלי?
אלגוריתם גנטי (GA)	חיפוש מקומי במצב-שלם	תלוי דורות	$O(N \cdot L)$	לא מובטח	לא מובטח
חיפוש ממצה (Exhaustive)	סריקה עיוורת שיטתית	$O(2^N)$	$O(1)$	כן	כן
SAHC עם מהלכי צד	מישורים שטוחים	תלוי חסם	$O(1)$	לא	לא
Random Restarts	ריבוי פסגות דמה	תוחלת $1/p$	$O(1)$	הסתברותית	הסתברותית
חישול מדומה (SA)	עמקים וחפירים	קצב קירור	$O(1)$	כן (קירור אטי)	כן (קירור אטי)
מינימקס (Minimax)	משחקי 2 שחקנים סכום 0	$O(b^m)$	$O(bm)$	כן (בעץ סופי)	כן
גיזום אלפא-בטא	משחקים עם סידור מהלכים	$O(b^{m/2})$ מיטבי	$O(bm)$	כן	כן (זהה למינימקס)

⚠️ 3. מלכודות נפוצות בבחינה ובממ"נים – דגשי ברזל!

🔴 מלכודת 1: בלבול בין כיווני העדכון של אלפא וביתא

זכרו את כלל הברזל: אלפא ($\alpha$) תמיד עולה! היא מאותחלת ל-$-\infty$ ומעודכנת אך ורק בצמתי MAX. לעומתה: ביתא ($\beta$) תמיד יורדת! היא מאותחלת ל-$+\infty$ ומעודכנת אך ורק בצמתי MIN.

🔴 מלכודת 2: האם גיזום אלפא-בטא פוגע באופטימליות?

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

🔴 מלכודת 3: עיגול כלפי מעלה בהצבת פרשים

בנוסחת מספר הפרשים המרבי בלוח $n \times n$, חובה לזכור את פונקציית התקרה: $\lceil n^2/2 \rceil$. עבור לוח $5 \times 5$, $25/2 = 12.5 \implies$ התשובה הנכונה היא 13 פרשים (ולא 12!).

היעד הבא בתוכנית הלימודים פרק 4

בעיות סיפוק אילוצים (Constraint Satisfaction Problems - CSPs)

בפרקים הקודמים התייחסנו למצב במרחב החיפוש כאל "קופסה שחורה" מופשטת שפונקציית ההיוריסטיקה מעריכה מבחוץ. בפרק 4 נעבור למהפכת ה-Factored Representation (ייצוג מפורק): נפרק כל מצב למערכת של משתנים (Variables), תחומים (Domains) ואילוצים (Constraints). נלמד כיצד מחשב פותר סודוקו, צובע מפות מדינות, משבץ מערכות שעות מורכבות, ונכיר את אלגוריתמי האילוצים המובילים: AC-3 (עקביות קשתות), Forward Checking, ויוריסטיקות בחירת משתנים כגון MRV ו-Degree Heuristic.

מעבר לפרק 4: בעיות סיפוק אילוצים (CSPs) ←

מעבר לפרק 4: בעיות סיפוק אילוצים (CSPs)