משחק אסטרטגיה מופשט

שחמט, דמקה וגו

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

היסטוריה

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

חיבור נים

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

מספרי גרונדי

אסטרטגיית הניצחון בנים משחקת תפקיד חשוב במשחקים רבים נוספים, ובעיקר בניתוח של משחקים שוויוניים (impartial games): כלומר משחקים שבהם כל מהלך שיכול לבצע אחד השחקנים, יכול לבצע גם השחקן השני. בשנת 1935 נוסח משפט ספרג-גרונדי הקובע שכל המשחקים השוויוניים שקולים לנים. תורת גרונדי קובעת שלכל מצב ניתן לייחס מספר גרונדי ומספרים אלו נבנים באופן רקורסיבי: מצב שבו אין אף מהלך אפשרי מקבל את הערך 0, הערך של מצבים אחרים ניתן על ידי המספר השלם הקטן ביותר שאליו לא ניתן להגיע במהלך מאותו מצב.
כך לדוגמה נסתכל על משחק ערמות שבו מותר לכל שחקן בתורו לקחת מערמה אחת לא יותר משלושה גפרורים. ניתן לראות שמספר גרונדי של ערמה שיש בה 1,2,3 גפרורים הוא 1,2,3 בהתאמה. לעומת זאת מערמה עם 4 גפרורים לא ניתן להגיע למצב שהערך שלו הוא 0, ולכן הערך של ערמה זאת הוא 0. מכאן אפשר לראות שכאשר יש ערמה בודדת המצבים המפסידים הם כאשר מספר הגפרורים בערמה הוא כפולה של 4. כאשר יש יותר מערמה אחת, אזי בעזרת חיבור נים של ערכי גרונדי של הערמות ניתן לקבל את הערך של המצב.

בינה מלאכותית

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

סקר מצבים

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