هاكنبوش

لعبة هاكنبوش هي لعبة ثنائية اللاعبين ابتكرها عالم الرياضيات جون هورتون كونواي . ^{[ 1 ]} يمكن لعبها على أي شكل من أشكال القطع المستقيمة المتصلة ببعضها البعض من نقاط نهايتها وبخط "أرضي". تستخدم نسخ أخرى من اللعبة خطوطًا بألوان مختلفة.

تبدأ اللعبة برسم اللاعبين خطًا "أرضيًا" (عادةً، ولكن ليس بالضرورة، خطًا أفقيًا في أسفل الورقة أو منطقة اللعب) وعدة قطع مستقيمة متصلة بالأرض، إما مباشرةً عند نقطة النهاية، أو بشكل غير مباشر، عبر سلسلة من القطع الأخرى المتصلة بنقاط النهاية. يمكن أن تلتقي أي عدد من القطع عند نقطة واحدة، وبالتالي قد يكون هناك مسارات متعددة إلى الأرض.

في دوره، يقوم اللاعب بـ"قطع" (محو) أي قطعة مستقيمة يختارها. كل قطعة مستقيمة لم تعد متصلة بالأرض بأي مسار "تسقط" (أي تُمحى). وفقًا لقواعد اللعب المعتادة في نظرية الألعاب التوافقية، يخسر اللاعب الأول الذي لا يستطيع التحرك.

يمكن أن تتكون لوحات هاكنبوش من عدد محدود من القطع المستقيمة (في حالة "اللوحة المحدودة") أو عدد لا نهائي منها (في حالة "اللوحة اللانهائية")، طالما أن التكوين لا يخالف افتراض نظرية الألعاب بأن اللعبة يمكن إنهاؤها في فترة زمنية محدودة. أما على اللوحة اللانهائية، فيمكن أن تستمر اللعبة إلى ما لا نهاية، بافتراض وجود عدد لا نهائي من القطع المستقيمة الملامسة للأرض.

المتغيرات

في النسخة الشعبية الأصلية من لعبة هاكنبوش، يُسمح لأي لاعب بقطع أي حافة: ولأنها لعبة محايدة، فمن السهل نسبيًا إجراء تحليل كامل باستخدام نظرية سبراغ-غروندي . وبالتالي، فإن نسخ هاكنبوش ذات الأهمية في نظرية الألعاب التوافقية هي ألعاب أكثر تعقيدًا ذات توجهات متحيزة ، مما يعني أن الخيارات (التحركات) المتاحة لأحد اللاعبين لن تكون بالضرورة هي نفسها المتاحة للاعب الآخر إذا كان دوره في التحرك في نفس الوضع. ويتحقق ذلك بإحدى طريقتين:

• هاكنبوش الأصلي: جميع القطع المستقيمة لها نفس اللون ويمكن لأي من اللاعبين قطعها. هذا يعني أن العوائد متناظرة، ولكل لاعب نفس العمليات بناءً على موقعه على اللوحة (في هذه الحالة، هيكل الرسم). يُطلق على هذا النوع أيضًا اسم هاكنبوش الأخضر. ^{[ 2 ]}
• لعبة هاكنبوش الأزرق والأحمر : كل قطعة من الخط ملونة إما باللون الأحمر أو الأزرق. يُسمح لأحد اللاعبين (عادةً اللاعب الأول، أو اللاعب الأيسر) بقطع القطع الزرقاء فقط، بينما يُسمح للاعب الآخر (عادةً اللاعب الثاني، أو اللاعب الأيمن) بقطع القطع الحمراء فقط.
• لعبة هاكنبوش الأزرق-الأحمر-الأخضر : كل قطعة من الخط ملونة بالأحمر أو الأزرق أو الأخضر. القواعد هي نفسها كما في لعبة هاكنبوش الأزرق-الأحمر، مع إضافة شرط أن أي لاعب يستطيع قطع القطع الخضراء.

تُعدّ لعبة هاكنبوش الزرقاء-الحمراء حالةً خاصةً من لعبة هاكنبوش الزرقاء-الحمراء-الخضراء، ولكن يجدر ذكرها بشكلٍ منفصل، إذ غالبًا ما يكون تحليلها أبسط بكثير. والسبب في ذلك هو أن لعبة هاكنبوش الزرقاء-الحمراء تُصنّف ضمن ما يُسمى باللعبة الباردة ، ما يعني، بشكلٍ أساسي، أنه لا يُمكن أن يكون البدء باللعبة ميزةً أبدًا.

كثيراً ما استُخدمت لعبة هاكنبوش كمثال توضيحي لشرح تعريفات ومفاهيم نظرية الألعاب التوافقية ، بدءاً من استخدامها في كتابي " عن الأعداد والألعاب" و "طرق الفوز في ألعابك الرياضية" لبعض مؤسسي هذا المجال. ويمكن استخدام لعبة هاكنبوش الزرقاء-الحمراء تحديداً لبناء أعداد سريالية : إذ يمكن للوحات هاكنبوش الزرقاء-الحمراء المحدودة بناء أعداد نسبية ثنائية ، بينما تمثل قيم لوحات هاكنبوش الزرقاء-الحمراء غير المحدودة الأعداد الحقيقية ، وفي حالة الأعداد المتسامية، الأعداد الترتيبية ، والعديد من القيم العامة الأخرى التي لا تنتمي إلى أي من هذين النوعين. وتتيح لعبة هاكنبوش الزرقاء-الحمراء-الخضراء بناء ألعاب إضافية لا تمثل قيمها أعداداً حقيقية، مثل لعبة النجمة وجميع الأعداد الأخرى .

يمكن إجراء المزيد من التحليل للعبة باستخدام نظرية الرسم البياني من خلال اعتبار اللوحة كمجموعة من الرؤوس والحواف وفحص المسارات إلى كل رأس يقع على الأرض (والذي ينبغي اعتباره رأسًا مميزًا - لا ضرر من تحديد جميع نقاط الأرض معًا - بدلاً من اعتباره خطًا على الرسم البياني).

في النسخة المحايدة من لعبة هاكنبوش (التي لا يحدد فيها اللاعبون الألوان)، يمكن اعتبارها استخدامًا لأكوام نيم بتقسيم اللعبة إلى عدة حالات: عمودية، ومتقاربة، ومتباعدة. عند لعبها حصريًا باستخدام أكوام عمودية من القطع المستقيمة، والتي تُعرف أيضًا بسيقان الخيزران، تتحول اللعبة مباشرةً إلى لعبة نيم ويمكن تحليلها على هذا الأساس. تُضيف القطع المتباعدة، أو الأشجار، تعقيدًا إضافيًا للعبة وتتطلب استخدام مبدأ النقطتين الذي ينص على أنه عندما تلتقي الفروع عند رأس، يمكن استبدال الفروع بساق غير متفرعة طولها يساوي مجموع نقاط نيم . يُغير هذا المبدأ تمثيل اللعبة إلى النسخة الأساسية من سيقان الخيزران. أما المجموعة الأخيرة الممكنة من الرسوم البيانية فهي الرسوم المتقاربة، والمعروفة أيضًا بالرسوم البيانية ذات الجذور العشوائية. باستخدام مبدأ الدمج، يمكننا القول إنه يمكن دمج جميع الرؤوس في أي دورة معًا دون تغيير قيمة الرسم البياني. ^{[ 3 ]} لذلك، يمكن تفسير أي رسم بياني متقارب على أنه رسم بياني بسيط لساق الخيزران. وبدمج الأنواع الثلاثة من الرسوم البيانية، يمكننا إضافة تعقيد إلى اللعبة، دون تغيير مجموع نقاط لعبة نيم، مما يسمح للعبة باتباع استراتيجيات لعبة نيم.

ينص مبدأ النقطتين على أنه عند التقاء الفروع عند رأس، يمكن استبدالها بجذع غير متفرع طوله يساوي مجموعها (nim). لنفترض وجود رسم بياني ثابت ولكنه عشوائي، G ، ولنختر رأسًا عشوائيًا، x ، في G. ولتكن H1 و H2 شجرتين (أو رسمين بيانيين) عشوائيتين لهما نفس قيمة سبراغ-غروندي. لنفترض الرسمين البيانيين _{G1 =} Gx : H1 وG2 = Gx : H2، حيث يمثل Gx : H1 _الرسم البياني الناتج عن  ربط _الشجرة H1 _بالرأس x في الرسم البياني G. ينص _{مبدأ النقطتين} على أن الرسمين البيانيين G1 و G2 _لهما نفس قيمة سبراغ - _{غروندي . لنفترض} مجموع اللعبتين. الادعاء بأن G1 _و G2 لهما نفس قيمة سبراغ-غروندي يُكافئ الادعاء بأن مجموع اللعبتين له قيمة سبراغ-غروندي تساوي صفرًا. بعبارة أخرى، علينا أن نُثبت أن المجموع _G1 + G2 يُمثل وضعية P. يضمن اللاعب الفوز إذا كان ثاني لاعب يتحرك في G1 + G2 . إذا _تحرك اللاعب _{الأول بقطع} أحد حواف G في إحدى اللعبتين، ثم قام اللاعب الثاني بقطع نفس الحافة في G في اللعبة الأخرى. (قد _يؤدي هذا الزوج من التحركات إلى حذف _H1 و H2 من اللعبتين، ولكن بخلاف ذلك، لا تتأثر H1 _و H2 _{) .} إذا تحرك اللاعب الأول بقطع حافة في _H1 أو H2 ، فإن قيم سبراغ-غروندي لـ _H1 و H2 لم تعد متساوية _، وبالتالي توجد حركة في H1 _أو H2 _تُبقي قيم سبراغ-غروندي _{متساوية} . وبهذه الطريقة، سيكون لديك دائمًا رد على كل خطوة قد يقوم بها. وهذا يعني أنك ستتخذ الخطوة الأخيرة وبالتالي ستفوز. ^{[ 4 ]}  

• 
  مثال على كيفية تبسيط اللعبة باستخدام مبدأ النقطتين

• جون إتش. كونواي، في الأرقام والألعاب ، الطبعة الثانية، إيه كيه بيترز، 2000.

• Hackenstrings، و 0.999... مقابل 1
• هاكنبوش على ألعاب القلم والورق