ב-Online
 
 
 
 
 
 
 
 
מחשב חובב 'איקס-עיגול' 

מחשב חובב 'איקס-עיגול'

 
 
עידו גנדל

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

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

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

ייצוג והערכה

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

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

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

לראות את העתיד

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

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

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

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

משחקים של גדולים

מפה, זה תלוי ביצירתיות של המתכנת (צ': GettyImages)
 מפה, זה תלוי ביצירתיות של המתכנת (צ': GettyImages)   
שיטת המשחק שהוצגה כאן היא דוגמה לגישת Brute force ("כוח גס") לפתרון בעיות: היא פשוט עוברת על כל אחד ואחד מהמצבים או הפתרונות האפשריים, ובוחרת את המוצלח מביניהם. זו הגישה הקלה ביותר לתכנות ולהבנה, אך היא גם הבזבזנית ביותר מבחינת משאבים – זיכרון וזמן. באיקס-עיגול, הבזבוז הזה לא מהווה מגבלה משמעותית, כי יש רק תשע אפשרויות למהלך הראשון, שמונה לשני וכן הלאה: כל מהלך נוסף מקטין את מספר האפשרויות הזמינות, והמחשבים של היום לא צריכים אפילו להתאמץ כדי לזהות בתוך חלקי שניה ספורים את המהלך האופטימלי.

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

למתכנתים החובבים: פרס של עשרת אלפים דולרים או יותר מוצע למי שיצליח לכתוב תוכנה שתביס את בני האדם במשחק "ארימאא" הייחודי. המועד האחרון להגשה הוא שנת 2020. לעבודה!
 
 
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
 
תגובות
הוסף תגובה0 תגובות
הוספת תגובה
מאת
 
נושא
 
תוכן
 
 
 
 
תודה! תגובתך התקבלה.
התגובה תתפרסם בכפוף לתנאי האתר.
 
 
 
 
 

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by