TD-Gammon

מ-Neurogammon ללמידה בלי מורה

עוד לפני ⁦TD-Gammon⁩, בנה ⁦Gerald Tesauro⁩ ב-⁦IBM⁩ את ⁦Neurogammon⁩: רשת עצבית שלמדה מתוך מסד-נתונים של משחקים מתועדים של שחקני-שש-בש מומחים, בעזרת תכונות שתוכנתו ביד. ב-1989 זכתה ⁦Neurogammon⁩ באליפות השש-בש של ⁦International Computer Olympiad⁩, והגיעה לרמה חזקה של שחקן בינוני. אבל הלמידה הזו דרשה מאגר מוכן של משחקי-מומחים מתויגים, וזה לא קיים בכל תחום.

טסאורו רצה לבדוק אם רשת יכולה ללמוד בלי שום מורה בכלל. ברשת ⁦TD-Gammon⁩ הראשונה המשקלים התחילו אקראיים לגמרי, והרשת קיבלה רק את המיקום הגולמי של הכלים על הלוח, בלי אף תכונה שתוכנתה ביד. היא שיחקה נגד עצמה 200,000 משחקים, ב-40 יחידות נסתרות, בשיטת למידת-הפרשים-הזמניים. התוצאה הגיעה, לפי תיאורו של טסאורו עצמו, לרמה דומה בקירוב ל-⁦Neurogammon⁩ — בלי אף תכונה שתוכנתה ביד, ובלי אף משחק-מומחים לדוגמה. רק בגרסאות הבאות, החל מגרסה 1.0, הוסיף טסאורו את אותה קבוצת תכונות שש-בש שגם ⁦Neurogammon⁩ השתמשה בה, כדי לשפר עוד את הביצועים.

איך זה עבד: למידת-הפרשים-הזמניים

הבסיס האלגוריתמי לשיטה גובש עוד קודם בידי החוקר ⁦Richard Sutton⁩ במעבדות ⁦GTE⁩, אבל טסאורו היה הראשון שהפעיל אותה בקנה-מידה גדול. הרשת של ⁦TD-Gammon⁩ מקבלת כקלט את מצב הלוח: 198 יחידות קלט שמקודדות את מספר הכלים של כל שחקן בכל מקום על הלוח, ומגרסה 1.0 גם כמה תכונות שחושבו מראש. לאחר כל מהלך, הרשת משווה בין ההערכה שהיא נתנה למצב הקודם ובין ההערכה שהיא נותנת למצב החדש, ומעדכנת את משקוליה כדי להקטין את הפער בין שתי ההערכות — מכאן השם "הפרשים זמניים". התוצאה האמיתית של המשחק מגיעה רק בסופו, אבל הרשת לא מחכה לה כדי ללמוד: ההערכה עצמה משתפרת בהדרגה, מהלך אחרי מהלך. מגרסה 1.0 היו לרשת 80 יחידות נסתרות. גרסה 2.0 מ-1992 הוסיפה חיפוש בעומק של שני חצאי-תורות (המהלך שלה ותגובת היריב), גרסה 3.0 מ-1995 העמיקה את החיפוש לשלושה, ובגרסה האחרונה, 3.1, היו 160 יחידות נסתרות.

המבחן האמיתי: נגד טובי השחקנים בעולם

בסוף 1991 שיחקה הגרסה הראשונה, ⁦TD-Gammon 1.0⁩, 51 משחקים נגד שלושה מהשחקנים החזקים בעולם — ⁦Bill Robertie⁩, ⁦Paul Magriel⁩ ו-⁦Malcolm Davis⁩ (אז השחקן המדורג ה-11 בעולם) — והפסידה בהפרש כולל של 13 נקודות, כרבע נקודה למשחק בממוצע. ב-1992, בטורניר ⁦World Cup of Backgammon⁩, שיחקה גרסה 2.0, עם חיפוש בעומק של שני חצאי-תורות, 38 משחקי-תערוכה נגד שחקנים מהצמרת, ובהם ⁦Kit Woolsey⁩ ואלוף העולם לשעבר ⁦Joe Russell⁩. לפי התיעוד של ⁦IBM⁩, היא סיימה 19–19 במספר המשחקים, ולפי טסאורו הפסידה בהפרש כולל של שבע נקודות בלבד. ב-1993 שיחקה גרסה 2.1 40 משחקים נגד ⁦Bill Robertie⁩. לפי תיאורו של טסאורו עצמו, רוברטי פיגר אחרי ⁦TD-Gammon⁩ במשך כל המפגש, וניצח רק את המשחק האחרון — כך שההפרש הסופי בין השניים היה נקודה אחת בלבד, לרעת ⁦TD-Gammon⁩. ב-1995 ניצחה גרסה 3.0, עם חיפוש בעומק של שלושה חצאי-תורות, משחק של 25 נקודות נגד ⁦Neil Kazaross⁩, שחקן ברמת מאסטר, וטסאורו העריך שרמתה עולה על גרסה 2.1 בכ-0.07 עד 0.08 נקודה למשחק בממוצע. הגרסה האחרונה, 3.1 מ-1998, אומנה על יותר מ-6 מיליון משחקים, עם 160 יחידות נסתרות; ב-100 משחקים נגד ⁦Malcolm Davis⁩ היא הפסידה בשמונה נקודות — הפסד שנבע בעיקר מטעות-הכפלה אחת: ⁦TD-Gammon⁩ בחרה להכפיל את ההימור, הפסידה את המשחק ההוא בגאמון, ואיבדה בו 32 נקודות.

המהלך שטסאורו לא תכנת: השפעה על תורת הפתיחות

אחד הרגעים המשמעותיים ביותר של ⁦TD-Gammon⁩ לא היה ניצחון במשחק בודד, אלא שינוי בתורת הפתיחות של השש-בש כולה. עשרות שנים חשבו מומחים ששלוש פתיחות נפוצות — 2-1, 4-1 ו-5-1 — כדאי לשחק בהן "סלוטינג" (⁦slotting⁩): הזזת כלי מהנקודה השישית לחמישית. ניתוח שתוצאותיו פורסמו ב-1992 במאמר של ⁦Bill Robertie⁩ בכתב-העת ⁦Inside Backgammon⁩, המבוסס על הערכות ⁦TD-Gammon⁩, הראה שפיצול כלי-ההגנה (24-23) טוב יותר. שחקני-תחרות מובילים אימצו את הפיצול, ולפי תיאורו של טסאורו הוא "צבר במהירות עוד תומכים" עד שהפך לבחירה הכמעט-אוניברסלית, ו"סלוטינג" כמעט נעלם ממשחקי התחרות. מומחה-שש-בש נוסף, ⁦Kit Woolsey⁩, כתב שאין לו ספק שכושר-השיפוט המצבי של ⁦TD-Gammon⁩ "טוב בהרבה" משלו, ושהשיפוט שלה בין מהלך נועז למהלך בטוח "פשוט פנומנלי". יחד עם זה, ההישג לא היה מלא: ⁦Bill Robertie⁩ מצא בה טעויות טכניות קטנות במשחק-הסיום, שלפי טסאורו חיפוש עמוק יותר צפוי להעלים, וטעויות קטנות בהחלטות-הכפלה — תחום שהרשת לא אומנה עליו כלל: את ההחלטות על קוביית-ההכפלה הוסיפו לה רק אחרי האימון, בעזרת נוסחה תאורטית.

למה זה נחשב לרגע-מפנה בלמידת חיזוק

⁦TD-Gammon⁩ מוזכרת שוב ושוב בספרות למידת חיזוק כאחת ההדגמות הראשונות שרשת עצבית יכולה ללמוד משימה מורכבת מאפס, רק דרך משחק נגד עצמה — בלי מאגר-מומחים ובלי תכונות שתוכנתו ביד, בגרסתה הראשונה. ⁦TD-Gammon⁩ עצמה מעולם לא הפכה למוצר מסחרי, אבל היא שימשה השראה לתוכנות שש-בש מסחריות המבוססות על רשתות עצביות, כמו ⁦JellyFish⁩ (1994) ו-⁦Snowie⁩ (1998). היום, כשסוכני בינה מלאכותית לומדים לשחק דרך ניסוי וטעייה — מ-⁦DQN⁩ של ⁦DeepMind⁩ ועד ⁦AlphaGo⁩ ו-⁦AlphaZero⁩ — הם הולכים בעקבות ההדגמה ש-⁦TD-Gammon⁩ נתנה כבר בתחילת שנות ה-90: שרשת עצבית יכולה ללמוד בעצמה אסטרטגיה שבחלק מהמצבים עדיפה אפילו על שיפוט של מומחים אנושיים.