משחק החיים
29/07/2020
אנשים שעוקבים אחרי הדיווחים על תנועות נשאי קורונה, מספרים בבדיחות שהם מרגישים כמו גיבורים במשחקי מחשב ישנים. מישהו כתב שהוא מדמה את עצמו למשתתף במשחק "שולה מוקשים", בו צריך להעריך בכל צעד היכן קיים חשד להמצאות מוקשים ("נשאים"). אחרים מדמים שהם משחקים ב- “Pac-Man”, בו יש צורך לנווט בזהירות, לאסוף פרסים (למשל: קרטוני ביצים מהסופר), ולהתחמק "ממפלצות משוטטות", כמו נשאי קורונה, או להבדיל משוטרים ופקחים.
לאחרונה, עלה לכותרות גם אחד המשחקים המתמטיים הידועים: "משחק החיים". יוצרו, המתמטיקאי הגדול ג'ון הורטון קונוויי, מת באפריל האחרון מסיבוכי מחלת COVID-19, בגיל 82 [1]. קונוויי היה מתמטיקאי ססגוני שתרם בתחומים רבים במתמטיקה, אולם שמו נקשר במיוחד למשחק זה.
"משחק החיים" הוא סימולציה למחזור החיים של יצורים דמיוניים. אולם, לשם גיוון נדמה אותו דווקא לסימולציה של מקום הישיבה של משתתפים באולם כנסים. המשתתפים בכנס משעמם מעוניינים לשבת בשכנות לעמיתיהם, להשמיע ולשמוע רכילויות. (נגדיר "שכן" כמי שיושב על אחד משמונת הכיסאות הצמודים למשתתף, כולל באלכסון). אם משתתף יושב לבד או ליד שכן אחד, הוא ישתעמם ויעזוב בהפסקה. אם יש לו ארבעה או יותר שכנים, הוא יתקשה להתבטא, ולכן יעזוב. המצב המועדף הוא שלושה שכנים, ולכן כשיש באולם כיסא פנוי ששלושה משכניו מאוישים, משתתף חדש ייכנס לאולם למלא אותו.
למרות פשטותו, כמות האפשרויות במשחק הנגזרות מהמיקומים בתחילת הכנס היא עצומה. למשל, נניח שאתם יושבים כאשר לפניכם ומאחוריכם יושב מישהו. אתם מרוצים, אולם היושב מקדימה שיש לו רק שכן אחד, וגם זה שיושב מאחורה, משתעממים ומחליטים לעזוב בהפסקה. באותו זמן, שני אנשים שראו מקודם שיש מימינכם ומשמאלכם מקומות פנויים הצמודים לשלושה כסאות מאוישים, מתיישבים שם. לכן, בסוף ההפסקה תגלו שיש לכם שני שכנים: מימין ומשמאל. התהליך יימשך ובהפסקה הבאה השכנים המתוסכלים יעזבו ובמקומם יגיעו חדשים שישבו מלפנים ומאחור, וחוזר חלילה. מצב משונה זה, שנקרא "מתנד", הוא רק אחד משלל המצבים האפשריים במשחק. מה יקרה אם נושיב חמישה משתתפים בשורה? (התשובה באתר).
אנלוגיה מקובלת יותר היא התנהגות מושבת "חיידקים", בה כל חיידק צריך בדיוק שניים או שלושה שכנים כדי לשרוד, וכשיש מקום פנוי ליד שלושה חיידקים, יוולד שם חיידק חדש. בהתאם למצבה ההתחלתי, המושבה יכולה להשתנות, לקטון או לגדול, לעיתים עד אינסוף. המשחק הוא הדגמה פשוטה ל"אוטומט תאי" - מושג בסיסי במדעי המחשב. ברבות השנים פותחו למשחק הרחבות רבות, ונודעה לו השפעה על רעיונות רבים במתמטיקה ומדעי המחשב.
בעיה מעניינת היא האם ניתן לכתוב תוכנית מחשב שתענה על השאלה : "האם מושבת החיידקים תפסיק אי פעם להשתנות, בהינתן מצב התחלתי כלשהו?" המתמטיקאים גילו שלא ניתן לעשות זאת, שכן בעיה זו שקולה ל"בעיית העצירה" [2] המפורסמת, שמחשבים לא מסוגלים לפתור. לכן, עתיד מושבת החיידקים יישאר במקרים מסוימים לוט בערפל.
בתקופה קשה זו, אנו מזמינים אתכם לנסות אפליקציה שפיתחנו העושה סימולציה למשחק. באמצעותה תוכלו למשל לתכנן כיצד למקם את המשתתפים בכנס הבא שתארגנו (כשיתאפשר!), או סתם להשתעשע מהיופי והעושר של "משחק החיים".
קישורים ומקורות:
[1] ג'ון הורטון קונוויי נפטר – דוידסון
מהנדס מחשבים, חוקר ויזם בתחום החינוך המתמטי.
