III. חיפוש ומשחקים

 

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

 

דוגמה: משחק איקס-עיגול

 

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

יום אחד הן שיחקו איקס-עיגול:

 

•מקסים (או בקיצור: מקס) שיחק עם X

•מיני שיחקה עם O

 

מיני בדיוק שיחקה את התור שלה, ולוח המשחק כעת נראה כך:

 

 

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

 

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

 

אז למה, בעצם, מקס הייתה כל כך פסימי?

 

עצי משחק

 

כדי לפתור משחקים בעזרת בינה מלאכותית, נשתמש ברעיון שנקרא “עץ משחק”.
המצבים השונים של המשחק מיוצגים כקודקודים בעץ, בדומה מאוד לבעיות תכנון שראינו קודם –אבל הרעיון כאן קצת שונה.
בעץ משחק, הקודקודים מסודרים לפי רמות – כך שכל רמה מייצגת את תורו של שחקן אחר. הקודקוד העליון, המכונה שורש העץ, מייצג את מצב הפתיחה של המשחק. באיקס-עיגול, למשל, זה יהיה לוח ריק – לפני ששוחק X או O כלשהו.
מתחת לשורש, ברמה השנייה, מופיעים כל המצבים האפשריים שנוצרים כתוצאה מהמהלכים האפשריים של השחקן הראשון. הקודקודים האלה נקראים “ילדים” של השורש.

 

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

 

מיזעור ומיקסום של ערכים

 

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

 

•אם מקסים (X) מנצח – הערך הוא 1+

•אם מיני (O) מנצחת – הערך הוא 1-

•אם יש תיקו – הערך הוא 0

 

(הערכים עצמם לא חשובים כל עוד הסדר נשמר: מקסים מנסה למקסם, מיני מנסה למזער.)

כך אפשר לייצר תהליך חישובי שבו כל שחקן בוחר את המהלך שמביא אותו הכי קרוב למטרה –

מקסים מנסה למקסם את הערך, ומיני מנסה למזער אותו.

 

דוגמה לעץ משחק

 

נתבונן כעת בדוגמה של עץ משחק – שמוצג לא מהשורש, אלא מאמצע המשחק (כי אם נתחיל מההתחלה, העץ יהיה עצום בגודלו).
שימו לב: זו לא אותה הדוגמה שנראתה בתחילת הפרק. מספרנו את הקודקודים במספרים: 1, 2, 3, …, 14.

 

העץ מורכב מרמות מתחלפות, בכל רמה, זהו או תור של מיני לשים O, או תור של מקסים לשים X. השחקן שתורו כעת מסומן בצד הימני של התרשים :

 

 

המשחק נמשך מהמיקום שמוצג בקודקוד השורש, שמסומן במספר (1) בראש העץ, כאשר זהו תורה של מיני לשים O באחת משלוש המשבצות הפנויות. הקודקודים (2)–(4) מייצגים את מצבי הלוח שיתקבלו לפי כל אחת מהשלוש האפשרויות. בשלב הבא, לכל קודקוד יש שתי אפשרויות פעולה עבור מקסים – לשים X – ולכן העץ מתפצל שוב.

 

כאשר מתחילים מהמצב ההתחלתי הזה, המשחק תמיד מסתיים בשלישייה מנצחת:

 

•בקודקודים (7) ו-(9), מקסים מנצח עם שלישיית X

•בקודקודים (11)–(14), מיני מנצחת עם שלישיית O

 

מכיוון שתורי השחקנים מתחלפים בקביעות, ניתן לתייג את רמות העץ לפי השחקן שתורו:

רמות של מיני, ורמות של מקסים – כדי לדעת מי מקבל את ההחלטה באותה רמה.

 

להיות אסטרטגי

 

נתבונן בקודקודים (5)–(10), שנמצאים ברמה השנייה מהסוף. בקודקודים (7) ו-(9), המשחק נגמר – ומקס מנצח, ולכן, הערך של הקודקודים האלה הוא 1+.

 

בקודקודים (5), (6), (8) ו-(10), המשחק כמעט נגמר – מיני צריכה רק לשים את ה־O האחרון במשבצת היחידה שנותרה כדי לנצח. במילים אחרות – אנחנו כבר יודעים איך המשחק יסתיים בכל אחד מהקודקודים האלה, ולכן, נוכל לשייך להם את הערך 1-, כי מיני תנצח בהם.

 

 

כאן מגיע החלק המעניין.

 

נסתכל כעת על הרמה שמעל – הקודקודים (2)–(4), הקרובים יותר לשורש.

 

בקודקוד (2), שני הילדים שלו – (5) ו-(6) – שניהם מובילים לניצחון של מין. לכן, ללא היסוס נוכל להצמיד לקודקוד (2) את הערך 1-. אבל מה לגבי קודקוד (3)? כאן, הילד השמאלי (7) מוביל לניצחון של מקסים (1+), בעוד שהילד הימני (8) מוביל לניצחון של מיני (1-). אז מה יהיה הערך של קודקוד (3)? חשבו על זה רגע – וזכרו של מי התור בקודקוד הזה.

 

מכיוון שזהו תורה של מקסים לשחק, הוא כמובן יבחר את הילד השמאלי – קודקוד (7). כלומר, בכל פעם שמגיעים למצב הלוח של קודקוד (3), מקסים יכולה להבטיח לעצמו ניצחון. ולכן – אנו מצמידים לקודקוד (3) את הערך 1+.

 

אותו עיקרון חל גם על קודקוד (4): גם כאן מקסים בוחר היכן למקם את ה־X, וגם כאן הוא יכול להבטיח לעצמו ניצחון – ולכן נצמיד לקודקוד (4) את הערך 1+.

 

 

קביעת המנצח

 

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

 

עד עכשיו החלטנו כך, לקודקוד (2) יש ערך 1-, כלומר, אם נגיע למצב הזה, מיני תוכל להבטיח לעצמה ניצחון. לקודקודים (3) ו-(4) יש ערך 1+, כלומר, מקסים יוכל להבטיח לעצמו ניצחון, אם ישחק בצורה נבונה כשהוא בתורו.

 

מכאן אפשר להסיק שמכיוון  שמיני היא שחקנית מנוסה היא תדע להסיק בדיוק את אותן המסקנות. ולכן – יש לה רק אפשרות אחת “אמיתית”: להציב את העיגול (O) במרכז הלוח.

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

 

 

ערך השורש = מי מנצח

 

הערך של קודקוד השורש – שמכונה גם “ערך המשחק” – אומר לנו מי ינצח, ואם מדובר במשחק עם תוצאה מספרית – גם בכמה:

 

•אם ערך המשחק הוא 1+ ← מקס ינצח

•אם הערך הוא 1- ← מיני תנצח

•אם הערך 0 ← המשחק יסתיים בתיקו

 

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

 

 

? מציאת מהלכים אופטימליים

לאחר שקבענו את הערכים של כל הקודקודים בעץ המשחק, אפשר להסיק מהם את המהלכים האופטימליים:

• בכל קודקוד של מיני – היא תבחר את הילד עם הערך הנמוך ביותר

• בכל קודקוד של מקסים – הוא יבחר את הילד עם הערך הגבוה ביותר

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

 

אלגוריתם מינימקס (Minimax)

 

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

 

•דטרמיניסטי (אין אקראיות)

• שני שחקנים

•מידע מלא (כל מצב גלוי)

• משחק סכום אפס

 

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

?‍? האלגוריתם עצמו ניתן למימוש בכמה שורות קוד פשוטות. כאן נסתפק בהבנה של הרעיון המרכזי. מי שמעוניין לראות את הקוד בפועל – יכול להציץ למשל ב־מינימקס בויקיפדיה (בערך באנגלית).

 

 

נשמע טוב! אפשר ללכת הביתה?

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

 

• דטרמיניסטי

• לשני שחקנים

• עם מידע מלא

• ומשחק סכום אפס

 

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

 

אז האם זהו? אפשר ללכת הביתה?

 

 בתיאוריה – כן. בפועל – ממש לא.

 

? הבעיה בעצי משחק עצומים

 

ברבים מהמשחקים, עץ המשחק פשוט גדול מדי מכדי שנוכל לעבור עליו במלואו. לדוגמה, בשחמט:

• ממוצע האפשרויות בכל תור הוא בערך 35 מהלכים

• כדי לבדוק רק שני מהלכים קדימה – צריך לעבור על כ־35 × 35 = 1225 קודקודים

• שלושה מהלכים קדימה: כ־42875 קודקודים

• ארבעה מהלכים קדימה: 1,500,625

• עשרה מהלכים קדימה: בערך 2.7 קוודריליון קודקודים (כן, זה מספר אמיתי)

במשחק גו (Go), ממוצע האפשרויות לתור מוערך בכ-250 מהלכים – וזה כבר Game Over עבור מינימקס הפשוט.

 

 

טריקים נוספים: איך מתמודדים עם עץ עצום?

במקרים כאלה, צריך להשתמש בטריקים חכמים – רבים מהם היו חלק חשוב בהצלחה של מחשב Deep Blue של IBM, שהביס את אלוף העולם בשחמט גארי קספרוב בשנת 1997.

אם אנחנו יכולים להרשות לעצמנו לחקור רק חלק קטן מעץ המשחק, אנחנו צריכים דרך לעצור את אלגוריתם Minimax לפני שהוא מגיע לקצה העץ – כלומר, לפני שמגיעים למצב סופי שבו המשחק נגמר והמנצח ידוע. כדי לעשות את זה, משתמשים במה שנקרא פונקציית הערכה היריסטית (heuristic evaluation function). פונקציה זו מקבלת כקלט:

 

•מצב לוח מסוים

•כולל מידע על מי בתור לשחק

 

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

 

? היריסטיקות טובות

 

היריסטיקות טובות בשחמט, למשל, מבוססות לרוב על ספירת החומר (הכלים) בלוח, תוך שקלול הערך של כל כלי לפי סוגו:

 

•מלכה שווה בערך פי 2 מצריח

•מלכה שווה בערך פי 3 מרץ או מפרש

•מלכה שווה בערך פי 9 מחייל

 

כמובן שהמלך שווה יותר מכל הכלים גם יחד, כי הפסדו = הפסד מיידי במשחק.

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

 

האלגוריתם של מינימקס שהצגנו קודם דורש שינויים מינימליים בלבד כדי להפוך לגרסה מוגבלת עומק (depth-limited) – כלומר, גרסה שבה במקום להמשיך עד לסיום המשחק, האלגוריתם עוצר בעומק מסוים ומחזיר את הערך ההיריסטי בכל קודקוד שמגיע לעומק הזה. המונח “עומק” כאן מתייחס פשוט למספר השלבים שעץ המשחק מתרחב לפניהם, לפני שמופעלת פונקציית ההערכה ההיריסטית.

 

? המגבלות של חיפוש פשוט

 

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

אבל… המציאות מורכבת הרבה יותר, וכשאנחנו מנסים ליישם בינה מלאכותית על בעיות מהעולם האמיתי, מתעוררות כמה בעיות קשות.

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

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

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

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

? וזהו בדיוק הנושא של פרק 3.