בינה מלאכותית

5.4.1. פרוצדורת מינימקס

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

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

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

העומק נקבע לפי הזמן שמוקצב לביצוע מהלך.

בעייה: כיצד נסמן את עלי העץ?

פתרון: שימוש בפונקצית הערכה. פונקציה המחזירה לכל לוח ציון מספרי.

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

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