בתשובה למיץ פטל, 02/08/03 22:07
חידה 161172
אבל איך זה יעזור לי? אז אני אקבל את התוחלת למשחק של 8 קלפים. יש. הסימולציה שלי אומרת לי כרגע "אם יש לך בקופה X שקלים, הפסק למשוך" (לגלות את X?), ודי סביר שזה נכון, אבל א. - מי אמר שזה נכון, אפילו אם אני אריץ על כל האפשרויות למשחק של 8 קלפים וב. - זה לא כל כך מעניין. אני רוצה לדעת למה, לא רק כמה.
חידה 161174
אתה לא יכול להתאים את X למקרה של 8 קלפים? הרי בטח הגעת ל-X דרך 52. או שבדקת רק אסטרטגיות מסוג "אם יש לך בקופה X שקלים, הפסק למשוך", ומבין אלה, עבור מדגם של חפיסות 52 קלפים ועבור מדגם של Xים גילית שיש ערך X שונה מ-‏1 המביא לתוחלת גבוהה מ- 26/27 ?

א. מה זה "זה"? שהאסטרטגיה המיטבית היא מסוג "אם יש לך בקופה X שקלים, הפסק"?
עדכון 161197
רבע דף A4 הספיק לניתוח המשחק בן 4 קלפים (כלומר לבחינת *כל* האסטרטגיות). במקרה זה, האסטרטגיה המיטבית אינה מטיפוס "אם יש לך בקופה X שקלים, הפסק למשוך", ותוחלת הרווח שלה היא 7/8. לכן קשה לי להאמין שבמקרה המורכב יותר של 52 קלפים, האסטרטגיה המיטבית תהייה מהטיפוס הנ"ל. (עם זאת, מבין האסטרטגיות הנ"ל, עבור 4 קלפים המנצחת היא כמובן X=1 ). אני חושש שאין לי די נייר וסבלנות לניתוח המשחק בן 6 הקלפים.
רבותי נברר 161200
בשלב כלשהו במשחק, יש לפנינו n קלפים אדומים ו-k קלפים שחורים. עלינו לקבל החלטה: האם למשוך קלף, או לעצור? ההחלטה תלויה אך ורק במספרים n ו-k, ולא במה שהרווחנו עד כה. אם קביעה זו טעונה הסבר, אשמח להסביר.

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

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

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

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

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

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

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

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

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

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

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

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

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

- אלון
רבותי נברר 161218
טוב, העובדה שקיימת אסטרטגיה מיטבית ברורה, וכך גם העובדה שניתן לחשב אותה כפי שהצעת. מניתוח המשחק ה-‏4-קלפי כבר עולה שהאסטרטגיה המיטבית אינה כלל התלוי רק במה שהרווחנו עד כה, כך שאתה לא צפוי להפתעות. השאלה המעניינת היא מה הנוסחא לתוחלת המירבית במשחק עם 2n קלפים.
תיקון 161217
התוחלת במשחק בן ארבעת הקלפים היא 5/6. במשחק עם שישה קלפים, 19/20.
תיקון 161220
אתה בטוח? לדעתי, התוחלת במשחק עם ארבעה קלפים (שני אדומים, שני שחורים) היא 2/3. הבה נראה: האם אתה מסכים שהמצב (אדום, שני שחורים) שווה 0? ושהמצב (שחור, שני אדומים) שווה 4/3?

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

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים