בתשובה לאסף עמית, 15/12/01 9:21
ליבוביץ' והמחשב ''האל'' 48091
כפי שאמרתי, כל עוד המטרה היא לפתור עבורנו בעיות ולעזור לנו, זה בסדר. אבל כשהעניין של בריאת מכונה שתחשוב כאדם הופך למטרה, בתקווה שנמצא כבר אחר כך שימוש לכך, זה לא נראה לי.
אגב, לי קרה פעם תהליך הפוך. איני יודע אם אתה מכיר את המשחק "בול קליעה" שבו כל שחקן בוחר מספר בין ארבע ספרות שאינן חוזרות על עצמן, ומנסים להגיע למספר של היריב תוך מספר ניחושים הקטן ביותר. במשחק הזה היינו מרבים להשתעשע בשרותי המילואים בשעות הפנאי, כדי להעביר את הזמן. כשהייתי משחק בו לא הייתה לי שיטה ברורה. לפעמים הייתי מנצח ולפעמים מפסיד.
פעם החלטתי לכתוב תכנית שמנסה לנחש מספר כזה. האלגוריתם שבו השתמשתי היה בשיטה של "ברוט פורס" כמו שמתאים למחשב: הליכה שיטתית ע"פ כל האפשרויות מהמספר הקטן ביותר האפשרי לגדול יותר הקרוב ביותר, כשבכל פעם נבחרת אפשרות שהתשובות לשאלות הקודמות לא פוסלות אותה מלהיות המספר המבוקש.
מדובר באלגוריתם די פשוט לתכנות, והמשימה בוצעה בהצלחה, ודי בקלות. הבחירה הכי קשה דורשת בשיטה זו שמונה ניחושים, ובדרך כלל ניתן להגיע למטרה אחרי שישה נחושים.
החלק המעניין היה שאחרי שהשלמתי את התכנית ניסיתי, כשאני משחק במשחק (אדם מול אדם) לחקות את פעולת המחשב. ואז פתחתי שיטת משחק שמבוססת בעיקרה על השיטה הנ"ל שמתאימה למחשב עם עוד מעט תוספות כדי להאיץ מעט את התהליך במצבים מסויימים. להפתעתי גיליתי שהשיטה הזאת מתאימה גם לאדם, ואפשרה לי לגבור ברוב המקרים על יריביי.
ליבוביץ' והמחשב ''האל'' 48117
כאחד שבתור ילד היה שכן של ממציא המשחק (ישראלי ד"א)שעליו דובר (בול פגיעה ולא בול קליעה:)) והצלחנו בפחות משמונה ניחושים ואפילו משישה למיטב זכרוני.

אבל זכרוני אולי מטעה ני.
אפרופו זכרון.. נדבך חשוב בהתפתחות התודעה של האדם או שמה רק כלי להשרדות בסיסית?
ליבוביץ' והמחשב ''האל'' 48122
תלוי איזה זכרון - זכרון של ''איפה החבאתי את האגוזים שלי'' הוא זכרון השרדותי. אבל זכרון של פרצופים ויחסים חברתיים - הוא גם השרדותי וגם חלק מהתפתחות התודעה (ומכיוון שהסוג הראשון הוא חלק מהסוג השני, הרי שגם הזכרון הראשון הוא נדבך בפיתוח התודעה).
ליבוביץ' והמחשב ''האל'' 48131
כדי שתהיה בתור ילד שכן של ממציא המשחק, עליך להיות מבוגר לפחות ממני ולא נראה לי שכך הוא. אני לא הכרתי את הממציא ובכל זאת שחקתי במשחק הזה לפני למעלה מארבעים שנה.
מכל מקום אפשר להצליח גם בניחוש אחד, אם במקרה תנחש בפעם הראשונה. אבל אם יש בידיך שיטה סיסטמטית לפיה תוכל לנחש *כל מספר* בפחות משמונה ניחושים אשמח לראותה. זה מעניין אותי.
אדום, כתום, צהוב, ירוק, כחול 48133
לפני שנים רבות (הכל יחסי) כתבתי תוכנת מחשב שמשחקת במשחק זה, והצלחתי לבנות לה אלגוריתם שפותר כל צירוף בפחות ממספר מקסימלי קבוע של ניחושים (אינני זוכר איזה...).

נראה לי שהתוכנה הזו אבדה לי באחד מקריסות המחשב התכופות שקורות לכולנו, אך אשתדל למצוא אותה.
ליבוביץ' והמחשב ''האל'' 48148
לא נראה לי שיש שיטה כזאת. גם לי יצא לכתוב פעם תוכנית שמנחשת את המספר בבול פגיעה (ועוד באסמבלר של מיינפריים, תאר לך) וגם אני זוכר שמספר הניחושים המקסימלי היה שמונה.
ליבוביץ' והמחשב ''האל'' 48154
למישהו אכפת להזכיר מהם חוקי המשחק?
ליבוביץ' שיחק "בול פגיעה"? 48157
כל משתתף בוחר צירוף אקראי של 4 פינים מתוך 6 צבעים אפשריים (החמישה שכתבתי מקודם, ועוד אחד ששכחתי).
אסור להשתמש באותו צבע פעמיים בבחירה.

המשתתף השני צריך לנחש את הצירוף במספר מינימלי של ניחושים, כאשר בכל תור הוא יוצר צירוף על הלוח שלו, והיריב "עונה" לו בצורת פינים לבנים ושחורים קטנים.

פין לבן - "פגיעה", כלומר צבע נכון במיקום לא נכון.
פין שחור - "בול", כלומר צבע נכון במיקום נכון.

היריב איננו יודע איזה פין מייצג איזה צבע ובתור הבא עליו להתבסס על כל המידע שצבר בתורות הקודמים, על מנת ליצור צירוף הגיוני.

המשחק נגמר כשאחד מהמשתתפים מקבל 4 פינים שחורים, כלומר:
ניחוש ארבעת הצבעים, במיקום המדויק שלהם.
ליבוביץ' והמחשב ''האל'' 48170
המשחק כפי שאני מכיר הוא מעט אחר. בחירת מספר בן ארבע ספרות. מותרות כל הספרות חוץ מהספרה אפס. אסור שבמספר תהיינה ספרות זהות.
התשובות לכל ניחוש הן מספר הקליעות כלומר כמה מתוך הספרות נוחשו נכון, וכמה מתוכן בולים כלומר הספרות שבמספר הניחוש ממוקמות בדיוק במקומות הנכונים.

למשל נניח שהמספר שנבחר הוא 4537

אם שואלים: 1234 (באלגוריתם של תכנית המחשב שלי זו תמיד השאלה הראשונה כי זה המספר הקטן ביותר שאפשרי לפי הכללים)
התשובה היא: שתי קליעות (3 ו 4) שמתוכן אחת בול (3).

אבל איך אתה לא מכיר את זה ?
הייתה לך ממש ילדות קשה . . .
ליבוביץ' והמחשב ''האל'' 48183
זה מסביר למה לכם נדרש מספר מקסימלי גבוה יותר של ניסויים...
ליבוביץ' והמחשב ''האל'' 49247
בגירסה שאני שיחקתי היה מותר 0, אך לא כספרה השמאלית ביותר.
בול פגיעה בשבעה ניחושים 183433
אפשר למצוא את המצב-הסודי של המשחק באמצעות שבעה ניחושים. אני מתייחס כאן לווריאציות של ארבע מתשע או עשר ספרות שונות (שבעה ניחושים מספיקים בשני המקרים). בווריאציה הנפוצה של ששה צבעים, מספיקים חמישה ניחושים.

כדי לפשט את הסיפור, אתייחס בהמשך רק למקרה של תשע ספרות. יש 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 ספרות, אפשר לשאול חמש שאלות מראש, ואז - בכל מקרה - מספיקות שתיים נוספות.
ועם ששה צבעים, אחרי ארבע השאלות הראשונות מספיקה רק שאלה אחת.
בול פגיעה בששה ניחושים 183815
במחשבה נוספת, המאמץ בהכנת עץ שאלות אינו גדול יותר מאשר בקביעת השאלות מראש.

במשחק עם 6 צבעים מספיקים 4 ניחושים.
במשחק עם 7 צבעים מספיקים 5 ניחושים.
במשחק עם 8 צבעים מספיקים 6 ניחושים (5 מספיקים בכל מקרה, פרט לזוג אחד שהם מתקשים להפריד).
במשחק עם 9 צבעים מספיקים 6 ניחושים (5 מספיקים, פרט לשמונה זוגות).
במשחק עם 10 צבעים מספיקים 6 ניחושים.

מדובר כאן על הגרסה המתמטית של המשחק (ממשיכים עד שהמנחש יכול להוכיח שהוא יודע את התשובה), ולא זו הפופולרית (שבה הוא צריך ממש לומר את התשובה, וזה עולה לו בניחוש נוסף). אם דווקא הגרסה השניה מעניינת אתכם, הוסיפו ניחוש אחד בכל ווריאציה. זה עדיין עונה לשאלה המקורית (פחות משמונה ניחושים בווריאציה של 9 צבעים).

בניגוד לחכמה המקובלת, ניחוש טוב בדרך-כלל אינו תואם את הניחושים הקודמים. בווריאציה ה 9-צבעית, רק 74 מתוך כ- 1000 ניחושים "מוקדמים" בעץ שלי (כאלה שאינם מאפשרים זיהוי מיידי של הסוד) עשויים להיות זהים לסוד על-פי המידע בזמן הניחוש.

בחרו את המספרים הסודיים שלכם. הניחוש הראשון שלי: 1234.
בול ופגיעה 183826
מהר, לפני שיעלו עלינו.
1256 183827
(9 צבעים בסך הכל, 1-9).
בול ופגיעה 183833
(נכון)
1367 183836
אני מגשים חלום ישן (לשחק באתר הרציני הזה).
בול ופגיעה 183837
חדגונית משהו, השיטה שלך.
1728 183839
גם התשובות לא משהו. מט במסע הבא.
שלושה בולים 183843
השגות על התשובות יש להפנות לאדונים ה' ו-ר'. מתכופף...
1729. 183848
(בחפזוני, הקובץ מחזיק רק את השאלות - כך שהמחשב שלי מסיר אחריות מן הצעד האחרון).
ארבעה בולים ובינגו 183851
העץ שלך בנוי להתמודד עם התשובה "שלושה בולים ופגיעה"? לדעתי התגובה הזו עברה בין אחותי לביני מתישהו בילדותי הרחוקה.

שמח שעזרתי להגשים חלום! תבלו במפגש, וד"ש...
אוף! 362765
לו רק הייתי רואה את הדיאלוג הזה בזמן אמת, כי אז הייתי מדהים את עולם הבול-פגיעה במט במסע אחד. ניחא.
עכשיו נזכרים? 362785
תגובה 186018.
אוף! 362797
סליחה על הבורות אבל מה זה בול פגיעה? אני מניח שאתם לא מדברים על בית שימוש טורקי
Coupe de grace, s'il vous plais? 183849
החלטת להשאיר את המט לאינטלקט הקולקטיווי הרצחני, או שדווקא עכשיו נשרף המחשב?
בול פגיעה בשבעה ניחושים 362468
שלום רב אני אותה לך אם תעביר אלי את אלגוריתם של עץ השאלות
בול פגיעה בשבעה ניחושים 362624
''בכל פעם קובעים את השאלה שמשפרת את מצב הידע שלנו במידה הרבה ביותר''. זה האלגוריתם.

(''מצב הידע'' זה האנטרופיה של ההתפלגות, ו''משפרת'' זה מורידה את האנטרופיה).
בול פגיעה בשבעה ניחושים 362646
אני בטוח שעזרת לו מאד.
בול פגיעה בשבעה ניחושים 362651
שאלת תם: האם ברור שהשיטה הזו אופטימלית? כלומר, האם ייתכן שיש שיטה חסכונית יותר במספר השאלות הממוצע אשר מדי פעם מוותרת על הזכות להרוויח הכי הרבה אינפורמציה לטובת שאלות מאוחרות יותר? איכשהו?
בול פגיעה בשבעה ניחושים 362740
והשאלה הגדולה היא איך לוקחים בחשבון את העובדה שיש שאלות שמניבות הרבה יותר אינפורמציה משאלות אחרות?
בול פגיעה בשבעה ניחושים 362776
מה הבעייה עם זה? השיטה שעוזי מציע היא לסרוק בכל שלב את כל השאלות האפשריות ולבחור בזו שמניבה הכי הרבה אינפורמציה.
בול פגיעה בשבעה ניחושים 362778
זו שאלת השאלות.
בול פגיעה בשבעה ניחושים 362937
אני די בטוח שזה נכון (כלומר, שאפשר לקבל את התשובה מהר יותר אם משקיעים מחשבה מראש, ולא בוחרים בכל צעד את השאלה החמדנית ביותר). הבעיה היא שזה דורש לעבור על יותר אפשרויות.
ליבוביץ' והמחשב ''האל'' 405651
נתקלתי (במקרה) בדיונצ'יק הזה, והחלטתי לבדוק. אליבא דויקיפדיה, המשחק הומצא ב-‏1970, באמת ע"י ממציא ישראלי בשם מרדכי מאירוביץ'. דב, אתה משוכנע ששיחקת "בול פגיעה" לפני 1960?

ליבוביץ' והמחשב ''האל'' 405652
מאירוביץ' אולי המציא את זה כמשחק לוח, אבל בלי לוח הוא היה קיים הרבה קודם.
ליבוביץ' והמחשב ''האל'' 405678
בטוח?
ליבוביץ' והמחשב ''האל'' 405689
הספק הוא מאושיות אישיותי.:)

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים