ברוכים הבאים ליחידת הלימוד "חיפוש בתנאי יריבות (משחקים)" בקורס מבוא לבינה מלאכותית (20551). יחידה זו עוסקת בקבלת החלטות אופטימלית בסביבות מרובות שחקנים בעלי אינטרסים מנוגדים, כלומר, משחקים. נלמד כיצד סוכנים חכמים יכולים לתכנן מהלכים אסטרטגיים כדי למקסם את סיכוייהם לנצח, תוך התחשבות בתגובות אפשריות של היריב.
קבלת החלטות אופטימלית במשחקים
בניגוד לבעיות חיפוש רגילות בהן הסוכן פועל לבדו בסביבה, במשחקים קיימים מספר שחקנים, ולרוב האינטרסים שלהם מנוגדים. המטרה היא למצוא את המהלך הטוב ביותר עבור השחקן הנוכחי, בהנחה שהיריב ישחק בצורה אופטימלית נגדו. יחידה זו מתמקדת בעיקר במשחקי שני שחקנים, סכום אפס, בעלי מידע מלא (כמו שחמט או איקס-עיגול).
עץ מינימקס וגיזום אלפא-בטא
עץ מינימקס (Minimax Tree)
אלגוריתם מינימקס הוא הגישה הבסיסית לקבלת החלטות אופטימלית במשחקי שני שחקנים, סכום אפס ומידע מלא. הוא בונה עץ חיפוש שבו כל צומת מייצג מצב משחק אפשרי, וכל קשת מייצגת מהלך. העץ נבנה לעומק מסוים או עד למצבי סיום. הערכים מחושבים מלמטה למעלה:
- צמתי Max: מייצגים תור של השחקן שלנו. הוא בוחר את המהלך שמוביל לערך המקסימלי מבין צמתי הילדים.
- צמתי Min: מייצגים תור של היריב. הוא בוחר את המהלך שמוביל לערך המינימלי מבין צמתי הילדים (מנקודת מבטו של שחקן ה-Max).
- עלי העץ: מצבי סיום או מצבים שבהם החיפוש נעצר. ערכם נקבע על ידי פונקציית תועלת (utility function) המעריכה את התוצאה עבור שחקן ה-Max.
גיזום אלפא-בטא (Alpha-Beta Pruning)
אלגוריתם מינימקס סובל מחוסר יעילות, שכן הוא סורק את כל העץ. גיזום אלפא-בטא הוא אופטימיזציה שמאפשרת לקצץ ענפים בעץ שברור שלא ישפיעו על ההחלטה הסופית, ובכך לחסוך זמן חישוב משמעותי מבלי לפגוע באופטימליות התוצאה.
- ערך אלפא (α): הערך המינימלי המובטח לשחקן ה-Max לאורך הנתיב הנוכחי. Max לעולם לא יבחר מהלך שמוביל לערך נמוך יותר.
- ערך בטא (β): הערך המקסימלי המובטח לשחקן ה-Min לאורך הנתיב הנוכחי. Min לעולם לא יבחר מהלך שמוביל לערך גבוה יותר (עבור Max).
- תנאי גיזום: אם בכל שלב מתקיים α ≥ β, ניתן לקצץ את שאר הענפים בצומת הנוכחי, מכיוון שהם לא יובילו לתוצאה טובה יותר עבור השחקן הנוכחי מאשר מהלך שכבר נמצא.
מינימקס
סורק את כל העץ. מבטיח את המהלך האופטימלי. יקר חישובית, במיוחד בעצים עמוקים ורחבים.
אלפא-בטא
מגיע לאותה תוצאה אופטימלית כמו מינימקס. יעיל הרבה יותר בפועל, במיוחד עם סדר מהלכים טוב. מקצץ ענפים מיותרים.
פונקציית הערכה ומשחקים עם אלמנט אקראי
פונקציית הערכה למשחקים (Evaluation Function)
ברוב המשחקים המורכבים (כמו שחמט), עץ המשחק עמוק ורחב מכדי שניתן יהיה לסרוק אותו עד למצבי סיום בזמן סביר. במקרים אלו, אנו מגבילים את עומק החיפוש ומשתמשים בפונקציית הערכה כדי להעניק ציון מספרי למצבי משחק לא סופיים. פונקציה זו מעריכה את מידת העדפתו של מצב מסוים עבור שחקן ה-Max.
פונקציית הערכה טובה צריכה להיות:
- מהירה לחישוב: נקראת מיליוני פעמים במהלך החיפוש.
- מדויקת: משקפת היטב את פוטנציאל הניצחון של המצב.
- מבוססת מאפיינים: לוקחת בחשבון גורמים רלוונטיים למשחק (כמו כמות כלים, מיקום, שליטה במרכז).
משחקים עם אלמנט אקראי (Games with Chance)
חלק מהמשחקים כוללים אלמנטים אקראיים (כמו הטלת קובייה בשש-בש או חלוקת קלפים בפוקר). עבור משחקים אלו, אלגוריתם מינימקס אינו מספיק, ויש להשתמש באלגוריתם Expectimax (אקספקטימקס).
אלגוריתם Expectimax מרחיב את מינימקס על ידי הוספת סוג חדש של צמתים:
- צמתי סיכוי (Chance Nodes): צמתים אלו מייצגים אירועים אקראיים. הערך של צומת סיכוי אינו המקסימום או המינימום מבין ילדיו, אלא התוחלת (ממוצע משוקלל) של ערכי הילדים, כאשר המשקלות הם ההסתברויות של כל תוצאה אקראית.
שאלות לדיון
- הסבירו את ההבדל העקרוני בין חיפוש בעץ מינימקס לבין חיפוש באלגוריתם חיפוש רגיל (כמו BFS/DFS) בהקשר של משחקים.
- תארו מצב שבו גיזום אלפא-בטא לא יביא לחיסכון משמעותי בזמן חישוב, ומצב שבו הוא יביא לחיסכון מקסימלי. מה הגורם העיקרי המשפיע על יעילות הגיזום?
- מדוע פונקציית הערכה היא הכרחית ברוב משחקי לוח מורכבים (כמו שחמט), ומהם המאפיינים החשובים של פונקציית הערכה טובה?
- כיצד משתנה אלגוריתם קבלת ההחלטות במשחק כמו שש-בש (Backgammon) בהשוואה למשחק כמו איקס-עיגול (Tic-Tac-Toe), ואיזה אלגוריתם מתאים יותר לכל אחד מהם?
נקודות לתשובת מודל
- **חיפוש מינימקס מול חיפוש רגיל:** חיפוש רגיל מחפש נתיב למטרה בסביבה שיתופית/נייטרלית. מינימקס מחפש את המהלך האופטימלי נגד יריב אינטליגנטי שמנסה למזער את התועלת שלנו. הוא דורש התחשבות בתורות מתחלפים (Max/Min) ובהנחה שהיריב ישחק בצורה הטובה ביותר עבורו.
- **יעילות אלפא-בטא:** יעילות הגיזום תלויה בסדר המהלכים (move ordering). חיסכון מינימלי יתרחש כאשר המהלכים הגרועים נבדקים ראשונים, וחיסכון מקסימלי כאשר המהלכים הטובים נבדקים ראשונים. סדר מהלכים אופטימלי יכול לקצץ את עומק החיפוש בחצי (שורש ריבועי של מספר הצמתים).
- **הכרח פונקציית הערכה:** עצי חיפוש במשחקים מורכבים הם עצומים ולא ניתנים לסריקה מלאה עד למצבי סיום. פונקציית הערכה מאפשרת "לחתוך" את העץ בעומק מסוים ועדיין לקבל החלטה מושכלת. מאפיינים חשובים: מהירות חישוב, דיוק, שיקוף נכון של מצב המשחק (לדוגמה: יתרון חומרי, שליטה במרכז, בטיחות המלך בשחמט).
- **השוואת אלגוריתמים למשחקים:** איקס-עיגול הוא משחק דטרמיניסטי (ללא אלמנט אקראי) ובעל עץ חיפוש קטן יחסית, ולכן אלגוריתם מינימקס (או אלפא-בטא) מתאים לו. שש-בש הוא משחק עם אלמנט אקראי (הטלת קוביות), ולכן דורש את אלגוריתם Expectimax, המשלב צמתי סיכוי המחשבים תוחלת בנוסף לצמתי Max/Min.