מדען המחשב שמוצא שיעורי חיים במשחקים

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

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

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

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

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

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

מחלקה מפורסמת אחת של מורכבות נקראת בשם הפרוזאי P, עבור "זמן פולינומי", ומכילה את סוג הבעיות שניתן לפתור בפרק זמן סביר, באופן גס. בעיות במחלקה המפורסמת לא פחות NP עשויות לקחת פרק זמן בלתי סביר לפתור, אבל קל לבדוק את הפתרונות שלהן. לבעיות במחלקת מורכבות אחרת, המכונה PSPACE, אפילו אימות יעיל שכזה אינו מובטח. כאשר חוקרים מחשיבים את "ההיגיון העמוק" של משחקים לשני שחקנים - "אם אתה עושה X, ואז אם אני עושה Y, ואז אם אתה עושה Z", וכן הלאה - הם מוצאים את עצמם לעתים קרובות מדברים על PSPACE. אבל כפי שטנג עזר להוכיח, המתמטיקה של משחקים קומבינטוריים אינה תמיד פשוטה.

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

איך זה היה לקבל השכלה בסין?

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

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

איך בחרת במדעי המחשב?

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

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

איך הפערים האלה בידע שלך השפיעו על החוויה שלך בבית הספר לתואר שני?

יום אחד גילה [היועץ שלי, גארי מילר,] שמעולם לא שמעתי על NP. זה היה בדיון. הוא אמר, "הבעיה הזו נראית NP-קשה." אמרתי, "אה-הא." הוא אמר, "אתה לא מאמין לי?" ואז הוא התחיל להוכיח את זה, ובאמצע הדרך הוא פנה אליי בחדות, כי בדיוק ישבתי שם, והוא אמר, "אתה יודע מה זה NP-קשה?" אני אמרתי לא.

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

אתה בעיקר תיאורטיקן, אבל לאורך הקריירה שלך עשית גיחות לתעשייה. איך העבודה המעשית הזו התחברה למחקר התיאורטי שלך?

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

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

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

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

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

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

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

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

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

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

האם אני יכול לשחק את המשחק בכל מקום?

זה זמין, עם כמה שינויים, באינטרנט.

באילו משחקים אתה אוהב לשחק?

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

איזו עבודה נוספת עשית על מתמטיקה של משחקי לוח?

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

מה זה אומר לחבר שני משחקים ביחד?

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

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

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

מאז שהוא דחף אותך לעבר מדעי המחשב, איך אביך הגיב לעבודה השונה שעשית במהלך השנים?

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

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

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

אמרתי לאבא שלי, "סוף סוף הבנתי את המשפט המתמטי הזה שמקביל לאחד הניבים המפורסמים שלנו!" הוא היה בן 94 באותה תקופה, חד מאוד, והוא אמר, "זה ניסיון טוב." לא ממש שכנעתי אותו. זו הייתה השיחה הטכנית האחרונה שלי איתו; כמה חודשים לאחר מכן הוא נפטר. בכל פעם שאני חושב להסביר את העבודה שלי, זה גולת הכותרת שלי.