אחת התוצאות המפתיעות של משפט צרמלו הוא שישנם משחקים שבהם ניתן להראות שאחד השחקנים יכול לכפות ניצחון, גם מבלי למצוא בצורה מפורשת את האסטרטגיה שלו. לדוגמה במשחק הקס, שבו לא תיתכן תוצאה של תיקו, ניתן להוכיח שלשחקן הראשון יש אסטרגיה המבטיחה לו ניצחון. ההוכחה היא על דרך השלילה: נניח בשלילה שלשחקן השני ישנה אסטרטגיה המבטיחה לו ניצחון. אזי, השחקן הראשון יכול במהלך הראשון לסמן משבצת אקראית, והחל מהתור הבא לחשוב על עצמו בתור השחקן השני, ולהשתמש באסטרטגיה של השחקן השני, ואסטרטגיה זאת מבטיחה לו ניצחון. נוצרה סתירה מכיוון שלא ייתכן שגם השחקן הראשון וגם השני יכולים לכפות ניצחון. מכאן שבמשחק הקס, אנחנו יודעים שישנה אסטרטגיה שמבטיחה לשחקן הראשון ניצחון, אף על פי שאסטרטגיה כזאת עדיין לא נמצאה עבור לוחות בעלי יותר מ-4x4 משושים.
שיטה זו של הוכחה נקראת גנבת אסטרטגיה, וניתן ליישם אותה על משחקים רבים, בין השאר גם על איקס עיגול, ועל חלק ניכר מהווריאציות שלו.
אנלוגיה בין משחקים שונים.
מאפיין של רבים ממשחקי החשיבה הפשוטים הוא ריבוי הצורות השונות, וה"תחפושות" השונות של המשחקים.
לדוגמה, במשחק השלם ל-15 מונחים תשעה קלפים שעליהם המספרים מאחד עד תשע. ישנם שני שחקנים ובכל תור אחד השחקנים לוקח קלף מתוך הקלפים שלא נלקחו עדיין. השחקן הראשון ששלושה מהקלפים שלו משלימים ל-15 מנצח. המשחק זהה למעשה לאיקס עיגול, ואת האנלוגיה (התאמה) ביניהם ניתן לראות מתוך ריבוע הקסם:
דוגמה נוספת היא המשחק 'השב את המלכה'. במשחק זה מניחים מלכה במקום כלשהו על לוח שחמט, והכללים הם שהמלכה יכולה לנוע כמה משבצות שהיא רוצה אבל רק בכיוונים שמאלה, למטה, או באלכסון שמאלה ולמטה. המשחק הוא לשני שחקנים, בכל תור אחד מהם מזיז את המלכה, והשחקן הראשון שמביא את המלכה למשבצת שבפינה השמאלית-תחתונה, מנצח. קיימת התאמה בין משחק זה למשחק הנים של ויתופ.
תורת המשחקים הקומבינטורית.
חיבור נים.
תחילתו של העניין המתמטי במשחקים החל בשנת 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, ולכן גם המחשבים המתקדמים ביותר אינם יכולים להביט יותר מדי מהלכים קדימה. מהסיבה הזאת עדיין לא נמצא אסטרטגיית ניצחון לשחמט, הקס, גו ולרבים אחרים.
משחק המשוחק בצורה מושלמת על ידי מחשב קרוי גם משחק פתור (אף כי ייתכן שמשחק פתור בצורה שלא מאפשרת ליישם את האסטרטגיה האופטימלית במחשב). המשחק בעל מספר המצבים הרב ביותר שמשוחק בצורה מושלמת על ידי מחשב הוא דמקה, בידי תוכנה הקרויה צ'ינוק.
הערכת מצבים ולמידה.
כאשר לא ניתן לסרוק את המשחק עד סופו, אזי ניתוח המשחק חייב להתבסס על מציאת דרך להערכת מצבים. בשחמט, לדוגמה, מעריכים שהשחקנים הטובים ביותר בעולם אינם רואים יותר מ-5 מהלכים קדימה, ולמרות זאת עד לתחילת המאה ה-21 תוכנות המחשב הובסו מול אלופי העולם בשחמט. הסיבה לכך היא היכולת של בני אדם להעריך מצבים. בשחמט באופן ספציפי, ישנה תורה שלמה המתארת כיצד לנתח מצבים: מה הערך של כל כלי במשחק, חשיבות השליטה במרכז, כמה המלך חשוף וכך הלאה. .
על מנת ללמד מחשבים להעריך מצבים נוסו מספר רב של שיטות. משמעותי מאוד עבור התפתחות הבינה המלאכותית הייתה יצירתם של תוכנות שחמט המסוגלות "ללמוד", כלומר תוכנות ההולכות ומשתפרות ממשחק למשחק.
בוריס בלכר
בוריס בלכר (בגרמנית: Boris Blacher, 6 בינואר 1903 - 30 בינואר 1975) היה מלחין ומורה גרמני. מוצאו היה מאסטוניה, ממשפחה בעלת שורשים גרמנים בלטיים, יהודים ורוסים. גדל בסין, בסיביר ובאסטוניה. היה אחת הדמויות המובילות במוזיקה הגרמנית של המאה ה-20.
רקע משפחתי וילדותו בסין ובסיביר.
בלכר נולד בעיר ניוצ'ואנג במנצ'וריה, סין, כיום יינגקו, במחוז ליאונינג, כבן לאדוארד בלכר, מנהל בבנק רוסיה-אסיה, ולהלנה בלכר, בת לבית ווּלף. מצד אביו הסב היה יהודי. בוריס בלכר, בן יחיד להוריו, נולד ושנותיו הראשונות עברו עליו בסין בגלל עבודת אביו בתחום יחסי בנקאות עם סין. בין השנים 1908-1913 הילד למד בבית הספר של המיסיונרים הפרוטסטנטים האנגלים בצ'פו (כיום העיר ינטאי, במחוז שאנדונג) ובשנת 1913 עבר לעיר האנקו, כיום חלק מהמטרופולין ווהאן. בין השנים 1914-1919 חי בסיביר, בעיר אירקוצק בה למד בתיכון ריאלי וקיבל גם חינוך מוזיקלי - למד כינור ופסנתר, תאוריה מוזיקלית והרמוניה. מ-1919 חי שוב בסין, בחרבין, שם המשיך לימודיו ועבד לתקופת מה כאיש תאורה באופרה. בנוסף עיבד מוזיקה למופעים כמו למשל עיבוד של האופרה "טוסקה" מאת פוצ'יני עבור תזמורת האופרה המקומית.
לימודיו ופעילותו בגרמניה.