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