Skip to main content
header

האם מחשבים יוכלו לשחק שחמט?

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

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

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

מדוע דווקא שאלה זו?

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

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

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

במשחק השחמט ברור מי טוב יותר – מי שמנצח במשחק. לכן, התשובה לשאלה היא יותר פשוטה מאשר נניח "האם מחשב יוכל לכתוב שיר יפה?".

שניים מחלוצי מדעי המחשב כנראה שנשאלו את השאלה הזאת וכל אחד מהם ענה עליה במאמר.

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

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

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


המגזין הפילוסופי, סדרה 7, כרך 41, מס' 314 – מרץ 1950
פרק 12. תכנות מחשב לשחק שחמט
מאת קלוד א. שאנון
מעבדות בל טלפוניה, בע"מ, גבעת מורי, ניו-ג'רזי
[התקבל ב-8 בנובמבר 1949]

1. הקדמה

מאמר זה נוגע בשאלה של יצירת הליך חישוב, או "תכנית" למחשב מודרני למטרות כלליות, אשר יאפשרו לו לשחק שחמט. אם כי אין לכך, אולי, כל חשיבות מעשית, שאלה זו היא בעלת עניין תיאורטי, והתקווה היא, שמציאת פתרון משביע רצון לשאלה זו תשמש כפתח לתקיפת בעיות אחרות בעלות אופי דומה וחשיבות רבה יותר. מספר אפשרויות בכיוון זה הן:
(1)    מכונות לעיצוב מסננים, מקזזים, וכד'
(2)    מכונות לתכנון מעגלי ממסר ומיתוג
(3)    מכונות, שיטפלו בניתוב של שיחות טלפון בהתבסס על נסיבות פרטניות, במקום על תבניות קבועות
(4)    מכונות לביצוע פעולות מתמטיות סימבוליות (לא-ספרתיות)
(5)    מכונות המסוגלות לתרגם משפה אחת לאחרת
(6)    מכונות לקבלת החלטות אסטרטגיות במבצעים צבאיים פשוטים
(7)    מכונות המסוגלות לחבר מלודיה
(8)    מכונות המסוגלות לבצע הסקה לוגית

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

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

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

כיום קיימת כבר ספרות נרחבת למדי על הנושא של מכונות המשחקות שחמט. לקראת סוף המאה ה-19 הוצג ברבים אוטומט השחמט של מאלצל (Maelzel), מכשיר שהומצא על-ידי פון קמפלן (Von Kempelen), בתור מכונה המשחקת שחמט. מספר מאמרים הופיעו באותה עת, כולל מאמר אנליטי מאת אדגר אלן פו (בשם 'שחקן השחמט של מאלצל'), המתיימרים להסביר את אופן הפעולה שלו. רוב הכותבים הסיקו, באופן מדויק למדי, שהאוטומט הופעל על-ידי אמן שחמט אנושי מוסתר; הטיעונים שהובילו למסקנה זו, עם זאת, היו לעתים קרובות שגויים. פו, למשל, מניח, קל באותה המידה לתכנן מכונה, שתנצח בכל משחק ומשחק, כמו לתכנן מכונה שלעתים מנצחת ולעתים מפסידה. מסקנתו היא, שמאחר שהאוטומט לא היה בלתי-מנוצח, הוא חייב להיות מופעל על-ידי בן-אנוש. מבחינה לוגית, מסקנה זו לחלוטין איננה מחוייבת. לדיווח מלא על ההיסטוריה של שיטת הפעולה של האוטומט, אני מפנה את הקורא לסדרת מאמרים מאת הארקנס ובאטל (Harkness & Battel) בכתב-העת Chess Review, 1947.

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

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

מקור : Programming a Computer for Playing Chess - Computer History Museum



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

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

1)    האם ניתן ליצור מכונה, שתציית לחוקי משחק השחמט, כלומר – כזו שתשחק מהלכים חוקיים רנדומליים, או שתוכל לומר לך האם מהלך נתון הוא חוקי?

2)    האם ניתן ליצור מכונה, שתפתור חידות שחמט, כלומר – לומר לשחקן האם, במצב נתון, הלבן יכול לכפות מט בשלושה מהלכים?

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

4)    האם ניתן ליצור מכונה שתשחק שחמט, ותשפר את אופן המשחק שלה ממשחק למשחק, תוך שהיא מפיקה לקחים מהניסיון שלה?

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

5)    האם ניתן ליצור מכונה, שתשיב על שאלות המוצגות לה, באופן כזה שלא ניתן יהיה להבחין בין התשובות של המכונה לתשובות של בן-אנוש?

6)    האם ניתן ליצור מכונה, שיהיו לה רגשות כמו לי ולך?

הבעיה שיש  לבחון אותה כאן היא (3), אך על-מנת להכניס את הבעיה הזו להקשר ביחס לבעיות האחרות, אתן כאן תשובות קצרות ביותר לכל אחת מהן.

לשאלות (1) ו-(2) תשובתי תהיה "ללא ספק ניתן לעשות זאת. אם זה לא נעשה עדיין, זה רק מפני שיש משהו טוב יותר לעשות."

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

לשאלות (4) ו-(5) תשובתי תהיה "אני מאמין שכן. אינני מכיר אף טיעון משכנע באמת, שיתמוך בעמדה זו, ובוודאי שאינני מכיר אף טיעון שיפריך אותה."

לשאלה (6) תשובתי תהיה, "אני לעולם לא אדע, בדיוק באותה המידה בה לעולם לא אוכל להיות לגמרי בטוח שאתה מרגיש כמוני."

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

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

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

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

מקור - Digital computers applied to games - The Turing Digital Archive


Image courtesy of Computer History Museum

לקריאה נוספת:

הערך  Computer Chess בוויקיפדיה

תערוכה וירטואלית  Mastering the game - A history of Computer Chess