בונים איקס עיגול עם מחשב שלא יודע להפסיד - ההיכרות הכי טובה עם אלגוריתמים¶
איקס עיגול נשמע כמו משחק ילדים, אבל הגרסה שאנחנו בונים כאן היא לא. אנחנו בונים גרסה שבה המחשב לא סתם משחק - הוא משחק מושלם. הוא לעולם לא יפסיד. במקרה הגרוע ביותר תסיימו בתיקו, אבל לנצח אותו זה בלתי אפשרי אם הוא משחק נכון. ואיך מגיעים לזה? עם אלגוריתם בשם Minimax, שהוא בעצם הבסיס לכל בינה מלאכותית ששיחקה נגד בני אדם במשחקי לוח - משחמט ועד גו.
זה הפרויקט שממיר "אני יודע לכתוב לולאות ותנאים" ל"אני מבין איך בונים אלגוריתם שחושב קדימה". שווה את ההשקעה.
שלב ראשון - ייצוג הלוח¶
לפני שחושבים על בינה מלאכותית, צריך לוח שאפשר לעבוד איתו. הדרך הכי פשוטה היא רשימה בת תשעה איברים, שמייצגת את הלוח משמאל לימין, מלמעלה למטה:
תא ריק הוא רווח, איקס הוא "X", עיגול הוא "O". זה נראה פרימיטיבי, אבל זו בדיוק הפשטות שמאפשרת לכם להתמקד בלוגיקה ולא בייצוג מסובך. שדרוג טבעי בהמשך הוא לעבור למטריצה תלת על שלוש, אבל אין צורך בזה כדי להתחיל.
שלב שני - בדיקת ניצחון¶
הפונקציה שבודקת אם מישהו ניצח היא בעצם רשימה של כל השורות, העמודות והאלכסונים האפשריים, ובדיקה אם שלושת התאים בכל אחד מהם זהים ולא ריקים:
def check_winner(board, player):
wins = [(0,1,2), (3,4,5), (6,7,8),
(0,3,6), (1,4,7), (2,5,8),
(0,4,8), (2,4,6)]
return any(all(board[i] == player for i in combo) for combo in wins)
זו שורה טובה ללמוד ממנה - שילוב של any ו-all הוא כלי חזק בפייתון שהרבה מתחילים לא מכירים, והוא חוסך המון קוד מיותר לעומת לולאות מקוננות עם דגלים בוליאניים.
שלב שלישי - להבין את Minimax בלי מתמטיקה¶
זה הלב של הפרויקט, אז בואו נבין אותו לפני שכותבים שורת קוד.
תדמיינו שאתם המחשב, ואתם צריכים לבחור מהלך. הרעיון של Minimax הוא פשוט להפליא - תסתכלו על כל מהלך אפשרי, תדמיינו מה יקרה אם תשחקו אותו, ותבחרו את זה שמוביל לתוצאה הכי טובה בשבילכם, בהנחה שהיריב ישחק הכי טוב שהוא יכול.
המילה המפתח היא "בהנחה". האלגוריתם לא רק בודק מה קורה אחרי המהלך שלו - הוא בודק מה היריב יעשה בתגובה, ומה הוא עצמו יעשה בתגובה לזה, וכן הלאה, עד שהמשחק נגמר. זו בדיוק הסיבה לשם "מיני-מקס" - המחשב מנסה למקסם (max) את הסיכוי שלו לנצח, אבל הוא מניח שהיריב תמיד ינסה למזער (min) אותו.
זה מיושם ברקורסיה - הפונקציה קוראת לעצמה, פעם בשביל כל מהלך אפשרי, עד שהיא מגיעה למצב שבו מישהו ניצח, יש תיקו, או שאין יותר מהלכים. בכל "עלה" של העץ הזה נותנים ניקוד - נניח, 1+ אם המחשב ניצח, 1- אם השחקן ניצח, 0 בתיקו - ואז מטפסים חזרה למעלה, כשבכל שכבה בוחרים את הניקוד הכי טוב עבור מי שהתור שלו.
def minimax(board, is_maximizing):
if check_winner(board, "O"):
return 1
if check_winner(board, "X"):
return -1
if " " not in board:
return 0
scores = []
for i in range(9):
if board[i] == " ":
board[i] = "O" if is_maximizing else "X"
scores.append(minimax(board, not is_maximizing))
board[i] = " "
return max(scores) if is_maximizing else min(scores)
שימו לב לתבנית - לכל תא ריק, מנסים מהלך, קוראים לפונקציה שוב, ומחזירים את הלוח למצב הקודם. זו טכניקה שנקראת "backtracking", והיא מופיעה בהמון בעיות אלגוריתמיות מעבר למשחקים.
למה זה שווה את הזמן¶
השיעור האמיתי כאן הוא לא איקס עיגול. זו ההבנה שבעיות "חכמות" נפתרות לא בקסם, אלא בבדיקה שיטתית של אפשרויות, כשרקורסיה עוזרת לכם לחקור אותן בלי לכתוב אלפי שורות קוד. זו בדיוק אותה תחושה - חקירת אפשרויות עתידיות ובחירת הטובה ביותר - שעומדת מאחורי מנועי שחמט, אלגוריתמי ניווט, ואפילו חלק מהמודלים שמאחורי כלי בינה מלאכותית מודרניים. אחרי שתבינו את Minimax באיקס עיגול, שמונה תאים לא מרגישים כמו הישג גדול - אבל ההבנה שרכשתם היא.
מלכודות נפוצות¶
מתחילים רבים שוכחים "להחזיר" את הלוח למצב הקודם אחרי כל ניסיון (השורה board[i] = " " בסוף הלולאה) - ובלי זה, כל מהלך היפותטי "נדבק" ללוח האמיתי והאלגוריתם משתגע. מלכודת נוספת היא לבלבל בין is_maximizing ל-is_minimizing - קל להתבלבל מי בתורו לשחק, ושווה לצייר על דף מה קורה בכל שכבה של הרקורסיה לפני שממשיכים.
מאיפה מתחילים¶
כדי להגיע לרמה שבה רקורסיה ואלגוריתמים כאלה מרגישים טבעיים, צריך קודם בסיס חזק בפייתון - פונקציות, לולאות, ומבני נתונים. את זה בדיוק בונים בקורס תכנות בסיסי החינמי שלנו, צעד אחר צעד, לפני שמגיעים לאלגוריתמים מתוחכמים יותר.
אם רקורסיה עדיין נשמעת לכם כמו קסם שחור, קורס תכנות בסיסי יבנה לכם את היסודות הנכונים כדי שפרויקטים כאלה יהיו הגיוניים ולא רק קוד שהעתקתם.