כיצד אפשר לנצח משחק רנדומלי?

[aceblackhole]

כיצד אפשר לנצח משחק רנדומלי?

ניתנה לי שאלה בפסקל והיא כזאת: משחקים משחק אבן נייר מספרייפ 1-אבן 2-נייר 3- מספריים אבן מנצחת את מספריים. נייר מנצח את אבן. ומספריים מנצחים את נייר. יש לכתוב משחק בין שני מחשבים: "מחשב חכם" מול מחשב אקראי – המחשב החכם לומד את התבניות התנהגות של מחשב אקראי ובכל צעד פועל בדרך החכמה ביותר ;מחשב אקראי בוחר תמיד באופן אקראי. יש לכתוב מערכת סימולציה שמבצעת לא פחות מ-10000 משחקים (כל משחק עד 5 ניצחונות) ומסכמת בעזרת אחוזי הצלחה איזה מחשב מצליח יותר. דוגמא לפלט: מחשב חכם – 60% הצלחה, מחשב אקראי – 40% הצלחה המחשב האקראי הוא למעשה הפונקציה random (3)+1; כיצד יתאפשר לי לחזות מה המחשב האקראי יגריל בכל פעם ובהתאם לכך אוכל לנצחו?

 

[ש ב ו ז]

חחח לא יתאפשר לך...

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

 

[כרובית הפלא]

אולי אפשר לחשב סטטיסטיקה

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

 

[gil levi]

אולי בכל שלב לבחור את מה שמנצח

את מה שהופיע הכי הרבה עד השלב הנוכחי, למרות שהשאלה נראית לי קצת מוזרה.

 

[gil levi]

אולי בכל שלב לבחור את מה שמנצח

את מה שהופיע הכי הרבה עד השלב הנוכחי, למרות שהשאלה נראית לי קצת מוזרה.

 

[vinney]

זה לא שאלה מוזרה כל כך

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

 

[gil levi]

ברור לי שמחשב לא יכול לבחור

מספר באופן רנדומלי, אבל לא ידעתי שיש מימושים של הפונ' ראנדום שבהם באמת ניתן לחזות את המספר הבא. תודה רבה על הקישור, אני אעיף בו מבט מאוחר יותר.

 

[amni2]

סחה על החתימה

סחה על החתימה, גיל.... נשמע ממש כמו ציטוט משיעור אלגברה מודרנית.

 

[gil levi]

אלגברה מודרנית

זה לא מבנים אלגבריים? החתימה שלי יותר נשמעת כמו ציטוט מתורת הקבוצות, לא?

 

[amni2]

טכניון

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

 

[Desslok of Gamilon]

אולי בדיוק להיפך אם המחשב בחר על עכשיו 50% נייר, 50% מספריים ו 0% אבן, אני הייתי מסיק מזה שההסתברות לקבל אבן היא נמוכה מאוד, ורוב הסיכויים לקבל גם בסיבוב הבא נייר או מספריים... אם יש לך מטבע שנופלת כל פעם על צד אחד, וזרקת אותה 100 פעם והיא נפלה על אותו צד - את מסיקה שבפעם הבאה היא תיפול על הצד השני כי "הגיע הזמן"? אני מסיק שהיא תמשיך ליפול על אותו צד.

 

[כרובית הפלא]

אבל זה רק במקרה שיש סיכוי

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

 

[vinney]

איפה בדיוק נתקלת במחשב

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

 

[כרובית הפלא]

זה לא חשוב כרגע

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

 

[MegaMango]

חח באמת נחמד

אף פעם לא חשבתי שיש טעם לחזות משהו אקראי. אם אני לא טועה יש גם הבדל בראנדום של מעבדי AMD ואינטל, נכון? אני זוכר שראיתי בעבר ראנדום שמתקדם כל שניה ב-2 (מודולו מספר גדול כלשהו) וחשבתי שמימשתי שם משהו לא טוב P:

 

[inbal76]

לפי חוקי ההסתברות זה לא תקף

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

 

[כרובית הפלא]

זה נכון

להסתברות אין היסטוריה... ואם הולכים על הסתברות תקינה, אז אין לי יותר רעיונות

 

[DorDassa]

אולי פשוט...

אל תכתוב randomize(); בהתחלה.. תראה מה יוצא בפעם הראשונה ותדע מה יצא כל הזמן..

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