בתשובה לגלעד ברזילי, 02/08/03 18:54
 |
|
 |
||
|
||||
 |
טוב, אז הנה המצב לאשורו, אם אינני טועה. ובהחלט יכול להיות שאני טועה. האסטרטגיה האופטימלית איננה יפה במיוחד. יש להמשיך כל עוד עודף מספר הקלפים השחורים על פני האדומים שנותרו בחבילה איננו "גבוה מדי", וכדי לפרש מהו "גבוה מדי" יש להיעזר בטבלה. למשל, אם נותרו 10 קלפים אדומים ו-13 שחורים כדאי להמשיך, אבל עם 10 אדומים ו-14 שחורים יש לעצור. את הטבלה המלאה ארשום בסוף התגובה. ערך המשחק, כלומר תוחלת הרווח אם משחקים היטב, הוא קצת יותר משני שקלים וששים ושתיים אגורות. עוד נתון טריוויה משעשע: אם שיחק מזלכם ומשכתם מיד בהתחלה 5 קלפים אדומים, יש להמשיך! תוחלת הסכום שתוכלו עוד להרוויח (נוסף על חמשת השקלים בכיס) היא קצת מעל 5 אגורות. למי שרוצה להשתכנע שאכן יש מצבים שבהם יש יותר קלפים שחורים מאדומים בחבילה ולמרות זאת כדאי לשחק - המצב הפשוט ביותר מהסוג הזה הוא: שני אדומים, שלושה שחורים. שווה להשקיע כל סכום נמוך מעשרים אגורות כדי להשתתף במשחק כזה. אשמח אם מישהו יבדוק את טענותי. ושאלה לגלעד - אתה יודע מניין הבעייה הזו? להלן האסטרטגיה: כל עוד נותרו 21 קלפים אדומים או יותר, יש להמשיך. אם נותרו 20 אדומים ו-26 שחורים, יש לעצור. אם נותרו 19 אדומים ו-25 שחורים או יותר, יש לעצור. אם נותרו 18 אדומים ו-23 שחורים או יותר, יש לעצור. וכן הלאה: 17 22 16 21 15 20 14 19 13 18 12 16 11 15 10 14 9 13 8 12 7 10 6 9 5 8 4 7 3 5 2 4 1 2 ערך המשחק המדוייק: 41984711742427/15997372030584 לבריאות! |
 |
 |
 |
|
|
|
||
|
||||
|
אלון, יצאו לי אותם המספרים שיצאו לך, גם לגבי תוחלת הרווח וגם בכלל העצירה. את נוסחת הנסיגה של תוחלת הרווח לא קשה לכתוב, אבל פתרון סגור (נוסחה) לכל n ו- k לא מצאתי. |
|
|
|
|
|
|
||
|
||||
|
תודה על האישור! נוסחה סגורה סביר שאין פה. | |
|
|
|
|
|
||
|
||||
|
כמה זמן לקחה לך הריצה במחשב? לפי החישוב שלי (לא בדקתי מעשית) זה אמור לצאת סדר גודל של מילישניות לכל היותר. | |
|
|
|
|
|
||
|
||||
|
אכן, איו פה שום בעיית מהירות - מילישניות אם לא פחות. גם באופן תאורטי האלגוריתם הוא כמובן מאוד מהיר (פולינומיאלי, פרופורציוני ל-n*k עבור n קלפים אדומים ו-k שחורים). אני מימשתי את זה בכמה שורות Mathematica. | |
|
|
|
|
|
||
|
||||
|
הרצתי את זה על 200 קלפים מכל סוג (וכמובן כתוצר לוואי קיבלתי את כל התוצאות הנמוכות יותר), נראה שהתוצאה כפונקציה של מספר הקלפים מאוד מאוד קרובה (לפחות עבור התחום הזה) לפונקצית שורש ריבועי. ריצה על מספר קלפים גדול יותר גירדה את תחתית מחסנית הרקורסיה שלי (אני צריך לשכתב את העסק לעומק סופי) אבל זה מעניין כי שום דבר (בערך) לא מתנהג כמו שורש ריבועי חוץ, אולי, מהילוך שיכור. | |
|
|
|
|
|
||
|
||||
|
בוא נשאל שאלה אחרת: נגיד שתרוץ כל פעם עד הסוף ותשמור את הערך הכי גבוה שאי פעם התקבל במשחק ( מין ניחוש בדיעבד כזה). באופן טיפוסי הערך הכי גדול יהיה בסביבות שורש מספר הקלפים ( מהלך שיכור וכולי)1. מה שגילית הוא שהאיסטרטגיה האופטימלית ללא ידיעת העתיד מתנהגת באופן דומה. איך מנתהגת נקודת העצירה? כלומר, באופן טיפוסי, אחרי כמה קלפים מפסיקים לשחק? 1 הערכים הם למעשה מהלך אקראי תחת האילוץ שהערך הראשון והאחרון הוא אפס. |
|
|
|
|
|
|
||
|
||||
|
למעשה "גיליתי" זאת רק עבור מספר ערכים קטנים. במשך היום חשבתי שיהיה נחמד גם לחסום את העסק מלמעלה ומלמטה ולהראות שההתנהגות היא תמיד שורש. אתה תיארת חסם מלעיל (צריך רק לראות בדיוק כמה הוא יוצא מספרית), עכשיו רק צריך חסם מלרע וסיימנו לתת second best לא רע בכלל לנוסחה סגורה. מה לגבי האסטרטגיה "עצור כאשר אתה מגיע לרווח x" כאשר x ליניארי בשורש n? מה התוחלת כאן? |
|
|
|
|
|
|
||
|
||||
|
הילוך השיכור כאן הוא מאוד לא סטנדרטי - ההסתברויות הן לא קבועות בזמן ואף תלויות בהיסטוריה, באופן שנוטה ''לרסן'' את ההילוך ולקרבו למרכז - למשל, כפי שציינת, בסוף תמיד חוזרים לאפס. חוץ מזה, כפי שכבר צויין, האסטרטגיה האופטימלית איננה ''חכה עד שהזכייה תהיה...'', ולכן אני לא בטוח שמודל ''ידיעת העתיד'' שופך עליה אור נוסף. |
|
|
|
|
|
|
||
|
||||
|
אתה צודק שזה לא בדיוק הילוך שיכור. בוא ננסה עוד טיעון פשוט: נשאל עבור אילו ערכי רווח הדחיפה הדטרמניסטית לכיוון המרכז הוא באותו סדר גודל כמו ה"רעש" בעקבות המצאות של שחורים ולבנים? כל עוד סטית התקן של הרעש היא יותר גדולה מעוצמת הדחיפה, אפשר להניח שהרווח מבצע מהלך שיכור. ברגע שהרווח חורג מכך, הדחיפה הדטרמנסטית תחזיר אותו. חישוב גס שביצעתי מראה שהדחיפה שווה לסטית התקן כאשר הרווח שווה( בעצם פרופורציוני) ל<מחצית>המרחק מסוף המשחק. כל עוד הרווח קטן "בהרבה" מכך, אפשר להתעלם מהדחיפה ולהתיחס לבעיה כאל מהלך שיכור עם סטית תקן שתלויה בזמן. אבל, התלות היא יחסית חלשה, ולכן אומדן של סתם מהלך שיכור הוא לא רע בתחום הזה. באשר לאיסטרטגיה, מבלי לפגוע באסטרגיה המדויקת (ובשיטה היפה שלך!), הייתי נותן אסטרטגיה מקורבת כזאת: אם הרווח שלך פרופורציוני ( עם קבוע עלום) למרחק עד הקצה - עצור, כי אתה מתקרב לאיזור הדטרמניסטי. האם מישהו יכול לבדוק על הפיתרון המדויק איך נראה קו ה<רווח,מספר קלפים> של האסטרטגיה המדויקת למשחק עם הרבה ( נגיד כמה מאות) קלפים? |
|
|
|
|
|
|
||
|
||||
|
(צר לי על העיכוב, בעיות גישה וזמינות) טוב, זו לא הייתה הגישה שלי - אני פתרתי את המשחק בצורה אמפירית, והגעתי לאסטרטגיה שאומרת "משוך, וכשיש לך 4 שקלים, הפסק". היא לא רעה, אבל המפורטת שלך עדיפה. מאידך גיסא, מאחר וטרחתי על שלי, אני אפרט מה עשיתי: אני הלכתי בגישה של כח טהור: הרצתי את המשחק, ובניתי וקטור של הקופה שלך כל שלב - אז יש לי וקטור של 53 אברים (מתחיל באפס), והמקסימום שלו הייתה האסטרטגיה הנכונה שלך בדיעבד - אם היית בוחר לעצור במקסימום, היית מנצח. עכשיו הרצתי את זה 10000 פעם, וחישבתי ממוצע - יוצא משהו קרוב מאד ל4 (מלמעלה). כ55% מהמשחקים מסתיימים ב4 ומעלה, כך שתוחלת הרווח שלי היא בערך 2.2 - פחות מ 2.6. אגב, גם לעצור ב3 זה לא רע - כ70% מהמשחקים מסתיימים ב3 ומעלה - תוחלת של בערך 2.1. ואת החידה סיפר לי חבר שלי - לא יודע מה המקור. |
|
|
|
|
|
|
||
|
||||
|
בקשר למקור החידה- זה לא פשוט גרסא מנוונת לבלק גק? | |
|
|
|
|
|
||
|
||||
|
לא חשבתי לייגע עם עוד נתונים, אבל נראה שיש כמה מתעניינים :-) ערך המשחק עבור מספר כללי של שחורים ואדומים הוא מספר רציונלי, כמובן. לא קשה לשים לב, ועוד יותר קל להוכיח, שאם נכפול ערך זה במקדם בינומי מתאים (מס' הקלפים הכולל מעל מס' האדומים), נקבל תמיד מספר *שלם*. נחמד. המספרים השלמים האלה מקיימים יחס רקורסיה טיפה יותר ידידותי מהערכים הרציונליים המקוריים. למרות זאת עדיין לא הצלחתי לבצע ניתוח אסימפטוטי מדוייק שלהם. לעומת זאת, שלחתי את הערכים האלכסוניים (אלה עבור מספר שווה של שחורים ואדומים, כמו בשאלה המקורית) בתור שאילתא ל-"אנציקלופדיה של סדרות השלמים", וקיבלתי בתור תשובה את יחד עם רפרנס למאמר שעדיין לא השגתי אבל לפי אבסטרקטו הוא דן כנראה בדיוק במשחק המדובר, באופן לא מפתיע. אם יש למישהו גישה לספריה אוניברסיטאית (מה שלי אין לצערי כרגע) אולי נוכל לקבל עוד פרטים. |
|
|
|
|
|
|
||
|
||||
|
קפיצה קטנה לספרייה של הפקולטה למדעי המחשב, והמאמר בידי. הוא אכן עוסק בבעייה הנ"ל (שבמקור נחקרה ע"י Shepp ב-1969). במהלך המאמר מוצגת המשוואה הרקורסיבית שהוזכרה, ומוכחים אי-שיוויונים שונים לגביה. למשל: V(m, p+1) <= V(m,p)+1/(n+1) כאשר V מייצג את תוחלת הרווח עם m כדורים שחורים ו-p אדומים.V(m, p) <= V(m+1,p)+1/(n+1) V(m+1, p+1) > V(m,p) בנוסף, Shepp בעצמו חישב את באופן אסימפטוטי את האסטרטגיה ל"מתי לעצור". (p+a*sqrt(2p) a=0.83992 כש-p שואף לאינסוף אם אתם חייבים לדעת). המאמר מציין שהחישוב הרקורסיבי ייצור שגיאה הולכת וגדלה, ולכן"מעביר את הבעייה לשלמים" ע"י הכפלה ב-(m+p)!, כפי שציין אלון. אחרי קצת עבודה, ועם שימוש בזהויות משולש פסקל, מגיעים לתוצאה הבאה: V(m, p) = (p-m) + m/(p+1) + O(p^-3) עבור m קבוע.תבדקו לראות אם זה יוצא... |
|
|
|
|
|
|
||
|
||||
|
המאמר מציין שעבור ערכים של p (מס' הקלפים ה"טובים") בין 0 ל-100, שווה לקחת עוד קלף אמ"ם מספר הקלפים ה"רעים" קטן מ- p+0.83992sqrt(2p)-0.1427 הם מסבירים שהחישובים שלהם הם עד p=100 מטעמי נוחות בלבד, ולא בגלל קשיים חישוביים ושזמן הריצה של המחשב עלה להם רק 10 דולר.
|
|
|
|
|
|
|
||
|
||||
|
קודם כל - תודה! אני לא בטוח שאני מבין את הנוסחה האחרונה שציטטת. עבור m=p זה יוצא בערך 1, בעוד שערך המשחק בוודאי שואף לאינסוף (כמו שורש n חלקי שתיים, לפי הניחוש שלי). חסר גורם? זה מנורמל אחרת? בכל אופן, תודה שוב על המאמץ. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |