קסם: ההתכנסות מוכרת רשמית כמשחק הקשה ביותר בעולם.

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

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

כמה מסובך הוא הקסם: ההתכנסות? קשה יותר

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

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

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

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

אבל למרות ששתי הבעיות הללו ניתנות לחישוב, המשאבים הדרושים לפתרונן משתנים מאוד.

כאן מופיע המושג המורכבות החישובית. זהו דירוג המבוסס על המשאבים הדרושים לפתרון בעיות.

במקרה זה, ההחלטה אם שנייםמספרים פשוטים יחסית, ניתן למצוא במספר שלבים כי הם פרופורציונליים לתפקוד הפולינומי של מספרי קלט. אם ערך הקלט הוא x, החבר החשוב ביותר בתפקוד הפולינומי יהיה בצורת Cx ^ n, כאשר C ו- n הם קבועים. זהו מעמד P, כלומר זמן פולינום.

להיפך, בעיית השחמט צריכה להיפתרעל ידי כוח פראי, ומספר הצעדים הנדרשים עולה ביחס פרופורציה מעריכי של נתוני קלט. אם הקלט הוא x, החבר החשוב ביותר בפונקציה המעריכית הוא Cn ^ x, כאשר C ו- n הם קבועים. כאן אנו מתמודדים עם קטגוריה של EXP המורכבות יותר, או זמן מעריכי.

בנוסף, יש קטגוריות שונות אחרות עם מורכבות שונה, כמו גם משימות שאין להם אלגוריתמים. הם נקראים noncomputable.

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

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

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

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

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

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

שיחקת במשחק הזה? ספר לנו בצ'אט שלנו בטלגרם.