עץ מינימקס

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

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

משפט המינימקס מאפשר לנו לדעת מה המהלך הטוב ביותר שנוכל לעשות, על בסיס המידע הנמצא בעץ.

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

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

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

לעץ המינימקס שימושים בפילוסופיה. לעץ תפקיד מרכזי בפילוסופיה של המוסר של ג'ון רולס.