בתשובה למיץ פטל, 02/08/03 19:09
 |
|
 |
||
|
||||
 |
אני לא חושב שזו האסטרטגייה הטובה ביותר. הסיבה שאני מסייג זה כי אני יודע את התשובה רק נומרית - סימלצתי הכל במטלב, וראיתי מה הכי הרבה רווח שאפשר להוציא בסיכוי טוב. אשמח לפתרון יותר אינטליגנטי. |
 |
 |
 |
|
|
|
||
|
||||
|
האסטרטגיה הטובה ביותר היא זו עם תוחלת הרווח הגדולה ביותר, כן? אני מבין שאינך יודע מה האסטרטגיה המיטבית אולם יש לך אסטרטגיה שתוחלת הרווח שלה גדולה משל האסטרטגיה שהצעתי, אבל גם בכך אינך משוכנע כי הסימולציה שלך לא כללה את כל ה-52 מעל 26 אפשרויות. נכון? האם ניסית לבדוק אותה במלואה על חפיסה בת 8 קלפים, למשל? | |
|
|
|
|
|
||
|
||||
|
כל סדרה סופית של משחקים עם תוחלת 0 תניב תוחלת 0. אם המטרה היא אחרת, נא לציין זאת בחידה. |
|
|
|
|
|
|
||
|
||||
|
אנו דנים בתוחלת הרווח של אסטרטגיות שונות במשחק הנתון. לי (וכנראה גם לגלעד) אסטרטגיות שתוחלת הרווח שלהן חיובית, ובפרט אינה 0. החידה היא מהי האסטרטגיה שתוחלת הרווח שלה היא המירבית. כל אסטרטגיה שתוצג תקבע חסם מלרע על התוחלת (וכאמור אנו כבר יודעים שהחסם הוא חיובי). גם הצגת חסם מלעיל לא-טריוויאלי תבורך, במיוחד אם החסם זהה לחסם מלרע שהוצג. | |
|
|
|
|
|
||
|
||||
|
התוחלת היא אפס רק במשיכה הראשונה - אחר כך יש שוני במספר הקלפים השחורים והאדומים שנשארו בחפיסה. התוחלת של המשחק כולו היא בברור חיובית - הרי אם תמשוך את כל הקלפים, תצא על אפס, אז אם תפסיק ברגע שמשכת 26 אדומים, ונארו עוד קלפים בחבילה, הרווחת. (לא האסטרטגיה המיטבית). |
|
|
|
|
|
|
||
|
||||
|
אבל איך זה יעזור לי? אז אני אקבל את התוחלת למשחק של 8 קלפים. יש. הסימולציה שלי אומרת לי כרגע "אם יש לך בקופה X שקלים, הפסק למשוך" (לגלות את X?), ודי סביר שזה נכון, אבל א. - מי אמר שזה נכון, אפילו אם אני אריץ על כל האפשרויות למשחק של 8 קלפים וב. - זה לא כל כך מעניין. אני רוצה לדעת למה, לא רק כמה. | |
|
|
|
|
|
||
|
||||
|
אתה לא יכול להתאים את X למקרה של 8 קלפים? הרי בטח הגעת ל-X דרך 52. או שבדקת רק אסטרטגיות מסוג "אם יש לך בקופה X שקלים, הפסק למשוך", ומבין אלה, עבור מדגם של חפיסות 52 קלפים ועבור מדגם של Xים גילית שיש ערך X שונה מ-1 המביא לתוחלת גבוהה מ- 26/27 ? א. מה זה "זה"? שהאסטרטגיה המיטבית היא מסוג "אם יש לך בקופה X שקלים, הפסק"? |
|
|
|
|
|
|
||
|
||||
|
רבע דף A4 הספיק לניתוח המשחק בן 4 קלפים (כלומר לבחינת *כל* האסטרטגיות). במקרה זה, האסטרטגיה המיטבית אינה מטיפוס "אם יש לך בקופה X שקלים, הפסק למשוך", ותוחלת הרווח שלה היא 7/8. לכן קשה לי להאמין שבמקרה המורכב יותר של 52 קלפים, האסטרטגיה המיטבית תהייה מהטיפוס הנ"ל. (עם זאת, מבין האסטרטגיות הנ"ל, עבור 4 קלפים המנצחת היא כמובן X=1 ). אני חושש שאין לי די נייר וסבלנות לניתוח המשחק בן 6 הקלפים. | |
|
|
|
|
|
||
|
||||
|
בשלב כלשהו במשחק, יש לפנינו n קלפים אדומים ו-k קלפים שחורים. עלינו לקבל החלטה: האם למשוך קלף, או לעצור? ההחלטה תלויה אך ורק במספרים n ו-k, ולא במה שהרווחנו עד כה. אם קביעה זו טעונה הסבר, אשמח להסביר. איך לקבל את ההחלטה? נניח שלצדנו פיה טובה היודעת להשיב על השאלה הבאה: מהי תוחלת הרווח ממשחק עם n אדומים ו-k שחורים, אם נשחק בצורה מיטבית? הפיה איננה אומרת איך יש לשחק, רק מהי תוחלת הרווח אם משחקים נכון. אם נעצור, נקבל בדיוק 0 (נוסף כמובן על מה שכבר הרווחנו או הפסדנו עד כה). אם נמשוך, יקרה אחד מהשניים: (+) נמשוך קלף אדום, נרוויח שקל, ונגיע למצב שבו לפנינו n-1 קלפים אדומים ו-k שחורים. (-) נמשוך קלף שחור, נפסיד שקל, ונגיע למצב שבו לפנינו n קלפים אדומים ו- k-1 שחורים. הסיכויים לכל אחת מהאפשרויות קלים לחישוב. כעת נברר, באמצעות הפיה, מהי תוחלת הרווח במשחקים שאליהם אנו עשויים להגיע, כלומר המשחק עם פחות קלף אדום או פחות קלף שחור. בהינתן שני מספרים אלה, והסיכויים ל-(+) ול-(-), נקבל מיד את תוחלת הרווח אם נחליט למשוך. עכשיו זה קל: אם תוחלת זו חיובית, יש למשוך. אם היא שלילית, יש לעצור ולהסתפק ב-0. טוב, אבל מה עם הפיה? כפי שבוודאי הבנתם, אין בה צורך, מפני שהניתוח הפשוט לעיל מורה את הדרך לחישוב תשובתה של הפיה בצורה נסיגתית: תשובת הפיה למצב נתון ניתנת לחישוב מתשובותיה למצבים פשוטים יותר. כמובן שאשמח לפרט אם דרושים יותר רמזים. בינתיים רק אציין כמה עובדות פשוטות כדי שמי שמנסה לפתור יוכל להשוות תוצאותיו לשלי: אם יש רק קלף אחד אדום וקלף אחד שחור, תוחלת הרווח היא מחצית השקל. במשחק עם ארבעה קלפים שחורים וארבעה אדומים, תוחלת הרווח היא בדיוק שקל! בקרוב אנסה לרשום במפורט את האסטרטגיה למקרה זה כדי שייקל לוודא זאת. במשחק עם 8 אדומים ו-8 שחורים, תוחלת הרווח היא 1.43411. לפטופי האומלל עדייו טוחן את המשחקים הסבוכים יותר. בכל אופן, אם כלל העצירה המיטבי תלוי רק במה שהרווחנו עד כה זה יפתיע אותי מאוד. מצד שני, כיוון שראינו שכלל זה תלוי רק בכמות השחורים והאדומים שנותרו, ברור שניתן לנסחו ככלל שתלוי רק במה שהרווחנו עד כה *וגם* בכמות הקלפים שכבר משכנו. ייתכן שהחמצתי איזו סימטריה מעניינת ואכן הנתון השני אינו חשוב - אבדוק זאת ואשוב אליכם. - אלון |
|
|
|
|
|
|
||
|
||||
|
טוב, העובדה שקיימת אסטרטגיה מיטבית ברורה, וכך גם העובדה שניתן לחשב אותה כפי שהצעת. מניתוח המשחק ה-4-קלפי כבר עולה שהאסטרטגיה המיטבית אינה כלל התלוי רק במה שהרווחנו עד כה, כך שאתה לא צפוי להפתעות. השאלה המעניינת היא מה הנוסחא לתוחלת המירבית במשחק עם 2n קלפים. | |
|
|
|
|
|
||
|
||||
|
התוחלת במשחק בן ארבעת הקלפים היא 5/6. במשחק עם שישה קלפים, 19/20. | |
|
|
|
|
|
||
|
||||
|
אתה בטוח? לדעתי, התוחלת במשחק עם ארבעה קלפים (שני אדומים, שני שחורים) היא 2/3. הבה נראה: האם אתה מסכים שהמצב (אדום, שני שחורים) שווה 0? ושהמצב (שחור, שני אדומים) שווה 4/3? נוסחה כללית "מפורשת" למשחק עם N קלפים אין, לדעתי. נוסחה רקורסיבית יש ויש, והיא לא מאוד קשה לחישוב. |
|
|
|
|
|
|
||
|
||||
|
טוב, על זה כבר אמר מיודענו ירדן ניר תגובה 83059. אתה צודק, מה שאומר שגם החישוב שלי עבור שישה קלפים שגוי. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |