משחק פתור

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

הגדרות

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

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

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

משחק פתור חלש

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

משחק פתור חזק

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

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

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

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

משחק מושלם

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

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

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

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

משחקים פתורים

• ארבע בשורה – משחק מושלם של השחקן הפותח יוביל אותו לניצחון.
• איקס עיגול – משחק מושלם של שני הצדדים מוביל לתוצאת תיקו.
• הקס – פתור אולטרה-חלש: עבור לוחות מרובעים, השחקן הראשון לא יכול להפסיד. זאת בצירוף ההוכחה כי לא תיתכן תוצאת תיקו, מראה כי בהינתן משחק מושלם של השחקן הראשון – הוא בהכרח ינצח (אך האלגוריתם לאותו משחק מושלם אינו ידוע). כמו כן המשחק פתור במובן החזק על לוחות בגודל של עד 6×6, וכן פתור במובן החלש על לוחות 7×7, 8×8, 9×9. פתרון חזק לבעיה המוכללת של לוח בגודל n×n (תוך הצגת הבעיה כבצורה של בעיית הכרעה) היא בעיה PSPACE-שלמה.
• דמקה אנגלית – המשחק נפתר בצורה חלשה ב-2007, לאחר מאמץ שנמשך 18 שנה בו השתתפו מאות מחשבים, משחק מושלם של שני השחקנים יוביל לתיקו. האסטרטגיה האופטימלית מומשה בתוכנה צ'ינוק.
• ששת הרגלים - משחק מושלם של השחקן השני יוביל אותו לניצחון.

משחקים פתורים חלקית

• רברסי – על לוח בגודל n×n זו בעיה PSPACE שלמה. במקרים הפרטיים של משחק 4×4 ו- 6×6, משחק מושלם של השחקן השני (כלומר לא זה שפתח) יוביל אותו לניצחון.
• דמקה בינלאומית – המשחק פתור עבור מקרים מסוימים בלבד.
• גו – עבור לוח בגודל 4×4 המשחק פתור במובן החזק. עבור לוח 5×5 המשחק פתור במובן אולטרה-חלש. בני אדם משחקים בדרך כלל בלוח 19×19.

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

נתבונן במשחק הבא: ישנה טבלה m על n. כל אחד מהמשתתפים בוחר בתורו ריבוע מהטבלה, ומסיר אותו ואת כל הריבועים שנמצאים מעליו, מימינו, או מעליו-מימינו (במילים אחרות, אם הוא בחר את הריבוע בשורה r ובעמודה c" הוא מסיר את כל הריבועים שהשורה שלהם היא לכל היותר r והעמודה היא לכל היותר c). מי שלוקח את הריבוע האחרון (פינה שמאלית למטה) מפסיד.

טענה: לשחקן הראשון יש אסטרטגיה מנצחת.

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

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