קיימת ידיעה מלאה, כלומר בכל רגע כל השחקנים יודעים הכול על מצב המשחק. בשונה למשל מהמשחק טקטיקו, או ממשחקי קלפים שבהם השחקנים אינם יודעים אילו כלים, או אילו קלפים מחזיק השחקן השני.
המהלכים מתבצעים בזה אחר זה, להבדיל לדוגמה מהמשחק אבן נייר ומספריים שבו שני השחקנים צריכים להראות את האצבעות שלהם בו זמנית.
בהתאם לכך, גורל המשחק למעשה נקבע רק לפי ההחלטות של השחקנים ולפי החשיבה שלהם. תכונה זאת הופכת את המשחקים הללו לכר נרחב למחקר של תכונותיהם המתמטיות, ולשעשועי מתמטיקה. התחום שעוסק בכך נקרא תורת המשחקים הקומבינטורית.
איקס עיגול, הנקרא גם "איקס-מיקס-דריקס" הוא אחד ממשחקי הלוח הפופולריים ביותר ומעטים הילדים שלא שיחקו בו. המשחק מתבצע על לוח 3x3, ובכל תור אחד השחקנים מסמן עם הסימן שלו (איקס – X או עיגול – 0) את אחת המשבצות שעדיין פנויות. הראשון ביניהם שמשיג 3 סימנים ברצף (על אותה שורה, טור או אלכסון) מנצח. אם הלוח מתמלא כולו ואף שחקן לא השיג מטרה זו, המשחק מסתיים בתיקו. לא קשה לנתח את המשחק הזה בשלמותו ולראות שאף אחד מהשחקנים אינו יכול לכפות ניצחון, ואם שני השחקנים משחקים היטב המשחק ייגמר תמיד בתיקו.
למשחק הזה יש וריאציות רבות. אחת הווריאציות המהנות ביותר היא לשחק על לוח גדול מאוד כשהמטרה היא להשיג 5 סימנים ברצף. וריאציה מוצלחת נוספת היא לשחק על לוח תלת־ממדי 4x4x4, והראשון שמשיג 4 סימנים ברצף מנצח. יש גם ואריאציות שבהן השחקן שמשיג רצף דווקא מפסיד, וכן משחקים שמחולקים לשני שלבים, בשלב הראשון מסמנים משבצות בסימנים ובשלב השני ניתן גם להזיז את הסימנים.
המשחק המפורסם ביותר מבין משחקי ערימות הוא נים שבו יש כמה ערמות של גפרורים, ובכל תור שחקן יכול לקחת כמה גפרורים שהוא רוצה אבל רק מערימה אחת. השחקן שלוקח את הגפרור האחרון מנצח. למשחק זה ידועה אסטרטגיית ניצחון (ראו להלן).
נים הוא רק אחד בשורה ארוכה של משחקי ערימות. בנים של ויתופ החוקים שונים במעט. יש שתי ערימות, ובכל תור שחקן יכול לקחת כמה גפרורים שהוא רוצה מאחת הערמות, או לקחת משתי הערימות כמות זהה של גפרורים. במשחק הראשון שמגיע לעשרים ואחת יש 21 גפרורים בערימה ובכל תור שחקן יכול לקחת גפרור אחד, שניים או שלושה גפרורים מהערימה. שוב השחקן שלוקח את הגפרור האחרון מנצח.
הקס הוא משחק בו השחקנים משחקים על לוח משושים. בכל תור, שחקן מסמן משושה בצבע שלו – השחקן הראשון באדום והשחקן השני בכחול. המטרה של השחקן הראשון היא ליצור שביל המקשר את שני צידי הלוח המסומנים באדום, והמטרה של השחקן השני היא ליצור שביל של משושים כחולים המקשרים את שני צדי הלוח המסומנים בכחול. במשחק זה לא תיתכן תוצאת תיקו, כלומר כאשר כל המשושים בלוח מסומנים, אזי יש שביל אדום שמקשר את שני הצדדים האדומים, או שקיים שביל כחול המקשר את שני הצדדים הכחולים.
שחמט, דמקה וגו
שחמט, דמקה וגו הם דוגמאות למשחקים עם כללים מעט מסובכים יותר, שמאפשרים עושר עצום של אפשרויות משחק. משחקים אלו פופולריים מאוד, עד כדי כך שקיימים מועדונים, תחרויות ואליפויות בהם. למשחקים הללו ישנה היסטוריה עתיקה ועשירה. השחמט לדוגמה הומצא ככל הנראה או בהודו, או בסין, במאה ה-2 לפנה"ס. וואריאציות של המשחק שוחקו גם בתקופות קדומות מאוד ביפן, קמבודיה ותאילנד. צורת הכלים, שמותיהם וחוקי המשחק עברו התפתחות רבה עם השנים. המשחק גו הומצא כבר באלף השני לפני הספירה ומוזכר לראשונה בספרות באחד מספריו של קונפוציוס.
מקורותיהם של חלק ממשחקי המחשבה הם עתיקים ועלומים. איקס עיגול ונים קיימים כנראה כבר מתקופות קדם. השחמט על גלגוליו ההיסטוריים מקורו במזרח הרחוק, כנראה מהודו או סין והוא מתוארך למאה השנייה לפנה"ס או אפילו מוקדם יותר. יש הטוענים שגו, שהומצא בסין, אף קדום יותר. לעומת זאת ישנם משחקים פופולריים מאוד שהומצאו בעת החדשה: לדוגמה המשחק הקס הומצא בשנת 1942 על ידי המשורר והמתמטיקאי פייט היין, ובאופן עצמאי בשנת 1947 על ידי המתמטיקאי ג'ון נאש.
עם התפתחות המחשב במאה-ה20, החלו להיכתב יישומים ממוחשבים למשחקים אבסטרקטיים. בספרי לימוד רבים במדעי המחשב, התכנות של משחקים כמו איקס עיגול הוא משימה קלאסית, כמו גם הניתוח שלהם בשיטת העץ. מציאת דרכים ללמד מחשבים לשחק משחקי לוח מופשטים הפך לאתגר מרכזי בתחום הבינה המלאכותית. בשנות ה-50 של המאה ה-20 חלה התקדמות רבה בתחום זה, ובפרט בהתמודדות עם משחקי מחשב מופשטים קשים יחסית כגון גו ושחמט. התחזיות המוקדמות בשנות ה-50 היו שתוך שנים בודדות יצליחו תוכנות מחשב להביס את אלופי העולם בשחמט ובדמקה, ואולם למרות הצלחות מוקדמות של מחשבים בשש-בש (שאינו משחק מופשט בשל אלמנט המזל הכלול בו), רק בשנת 1997 הצליחה תוכנת מחשב, כחול עמוק, לנצח לראשונה את אלוף העולם, גארי קספרוב, במשחק שחמט צמוד.
אסטרטגיה או תכסיס בתורת המשחקים, פירושה: מפרט של הוראות לשחקן איך לשחק בכל מצב נתון. עבור משחקי חשיבה שבהם יש בנוסף גם הגבלה על מספר המהלכים, מתקיים משפט שנקרא משפט צרמלו. הוא קובע שקיימת אסטרטגיה שמבטיחה לאחד השחקנים ניצחון, או שלפחות שני השחקנים יכולים לכפות תיקו. משפט זה איננו מתקיים לגבי משחקים שלא מקיימים את התנאים שהוזכרו למעלה. לדוגמה באבן נייר ומספריים (שבו המהלכים מתבצעים בו זמנית) אין אסטרטגיה שיכולה לכפות ניצחון או תיקו, וכך גם במשחקים המבוססים על מזל.
אחת התוצאות המפתיעות של משפט צרמלו הוא שישנם משחקים שבהם ניתן להראות שאחד השחקנים יכול לכפות ניצחון, גם מבלי למצוא בצורה מפורשת את האסטרטגיה שלו. לדוגמה במשחק הקס, שבו לא תיתכן תוצאה של תיקו, ניתן להוכיח שלשחקן הראשון יש אסטרגיה המבטיחה לו ניצחון. ההוכחה היא על דרך השלילה: נניח בשלילה שלשחקן השני ישנה אסטרטגיה המבטיחה לו ניצחון. אזי, השחקן הראשון יכול במהלך הראשון לסמן משבצת אקראית, והחל מהתור הבא לחשוב על עצמו בתור השחקן השני, ולהשתמש באסטרטגיה של השחקן השני, ואסטרטגיה זאת מבטיחה לו ניצחון. נוצרה סתירה מכיוון שלא ייתכן שגם השחקן הראשון וגם השני יכולים לכפות ניצחון. מכאן שבמשחק הקס, אנחנו יודעים שישנה אסטרטגיה שמבטיחה לשחקן הראשון ניצחון, אף על פי שאסטרטגיה כזאת עדיין לא נמצאה עבור לוחות בעלי יותר מ-4x4 משושים.
שיטה זו של הוכחה נקראת גנבת אסטרטגיה, וניתן ליישם אותה על משחקים רבים, בין השאר גם על איקס עיגול, ועל חלק ניכר מהווריאציות שלו.
אנלוגיה בין משחקים שונים
מאפיין של רבים ממשחקי החשיבה הפשוטים הוא ריבוי הצורות השונות, וה"תחפושות" השונות של המשחקים.
לדוגמה, במשחק השלם ל-15 מונחים תשעה קלפים שעליהם המספרים מאחד עד תשע. ישנם שני שחקנים ובכל תור אחד השחקנים לוקח קלף מתוך הקלפים שלא נלקחו עדיין. השחקן הראשון ששלושה מהקלפים שלו משלימים ל-15 מנצח. המשחק זהה למעשה לאיקס עיגול, ואת האנלוגיה (התאמה) ביניהם ניתן לראות מתוך ריבוע הקסם:
4
9
2
3
5
7
8
1
6
דוגמה נוספת היא המשחק 'השב את המלכה'. במשחק זה מניחים מלכה במקום כלשהו על לוח שחמט, והכללים הם שהמלכה יכולה לנוע כמה משבצות שהיא רוצה אבל רק בכיוונים שמאלה, למטה, או באלכסון שמאלה ולמטה. המשחק הוא לשני שחקנים, בכל תור אחד מהם מזיז את המלכה, והשחקן הראשון שמביא את המלכה למשבצת שבפינה השמאלית-תחתונה, מנצח. קיימת התאמה בין משחק זה למשחק הנים של ויתופ.
תורת המשחקים הקומבינטורית
חיבור נים
תחילתו של העניין המתמטי במשחקים החל בשנת 1901, כאשר צ'ארלס בולטון פרסם את אסטרטגיית הניצחון בנים. האסטרטגיה מבוססת על חלוקה של המצבים למצבים "מנצחים" – שבהם השחקן שתורו כעת מנצח, ומצבים "מפסידים" שבהם השחקן שתורו מפסיד. הדרישה ממצב מנצח היא שלפחות מהלך אחד שמוביל למצב מפסיד, ולעומת זאת ממצב מפסיד כל המהלכים יובילו למצב מנצח.
בנים ניתן לזהות האם מצב הוא מנצח או מפסיד על ידי פעולה שנקראת "חיבור נים" או בשמה המתמטי או אקסקלוסיבי (XOR). כאשר מבצעים סכום נים על מספרי הגפרורים בכל ערמה, אם התוצאה היא 0 אזי המצב הוא מפסיד, אחרת המצב הוא מנצח.
מספרי גרונדי
אסטרטגיית הניצחון בנים משחקת תפקיד חשוב במשחקים רבים נוספים, ובעיקר בניתוח של משחקים שוויוניים (impartial games): כלומר משחקים שבהם כל מהלך שיכול לבצע אחד השחקנים, יכול לבצע גם השחקן השני. בשנת 1935 נוסח משפט ספרג-גרונדי הקובע שכל המשחקים השוויוניים שקולים לנים. תורת גרונדי קובעת שלכל מצב ניתן לייחס מספר גרונדי ומספרים אלו נבנים באופן רקורסיבי: מצב שבו אין אף מהלך אפשרי מקבל את הערך 0, הערך של מצבים אחרים ניתן על ידי המספר השלם הקטן ביותר שאליו לא ניתן להגיע במהלך מאותו מצב.
כך לדוגמה נסתכל על משחק ערמות שבו מותר לכל שחקן בתורו לקחת מערמה אחת לא יותר משלושה גפרורים. ניתן לראות שמספר גרונדי של ערמה שיש בה 1,2,3 גפרורים הוא 1,2,3 בהתאמה. לעומת זאת מערמה עם 4 גפרורים לא ניתן להגיע למצב שהערך שלו הוא 0, ולכן הערך של ערמה זאת הוא 0. מכאן אפשר לראות שכאשר יש ערמה בודדת המצבים המפסידים הם כאשר מספר הגפרורים בערמה הוא כפולה של 4. כאשר יש יותר מערמה אחת, אזי בעזרת חיבור נים של ערכי גרונדי של הערמות ניתן לקבל את הערך של המצב.
את תורת גרונדי הרחיב ג'ון קונוויי למשחקים שאינם שוויוניים. קונויי הציג את מה שקרוי היום מספרים סוריאליסטיים, המתארים מצב במשחק על ידי שתי קבוצות: קבוצת המצבים שהשחקן הראשון יכול להגיע אליהם אם זה תורו, וקבוצת המצבים שהשחקן השני יכול להגיע אליהם אם זה תורו. המספרים מסומנים כך {...a,b,c...| d,e,f} כאשר המצבים משמאל מייצבים את המצבים אליהם השחקן הראשון יכול להגיע אם זה תורו, והמצבים מימין מסמנים את המצבים אליהם יכול להגיע השחקן הראשון. כמו מספרי גרונדי גם מספרים אלו נבנים בצורה רקורסיבית: המצב הבסיסי המסומן 0, הוא מצב שבו אף שחקן אינו יכול לבצע מהלך, הוא המצב { | }; מצב 1 הוא מצב שבו רק השחקן הראשון יכול לבצע מהלך, שמוביל למצב 0: { | { | }}; מצב בעל ערך 2 הוא מצב שממנו השחקן הראשון יכול להגיע למצב אחד. לעומת זאת מצב 1- הוא מצב שבו רק השחקן השני יכול להגיע למצב 0, וכן הלאה.
חיבור משחקים: אם וישנם שני משחקים (או במשחקי ערמות כמה ערמות) כך שבכל תור שחקן יכול לבחור את אחד המשחקים ולבצע בו מהלך, אזי הערך של המצב הכולל הוא חיבור של הערכים המשחקים השונים. כך לדוגמה משחק שבו יש ערמה של 5 גפרורים שרק השחקן הראשון יכול לקחת – ערכו 5, בתוספת משחק שבו ערמה אחת של 3 גפרורים שרק השחקן השני יכול לקחת – ערכו 3-, מוביל למשחק שערכו 5-3=2. מכאן שפעולות חשבון על משחקים המתוארים על ידי מספרים סוריאליסטיים דומים לפעולת חשבון על מספרים רגילים.
משחקים שאינם מספרים: ואולם בכתיבה של קונוויי ניתן להגדיר מצבים שאינם מספרים – אין להם מקבילה במספרים הממשיים. לדוגמה המצבים במשחק נים, שבהם לשני השחקנים ישנם אותם אפשרויות. ערמה בעלת גפרור בודד במשחק נים מסומנת על ידי: \{ { | }| { | }}, והיא מסומנת על ידי קונויי בתור 1*, ובאופן דומה ערמת נים בעלת n גפרורים זוכה לסימון n*. כפי שהוסבר למעלה, החיבור של מצבים כאלו מתנהג על פי חוקים שונים מחיבור של מספרים טבעיים.
בינה מלאכותית
כבר מראשית התפתחותם של מדעי המחשב, החלו להיכתב אלגוריתמים על מנת לאפשר למחשבים לשחק משחקים, ומציאת אלגוריתמים אלו הפכה לאתגר מרכזי בבינה מלאכותית.
סקר מצבים
האלגוריתמים הבסיסיים ביותר לניתוח משחקים מבוססים על סקירה של כל המצבים שאליהם ניתן להגיע. אלגוריתמים עושים שימוש בשיטה הקרויה מיני-מקס לפי לכל מצב במשחק ניתן ערך בשיטה רקורסיבית: הערך של המשחק הוא הערך המקסימלי מבין המצבים שניתן להגיע אליהם מתוך אותו מצב, והערך של המצבים ההם הוא המינמלי (מכיוון שהמהלך הבא נעשה על ידי השחקן השני) מבין המצבים שניתן להגיע משם, וכך הלאה... בשיטה זאת ניתן לדוגמה לנתח את המצבים האפשריים באיקס עיגול בקלות יחסית, ומשימה זאת מופיעה פעמים רבות כתרגיל תכנותי. עבור איקס עיגול נבנו אפילו מכונות אנלוגיות (מכונות שלא מבוססות על אלקטרוניקה) המסוגלות לשחק את המשחק.
הבעיה בשיטת המינמקס היא שמספר המצבים עשוי להיות עצום. במשחק לוח שבו בלוח יש n תאים או משבצות, מספר המצבים גדל בצורה אקספוננציאלית ב-n, ולכן גם המחשבים המתקדמים ביותר אינם יכולים להביט יותר מדי מהלכים קדימה. מהסיבה הזאת עדיין לא נמצא אסטרטגיית ניצחון לשחמט, הקס, גו ולרבים אחרים.
משחק המשוחק בצורה מושלמת על ידי מחשב קרוי גם משחק פתור (אף כי ייתכן שמשחק פתור בצורה שלא מאפשרת ליישם את האסטרטגיה האופטימלית במחשב). המשחק בעל מספר המצבים הרב ביותר שמשוחק בצורה מושלמת על ידי מחשב הוא דמקה, בידי תוכנה הקרויה צ'ינוק[1].
הערכת מצבים ולמידה
כאשר לא ניתן לסרוק את המשחק עד סופו, אזי ניתוח המשחק חייב להתבסס על מציאת דרך להערכת מצבים. בשחמט, לדוגמה, מעריכים שהשחקנים הטובים ביותר בעולם אינם רואים יותר מ-5 מהלכים קדימה, ולמרות זאת עד לתחילת המאה ה-21 תוכנות המחשב הובסו מול אלופי העולם בשחמט. הסיבה לכך היא היכולת של בני אדם להעריך מצבים. בשחמט באופן ספציפי, ישנה תורה שלמה המתארת כיצד לנתח מצבים: מה הערך של כל כלי במשחק, חשיבות השליטה במרכז, כמה המלך חשוף וכך הלאה.
על מנת ללמד מחשבים להעריך מצבים נוסו מספר רב של שיטות. משמעותי מאוד עבור התפתחות הבינה המלאכותית הייתה יצירתם של תוכנות שחמט המסוגלות "ללמוד", כלומר תוכנות ההולכות ומשתפרות ממשחק למשחק.
