תוכנת שחמט

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

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

מטרות[עריכת קוד מקור | עריכה]

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

עקרונותיה של תוכנת שחמט[עריכת קוד מקור | עריכה]

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

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

  1. ישנם (בקירוב) 30 מסעים חוקיים אפשריים בכל עמדת שחמט וחישוב לעומק 3 מסעים (6 חצאי מסעים) יניב 700 מיליון (306) עמדות שיש לבחון. גם בגישה האופטימית של ניתוח מיליון עמדות בשנייה, נידרש ל-16 דקות לניתוח לעומק של 3 מסעים. (בפועל המחשבים הגיעו לעוצמה המאפשרת ניתוח מיליון עמדות בשנייה 40 שנים לאחר כתיבת המאמר, אך הנימוק נותר מדויק בהחלפת שלושת המסעים בארבעה).
  2. החישוב הקודם התעלם ממסעים "שקטים" וניסה להעריך רק עמדות שבסיום החלפת כלים או לאחר סדרת מסעים משמעותית. שאנון הניח שהוספת מסעים שקטים, פרופילקטיים, תגדיל מאוד את מספר העמדות שיהיה צורך לבחון ולכן תאיט את התוכנית עוד יותר.

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

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

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

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

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

תחרות בין מחשב לאדם[עריכת קוד מקור | עריכה]

בשנות השבעים והשמונים לא היה ברור אם אי פעם תגיע תוכנת מחשב ליכולת להביס את טובי השחקנים האנושיים. בשנת 1968 התערב האמן הבינלאומי דוד לוי שאף תוכנת שחמט לא תהיה מסוגלת לנצח אותו ב-10 שנים הקרובות. הוא זכה בהתערבות בשנת 1978 בניצחון על תוכנת שח 4.7 (המחשב החזק ביותר דאז) אך הסכים שלא ייקח זמן רב עד שלא יוכל יותר לתוכנות המחשב. בשנת 1989 נוצח לוי על ידי תוכנת "מחשבה עמוקה".

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

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

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

דו-קרב בן שישה משחקים בין קספרוב לתוכנה "דיפ ג'וניור" מישראל שנערך בינואר 2003 הסתיים בתיקו 3 - 3. תחרות בת ארבעה משחקים שנערכה בנובמבר 2003 בין קספרוב ובין המחשב "פריץ X3D" הסתיימה בתיקו.

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

תחרויות בין תוכנות השחמט השונות[עריכת קוד מקור | עריכה]

בנוסף לתחרויות בין תוכנות השחמט לבין בני אדם, מתקיימות תחרויות בקרב תוכנות השחמט, כדי לקבוע מי מהן היא הטובה ביותר. באליפויות העולם למחשבי שחמט שנערכו בשנים 1997, 2001 ו-2002, זכתה התוכנה "דיפ ג'וניור", שפותחה בישראל על ידי שי בושינסקי ואמיר באן. בשנת 2003 זכתה "שרדר" במקום הראשון, "פריץ" במקום השני, ו"דיפ ג'וניור" נדחקה למקום השלישי. אליפות העולם לשנת 2004 התקיימה באוניברסיטת בר-אילן, בתחילת יולי, ובה זכתה "דיפ ג'וניור" במקום הראשון, ו"שרדר" במקום השני. בשנת 2005 זכתה "זאפה" האמריקאית במקום הראשון, ובשנת 2006 זכתה "ג'וניור" מחדש במקום הראשון, "שרדר" הגיעה למקום השני, ו"זאפה" – למקום השלישי. ביוני 2007 גברה דיפ ג'וניור על דיפ פריץ בדו-קרב שנערך מטעם הפיד"ה.

דירוג תוכנות שחמט[עריכת קוד מקור | עריכה]

קיימים שני דירוגים עיקריים של תוכנות שחמט:

  • דירוג המתבצע על ידי SSDF, ובו (נכון למאי 2011) נמצאת במקום הראשון תוכנת "ריבקה" עם 3216 נקודות, במקום השני "נאם" עם 3155 נקודות, ובמקום השלישי "דיפ שרדר" עם 3115 נקודות.
  • דירוג המתבצע על ידי קבוצה גרמנית CEGT שמריצה עשרות אלפי משחקים ומדווחת מדי מספר שבועות על הדירוג המעודכן. על פי הדירוג (נכון לינואר 2012) במקום הראשון מדורגת התוכנה "הודיני" עם 3309 נקודות, במקום השני "ריבקה" עם 3243 נקודות, ובמקום השלישי "קריטר" עם 3239 נקודות.

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]