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