תוכנת שחמט
מתוך ויקיפדיה, האנציקלופדיה החופשית
תוכנת שחמט היא תוכנה המסוגלת לשחק שחמט. כיוון ששחמט נחשב למשחק אסטרטגיה המביא לשיא את יכולתו של המוח האנושי, פיתוח תוכנת שחמט ברמה גבוהה, כזו המסוגלת לנצח כל שחקן אנושי, הוא אתגר רב שנים. בעבר נחשב אתגר זה כדרך להתקדמות בפיתוחה של בינה מלאכותית, אך כעת אין הוא נחשב ככזה, משום שתוכנת שחמט מגיעה להישגים גבוהים בתחום ספציפי זה בלבד, ואין בה את היכולות הכלליות של המוח האנושי.
תוכן עניינים |
[עריכה] מטרות
מעבר להנאה בעצם המשחק מול המחשב, המאפשר לשחקנים להתאמן כאשר אין יריב אנושי זמין, תוכנת השחמט היא עזר בניתוח העמדה וכלי מחקרי המאפשר להגיע לתובנות לגבי החשיבה האנושית. בשני הנושאים הראשונים תוכנות השחמט הפכו להצלחה מסחררת. לאכזבתם של רבים, פיתוח תוכנות השחמט לימד רק מעט לגבי בניית תוכנות המעניקות אינטליגנציה דמוית אנוש, או למעשה כל דבר מלבד לשחק שחמט ברמה גבוהה. מסיבה זו הפסיק נושא זה לעניין את חוקרי האקדמיה בתחום האינטליגנציה המלאכותית. הענין המחקרי עבר למשחק הגו.
[עריכה] עקרונותיה של תוכנת שחמט
המאמר הראשון בנושא נכתב על ידי קלוד שנון, פורסם בשנת 1950 לפני שאיש תכנת מחשב לשחק שחמט, וחזה בהצלחה את שתי האסטרטגיות בהן ייעשה שימוש שאותן כינה סוג א' וסוג ב'.
תוכנות סוג א' אמורות להשתמש בגישת "כח הזרוע" ולבחון על עמדה אפשרית לעומק מוגדר של מסעים תוך שימוש באלגוריתם מינימקס. שנון סבר שגישה זו לא מעשית משתי סיבות:
א. ישנם (בקירוב) 30 מסעים חוקיים אפשריים בכל עמדת שחמט וחישוב לעומק 3 מסעים (6 חצאי מסעים) יניב 700 מיליון (30 בחזקת 6) עמדות שיש לבחון. גם בגישה האופטימית של ניתוח מיליון עמדות בשנייה , נידרש ל-16 דקות לניתוח לעומק של 3 מסעים. (בפועל המחשבים הגיעו לעוצמה המאפשרת ניתוח מיליון עמדות בשנייה 40 שנים לאחר כתיבת המאמר).
ב. החישוב הקודם התעלם ממסעים "שקטים" וניסה להעריך רק עמדות שבסיום החלפת כלים או לאחר סדרת מסעים משמעותית. שנון הניח שהוספת מסעים שקטים , פרופילקטיים , תגדיל מאוד את מספר העמדות שיהיה צורך לבחון ולכן תאיט את התוכנית עוד יותר.
במקום לבזבז את עוצמת המחשב לניתוח מסעים רעים או טריביאליים , הציע שנון שתוכנות מסוג ב' ישתמשו בגישת אינטליגנציה מלאכותית כדי לפתור את הבעיה על ידי בחינת מסעים מועטים אך חזקים בכל עמדה. כת יתפנו לתוכנה משאבי זמן להעמיק בוריאנטיים המשמעותיים יותר.
אדריאן דה גרוט ראיין מספר שחקני שחמט מרמות שונות והסיק שהן אמנים והן מתחילים בוחנים 40-50 עמדות לפני שהם מחליטים איזה מסע לשחק. מה שהופך את האמנים שלחקנים חזקים בהרבה הוא בכך שהם עושים שימוש שכישורי זיהוי תבניות שנבנו מנסיונם האישי. כך הם יכולים לבחון הסתעפויות אחדות בעומק רב יותר ולהתעלם ממסעים שהם סבורים שהם חלשים.
הבעיה בתוכנות מסוג ב' נעוצה בכך שהתוכנה אמורה להחליט איזה מסע טוב מספיק כדי שיישקל בכל עמדה נתונה. התברר שזו בעיה קשה בהרבה לפתרון מאשר האצת תוכנות מסוג א' בעזרת חומרה משופרת.
תוכנות שחמט פועלות על מחשב סטנדרטי, או על חומרה מיוחדת שנבנתה למטרה זו, כך ששילוב התוכנה והחומרה יוצר מחשב שחמט. שיאה של המגמה ליצירת מערכת מיוחדת למטרה זו הוא מערכת "כחול עמוק" (Deep Blue), שפותחה על-ידי חברת IBM ופורקה אחרי כמה משחקים עקב עלותה הגבוהה של החומרה.
בליבה של תוכנת השחמט נמצאת פונקציית הערכת העמדה. פונקציה זו נותנת ערך מספרי לכל עמדה במשחק, המתקבלת על ידי ניתוח המסעות, על פי פרמטרים קבועים מראש כגון מספר הכלים, חוזקם היחסי ומיקומם. כך, מסוגלת התוכנה לבנות מעל עמדה נתונה "עץ מסעות" (אשר ענפיו הם כל העמדות המתקבלות מכל המסעות החוקיים), ובהינתן "עומק עץ" (מספר המסעות קדימה שהתוכנה מסוגלת לראות), לחשב את ה"עלה" או המסע האידאלי, על פי אלגוריתם רקורסיבי, המסתייע בעקרון פשוט של מציאת המקסימום מבין המינימום (שהרי יש לקחת בחשבון יריב שמשחק היטב). ככל שהחומרה שעליה פועלת תוכנת השחמט תהיה חזקה יותר (כגון מעבד חזק וזיכרון וירטואלי גבוה) כך יהיה באפשרותה של תוכנת השחמט לסרוק מספר רב יותר של מהלכים (על כל האפשרויות הנגררות מהן) קדימה בפחות זמן. נכון להיום , תוכנת שחמט סטנדרטית הפועלת על מחשב סטנדרטי מסוגלת לסרוק בסביבות 2.5 מיליון מהלכים בשנייה , ולחשב כיצד יראה לוח השחמט על כל אפשרויותיו ב 14-10 המהלכים הבאים.
[עריכה] תחרות בין מחשב לאדם
בשנות השבעים והשמונים לא היה ברור אם אי פעם תגיע תוכנת מחשב ליכולת להביס את טובי השחקנים. בשנת 1968 התערב האמן הבינלאומי דוד לוי שאף תוכנת שחמט לא תהיה מסוגלת לנצח אותו בתוך 10 שנים. הוא זכה בהתערבות בשנת 1978 בנצחון על תוכנת שח 4.7 (המחשב החזק ביותר באותה שנה) אך הסכים שלא יקח זמן רב עד שלא יוכל יותר לתוכנות המחשב. בשנת 1989 נוצח דוד לוי על ידי תוכנת "מחשבה עמוקה".
תוכנת מחשבה עמוקה הייתה עדיין חלשה בהרבה מרמת אלופי העולם כפי שהוכיח אלוף העולם דאז גארי קספרוב, בשני נצחונות מבריקים בשנת 1989.
בחודש מאי 1997 גרסה משופרת של "דיפ בלו" ניצחה את קספרוב 3.5-2.5. ניתן לומר שמתאריך זה תוכנת המחשב הפכה לשחקן החזק ביותר בעולם. על טענה זו יש חולקים, במיוחד לאור העובדה שהמחשב נעזר בבסיסי נתונים של פתיחות ושל סיומים ולעתים מתאימים את סגנון משחקו במיוחד לצורך התמודדות עם שחקן ספציפי.
בשנות התשעים הגיעו תוכנות השחמט לרמה גבוהה, כך שהן מסוגלות לנצח את רוב בני האדם. בתחילת הדרך נזקקו תוכנות שחמט למחשב-על, משום שרק עוצמתו אפשרה להן לבדוק מספר מהלכים קדימה במידה שתאפשר להן משחק ברמה גבוהה. כיום פועלות תוכנות מחשב מעולות גם על מחשב אישי. השינוי נובע בעיקר מהשיפור בתחכום של תוכנות השחמט, ומעבר משימוש בעוצמת מחשוב (כוח גס) לשימוש באסטרטגיה משופרת.
תחרות בת ארבעה משחקים שנערכה בנובמבר, 2003 בין קספרוב ובין המחשב "פריץ X3D" הסתיימה בתיקו. כיום תוכניות המחשב הולכות ומשתפרות ביכולתן.
עם התחזקותם של המחשבים הביתיים בעשור האחרון, ושיפור רמת התחכום של תוכנות השחמט המובילות, סבורים מומחים שבעוד כמה שנים לא יהיה אדם המסוגל להביס את המחשב בשחמט.
[עריכה] תחרויות בין תוכנות השחמט השונות
בנוסף לתחרויות בין תוכנות השחמט לבין בני אדם, מתקיימות תחרויות בקרב תוכנות השחמט, כדי לקבוע מי מביניהם היא הטובה ביותר. באליפות העולם למחשבי שחמט שנערכה בשנת 2001 ובשנת 2002, זכתה התוכנה "דיפ ג'וניור", שפותחה בישראל על-ידי שי בושינסקי ואמיר באן. בשנת 2003 זכתה "שרדר" במקום הראשון, "פריץ" במקום השני, ו"דיפ ג'וניור" נדחקה למקום השלישי. אליפות העולם לשנת 2004 התקיימה באוניברסיטת בר אילן, בתחילת יולי 2004, ובה זכתה "דיפ ג'וניור" במקום הראשון, ו"שרדר" במקום השני. בשנת 2005 זכתה "זאפה" האמריקאית במקום הראשון, ובשנת 2006 זכתה "ג'וניור" מחדש במקום הראשון, "שרדר" הגיעה למקום השני, ו"זאפה" - למקום השלישי.
[עריכה] דרוג תוכנות שחמט
ישנם שני דרוגים עקריים של תוכנות שחמט:
הראשון על ידי SSDF , בו נמצאת במקום הראשון תוכנת "ריבקה" עם 2918 (נכון ל-24.11.2006) ובמקום השני "דיפ ג'וניור" עם 2854. במקום השלישי "היארכס" עם 2850.
השני על ידי קבוצה גרמנית CEGT שמריצה עשרות אלפי משחקים ומדווחת מדי מספר שבועות על הדירוג המעודכן. הדרוג נכון ל-7.1.2007 הוא תוכנת "ריבקה" עם 3027 ובמקום השני "דיפ פריץ" עם 2877. במקום השלישי "דיפ שרדר" עם 2855.
[עריכה] ראו גם
[עריכה] קישורים חיצוניים
- ישראל בנימיני, לשחק כמו מכונה, באתר ifeel.
- שוויון בסיום ההתמודדות בין קספרוב ופריץ, ynet.
- אורי צחור וגל מור, מלכת השחמט הישראלית, ynet.
- נמרוד ניר-שלום, מקום שלישי לישראל באליפות העולם למחשבי שחמט, ynet.
- שחר סמוחה, הגביע שוב שלנו, בעיתון הארץ, התוכנה "דיפ ג'וניור" שוב זכתה באליפות העולם לשנת 2004 לתוכניות שחמט.
- גל מור, תוכנת השחמט הישראלית "ג'וניור": אלופת העולם, באתר ynet
- מאמר בנושא ההתמודדות של קספארוב מול דיפ ג'וניור.
- [/http://web.telia.com/~u85924109/ssdf דרוג SSDF]
- דרוג CEGT
