משחק פתור

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

הגדרות

למשחק פתור שלוש הגדרות שונות שמעידות על אופי ועומק הפתרון:

משחק פתור אולטרה-חלש

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

משחק פתור חלש

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

משחק פתור חזק

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

משחק מושלם

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