בתשובה למיץ פטל, 03/08/03 0:18
רבותי נברר 161200
אלון עמית • בתשובה למיץ פטל יום א', 3/8/2003, 1:03
בשלב כלשהו במשחק, יש לפנינו n קלפים אדומים ו-k קלפים שחורים. עלינו לקבל החלטה: האם למשוך קלף, או לעצור? ההחלטה תלויה אך ורק במספרים n ו-k, ולא במה שהרווחנו עד כה. אם קביעה זו טעונה הסבר, אשמח להסביר.

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

אם נעצור, נקבל בדיוק 0 (נוסף כמובן על מה שכבר הרווחנו או הפסדנו עד כה). אם נמשוך, יקרה אחד מהשניים:

(+) נמשוך קלף אדום, נרוויח שקל, ונגיע למצב שבו לפנינו n-1 קלפים אדומים ו-k שחורים.

(-) נמשוך קלף שחור, נפסיד שקל, ונגיע למצב שבו לפנינו n קלפים אדומים ו- k-1 שחורים.

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

עכשיו זה קל: אם תוחלת זו חיובית, יש למשוך. אם היא שלילית, יש לעצור ולהסתפק ב-‏0.

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

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

אם יש רק קלף אחד אדום וקלף אחד שחור, תוחלת הרווח היא מחצית השקל.

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

במשחק עם 8 אדומים ו-‏8 שחורים, תוחלת הרווח היא 1.43411.

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

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

- אלון
רבותי נברר 161218
מיץ פטל • בתשובה לאלון עמית יום א', 3/8/2003, 8:12
טוב, העובדה שקיימת אסטרטגיה מיטבית ברורה, וכך גם העובדה שניתן לחשב אותה כפי שהצעת. מניתוח המשחק ה-‏4-קלפי כבר עולה שהאסטרטגיה המיטבית אינה כלל התלוי רק במה שהרווחנו עד כה, כך שאתה לא צפוי להפתעות. השאלה המעניינת היא מה הנוסחא לתוחלת המירבית במשחק עם 2n קלפים.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות