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