חידה

[snogal]

../images/Emo35.gif חידה

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

 

[Pavel101]

זה לא חידה זה משחק כזה

אני וחבר שלי חרשנו עליו בשיעורי תנ"ך.... זכרונות.....

 

[טלמון סילבר]

לא שמעתי על קיומו של

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

 

[snogal]

טוב אז אני אנסח בצורה אחרת.

1 הוכח שיש דרך לשחקן השני (שלא פתח) למנוע נצחון מהשחקן הראשון. 2 מה זה פרים ופרות? אם תסביר מה זה אני אנסה לכתוב תוכנית.

 

[טלמון סילבר]

1. אני אישית נכנע, ומחכה לפרסום

הפתרון. 2. משחקים שניים. כל אחד רושם לעצמו 4 ספָרות עשרוניוֹת שונות. כל אחד מנסה לנחש את 4 הספרות של היריב. סדר הספרות חשוב: 1234 ו-4321 נחשבים למספרים שונים. כל ניחוש מתבצע כך: אחד השחקנים מנסה לנחש את מספרו של השני, ואומר 4 ספָרות עשרוניוֹת, והשני עונה לו מה היא כמות הפרים, ומה היא כמות הפרות. פר היא ספרה קיימת בדיוק באותו מקום, ופרה היא ספרה קיימת אבל במקום אחר. למשל אם המספר הוא 0123, והניחוש היה 0712, אז התשובה היא: פר אחד (הספרה 0) ושתי פרות (הספרות 1 ו-2). מנצח זה שניחש בפחות נסיונות. אפשרית תוצאת תיקו: שניהם ניחשו באותו מספר שאלות. בגלל שיכול להיות מזל, משחקים בדר"כ הרבה פעמים, ואם רוצים סופרים את סה"כ השאלות. בזמנו כתבתי תכנית "שופט" הממציאה מספרים אקראיים, מפעילה מספר "שחקנים" - תכניות המנחשות את המספרים, ומציגה את תוצאות סך הכל. כל "שחקן" "דיבר" עם "השופט" בלבד: קיבל כפרמטר את מספר המהלך ואת התשובה לניחושו הקודם, והחזיר לשופט את ניחושו הבא. כאשר התשובה לניחוש הייתה "4 פרים", השופט לא היה פונה יותר אל אותו שחקן, אלא מציין לעצמו שהשחקן כבר מצא את המספר.

 

[snogal]

שני דברים:

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

 

[טלמון סילבר]

עד כמה שאני זוכר יצא לי בממוצע 5.6

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

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

 

[kalen הכבאי]

אפשר לדעתי

ליצור מעין מערך בגודל X, שאם הוא ממלא את כולו ולא מנצח, הוא מפסיד המערך יכול להיות נגיד דו מימדי 20X4 וכל תא כזה הוא רשומה של פר , פרה מסוג בוליאן, והמספר שהוכנס

 

[טלמון סילבר]

באיזו שפה אתה מוכן

לכתוב את התכנית?

 

[kalen הכבאי]

../images/Emo26.gif

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

 

[טלמון סילבר]

נחמד, אבל זה לא כך פשוט.

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

 

[kalen הכבאי]

לא נכון

אפשר לעשות נגיד שני פורמים בויזואל בייסיק אחד של השופט ואחד של המתחרה השופט מגריל מספר נגיד 1123 ואז הוא אומר למתחרה תנחש מספר , אם אחרי 20 נסיונות לא נחשת אכלת אותה .. ואז הוא מקליד מספר שנכנס לתא הראשון במערך נגיד הוא הקליד מספר 1329 אז הוא יקבל ככה : פר : 1 פרה : 1 מספר : 1329. וככה הלאה והלאה.. הבנת את הרעיון שלי?

 

[טלמון סילבר]

../images/Emo13.gif ואתה הבנת מה כתבתי?

להזכירך, במשך השנים הרבות שאני עובד כמתכנת (כפול מכל שנות חייך) הזדמן לי לא אחת, בשפות תכנות שונות, לכתוב הן תכנית השופט והן את תכניות השחקנים, והכל עבד. מעשית, לא רק בדיבורים. לכן, אם אתה חושב שהבנתָ את השאלה שלי, ואם לא קשה לך, אז בבקשה חזור על השאלה ופרט - מה "לא נכון"?

 

[kalen הכבאי]

../images/Emo26.gif

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

 

[thrall]

קוראים לזה בול פגיעה בימנו

 

[טלמון סילבר]

תודה! סתם תרגמתי מאנגלית ../images/Emo8.gif