ב-Online
 
 
 
 
 
 
 
לפרק את הבייט 
בין קלפים לפצצות אטום 
 
  צילום: Gettyimages    
לפרק את הבייט |
 

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

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

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

משחקי מלחמה

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

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

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

האקראיות בשירות החוקר

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

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

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

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

קדימה לפרמוטציות

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

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

נניח שהיו לנו תשעה-עשר ילדים בסך הכל, תשעה בקבוצה א' ועשרה בקבוצה ב'. הממוצע של קבוצה א' במבחן היה 6.7 ושל קבוצה ב' – 7.1, כלומר הפרש של 0.4 בין הממוצעים. מה שהתוכנה שלנו עושה הוא לקחת את כל 19 התוצאות, לערבב אותן ולחלק אותן אקראית לקבוצה של 9 ולקבוצה של 10. עשינו זאת פעם אחת וקיבלנו הפרש של 0.3. עשינו זאת שוב וקיבלנו הפרש של 0.6. אם נחזור על הפעולה 92,378 פעמים (מספר הקומבינציות האפשריות של 19 ילדים בשתי קבוצות כאלה), נקבל התפלגות של כל ההפרשים האפשריים. היכן נמצא, בהתפלגות זו, ההפרש המקורי של 0.4? אם הוא קרוב מאד לקצה ההתפלגות, בתחום של 5% העליונים, אנחנו נדחה את השערת האפס: על פי הקריטריונים שהגדרנו, כנראה שההבדל בין נוטלי הריטלין לאחרים אינו מקרי.

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

איך ניתן להשתמש במבחן הפרמוטציות כדי לפתור את חידת ה"מלחמה" שהצגנו בהתחלה? השערת האפס תהיה שמיקומם של האסים והג'וקרים אינו משנה, ושלשחקן יש סיכוי של 50% לנצח במשחק. נשתמש בחפיסת הקלפים בתור ה"נתונים" שלנו, נערבב אותם שוב ושוב, נחלק בין שני השחקנים – אך נוודא תמיד, באמצעות החלפה בעת הצורך, ששחקן א' יקבל את הגבוהים. נשלח אלף חלוקות כאלה לפונקציה נפרדת שמשחקת "מלחמה" עד שהיא מגיעה להכרעה, ונספור כמה פעמים שחקן א' זכה. את אחוזי הזכיה ואת מספר המשחקים הכללי נוכל להזין לתוך מחשבון התפלגות בינומית (בכל זאת, אי אפשר בלי קצת סטטיסטיקה קלאסית!) ולגלות, אחת ולתמיד, את התשובה.
 
 
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
 
תגובות
הוסף תגובה0 תגובות
הוספת תגובה
מאת
 
נושא
 
תוכן
 
 
 
 
תודה! תגובתך התקבלה.
התגובה תתפרסם בכפוף לתנאי האתר.
 
 
 
 
 

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by