הנפילה הגדולה והקושי של שולה המוקשים

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

התחלה טובה
התחלה טובה

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

אלה לא המוקשים שאתה מחפש

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

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

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

אבל כמו שאומרים, פעם שלישית גלידה: האפליקציה החינמית השלישית אשכרה עבדה בלי להתרסק, ונראתה לא רע והגיבה במהירות נסבלת, פלאי פלאים! ורק כשעליתי על מוקש צצה הודעת הפטירה העילגת "Maybe it's just back luck…" [כך במקור].

ועכשיו למשהו שונה רק קצת

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

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

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

והנה סיפור מעניין באמת: מישהו הוכיח שפתרון של לוח Minespweeper הוא בעיה מסוג NP-Complete, כלומר כזו שאי אפשר לפתור בזמן פולינומי. אני לא אעמיד פנים שאני מבין ממש לעומק מה זה אומר – ולא שזה הפריע לי לכתוב על הנושא בעבר – אבל ממה שהצלחתי להבין, הדרך שהוא עשה את זה היא מסוג הדברים שגורמים לך לחייך חיוך רחב בהתחלה, ואחר כך לזחול בבושה לפינה כי בחיים לא היית יכול לחשוב על זה בעצמך. בקיצור, כדי להראות שפתרון המשחק הוא NP-Complete, מחבר המאמר המיר את שולה המוקשים לבעיה אחרת, שהיה ידוע עוד קודם שהיא בעצמה NP-Complete: בעיית SAT (קראו בעצמכם, אין לי כוח). זו בעיה של לוגיקה בוליאנית, שאפשר לייצג עם שערים לוגיים. אז כל מה שצריך זה ליצור מערכים של Minesweeper שיהיו מקבילים לשערים לוגיים ולחיבור ביניהם, ואז אפשר לבנות מהם ביטויים שמתאימים ל-SAT, ואז יוצא ש-Minesweeper הוא NP-Complete. כי אם זה לא היה ככה, אז פתרון מהיר של שולה המוקשים היה פותר במהירות גם את SAT, וזה סותר את ההגדרה של NP-Complete. נכון? נכון?

הקאץ' (וחלק גדול מהגאונות) הוא כמובן ביצירה של המערכים האלה, ולשם כך הנה שוב הקישור ל-PDF למקרה שפספסתם: הכיף מתחיל בדף 5, ומסוף עמ' 6 (שער XOR) זה נהיה מטורף לגמרי. תענוג.

זהו בינתיים, אני חוזר להשתעל. להתראות בפוסט הבא…

 

 

2 thoughts on “הנפילה הגדולה והקושי של שולה המוקשים”

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *