היי,
מצאתי את הפוסט הזה בפייסבוק, החידה ממש מעניינת מוזמנים לנסות לפתור את החידה בעזרת קוד בפייתון -
חידה!
אתם משחקים משחק קטלני עם השחקן הכי חכם בעולם (אף פעם לא טועה)!
המשחק הוא די פשוט:
יש אבן אחת שחורה
וכמה אבנים לבנות (מספר סופי)
מהלך המשחק:
כל אחד בתורו חייב לקחת בין 1 ל 3 אבנים.
המפסיד:
השחקן שחייב לקחת את האבן השחורה.
המטרה:
לבנות אלגוריתם כך שבהינתן כמות מסויימת של אבנים לבנות יכריע מי מתחיל.
החידה היא מסוג החידות הנקראות nim,
והיא מקוטלגת כמשחק בתאוריית המשחקים.
מה הכוונה ‘יכריע מי מתחיל’?
מי השחקן שאמור להתחיל בשביל לנצח, אתה או השחקן הכי חכם בעולם.
טוב, זה…היה נראה מעניין לרגע, ואז הבנתי ש:
השחקן השני תמיד יכול להשלים את סך האבנים שנלקחו על ידי שני השחקנים בשני התורות האחרונים ל-4.
מפה זה כבר מספיק פתור, מבחינתי.
חשבת איך לעלות את זה בקוד?
האמת שנגשתי “לפרום” את זה בצורת חשיבה שמתחילה מ-“איזו פונקציה תבדוק שנצחתי?” -
הרגשתי שעניין האבנים בצבעים טיפה מבלבל,
ושבמקום, אפשר לומר ש:
-נצחתי כי בתורי לקחתי את האבנים האחרונות.
(או: הפסדת - כי השארתי לך 0 אבנים לקחת).
אם יש על הלוח 1-3 אבנים:
*אז אני אקח את מה שנשאר - ונצחתי. (כי לא השארתי לך כלום).
אם יש על הלוח בדיוק 4 אבנים:
אז אני אתן ליריב להתחיל. ואז לא משנה כמה אבנים הוא ייקח, אנחנו נחזור למצב (1), ומפה כבר פתרנו
*כדאי לשים לב: אם יש 4 אבנים על הלוח, וזה תורנו - אז יריב חכם בוודאות ינצח אותנו.
אם יש על הלוח 5-7 אבנים:
אז נקח 1-3 אבנים בהתאמה, אז “נתקע את היריב עם 4”,
מה שיביא אותנו ל-(2), ומפה כבר נגיע ל-(1), ופתרנו.
*כדאי לשים לב: אם אתה לא “תתקע את היריב עם 4”, אז הוא יכול בהכרח לתקוע אותך, ואז לנצח.
אני חושב שמפה כבר אפשר לראות איך זה ממשיך מכאן, ואיך בכל שלב אפשר לחזור למקרה קודם ש-“מפה כבר פתרנו”, ואיך קיימת שיטת משחק “אולטימטיבית”.
בגדול, אפשר לתכנת משחק, ולתת לכל שחקן את “טכניקת המשחק המנצחת”, ולהריץ את המשחק כך שכל שחקן ישחק בתורו ויעשה בחירה (מבוססת תנאים) על פי האסטרטגיה…ולהריץ את זה על לולאה של משחק עם כמות אבנים הולכת וגוברת, ולשים לב לחוקיות מסויימת. (שקיימת - ואז נשאר רק לקוות לטוב, ולהניח שהיא מתקיימת לנצח, ושזה לא סתם צירוף מקרים)
העניין הוא שלא צריך להגיע לשם, כי “תנאי הבדיקה” של “שיטת המשחק האולטימטיבית” -
תקע את היריב שלך עם כפולה-של-4 אבנים בתורו, ואתה תנצח.
אם לא תעשה כן - היריב בהכרח יהיה יכול לתקוע אותך עם כפולה-של-4 אבנים בתורך, ולנצח.
עכשיו - בהנתן לפחות שחקן אידאלי אחד, אנחנו תמיד נגיע לכלל הזה, ולכן אין פה מקרים שלא מכוסים.
או בקיצור:
-אם מספר האבנים על הלוח מתחלק ב-4 ללא שארית: תן ליריב להתחיל, ומשם אתה יכול בהכרח לנצח.
-אחרת: תתחיל אתה, ואז תתקע את היריב עם המצב שבו מס’ האבנים על הלוח מתחלק ב-4 וזה תורו, ומשם אתה יכול בהכרח לנצח.
-בשלב הזה כבר יש לנו פתרון ביד, ואנחנו לא זקוקים למחשב. 