ד.7 — מונטה קרלו באיקס עיגול — טבלת Q וקוד האימון

המצגת: מונטה קרלו באיקס עיגול (עותק מקומי) · קוד: ממשק המשחק · הסוכן הטבלאי · דגימה ובדיקה · האימון

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

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

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

ממשק המשחק הדרוש לאימון

לפני שכותבים את הסוכן, נבהיר מה הוא צריך לקבל מהמשחק — זהו הממשק שתיארנו באופן כללי בפרק ד.3, וכאן הוא מופיע בגרסה קונקרטית לאיקס־עיגול. המשחק כבר נתון. אין צורך בגרפיקה כדי לאמן את הסוכן: הוא מקבל מצב, בוחר משבצת חוקית ומבקש מהסביבה לבצע את המהלך. בקובץ המצורף State.board הוא tuple של תשעה תאים לפי סדר השורות: 1 עבור X, ‎−1 עבור O ו־0 לתא ריק. State.player הוא השחקן שתורו כעת. פעולה מיוצגת בזוג (row, col), כשמספור השורות והעמודות מתחיל באפס.

התגמול הוא מנקודת המבט של X: ניצחון 1, הפסד ‎−1, תיקו 0. גם במהלך משחק שטרם הסתיים התגמול הוא 0. לכן בודקים סיום בנפרד מהתגמול; תגמול 0 לבדו אינו אומר אם צריך להמשיך.

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

מילון של מצב–פעולה וערך

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

Q = {}
state = State()
action = (1, 1)
Q[(state, action)] = 0.7
value = Q.get((state, action), 0.0)

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

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

טבלת גיבוב — ממפתח למקום בטבלה

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

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

בטבלת דוגמה בת עשרה מקומות אפשר לחשב אינדקס למפתח מספרי באמצעות key % 10. המפתח 23 יגיע לאינדקס 3. זו המחשה בלבד; אין זו פונקציית המימוש של מילון פייתון.

מחרוזות, ספר טלפונים וסיבוכיות

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

phones = {"Dana": "050-0000000", "Noam": "052-0000000"}
print(phones["Dana"])

פלט

050-0000000

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

מה עושים כששני מפתחות מגיעים לאותו מקום?

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

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

State כמפתח — גיבוב ושוויון

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

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

def __hash__(self):
    return hash((self.board, self.player))

def __eq__(self, other):
    if not isinstance(other, State):
        return NotImplemented
    return self.board == other.board and self.player == other.player

אלה שתי מתודות מיוחדות של פייתון (הכרנו מתודות כאלה, כמו __init__, בחלק א): המילון קורא להן בעצמו בכל פנייה למפתח. __hash__ עוזרת למילון למצוא את מקום החיפוש; __eq__ בודקת אם אכן מדובר באותו מצב. מצבים שווים חייבים לקבל אותו hash, אבל hash שווה אינו מחייב שמצבים יהיו שווים, בגלל האפשרות להתנגשות.

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

דוגמים את פעולתנו ואת תגובת היריב

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

def sample_step(env, state, action, opponent_rng):
    if state.player != 1:
        raise ValueError('The learner is X')
    after_state, reward = env.next_state(state, action)
    if env.end_of_game(after_state):
        return after_state, reward, True
    opponent_action = opponent_rng.choice(env.get_actions(after_state))
    next_state, reward = env.next_state(after_state, opponent_action)
    return next_state, reward, env.end_of_game(next_state)

הפונקציה מחזירה שלושה ערכים: המצב שבו X יבחר בפעם הבאה, התגמול של הצעד, ודגל שמציין אם המשחק הסתיים. אם X ניצח או מילא את הלוח לתיקו, אין לתת ליריב תור נוסף. אם המשחק נמשך, ההחזרה השנייה כוללת גם את תגובת O. ניצחון של O נותן ‎−1, בהתאם לנקודת המבט של הסוכן שאנחנו מאמנים.

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

אוספים אפיזודה

צעד אחד אינו מספיק למונטה קרלו — העדכון מחכה לסוף המשחק. כעת נאסוף משחק שלם שישמש לעדכון הטבלה. הסוכן הטבלאי בקובץ המצורף (המחלקה TabularAgent) מחזיק את המילון Q וכולל get_Q, שמחזירה את הערך מהמילון או 0, ו־get_action, שבוחרת לפי ε-greedy. מימוש הבחירה והדעיכה נמצא ב־פרק מונטה קרלו. כעת נשתמש בו כדי ליצור משחק שלם:

def generate_episode(env, agent, epsilon, opponent_rng):
    episode = []
    state = State()
    while not env.end_of_game(state):
        action = agent.get_action(state, epsilon)
        next_state, reward, done = sample_step(
            env, state, action, opponent_rng)
        episode.append((state, action, reward))
        state = next_state
    return episode

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

מעדכנים את Q מהסוף להתחלה

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

def update_episode(agent, episode, gamma=0.95, alpha=0.01):
    G = 0.0
    for state, action, reward in reversed(episode):
        G = reward + gamma * G
        old_value = agent.get_Q(state, action)
        agent.Q[(state, action)] = old_value + alpha * (G - old_value)

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

לולאת האימון ובדיקת הסוכן

כל החלקים מוכנים, ונותר לחבר אותם ללולאת אימון: לשחק משחק, לעדכן, ולחזור. נחזור על התהליך 200,000 פעמים, עם α=0.01 ו־γ=0.95. אלה פרמטרי מאמן מונטה קרלו בענף הפתרון. α קטן פירושו שכל משחק מזיז את הערכים רק מעט, ולכן צריך משחקים רבים; זה מתאים לסביבה שבה תוצאות של משחקים בודדים רועשות. ε יתעדכן לפי הפונקציה המעריכית שהוסברה בפרק הקודם.

import random
from ttt_env import State, TicTacToe
from tabular_agent import TabularAgent, epsilon_at
from ttt_training import sample_step, evaluate

def train(epochs=200000, seed=0):
    env = TicTacToe()
    agent = TabularAgent(env, seed)
    opponent_rng = random.Random(seed + 1)
    for epoch in range(epochs):
        episode = generate_episode(
            env, agent, epsilon_at(epoch), opponent_rng)
        update_episode(agent, episode)
    return env, agent

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

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

env, agent = train()
results = evaluate(env, agent.get_action, games=1000, seed=100)
print(results)

ברירת המחדל של agent.get_action היא ε=0, ולכן הבדיקה חמדנית. evaluate מתחילה בכל פעם בלוח ריק, מפעילה את אותו ממשק דגימה מול יריב אקראי וסופרת ניצחונות, הפסדים ותיקו. היא אינה קוראת ל־update_episode.

בהרצה שבוצעה עבור עותק הקוד המצורף התקבל:

פלט

{'wins': 989, 'losses': 0, 'draws': 11}

הסוכן ניצח ב־989 מתוך 1,000 משחקים, סיים 11 בתיקו ולא הפסיד אף פעם. זו תוצאה של 1,000 משחקי בדיקה מול היריב האקראי, לאחר 200,000 משחקי אימון עם הזרעים המוצגים. הסוכן הגיע לכך בלי שאיש הסביר לו את חוקי איקס־עיגול או אסטרטגיה כלשהי — רק מתוך תוצאות המשחקים. עם זאת, התוצאה אינה הוכחה שהסוכן אינו יכול להפסיד מול יריב אחר: הוא למד לשחק מול יריב אקראי, ומצבים שיריב חכם יוצר אולי לא הופיעו באימון כלל. אפשר לבדוק סוכן חדש באותה דרך ולבחון כיצד הפרמטרים משפיעים על התוצאות, בלי לערב את הגרפיקה של המשחק.

לריצה מלאה, שמרו את ארבעת קובצי הקוד המקושרים בראש הפרק באותה תיקייה והפעילו את mc_tictactoe.py. הקוד מבוסס על MC_Trainer.py מענף solved. בעותק הספר הופרדו דגימת המעבר והבדיקה לפונקציות, ייצוג המצב הוקפא, ונבחרו יריב אקראי בסיסי ודעיכת ε מעריכית. לחומרי Pygame אפשר לפנות לחלק ב של הספר ול־אתר הקורס.