אז איך מגרילים מספרים במחשב?

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

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

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

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

הפתרון השני הוא להסתמך על גורמים שאינם בדיוק אקראיים מבחינה פיזיקלית, אבל לכל דבר ועניין נראים אקראיים - למשל, הקלדות על המקלדת. מן הסתם יש חוקיות גדולה למדי בהקלדות על המקלדת (למשל, כשכותבים באנגלית, צפוי שמייד אחרי כתיבת q ייכתב u), אבל אם נמדוד את קצב ההקלדה, ובפרט את מספר השניות שעוברות בין כל הקלדה לזו שאחריה, נראה משהו אקראי למדי (שכמובן, נע בתוך תחום מוגדר). באותו אופן גם תנועות העכבר הן “אקראיות” (חשבו על כך שכל תזוזה, ולו הקטנה ביותר של העכבר, נמדדת; כך שגם אם מזיזים את העכבר מנקודה א’ לנקודה ב’, יש אלפי דרכים שונות לעשות זאת, וזו שנבחרת היא “אקראית”). ישנם עוד גורמים “אקראיים” בריצת המחשב, אבל לא נתעמק ברובם; במקום זה נעסוק במקור הפופולרי והנפוץ ביותר לאקראיות, למרות שהחוקיות שבו גדולה מאוד - השעון הפנימי.

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

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

כל זה טוב ויפה, אבל נניח שאני רוצה מספר אקראי בין 1 ל-6, כלומר הטלת קוביה. מה אני עושה? אני לוקח את הפלט של הפעלה אחת של המחולל, ובמקום להשתמש במספר כמות שהוא (כי כאמור, זה יהיה מספר ענקי) אני בודק מה השארית שהמספר הזה נותן בחלוקה ב-6 (כלומר, מהו ערכו של המספר מודולו 6). זה יהיה ערך בין 0 ל-5, שמתפלג באופן אחיד אם המחולל אכן מוצלח (כלומר, אם אחזור על ההגרלה הזו פעמים רבות, אראה שכל מספר התקבל בערך שישית מהפעמים). בצורה דומה אפשר לקבל מספר טבעי בכל טווח שהוא; אפשר גם להגריל מספרים “ממשיים” בתחום שבין 0 ו-1, פשוט על ידי נרמול - חלוקת המספר האקראי שהמחולל החזיר, במספר המקסימלי שהוא יכול להחזיר. התוצאה שתתקבל תמיד תהיה מספר רציונלי, אבל ממילא רק מספרים כאלו מיוצגים במחשב בשיטת הייצוג הסטנדרטית.

כאן המקום לתאר כמה מחוללים קונקרטיים, אבל לא אעשה זאת, פשוט כי המתמטיקה של מחוללים טובים היא סבוכה וטכנית. אחד המחוללים הראשונים (אם לא הראשון) והפשוטים ביותר הומצא על ידי ג'ון פון נוימן - קח מספר בן n ספרות, העלה אותו בריבוע וקבל מספר עם 2n ספרות (הוסף 0 בתחילת המספר שהתקבל אם יש צורך), וכעת קח את n הספרות האמצעיות בתור הפלט. הבעיה בשיטה החביבה הזו היא שלולאות צצות יחסית מהר. פון נוימן, שמיוחס לו הציטוט “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”’, כנראה לא נזקק למשהו מחוכם יותר, אבל בשימושים קריפטוגרפיים, ואפילו עבור משחקים, זה לא מספיק טוב. הנה עוד דוגמה למחולל שכנראה לא כדאי להשתמש בו, באדיבות xkcd:

כעת אפשר להסביר מהו ה-Randomize timer של בייסיק. כשקוראים בשפת תכנות כלשהי לפונקציה שמחזירה מספר אקראי, לרוב הפונקציה הזו משתמשת במימוש של מחולל פסאודו אקראי זה או אחר. הגרעין של המחולל הזה מאותחל כאשר התוכנית מתחילה לרוץ - השאלה היא לאיזה ערך הוא יאותחל. אם השפה מאתחלת אותו תמיד ל-0, מן הסתם תמיד נקבל את אותה סדרה אקראית. לכן כדי לקבל סדרות שונות בכל הרצה, יש להשתמש במקור שמובטח שתמיד יתן ערך שונה - והשעון הפנימי של המחשב הוא המקור המושלם לכך. הפקודה Randomize timer מאתחלת את הגרעין של המחולל האקראי לערך שמושג מהשעון; בשפות אחרות יש פונקציה בשם srand שעושה את אותו הדבר. אלא שאין הכרח לאתחל דווקא באמצעות השעות; אפשר לאתחל גם באמצעות ערך מספרי שמועבר על ידי המשתמש עצמו, וכאן נכנס לתמונה אחת ההיבטים החביבים ביותר של מחולל פסאודו אקראי - אפשר לשחזר במדוייק את הסדרות האקראיות שהוא מייצר. פשוט מכניסים שוב את אותו גרעין, ומקבלים את אותה סדרה. בשביל מה זה טוב?

לפני שנים הייתי מכור למשחק מחשב אווילי בשם Worms, שבו אתה שולט על צוות תולעים אכזריות שמפצפצות לצוותים אחרים של תולעים את הצורה עם בזוקות, רימונים ושאר מרעין בישין. הקרבות התנהלו בשדה קרב שנוצר באופן אקראי. חלק משדות הקרב היו מוצלחים במיוחד (נניח, הם היו עמוסים בצוקים שאם תולעת עומדת עליהם, אפשר לפצפץ אותה לאינסוף ביתר קלות). איך אפשר, אם כן, לשחזר את אותו שדה קרב? פשוט מאוד - לכל שדה קרב שהוגרל היה כתוב באופן מפורש הגרעין של המחולל הפסאודו אקראי שיצר אותו. כדי לקבל את אותו שדה קרב, היה צורך לכתוב מחדש את הגרעין, וזהו. כמובן, הגרעין נראה סתם כמו ג’יבריש מאוד ארוך וזה לא היה הכי פרקטי לזכור אותו; אבל אפשר היה להכניס גרעינים משלך, פשוט בתור טקסט באנגלית (ההמרה של הטקסט למספר בוצעה, כמובן, מאחורי הקלעים), ולראות מה קיבלת. כך למשל, אם היית כותב “Alamo” היית מקבל דבר אחד (שנוצר בצורה אקראית לגמרי, ויכל להיות מוצלח או לא מוצלח, תלוי במזל), ואם היית כותב “Waterloo” היית מקבל משהו שונה; אבל בכל פעם שבה היית כותב אותם, היית מקבל את אותו שדה קרב כמו בפעם הקודמת. התעלול נפוץ גם במשחקי מחשב אחרים, כמובן.

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

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

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