 |
|
 |
||
|
||||
 |
צוות של מדענים מאוניברסיטת אלברטה כתב תוכנה שפתרה את המשחק דמקה: http://games.slashdot.org/article.pl?sid=07/07/19/19... |  |
 |
 |
|
|
|
||
|
||||
|
למרבה הצער, זה גורלו התיאורטי של כל משחק שאין בו אלמנטים של מזל או חוסר ודאות... | |
|
|
|
|
|
||
|
||||
|
הלבן מנצח תמיד? | |
|
|
|
|
|
||
|
||||
|
לא. מתוך הידיעה המקושרת ב-nature: "its creators have proved that even a perfectly played game against it will end in a draw."
http://www.nature.com/news/2007/070716/full/070716-1... |
|
|
|
|
|
|
||
|
||||
|
אין איזה משפט שאומר שחייב להיות מנצח? | |
|
|
|
|
|
||
|
||||
|
לא. עד כמה שאני מבין, תנאי משפט צרמלו חלים גם על דמקה: משפט צרמלו [ויקיפדיה]. | |
|
|
|
|
|
||
|
||||
|
למה כוונתך? במשחק בו תיקו הוא אופציה (עפ"י חוקי המשחק), ברור שלא ניתן להוכיח שמישהו חייב לנצח. המשחק יכול, למשל, להיות כזה בו תיקו הוא האפשרות היחידה. אולי לא הבנתי את השאלה. המשפטים הבסיסיים אומרים: במשחק1 ללא תיקו, אחד השחקנים יכול לכפות נצחון; במשחק עם תיקו, אחד השחקנים יכול למנוע מהשני לנצח (כלומר, לזכות בעצמו, או לכפות תיקו). 1 עם כל מיני תנאים טכניים: סופי, מס' סופי של אפשרויות בכל מהלך, ללא הגרלות, עם אינפורמציה מלאה, אולי עוד ששכחתי, ואולי חלק מהללו מיותרים. |
|
|
|
|
|
|
||
|
||||
|
המשפט הראשון שלך אינו ברור. האם כוונתך היא למשחק *כלשהו*? אם כן, אזי זה כמעט טריוויאלי. אלא שייתכנו משחקים ספציפיים [לא עולה לי משהו בראש אבל ניתן בקלות להמציא דוגמת-צעצוע אד-הוק] בהם תיקו הוא תוצאה חוקית, אבל פרישה של כל האפשרויות מניבה נצחון בלתי-נמנע (במשחק מושלם של שני הצדדים וכו') לאחד הצדדים. | |
|
|
|
|
|
||
|
||||
|
נצחון בלתי נמנע בהחלט עומד בתנאי ''למנוע מהצד השני לנצח''. | |
|
|
|
|
|
||
|
||||
|
אני התייחסתי רק ל-''במשחק בו תיקו הוא אופציה (עפ''י חוקי המשחק), ברור שלא ניתן להוכיח שמישהו חייב לנצח''. | |
|
|
|
|
|
||
|
||||
|
חלק מהיופי במתמטיקה הוא היכולת לומר על דברים כמעט טריוויאליים שהם באמת טריוויאליים ואין מלכודת שמסתתרת מאחוריהם (מלכודות כאלו קיימות הרבה יותר משנדמה במבט ראשון). | |
|
|
|
|
|
||
|
||||
|
זהו, שיש מלכודת. המשפט "במשחק בו תיקו הוא אופציה (עפ"י חוקי המשחק), ברור שלא ניתן להוכיח שמישהו חייב1 לנצח" הוא שגוי. ___ 1 חייב במובן זה שהנצחון תלוי רק בו, ולצד השני אין דרך להימנע מהפסד. |
|
|
|
|
|
|
||
|
||||
|
התייחסתי ל''כמעט טריוויאלי'' מההודעה הקודמת שלו (על משחק ''כלשהו''). | |
|
|
|
|
|
||
|
||||
|
הנה משהו שעלה לי בראש: איקס-מיקס-דריקס כשהפותח מניח שתי אבנים במסע הראשון. | |
|
|
|
|
|
||
|
||||
|
אלא אם טעיתי בבדיקה הזריזה, לא דוגמא מוצלחת במיוחד. | |
|
|
|
|
|
||
|
||||
|
למה? 1. תיקו הוא תוצאה אפשרית. 2. לפותח יש איסטרטגיה שמבטיחה זכיה. |
|
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
הניסוח שלי היה מרושל - סליחה. ''בכל משחק עם תיקו, לא ניתן להוכיח שמישהו חייב לנצח'' - לא נכון. ''לא ניתן להוכיח כי (בכל משחק עם תיקו, מישהו חייב לנצח)'' - נכון. לכך התכוונתי, וכך פירשתי (אולי בטעות) את השאלה של ראובן. |
|
|
|
|
|
|
||
|
||||
|
השאלה שלי לא היתה האם ישנם משחקים המסתיימים בתיקו במשחק שחוקיו מאפשרים תיקו1. השאלה שלי היתה לגבי קיום אסטרטגיה המבטיחה זכיה. הבנתי שלגבי דמקה ושח ידוע שיש אסטרטגיה שמבטיחה "לא הפסד" ללבן. 1 כפילות מרגיזה. איך מבדילים בין "ריצה" של המשחק לבין המשחק עצמו? |
|
|
|
|
|
|
||
|
||||
|
ישנם משחקים בהם תיקו הינו תוצאה חוקית, שיש להם איסטרטגיה המבטיחה זכיה. | |
|
|
|
|
|
||
|
||||
|
אני מתאר לעצמי. השאלה היתה לגבי דמקה ושח. | |
|
|
|
|
|
||
|
||||
|
אם הבנתי נכון, לגבי דמקה הוכיחו (בדרך הקשה). לגבי שח אין הוכחה כזאת אם כי אינטואיטיבית זה נראה נכון. | |
|
|
|
|
|
||
|
||||
|
ואני הבנתי משהו אחר: גם לדמקה וגם לשח יש הוכחת *קיום*. לדמקה יש היום גם הוכחת *בניה*. |
|
|
|
|
|
|
||
|
||||
|
אם אפשר, אשמח לקבל לינק להוכחת הקיום לגבי שח. | |
|
|
|
|
|
||
|
||||
|
הוכחת הקיום, כפי שאמרו קודם, היא "משפט צרמלו". לרוע המזל, ההוכחה מראש שקיימת אסטרטגיית נצחון לשחור או ללבן, או שקיימת לשניהם אסטרטגיית תיקו; היא לא אומרת (וזו השאלה המעניינת) מה משלושת האפשרויות הללו מתקיים במקרה של שחמט. משפט צרמלו [ויקיפדיה] |
|
|
|
|
|
|
||
|
||||
|
המשפט מוכר לי [אגב, לכך כיוונתי כאשר אמרתי שזה "כמעט טריוויאלי", לא הייתה זו כוונתי לזלזל בהוכחה הראשונית]. בפרט, ראובן דיבר על נצחון/תיקו *ללבן*, ולגבי כך שאלתי. אני חושד שהוכחת קיום כזאת לא קיימת לפי שעה. אבל תודה בכל אופן. |
|
|
|
|
|
|
||
|
||||
|
כן, אולי אני מתבלבל בין לבן לבין ''צבע כלשהו''. | |
|
|
|
|
|
||
|
||||
|
לרגע חשבתי שאתה מתחכם עם ''שחור אינו צבע''. בשחמט הוא כן. | |
|
|
|
|
|
||
|
||||
|
זה לא עלה על דעתי. | |
|
|
|
|
|
||
|
||||
|
תודה, (גם לערן). | |
|
|
|
|
|
||
|
||||
|
1 סופי => מס' סופי של אפשרויות בכל מהלך, ולכן ברור שאחד מהם מיותר או שגוי. די ברור שניתן להסתפק בדרישה שאורך המשחק יהיה חסום (מראש), לא משנה כמה אפשרויות יש בכל צעד (בעצם, אולי לזה התכוונת ב"סופי"). מה שיותר מענין, הוא שניתן להרחיב את המשפט (הרבה) מעבר לכך: כל כמות של אפשרויות, משחק באורך אינסופי עם הדרישה היחידה שקבוצת הניצחון תהיה מדידה. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |