תורת המשחקים!

[The Ancient Mariner]

תורת המשחקים!

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

 

[Halfbaked]

משחקים וחבורות

אני שמח שהדיון על מגדלי האנוי גרם לך הנאה ותאבון לעוד. זה אולי נשמע מוזר, אבל תורת המשחקים אינה עוסקת במשחקים כגון מגדלי האנוי או הקוביה ההונגרית. המרכיב המרכזי של המשחק, שבו מתעניינת תורת המשחקים, הוא היריבות בין שניים או יותר שחקנים המנסים להטות את תוצאת המשחק לכיוונים שונים. במצב כזה נולד המושג של "אסטרטגיה מנצחת", כלומר דרך פעולה של שחקן מסוים המבטיחה לו ניצחון בכל דרך בה השחקנים האחרים ישחקו. משפט מפורסם של צרמלו אומר שבמשחקים עם תכונות מסוימות חייבת להיות לאחד השחקנים אסטרטגיה מנצחת. ממשפט זה נובע גם שבמשחק השחמט חייבת להיות ללבן או לשחור (או אולי לשניהם) אסטרטגיה המבטיחה לפחות תיקו, אולם משחק השחמט מורכב עד כדי כך, שאפילו בימינו מלאי הטכנולוגיה עדיין לא ידוע לאיזה צד אכן קיימת אסטרטגיה כזאת, וכמובן שלא ידועה גם האסטרטגיה עצמה. כאמור, תורת המשחקים אינה עוסקת במשחקי יחיד, כגון מגדלי האנוי או הקובייה ההונגרית, מכיוון שמשחקים אלו חסרים את גורם היריבות. אך לא לדאוג - משחקים אלה מטופלים באהבה בתחומים אחרים של המתמטיקה. הקובייה ההונגרית ניתנת לניתוח מעמיק באמצעות הכלים שפותחו בתורת החבורות. למביני עניין, קבוצת כל התמרונים האפשריים של הקובייה היא למעשה חבורה הפועלת על קבוצת המצבים האפשריים של הקובייה. לחבורה זו ישנן תת-חבורות רבות ומעניינות, המלמדות לא מעט על הקובייה. תורת החבורות עוזרת גם במציאת אלגוריתם לפתרון הקובייה. הספר "Inside Rubik´s Cube and Beyond" של Christoph Bandelow הוא אחד הספרים הטובים ביותר על הקובייה שהיה לי את העונג להכירם. הוא מציג את עיקרי תורת החבורות בשפה פשוטה, ומשתמש בהם בניתוח הקובייה. לאחר מכן הוא מביא רשימה של תמרונים מעניינים וצורות ויזואליות יפות שניתן להגיע אליהן בקוביה. ישנם גם אתרים רבים באינטרנט הדנים בקוביה. הייתי מציע להתחיל מהאתר של רוביק המופיע בדף הקישורים, ולאחר מכן אפשר להמשיך בחיפוש המלים "rubik´s cube" בכל מנוע חיפוש. אשמח אם תדווח לנו על ממצאיך! יובל.

 

[tali_le]

תגובה...

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

 

[The Ancient Mariner]

מי הפושע ששלח לך קישור?

שמח לראות אותך בפורום...

 

[The Ancient Mariner]

לגבי הקובייה הונגרית...

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

])

 

[The Ancient Mariner]

ועוד תוספת...

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