ב-Online
 
 
 
 
 
 
 
לפרק את הבייט 
מפרקים את שולה המוקשים 2 
 
 איך מפצחים את ``שולה המוקשים``. צילומסך ועיבוד: עידו גנדל   
לפרק את הבייט |
 

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

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

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

לפצל את האלגוריתם

באחד הטורים הקודמים הצגנו אלגוריתם שקובע האם מספר נתון הוא ראשוני. האלגוריתם היה כללי, ועבד באמצעות בדיקה האם המספר מתחלק ללא שארית במספר כלשהו בין 2 לשורש של עצמו. מבין הפעולות המתמטיות הבסיסיות, פעולת החלוקה נחשבת לתובענית ביותר מבחינת המעבד. אם היו נותנים לנו לבדוק מיליארד מספרים אקראיים, היינו יכולים אמנם להפעיל את האלגוריתם על כל אחד ואחד מהם, אבל היינו יכולים להיות יעילים עוד יותר ולפצל את אלגוריתם הזיהוי לשניים: אחד שבודק האם המספר זוגי (בדיקה שניתן לבצע באמצעות פעולות לוגיות פשוטות מאד על הביטים של המשתנה, בלי צורך בפעולת החילוק), ואלגוריתם שני רגיל שבודק את כל המספרים שהתגלו כאי-זוגיים, כי אם נתעלם מ-2 עצמו, רק מספר אי זוגי יכול להיות ראשוני. סטטיסטית, חצי מהמספרים לבדיקה יהיו זוגיים, וכך חסכנו המון פעולות חילוק מיותרות במחיר של תוכנה קצת יותר מסובכת.
 
 
פתרונות פשוטים (צילומסך: עידו גנדל)
 פתרונות פשוטים (צילומסך: עידו גנדל)   
אותו הדבר נכון לגבי פתרון "שולה המוקשים". ייתכן שאפשר לנסח אלגוריתם כללי למציאת מוקשים, שיכלול הסתברויות וחישובי חפיפה ומה לא, אבל הוא יהיה קצת מורכב וקצת כבד מדי בשביל רוב מקרי הזיהוי. קחו לדוגמה את הלוח שמשמאל. בחלקו השמאלי, בשורה השלישית מלמעלה, יש שני מספרים שמעידים חד משמעית שהריבוע המוסתר שנוגע בהם הוא מוקש. אין שום אי-ודאות ואין שום אפשרות אחרת. מדוע לא להתחיל באלגוריתם שמזהה מקרים פשוטים שכאלה ומסמן אותם? אלגוריתם זה צריך, בעצם, לעבור על כל המספרים הגלויים (נקרא לערך המספרי K) ועבור כל אחד מהם, לספור כמה ריבועים מוסתרים יש סביבו (לזה נקרא H) וכמה מוקשים מסומנים (M). אם K = M, יש "לפתוח" את כל הריבועים המוסתרים. לעומת זאת, אם K = H+M, יש לסמן את כל הריבועים המוסתרים כמוקשים. המשוואות הללו מכסות גם מקרים בהם H או M שווים לאפס. בהנחה שהשחקן האנושי לא מתערב ומסמן מוקשים במקומות שגויים, ברוב המקרים אפשר יהיה לפתור חלק ניכר מהלוח באמצעות הרצה חוזרת של אלגוריתם זה בלבד.
 

כיצד לתכנת באמצעות פטיש

פתרונות מורכבים (צילומסך ועיבוד: עידו גנדל)
 פתרונות מורכבים (צילומסך ועיבוד: עידו גנדל)   
כעת מגיע השלב המורכב יותר, שבו מספר בודד אינו נותן מספיק מידע כדי לגלות את המוקש (ונתעלם לצורך העניין מהמידע הנוסף שמספק לנו מספר המוקשים בלוח כולו). כפי שהראה המגיב בתגובה 5 בחלק הקודם, ישנם רצפים נפוצים למדי של מספרים, שאם מפעילים קצת היגיון אפשר לזהות בהם את המוקשים או את חלקם, או לפחות לדעת היכן בוודאות אין מוקש. מקרה לדוגמה מוצג משמאל. הסתכלו על המספר 3 שבצד ימין של הלוח. יש מוקש ידוע אחד מעליו, כלומר שעלינו למצוא עוד שניים (לפי הנוסחה הכללית K - M) שמסתתרים מתחתיו. על סמך ה-2 שמימין ל-3, ברור שיש מוקש אחד בלבד בשני הריבועים שמימין, ומכאן שהמוקש השלישי נמצא מתחת ל-2 שמשמאל ל-3. אחרי שנסמן מוקש זה, נראה שלא יכול להיות שיש מוקש נוסף מתחת ל-3, ולכן הוא חייב להיות מתחת ל-2 שמימין. נשמע מסובך? לתכנת את זה מסובך עוד יותר. אלגוריתם כללי טוב באמת יצטרך לבודד אזורים רלוונטיים לחיפוש מוקשים על סמך מספרים הגלויים (לדוגמה, האזורים שמוקפים במלבן שחור בתמונה לעיל), לאתר את כל החפיפות בין האזורים הללו, ואז להפחית – אם אפשר – את מספר המוקשים שבאזורים החופפים מהמספר שבאזורים המקוריים עד שתתקבל תוצאה חד-משמעית כלשהי. זו פעולה סבירה כשמדובר בשורה בודדת כמו במקרה שלנו, אבל בפועל יכולים להיות מקרים מורכבים בהרבה, עם מספרים ואזורים מכל ארבעת הכיוונים, וחישוב החפיפות יכול להפוך לכאב ראש רציני.

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

שהמחשב יבדוק את כל האפשרויות

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

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

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

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