בתשובה לדב אנשלוביץ, 15/12/01 15:34
 |
|
 |
||
|
||||
 |
אפשר למצוא את המצב-הסודי של המשחק באמצעות שבעה ניחושים. אני מתייחס כאן לווריאציות של ארבע מתשע או עשר ספרות שונות (שבעה ניחושים מספיקים בשני המקרים). בווריאציה הנפוצה של ששה צבעים, מספיקים חמישה ניחושים. כדי לפשט את הסיפור, אתייחס בהמשך רק למקרה של תשע ספרות. יש 9*8*7*6=3024 אפשרויות למצב הסודי, ועל כל שאלה יש 14 תשובות אפשריות (00, 01, 02, 03, 04, 10, 11, 12, 13, 20, 21, 22, 30, 40, כאשר 13 פירושו בול אחד ושלוש פגיעות, וכן הלאה. חלקן, כמו 00, אינן אפשריות במקרה של ששה צבעים.) מכאן ברור שצריכים לפחות 4 ניחושים - מספר התשובות האפשריות על שלושה ניחושים הוא רק 14*14*14=2744, וזה לא מספיק כדי להפריד בין 3024 אפשרויות. למעשה, אפשר בקלות יחסית להוכיח שצריך לפחות 5 ניחושים. הרעיון הוא ש- 14 התשובות האפשריות אינן שוות הסתברות (הרבה יותר סביר לקבל 02 מאשר 30), ולכן כמות ה"אינפורמציה" בכל תשובה אינה כזו של אחת-מתוך-14, אלא קרובה יותר ל- 1-מתוך-7.1. כעת, גם בארבע תשובות אין מספיק אינפורמציה כדי להפריד בין 3024 אפשרויות (אבל בחמש, עקרונית, יש). השיטה האופטימלית במשחק כזה תהיה להכין עץ של שאלות: לפי התשובה הראשונה קובעים את השאלה השניה, לפי התשובה השניה את השאלה השלישית, וכן הלאה. כדי לחסוך בזמן, בדקתי מה יקרה אם צריך לקבוע את כל השאלות מראש. אי-אפשר לעבור על כל השביעיות (או שמיניות) האפשריות של שאלות, ולכן העדפתי לצבור את השאלות בזו אחר זו, כאשר בכל פעם קובעים את השאלה שמשפרת את מצב הידע שלנו במידה הרבה ביותר. בתהליך כזה, מתברר, צריך שמונה שאלות כדי לדעת את המצב הסודי (מספיקות שמונה גם אם יש עשרה צבעים, וצריך שש אם יש ששה צבעים). אלא שקביעת כל השאלות מראש מגבילה אותנו מאד. במקום, אפשר לשאול כמה שאלות מראש, ואז לקבוע את ההמשך על-פי התשובות שקיבלנו. מסתבר שאם שואלים ארבע שאלות (את ארבע הראשונות מבין השמונה שהוזכרו לעיל), מספר האפשרויות יורד מ- 3024 ל- 1 עד 29 (תלוי בתשובות, כמובן), ואז מספיקות שלוש שאלות נוספות בכל המקרים. במקרה של 10 ספרות, אפשר לשאול חמש שאלות מראש, ואז - בכל מקרה - מספיקות שתיים נוספות. ועם ששה צבעים, אחרי ארבע השאלות הראשונות מספיקה רק שאלה אחת. |
 |
 |
 |
|
|
|
||
|
||||
|
במחשבה נוספת, המאמץ בהכנת עץ שאלות אינו גדול יותר מאשר בקביעת השאלות מראש. במשחק עם 6 צבעים מספיקים 4 ניחושים. במשחק עם 7 צבעים מספיקים 5 ניחושים. במשחק עם 8 צבעים מספיקים 6 ניחושים (5 מספיקים בכל מקרה, פרט לזוג אחד שהם מתקשים להפריד). במשחק עם 9 צבעים מספיקים 6 ניחושים (5 מספיקים, פרט לשמונה זוגות). במשחק עם 10 צבעים מספיקים 6 ניחושים. מדובר כאן על הגרסה המתמטית של המשחק (ממשיכים עד שהמנחש יכול להוכיח שהוא יודע את התשובה), ולא זו הפופולרית (שבה הוא צריך ממש לומר את התשובה, וזה עולה לו בניחוש נוסף). אם דווקא הגרסה השניה מעניינת אתכם, הוסיפו ניחוש אחד בכל ווריאציה. זה עדיין עונה לשאלה המקורית (פחות משמונה ניחושים בווריאציה של 9 צבעים). בניגוד לחכמה המקובלת, ניחוש טוב בדרך-כלל אינו תואם את הניחושים הקודמים. בווריאציה ה 9-צבעית, רק 74 מתוך כ- 1000 ניחושים "מוקדמים" בעץ שלי (כאלה שאינם מאפשרים זיהוי מיידי של הסוד) עשויים להיות זהים לסוד על-פי המידע בזמן הניחוש. בחרו את המספרים הסודיים שלכם. הניחוש הראשון שלי: 1234. |
|
|
|
|
|
|
||
|
||||
|
אני מגשים חלום ישן (לשחק באתר הרציני הזה). | |
|
|
|
|
|
||
|
||||
|
השגות על התשובות יש להפנות לאדונים ה' ו-ר'. מתכופף... | |
|
|
|
|
|
||
|
||||
|
(בחפזוני, הקובץ מחזיק רק את השאלות - כך שהמחשב שלי מסיר אחריות מן הצעד האחרון). | |
|
|
|
|
|
||
|
||||
|
העץ שלך בנוי להתמודד עם התשובה "שלושה בולים ופגיעה"? לדעתי התגובה הזו עברה בין אחותי לביני מתישהו בילדותי הרחוקה. שמח שעזרתי להגשים חלום! תבלו במפגש, וד"ש... |
|
|
|
|
|
|
||
|
||||
|
לו רק הייתי רואה את הדיאלוג הזה בזמן אמת, כי אז הייתי מדהים את עולם הבול-פגיעה במט במסע אחד. ניחא. | |
|
|
|
|
|
||
|
||||
|
תגובה 186018. | |
|
|
|
|
|
||
|
||||
|
סליחה על הבורות אבל מה זה בול פגיעה? אני מניח שאתם לא מדברים על בית שימוש טורקי | |
|
|
|
|
|
||
|
||||
|
החלטת להשאיר את המט לאינטלקט הקולקטיווי הרצחני, או שדווקא עכשיו נשרף המחשב? | |
|
|
|
|
|
||
|
||||
|
שלום רב אני אותה לך אם תעביר אלי את אלגוריתם של עץ השאלות | |
|
|
|
|
|
||
|
||||
|
''בכל פעם קובעים את השאלה שמשפרת את מצב הידע שלנו במידה הרבה ביותר''. זה האלגוריתם. (''מצב הידע'' זה האנטרופיה של ההתפלגות, ו''משפרת'' זה מורידה את האנטרופיה). |
|
|
|
|
|
|
||
|
||||
|
אני בטוח שעזרת לו מאד. | |
|
|
|
|
|
||
|
||||
|
שאלת תם: האם ברור שהשיטה הזו אופטימלית? כלומר, האם ייתכן שיש שיטה חסכונית יותר במספר השאלות הממוצע אשר מדי פעם מוותרת על הזכות להרוויח הכי הרבה אינפורמציה לטובת שאלות מאוחרות יותר? איכשהו? | |
|
|
|
|
|
||
|
||||
|
והשאלה הגדולה היא איך לוקחים בחשבון את העובדה שיש שאלות שמניבות הרבה יותר אינפורמציה משאלות אחרות? | |
|
|
|
|
|
||
|
||||
|
מה הבעייה עם זה? השיטה שעוזי מציע היא לסרוק בכל שלב את כל השאלות האפשריות ולבחור בזו שמניבה הכי הרבה אינפורמציה. | |
|
|
|
|
|
||
|
||||
|
זו שאלת השאלות. | |
|
|
|
|
|
||
|
||||
|
אני די בטוח שזה נכון (כלומר, שאפשר לקבל את התשובה מהר יותר אם משקיעים מחשבה מראש, ולא בוחרים בכל צעד את השאלה החמדנית ביותר). הבעיה היא שזה דורש לעבור על יותר אפשרויות. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |