הקס (משחק)
 | |
| משחק הקס המשוחק על פני לוח גו | |
| יוצר | פייט היין וג'ון נאש |
|---|---|
| מס' שחקנים | 2 |
| גילאים | מעל 4 |
| זמן המשחק | כ-15 דקות (על לוח 11X11) |
| מיומנות | אסטרטגיה וטקטיקה |
הקס הוא שמו של משחק לוח המתנהל על לוח מרוצף משושים. המשחק הומצא באמצע המאה ה-20, ומשום פשטותו רכש פופולריות רבה במהירות. למרות החוקים הפשוטים, המשחק מורכב מאד ומכיל אפשרויות רבות.
חוקים
המשחק מתנהל על לוח המרוצף משושים, כמצויר באיור, שגודלם לרוב 11x11 או 13x13. בכל תור, אחד השחקנים צובע משבצת ריקה באדום או בכחול, לסירוגין (מקובל שצבעו של השחקן הראשון - אדום). מטרתו של כל שחקן היא לקשר את צידי הלוח המסומנים בצבע שלו, בשרשרת רצופה של משושים בצבע זה. השחקן הראשון המצליח במשימה, ומונע בכך מן השחקן השני להשלים שרשרת משלו, מנצח.
היסטוריה
את המשחק המציאו, באופן בלתי תלוי, המשורר והמתמטיקאי הדני פייט היין ב-1942, והמתמטיקאי האמריקאי ג'ון נאש (שלימים קיבל פרס נובל על תרומותיו לתורת המשחקים) ב- 1948. היין קרא למשחק "פוליגון" ופרסם את המשחק בעיתון הדני "פוליטיקן" עבורו כתב סדרת חידות בנושא. נאש הצליח גם להוכיח שלשחקן הראשון יש אסטרטגיית ניצחון במשחק (למרות שאסטרטגיה כזאת לא התגלתה עד היום).
בשנת 1952 החלה חברת המשחקים האחים פארקר לשווק את המשחק תחת השם "הקס", הגזור מן המלה האנגלית Hexagon - משושה (לא ידוע איך נודע לחברה על המשחק). היום קיימות למשחק גם גרסאות מחשב ורשת.
המשחק התפרסם בין היתר לאחר שמרטין גרדנר כתב עליו בטורו בסיינטיפיק אמריקן[1].
לוחות שונים לאותו משחק
מבחינה מהותית תלוי המשחק רק בקשרים שבין משבצות סמוכות, ולא בגודלן או בצורתן. הגרסה המוזכרת כאן, שבה הלוח משושה, מיוחסת להיין. אצל נאש היה הלוח משובץ משבצות ריבועיות, כאשר זוג משבצות מקושרות אם הן חולקות צלע משותפת, או אם אחת מהן נמצאת משמאל ומעל השנייה. באותה מידה ניתן לשחק את המשחק על גרף, שבו נקודות מציינות את המשבצות, והשחקנים מניחים דיסקיות מעל הנקודות, כמו בתמונה השלישית.
-
המשחק הקס, בלוח 5x5, מצב מנצח לשחקן האדום -
הקס בגרסת המשבצות של ג'ון נאש; המצב באיור זהה למצב באיור הראשון
משחק המיתוג של שנון
משחק המיתוג של שנון היא הכללה של הקס. המשחק מוגדר על גרף כלשהו עם שני צמתים ייחודיים s ו-t. כמו בהקס, כל שחקן בתורו בוחר צומת. מטרת השחקן הראשון היא ליצור מסלול של צמתים מ-s ל-t שנבחרו על ידו ומטרת השחקן השני למנוע זאת. גרסה אחרת של המשחק היא שהשחקנים בוחרים קשתות ולא צמתים. המשחק מיוחס לקלוד שנון.
כל משחק הקס מסתיים בניצחון
במשחק הקס לא תיתכן תוצאת תיקו. כדי להראות זאת, מספיק להוכיח שאם כל המשבצות מסומנות, אז זהו מצב מנצח לשחקן הראשון או לשחקן השני. באופן אינטואיטיבי זה נראה מובן מאליו שכן הדרך היחידה בשביל השחקן הכחול למנוע גשר של משושים אדומים משני הקצוות האדומים היא ליצור גשר של משושים כחולים משני הצדדים המסומנים בכחול. הוכחת הטענה יכולה להתבסס על טיול דמיוני המתבצע על הצלעות של המשושים בלוח. מתחילים בפינה העליונה והכלל של הטיול הוא שבכל מהלך ממשיכים לצלע שנמצאת בין אזור אדום לאזור כחול (אפשר להראות כי תמיד יש כזאת). הטענה היא שהטיול יכול להסתיים רק באחת מהפינות האחרות של הלוח, ואם הוא מסתיים בפינה השמאלית אזי יש ניצחון לכחול, ואם הוא מסתיים בפינה הימנית אזי יש ניצחון לאדום (אם הוא מסתיים בפינה התחתונה אז שני הצדדים מנצחים, וזה בלתי אפשרי בשל גרסה בדידה למשפט ז'ורדן).
דייויד גייל (David Gale) הראה כי הטענה שאחד הצדדים מנצח שקולה למשפט נקודת השבת של בראואר[2]. כדי להוכיח שאם אחד הצדדים מנצח אז לכל פונקציה רציפה f מריבוע היחידה לעצמו יש נקודת שבת, מספיק להוכיח שלכל n יש נקודה שעבורה , משום שלפי הקומפקטיות של ריבוע היחידה תהיה לסדרת הנקודות תת-סדרה מתכנסת, וגבולה הוא נקודת שבת. שוב בגלל הקומפקטיות, הפונקציה רציפה במידה שווה, ולכן קיים m כך שאם אז . מחלקים את ריבוע היחידה למשבצות שצלען . נצבע באדום את המשבצות שהפונקציה מזיזה את נקודת המרכז שלהן בלפחות ימינה או שמאלה. המשבצות האדומות שעל הצלע הימנית, אם יש כאלה, הוזזו שמאלה, ואילו אלו שעל הצלע השמאלית הוזזו ימינה. השחקן האדום אינו יכול לחבר במסלול רציף את הצדדים ימין ושמאל, משום שלשם כך צריכות להיות משבצות אדומות סמוכות, שאחת מהן זזה ימינה והשנה זזה שמאלה, באופן הסותר את אי-השוויון של הרציפות במידה שווה. מאותה סיבה, אם נצבע בכחול את המשבצות שהפונקציה מזיזה את נקודת המרכז שלהן בלפחות למעלה או למטה, השחקן הכחול לא יוכל לחבר את הצלעות המנוגדות מעלה-מטה. אם כל המשבצות היו צבועות, אחד השחקנים היה מנצח - ומכאן שיש משבצת שאינה צבועה כלל, ונקודת המרכז שלה היא הנקודה המבוקשת.
גניבה של אסטרטגיה
אחת הפנינים של תורת המשחקים הקומבינטורית היא ההוכחה שבמשחק הקס לשחקן הראשון יש אסטרטגיה המבטיחה לו ניצחון. כלומר, במידה וישחק משחק מושלם, הוא בהכרח ינצח. ההוכחה, שמקורה בנאש, משתמשת בשיטה הנקראת גניבה של אסטרטגיה, שניתן להשתמש בה במגוון רחב של משחקים נוספים, כגון בווריאציות שונות של איקס עיגול.
על פי משפט צרמלו, בכל משחק סופי שאינו יכול להסתיים בתיקו או שיש לשחקן הראשון אסטרטגיה המבטיחה לו ניצחון (כלומר יש דרך שבה הוא יכול לנצח לא משנה מה עושה השחקן השני), או שיש לשחקן השני אסטרטגיה כזאת. בהקס לא תיתכן תוצאה של תיקו, כפי שראינו, ולכן נותר להוכיח שלשחקן השני אין אסטרטגיה המבטיחה לו ניצחון. נניח בשלילה שיש לו כזו, אז השחקן הראשון יכול לסמן בתור הראשון משושה כלשהו, ואחר כך להשתמש באסטרטגיה של השחקן השני, בשביל להבטיח לעצמו ניצחון. אם, תוך כדי המשחק, האסטרטגיה אומרת לו לסמן את המשושה שהוא סימן כבר במהלך הראשון (או במהלכים אחרים), אזי הוא מסמן משושה פנוי כלשהו. בכל מצב בו השחקן הראשון הוא המנצח, אם חלק מהמשושים עוברים מהשחקן השני לראשון נשאר מצב מנצח לראשון. מכאן מקבלים שאם יש לשחקן השני אפשרות לכפות ניצחון, אז גם לראשון יש אפשרות כזו.
סיבוכיות
בעוד שידוע כי במצב ההתחלתי הריק לשחקן הראשון יש אסטרטגיה מנצחת, הרי הבעיה הכללית, בהינתן לוח בגודל כלשהו, כשחלק מהמשושים כבר מסומנים כשייכים לשחקנים, להחליט לאיזה שחקן יש אסטרטגיה מנצחת, היא בעיה שלמה ל-PSPACE. הדבר הוכח בתחילה למשחק המיתוג של שנון על ידי שמעון אבן ורוברט טרג'אן ואחר כך בפרט להקס על ידי שטפן רייש[3].
