בתשובה לאלון עמית, 03/08/03 8:15
חידה 161330
אלון,

יצאו לי אותם המספרים שיצאו לך, גם לגבי תוחלת הרווח וגם בכלל העצירה. את נוסחת הנסיגה של תוחלת הרווח לא קשה לכתוב, אבל פתרון סגור (נוסחה) לכל n ו- k לא מצאתי.
חידה 161345
תודה על האישור! נוסחה סגורה סביר שאין פה.
חידה 161408
כמה זמן לקחה לך הריצה במחשב? לפי החישוב שלי (לא בדקתי מעשית) זה אמור לצאת סדר גודל של מילישניות לכל היותר.
חידה 161416
אכן, איו פה שום בעיית מהירות - מילישניות אם לא פחות. גם באופן תאורטי האלגוריתם הוא כמובן מאוד מהיר (פולינומיאלי, פרופורציוני ל-n*k עבור n קלפים אדומים ו-k שחורים). אני מימשתי את זה בכמה שורות Mathematica.
חידה 161561
הרצתי את זה על 200 קלפים מכל סוג (וכמובן כתוצר לוואי קיבלתי את כל התוצאות הנמוכות יותר), נראה שהתוצאה כפונקציה של מספר הקלפים מאוד מאוד קרובה (לפחות עבור התחום הזה) לפונקצית שורש ריבועי. ריצה על מספר קלפים גדול יותר גירדה את תחתית מחסנית הרקורסיה שלי (אני צריך לשכתב את העסק לעומק סופי) אבל זה מעניין כי שום דבר (בערך) לא מתנהג כמו שורש ריבועי חוץ, אולי, מהילוך שיכור.
חידה 161633
בוא נשאל שאלה אחרת: נגיד שתרוץ כל פעם עד הסוף ותשמור את הערך הכי גבוה שאי פעם התקבל במשחק ( מין ניחוש בדיעבד כזה). באופן טיפוסי הערך הכי גדול יהיה בסביבות שורש מספר הקלפים ( מהלך שיכור וכולי)‏1. מה שגילית הוא שהאיסטרטגיה האופטימלית ללא ידיעת העתיד מתנהגת באופן דומה.

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

1 הערכים הם למעשה מהלך אקראי תחת האילוץ שהערך הראשון והאחרון הוא אפס.
חידה 161811
למעשה "גיליתי" זאת רק עבור מספר ערכים קטנים. במשך היום חשבתי שיהיה נחמד גם לחסום את העסק מלמעלה ומלמטה ולהראות שההתנהגות היא תמיד שורש. אתה תיארת חסם מלעיל (צריך רק לראות בדיוק כמה הוא יוצא מספרית), עכשיו רק צריך חסם מלרע וסיימנו לתת second best לא רע בכלל לנוסחה סגורה.

מה לגבי האסטרטגיה "עצור כאשר אתה מגיע לרווח x" כאשר x ליניארי בשורש n? מה התוחלת כאן?
לא בדיוק... 161831
הילוך השיכור כאן הוא מאוד לא סטנדרטי - ההסתברויות הן לא קבועות בזמן ואף תלויות בהיסטוריה, באופן שנוטה ''לרסן'' את ההילוך ולקרבו למרכז - למשל, כפי שציינת, בסוף תמיד חוזרים לאפס.

חוץ מזה, כפי שכבר צויין, האסטרטגיה האופטימלית איננה ''חכה עד שהזכייה תהיה...'', ולכן אני לא בטוח שמודל ''ידיעת העתיד'' שופך עליה אור נוסף.
לא בדיוק... 161885
אתה צודק שזה לא בדיוק הילוך שיכור.
בוא ננסה עוד טיעון פשוט: נשאל עבור אילו ערכי רווח הדחיפה הדטרמניסטית לכיוון המרכז הוא באותו סדר גודל כמו ה"רעש" בעקבות המצאות של שחורים ולבנים? כל עוד סטית התקן של הרעש היא יותר גדולה מעוצמת הדחיפה, אפשר להניח שהרווח מבצע מהלך שיכור. ברגע שהרווח חורג מכך, הדחיפה הדטרמנסטית תחזיר אותו.

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

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

האם מישהו יכול לבדוק על הפיתרון המדויק איך נראה קו ה<רווח,מספר קלפים> של האסטרטגיה המדויקת למשחק עם הרבה ( נגיד כמה מאות) קלפים?

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

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