בול פגיעה

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

יש דרכים רבות לשחק במשחק, המיועד בעיקרו לשני שחקנים. במשחק שהמציא מאירוביץ', כל אחד משני השחקנים בוחר רצף של ארבעה צבעים משישה צבעים אפשריים ומסתיר אותו מעיני היריב. השחקן השני מנסה לנחש מהו הרצף שנבחר – הוא מציע רצף כלשהו של ארבעה צבעים, והשחקן ה"מסתיר" נותן לו ציון על איכות הניחוש שלו, על סמך שני החוקים האלה:

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

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

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

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

ראשית, נשים לב שיש חמישה ציונים אפשריים בלבד:

1. בול, בול
2. פגיעה, פגיעה
3. בול
4. פגיעה
5. (כלום)

הציון "בול, פגיעה" אינו יכול להופיע במשחק הזה. (מדוע?)

במשחק הזה יש שני סוגים של ניחושים: ניחוש ששני הצבעים שמנחשים בו הם צבעים שונים – ניחוש כזה נסמן ב-xy; או ניחוש של שני צבעים זהים (אדום אדום, כחול כחול או ירוק ירוק) – ניחוש כזה יסומן ב-xx.

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

כעת ניצור טבלה שבה ניעזר למציאת סוג הניחוש הראשון שכדאי לנו לנחש כדי למצוא את הרצף החבוי. האם כדאי לנו לבחור שני צבעים שונים בתור ניחוש ראשון או שמא כדאי לנו לבחור שני צבעים שונים?

בטבלה נרשום לכל סוג ניחוש (xx, xy) כמה רצפים חבויים מתאימים לכל אחד מהציונים האפשריים.

לפי הטבלה, אם ננחש שני צבעים זהים (xx), השחקן שמולנו יעניק לנו אחד משלושת הציונים האלה:

בול, בול – אם ניחשנו בדיוק את הרצף המוחבא.

בול אחד – אם אחד הצבעים שניחשנו נכון והאחר אינו נכון. ארבעה מתשעת הרצפים האפשריים יניבו את הציון הזה, ולכן מופיע בטבלה המספר 4. כדי להמחיש את המצב הזה באופן ברור יותר נניח שהשחקן ניחש "כחול כחול" וקיבל כציון בול אחד. הרצף החבוי יכול להיות אחד מארבעה רצפים: כחול ירוק, כחול אדום, אדום כחול או אדום ירוק.

(כלום) – אם הצבע שבחרנו אינו מופיע כלל ברצף המוחבא. ארבעה מתוך תשעת הרצפים האפשריים יניבו ציון זה.

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

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

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

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

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

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

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

יוסי ומיכל אלרן
מכון דוידסון לחינוך מדעי
מכון ויצמן למדע

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