עץ מינימקס

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

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

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

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

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

כשנגיע לשורש, נבחר בקודקוד שתחת לשורש עם הציון הטוב ביותר.

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