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