בתשובה לאלון עמית, 03/08/03 8:15
 |
|
 |
||
|
||||
 |
אלון, יצאו לי אותם המספרים שיצאו לך, גם לגבי תוחלת הרווח וגם בכלל העצירה. את נוסחת הנסיגה של תוחלת הרווח לא קשה לכתוב, אבל פתרון סגור (נוסחה) לכל n ו- k לא מצאתי. |
 |
 |
 |
|
|
|
||
|
||||
|
תודה על האישור! נוסחה סגורה סביר שאין פה. | |
|
|
|
|
|
||
|
||||
|
כמה זמן לקחה לך הריצה במחשב? לפי החישוב שלי (לא בדקתי מעשית) זה אמור לצאת סדר גודל של מילישניות לכל היותר. | |
|
|
|
|
|
||
|
||||
|
אכן, איו פה שום בעיית מהירות - מילישניות אם לא פחות. גם באופן תאורטי האלגוריתם הוא כמובן מאוד מהיר (פולינומיאלי, פרופורציוני ל-n*k עבור n קלפים אדומים ו-k שחורים). אני מימשתי את זה בכמה שורות Mathematica. | |
|
|
|
|
|
||
|
||||
|
הרצתי את זה על 200 קלפים מכל סוג (וכמובן כתוצר לוואי קיבלתי את כל התוצאות הנמוכות יותר), נראה שהתוצאה כפונקציה של מספר הקלפים מאוד מאוד קרובה (לפחות עבור התחום הזה) לפונקצית שורש ריבועי. ריצה על מספר קלפים גדול יותר גירדה את תחתית מחסנית הרקורסיה שלי (אני צריך לשכתב את העסק לעומק סופי) אבל זה מעניין כי שום דבר (בערך) לא מתנהג כמו שורש ריבועי חוץ, אולי, מהילוך שיכור. | |
|
|
|
|
|
||
|
||||
|
בוא נשאל שאלה אחרת: נגיד שתרוץ כל פעם עד הסוף ותשמור את הערך הכי גבוה שאי פעם התקבל במשחק ( מין ניחוש בדיעבד כזה). באופן טיפוסי הערך הכי גדול יהיה בסביבות שורש מספר הקלפים ( מהלך שיכור וכולי)1. מה שגילית הוא שהאיסטרטגיה האופטימלית ללא ידיעת העתיד מתנהגת באופן דומה. איך מנתהגת נקודת העצירה? כלומר, באופן טיפוסי, אחרי כמה קלפים מפסיקים לשחק? 1 הערכים הם למעשה מהלך אקראי תחת האילוץ שהערך הראשון והאחרון הוא אפס. |
|
|
|
|
|
|
||
|
||||
|
למעשה "גיליתי" זאת רק עבור מספר ערכים קטנים. במשך היום חשבתי שיהיה נחמד גם לחסום את העסק מלמעלה ומלמטה ולהראות שההתנהגות היא תמיד שורש. אתה תיארת חסם מלעיל (צריך רק לראות בדיוק כמה הוא יוצא מספרית), עכשיו רק צריך חסם מלרע וסיימנו לתת second best לא רע בכלל לנוסחה סגורה. מה לגבי האסטרטגיה "עצור כאשר אתה מגיע לרווח x" כאשר x ליניארי בשורש n? מה התוחלת כאן? |
|
|
|
|
|
|
||
|
||||
|
הילוך השיכור כאן הוא מאוד לא סטנדרטי - ההסתברויות הן לא קבועות בזמן ואף תלויות בהיסטוריה, באופן שנוטה ''לרסן'' את ההילוך ולקרבו למרכז - למשל, כפי שציינת, בסוף תמיד חוזרים לאפס. חוץ מזה, כפי שכבר צויין, האסטרטגיה האופטימלית איננה ''חכה עד שהזכייה תהיה...'', ולכן אני לא בטוח שמודל ''ידיעת העתיד'' שופך עליה אור נוסף. |
|
|
|
|
|
|
||
|
||||
|
אתה צודק שזה לא בדיוק הילוך שיכור. בוא ננסה עוד טיעון פשוט: נשאל עבור אילו ערכי רווח הדחיפה הדטרמניסטית לכיוון המרכז הוא באותו סדר גודל כמו ה"רעש" בעקבות המצאות של שחורים ולבנים? כל עוד סטית התקן של הרעש היא יותר גדולה מעוצמת הדחיפה, אפשר להניח שהרווח מבצע מהלך שיכור. ברגע שהרווח חורג מכך, הדחיפה הדטרמנסטית תחזיר אותו. חישוב גס שביצעתי מראה שהדחיפה שווה לסטית התקן כאשר הרווח שווה( בעצם פרופורציוני) ל<מחצית>המרחק מסוף המשחק. כל עוד הרווח קטן "בהרבה" מכך, אפשר להתעלם מהדחיפה ולהתיחס לבעיה כאל מהלך שיכור עם סטית תקן שתלויה בזמן. אבל, התלות היא יחסית חלשה, ולכן אומדן של סתם מהלך שיכור הוא לא רע בתחום הזה. באשר לאיסטרטגיה, מבלי לפגוע באסטרגיה המדויקת (ובשיטה היפה שלך!), הייתי נותן אסטרטגיה מקורבת כזאת: אם הרווח שלך פרופורציוני ( עם קבוע עלום) למרחק עד הקצה - עצור, כי אתה מתקרב לאיזור הדטרמניסטי. האם מישהו יכול לבדוק על הפיתרון המדויק איך נראה קו ה<רווח,מספר קלפים> של האסטרטגיה המדויקת למשחק עם הרבה ( נגיד כמה מאות) קלפים? |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |