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