בתשובה לדב אנשלוביץ, 11/02/03 17:23
 |
|
 |
||
|
||||
 |
ונניח שאין אפשרות מעשית לבדוק את כל עץ המסעים, האם עדיין אפשר שתהיה פונקציית מצב אופטימלית שתיתן לכל מצב בלוח את המסע הטוב ביותר האפשרי ע"ס האינפורמציה הקיימת, בלי לבנות בכלל את עץ התשובות האפשריות? (מי שמכיר את הפתרון למשחק "NIM" יודע למה אני מתכוון) |  |
 |
 |
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
אין שום תוצאה ששוללת את האפשרות הזו. | |
|
|
|
|
|
||
|
||||
|
פונקציה כזו, אם קיימת, תפתור את "בעית השחמט", לא? פשוט הפעל אותה בכל צעד, החל מהראשון. אם הלבן ניצח, משמע שהשחור אינו יכול להשיג תיקו במשחק אופטימלי. | |
|
|
|
|
|
||
|
||||
|
כן. השכ''ג מן הסתם התכוון לשאול אם ייתכן שישנה פונקציה יעילה לקביעת המהלך הבא, דהיינו כזו שהסיבוכיות שלה נמוכה משל הפתרון הטריוויאלי (בניית עץ המשחק המלא). כאמור, אין מניעה שקיימת פונקציה כזו, ואכן ב''נים'' היא קיימת. |
|
|
|
|
|
|
||
|
||||
|
אני יודע שיש תוכנות שחמט שמנסות לשלב את שני סוגי הבינ''מ הקיימים כדי לשפר את יכולותיה - מצד אחד לחשב צעדים קדימה עד כמה שאפשר (שבעה, במקרה שזכור לי), וכשמגיעים ל''עלים'' של הענפים הללו, מחשבים איזו פונקציה שבודקת סיכויי הצלחה לסיום המשחק מהמהלך ההוא, ולפי זה מחליטים. | |
|
|
|
|
|
||
|
||||
|
למיטב ידיעתי התוכנות המתקדמות אינן עוברות על כל המצבים האפשריים עד העומק שציינת, וחלק מה"חוכמה" שלהן הוא לאתר ענפים מבטיחים ו"לגזום" ענפים חסרי תוחלת - אבל אני לא בטוח. אלגוריתם כזה מאפשר חקירת העץ לעומק רב יותר, כשהמחיר הוא החמצת מסעים טובים בגלל שהם מביאים למצב נחות לכאורה לפני שרואים את האור, ובפרט יש לו השפעה שלילית על הקרבת כלים. אחת ההפתעות של הדוקרב היתה הקרבת רץ ע"י התוכנה במשחק החמישי (שהסתיים בתיקו), אלא שבניתוח בדיעבד היא פחות מפתיעה ממה שנראה בזמן אמיתי כי המלך הלבן נחשף בעקבותיה *מיידית* וכנראה שהיתרון הפוזיציוני הזה קיבל את המשקל הראוי. למרבה הצער, הצוות של צעיר עמוק לא נוטה לשתף את העולם במידע על עולמו הפנימי של הנער - מסיבות כלכליות, אני מניח. |
|
|
|
|
|
|
||
|
||||
|
הממם. למה לא לתת עומק מקסימלי ומינימלי לחיפוש? זאת אומרת, התוכנה אף פעם לא תחשב מעבר ל-, נאמר, שבעה מהלכים קדימה, ותנסה לגזום ענפים לא-רווחיים מבחינתה. אבל תהיה מוכנה לתת צ'אנס לכל ענף, אפילו כזה שאמור להיגזם, עד, נאמר, שני מהלכים קדימה, ורק אם שני מהלכים קדימה מתברר שבאמת אין לו שום תת-ענף משתלם, לזרוק אותו קיבינימאט ולהמשיך הלאה? ________ עדי סתיו, לא מבין גדול |
|
|
|
|
|
|
||
|
||||
|
אפשר לתת לענפים להתחרות על המשאבים ביניהם, כשהמצב-ההורה מתקצב את הזמן שיש לו ביניהם לפי הטיב היחסי של המצב. מצבים מעניינים כדאי לחקור לעומק; אלו שהם טפשיים על-פניהם צריכים בדיקה שטחית יותר. | |
|
|
|
|
|
||
|
||||
|
אני חושב שכך בדיוק התוכנה מתנהגת. הבעיה היא עם הביטוי "מתברר שבאמת אין לו שום תת-ענף משתלם" - שהרי אם בדקת רק שני מסעים קדימה ולדעת התוכנה כל האפשרויות שם גרועות זה לא חייב להיות באמת כך. אולי לאחר שני מסעים המצב נראה רע אבל המסע הבא היה הופך את הקערה על פיה (מה-ח8, מט). | |
|
|
|
|
|
||
|
||||
|
לדעתי זה גם האלגוריתם שבן אנוש משתמש בו; גם יכולת החשוב שלנו מוגבלת. | |
|
|
|
|
|
||
|
||||
|
ללא ספק בן אנוש בודק רק חלק קטן מהעץ, ההערכות מדברות על כך שקספרוב בודק 2-3 מסעים בשניה, הרבה פחות ממה שה pc על השולחן שלך עושה, אלא שאותם מסעים שהוא בודק נבחרים ע"י מנגנונים בהם המוח האנושי טוב בהרבה ממה שיודעים כרגע לתכנת (זיהוי תבניות) - אותן דרכי חשיבה שזוכות לכינוי "אינטואיציה". | |
|
|
|
|
|
||
|
||||
|
קספרוב "מתוכנת" למשימת השחמט בדיוק כמו שדיפ-ג'וניור מתוכנת, ואני חושב שהאלגוריתם שלו ושל דיפ-ג'וניור לא שונים בהרבה. להגיד שהמוח האנושי באופן כללי יותר טוב בדברים כאלו זו לדעתי הגזמה. אני מאמין שגם לו היה לשחקן השח הממוצע זמן חישוב כך שמספר המהלכים שהוא והמחשב רואים קדימה זהה, השחקן לא בהכרח היה בוחר את האפשרות הטובה יותר. -------------- השועל, שלא מצליח לעבור את רמה 2500 ב CHESSMASTER 8000 |
|
|
|
|
|
|
||
|
||||
|
אבל השחקן האנושי עובר על הרבה פחות אפשרויות, וכשרונו בזיהוי תבניות (pattern recognition) עולה על זה של המחשב לאין שיעור. מאחר והחומרה שונה לגמרי, אני מאמין שגם האלגוריתמים שונים. מחד יצור עם המון מעבדים איטיים והמון קשרים בין המעבדים האלה (כל נוירון קשור לאלפי נוירונים אחרים), ומאידך מחשב עם מעבדים מהירים אך עם בעיות מקביליוּת חמורות. רשתות נוירוניות יכולות, אולי, לקרב את המחשב לאופן החשיבה האנושי בשחמט, אבל לא ידוע לי אם נעשים מאמצים רציניים בכוון זה. __ שכ"ג, שנכנע תמיד אחרי ה4 |
|
|
|
|
|
|
||
|
||||
|
אחרי איזה 4? | |
|
|
|
|
|
||
|
||||
|
אני חושב שזה רמז: |
|
|
|
|
|
|
||
|
||||
|
רגלי נוסע ל-ה4. הפתיחה שבעזרתה מר ו. הביס אותי ללא תנאי. | |
|
|
|
|
|
||
|
||||
|
שלא לדבר על "א-ה-ה-הם. שלא תחשבו על זה אפילו" (תגובה 94387), שאיתו הביס העורך הראשי את שנינו. | |
|
|
|
|
|
||
|
||||
|
שני לינקים על תיאוריה (Chunking Theory) שמספרת כיצד מומחים תופסים את לוח השחמט אחרת מחובבים: |
|
|
|
|
|
|
||
|
||||
|
היכולת של מומחי שח לזכור מיקום כלים עך לוח שחמט איננה רק בגלל הכושר לאגד פיסות מידע אלא גם בגלל הכושר שלהם לבנות מחדש זיכרון על סמך הידע שלהם בשחמט. אם מציגים לכמה שניות לרבי-אמנים ולחובבים לוח שחמט, רבי האמן יזכרו טוב יותר את מיקום הכלים, בעוד החובבים יזכרו בהסתברות אקראית רגילה. זה נכון בתנאי שהכלים מסודרים על הלוח בתבנית על פי חוקי המשחק. אם סתם זורקים כלים על הלוח, רבי אמנים לא יזכרו טוב יותר מחובבים. בזמן איחזור, רבי האמנים זוכרים מיקום של כמה כלים, חושבים כמה רגעים וממשיכים עם הקבוצה הבאה, עד שהם ממקמים את כל הכלים על הלוח. הדבר הזה מצביע על האפשרות שהזכרון נבנה או נבנה מחדש באמצעות סימנים וידע של תבניות משחקיות, ולא סתם על ידי איחזור אחד לאחד של מידע סתמי. | |
|
|
|
|
|
||
|
||||
|
עם התיקון של השוטה (לפי עומק החישוב אינו אחיד), נדמה לי שכל תוכנות השחמט עושות זאת. די מובן מאליו, בעצם: אם אתה רק מחשב X מהלכים קדימה, מה תעשה אחרי שגמרת לחשב אותם? איך תבחר? | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
ב NIM האסטרטגיה המנצחת נמצאת על ידי מציאת שמורה (invariant) במשחק, וביצוע מהלכים המשמרים אותה. לא נראה שניתן למצוא שמורה כזו בשחמט - בטח לא בצורה קלה. | |
|
|
|
|
|
||
|
||||
|
למי שתוהה מה זה "נים": |
|
|
|
|
|
|
||
|
||||
|
למדת אצל גיל קלעי? | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
למד אצל גיל קלעי? קרא קצת באייל, מה שקרה זה שגיל קלעי למד אצלו... | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |