 |
בשלב כלשהו במשחק, יש לפנינו n קלפים אדומים ו-k קלפים שחורים. עלינו לקבל החלטה: האם למשוך קלף, או לעצור? ההחלטה תלויה אך ורק במספרים n ו-k, ולא במה שהרווחנו עד כה. אם קביעה זו טעונה הסבר, אשמח להסביר.
איך לקבל את ההחלטה? נניח שלצדנו פיה טובה היודעת להשיב על השאלה הבאה: מהי תוחלת הרווח ממשחק עם n אדומים ו-k שחורים, אם נשחק בצורה מיטבית? הפיה איננה אומרת איך יש לשחק, רק מהי תוחלת הרווח אם משחקים נכון.
אם נעצור, נקבל בדיוק 0 (נוסף כמובן על מה שכבר הרווחנו או הפסדנו עד כה). אם נמשוך, יקרה אחד מהשניים:
(+) נמשוך קלף אדום, נרוויח שקל, ונגיע למצב שבו לפנינו n-1 קלפים אדומים ו-k שחורים.
(-) נמשוך קלף שחור, נפסיד שקל, ונגיע למצב שבו לפנינו n קלפים אדומים ו- k-1 שחורים.
הסיכויים לכל אחת מהאפשרויות קלים לחישוב. כעת נברר, באמצעות הפיה, מהי תוחלת הרווח במשחקים שאליהם אנו עשויים להגיע, כלומר המשחק עם פחות קלף אדום או פחות קלף שחור. בהינתן שני מספרים אלה, והסיכויים ל-(+) ול-(-), נקבל מיד את תוחלת הרווח אם נחליט למשוך.
עכשיו זה קל: אם תוחלת זו חיובית, יש למשוך. אם היא שלילית, יש לעצור ולהסתפק ב-0.
טוב, אבל מה עם הפיה? כפי שבוודאי הבנתם, אין בה צורך, מפני שהניתוח הפשוט לעיל מורה את הדרך לחישוב תשובתה של הפיה בצורה נסיגתית: תשובת הפיה למצב נתון ניתנת לחישוב מתשובותיה למצבים פשוטים יותר.
כמובן שאשמח לפרט אם דרושים יותר רמזים. בינתיים רק אציין כמה עובדות פשוטות כדי שמי שמנסה לפתור יוכל להשוות תוצאותיו לשלי:
אם יש רק קלף אחד אדום וקלף אחד שחור, תוחלת הרווח היא מחצית השקל.
במשחק עם ארבעה קלפים שחורים וארבעה אדומים, תוחלת הרווח היא בדיוק שקל! בקרוב אנסה לרשום במפורט את האסטרטגיה למקרה זה כדי שייקל לוודא זאת.
במשחק עם 8 אדומים ו-8 שחורים, תוחלת הרווח היא 1.43411.
לפטופי האומלל עדייו טוחן את המשחקים הסבוכים יותר. בכל אופן, אם כלל העצירה המיטבי תלוי רק במה שהרווחנו עד כה זה יפתיע אותי מאוד. מצד שני, כיוון שראינו שכלל זה תלוי רק בכמות השחורים והאדומים שנותרו, ברור שניתן לנסחו ככלל שתלוי רק במה שהרווחנו עד כה *וגם* בכמות הקלפים שכבר משכנו.
ייתכן שהחמצתי איזו סימטריה מעניינת ואכן הנתון השני אינו חשוב - אבדוק זאת ואשוב אליכם.
- אלון
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש