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