نظرية اللعبة الاندماجية

نظرية الألعاب الاندماجية بالإنجليزية (Combinatorial game theory) واختصارا (CGT)هي فرع من فروع الرياضيات وعلوم الكمبيوتر النظرية التي تدرس عادةً الألعاب المتسلسلة بمعلومات مثالية. اقتصرت الدراسة إلى حد كبير على الألعاب ثنائية اللاعبين التي لها موقع يتناوب فيه اللاعبون على التغيير بطرق محددة أو حركات لتحقيق شرط فوز محدد. لم تدرس في نظرية الألعاب الاندماجية تقليديًا ألعاب الحظ أو تلك التي تستخدم معلومات غير كاملة أو غير كاملة، مفضلة الألعاب التي تقدم معلومات مثالية تكون فيها حالة اللعبة ومجموعة الحركات المتاحة معروفة دائمًا من قبل كلا اللاعبين. ومع ذلك، مع تقدم التقنيات الرياضية، تتسع أنواع الألعاب التي يمكن تحليلها رياضيًا، وبالتالي تتغير حدود المجال باستمرار. سيحدد العلماء عمومًا ما يقصدونه بكلمة «لعبة» في بداية البحث، وغالبًا ما تختلف هذه التعريفات لأنها خاصة باللعبة التي يتم تحليلها ولا يُقصد منها تمثيل النطاق الكامل للمجال.

رياضيات يلعبون دور كوناني في ورشة عمل نظرية الألعاب الاندماجية

تتضمن الألعاب الاندماجية ألعابًا مشهورة مثل الشطرنج، لعبة الداما، وغو، والتي تعتبر غير تافهة، ولعبة اكس او، والتي تعتبر تافهة، بمعنى أنها «سهلة الحل». قد تحتوي بعض الألعاب الاندماجية أيضًا على منطقة لعب غير محدودة ، مثل لعبة الشطرنج اللانهائية. في نظرية اللعبة الاندماجية، يتم تمثيل التحركات في هذه الألعاب وغيرها كشجرة ألعاب.

تشتمل الألعاب الاندماجية أيضًا على ألغاز اندماجية للاعب واحد مثل سودوكو و

لا لاعب آلي، مثل لعبة الحياة (حوسبة) على الرغم من التعريف الدقيق، يمكن القول إن «الألعاب» تتطلب أكثر من مشارك واحد.

تتضمن نظرية الألعاب بشكل عام ألعاب الحظ، وألعاب المعرفة غير الكاملة، والألعاب التي يمكن للاعبين التحرك فيها في وقت واحد، وتميل إلى تمثيل مواقف صنع القرار في الحياة الواقعية.

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

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

قد يكون من المفيد التمييز بين «الألعاب الرياضية» الاندماجية التي تهم علماء الرياضيات والعلماء في المقام الأول للتفكير في حلها وحلها، و «ألعاب اللعب» الاندماجية التي تهم عموم السكان كشكل من أشكال الترفيه والمنافسة. ومع ذلك، يقع عدد من الألعاب في كلا الفئتين. نيم، على سبيل المثال، هي لعبة لعب مفيدة في تأسيس نظرية الالعاب الاندماجية، وهي واحدة من أولى الألعاب المحوسبة. لا يزال يستخدم لعبة اكس أو لتعليم المبادئ الأساسية لتصميم لعبة الذكاء الاصطناعي لطلاب علوم الكمبيوتر.

التاريخ

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

جون هورتون كونواي أحد مؤلفي نظرية اللعبة الجريئة

في الستينيات من القرن الماضي، قدم الوين بيرليكامب وجون هورتون كونواي وريتشارد ك جوي معًا نظرية اللعبة الحزبية، حيث تم تخفيف اشتراط أن تكون المسرحية متاحة للاعب واحد متاحة لكليهما. نُشرت نتائجهم في كتابهم طرق الفوز لمسرحياتك الرياضية في عام 1982. ومع ذلك، فإن أول عمل نُشر حول هذا الموضوع كان كتاب كونواي عام 1976 حول الأرقام والألعاب ، والمعروف أيضًا باسم ONAG ، والذي قدم مفهوم الأرقام السريالية والتعميم على الألعاب. كانت على الأرقام والألعاب أيضًا ثمرة للتعاون بين بيرلكامب وكونواي وجوي.

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

صرح كونواي في ONAG أن الإلهام لنظرية الألعاب الحزبية كان مبنيًا على ملاحظته للمسرحية في

غو لعبة النهاية، والتي يمكن غالبًا أن تتحلل إلى مجموعات من ألعاب النهاية الأبسط المعزولة عن بعضها البعض في أجزاء مختلفة من اللوحة.

أمثلة

قدم النص التمهيدي طرق الفوز عددًا كبيرًا من الألعاب، ولكن تم استخدام ما يلي كأمثلة تحفيزية للنظرية التمهيدية:

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

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

لعبة أخرى تمت دراستها في سياق نظرية اللعبة الاندماجية هي لعبة الشطرنج. في عام 1953 كتب الان تورنغ عن اللعبة، «إذا كان بإمكان المرء أن يشرح بشكل لا لبس فيه باللغة الإنجليزية، بمساعدة الرموز الرياضية إذا لزم الأمر، وكيف يتم إجراء الحساب، فمن الممكن دائمًا برمجة أي كمبيوتر رقمي للقيام بهذا الحساب بشرط أن تكون سعة التخزين كافية». في ورقة بحثية صدرت عام 1950، قدر كلود شانون الحد الأدنى لتعقيد شجرة اللعبة في الشطرنج بـ10 ¹²⁰ ، واليوم يُشار إلى هذا برقم شانون . لا يزال الشطرنج دون حل، على الرغم من أن الدراسة المكثفة، بما في ذلك العمل الذي يتضمن استخدام أجهزة الكمبيوتر العملاقة، قد خلقت قواعد طاولة نهاية لعبة الشطرنج، والتي تظهر نتيجة اللعب المثالي لجميع الألعاب النهائية المكونة من سبع قطع أو أقل. يحتوي الشطرنج اللانهائي على تعقيد اندماجي أكبر من الشطرنج (ما لم يتم دراسة الألعاب النهائية المحدودة فقط أو المواقف المكونة مع عدد صغير من القطع).

الملخص

اللعبة، في أبسط مصطلحاتها، هي قائمة «التحركات» المحتملة التي يمكن للاعبين القيام بها، وهما اليسار واليمين . يمكن اعتبار موقع اللعبة الناتج عن أي حركة بمثابة لعبة أخرى. تؤدي فكرة مشاهدة الألعاب من منظور تحركاتها المحتملة إلى ألعاب أخرى إلى تعريف رياضي تعاودي للألعاب وهو المعيار القياسي في نظرية الألعاب التوافقية. في هذا التعريف، تحتوي كل لعبة على العلامة {L | R} . L هي مجموعة مواضع اللعبة التي يمكن للاعب الأيسر الانتقال إليها، و R هي مجموعة مواضع اللعبة التي يمكن للاعب الأيمن الانتقال إليها؛ يتم تعريف كل موضع في L و R على أنه لعبة تستخدم نفس الترميز.

باستخدام الاستبداد كمثال، قم بتسمية كل مربع من ستة عشر صندوقًا من أربعة في أربعة من قبل A1 للمربع العلوي الأيسر، C2 للمربع الثالث من اليسار في الصف الثاني من الأعلى، وهكذا. نستخدم على سبيل المثال (D3، D4) للدلالة على موضع اللعبة حيث تم وضع دومينو عمودي في الركن الأيمن السفلي. بعد ذلك، يمكن وصف الموضع الأولي في تدوين نظرية اللعبة الاندماجية كـ

$\{(\mathrm {A} 1,\mathrm {A} 2),(\mathrm {B} 1,\mathrm {B} 2),\dots |(\mathrm {A} 1,\mathrm {B} 1),(\mathrm {A} 2,\mathrm {B} 2),\dots \}.$

في لعبة كروس القياسية، يتناوب اللاعبون، ولكن يتم التعامل مع هذا التناوب ضمنيًا من خلال تعريفات نظرية اللعبة الاندماجية بدلاً من تشفيرها داخل حالات اللعبة.

$\{(\mathrm {A} 1,\mathrm {A} 2)|(\mathrm {A} 1,\mathrm {B} 1)\}=\{\{|\}|\{|\}\}.$

تصف اللعبة أعلاه سيناريو لا يتبقى فيه سوى نقلة واحدة لأي من اللاعبين، وإذا قام أي من اللاعبين بهذه الخطوة، يفوز ذلك اللاعب. (تم حذف مربع مفتوح غير ذي صلة في C3 من الرسم التخطيطي.) تسمى {|} في قائمة نقل كل لاعب (المقابلة للمربع المتبقي الفردي بعد النقل) لعبة الصفر، ويمكن اختصارها في الواقع بـ 0. في لعبة الصفر، لا يمتلك أي لاعب أي حركات صحيحة؛ وهكذا، فإن اللاعب الذي يكون دوره عند ظهور لعبة الصفر يخسر تلقائيًا.

نوع اللعبة في الرسم البياني أعلاه له أيضًا اسم بسيط؛ يطلق عليها لعبة النجمة، والتي يمكن أيضًا اختصارها ∗. في لعبة النجوم، تؤدي الحركة الصالحة الوحيدة إلى لعبة الصفر، مما يعني أن كل من يأتي دوره خلال لعبة النجوم يفوز تلقائيًا.

هناك نوع إضافي من الألعاب، غير موجود في الاستبداد، وهي لعبة لوبي ، حيث تكون الحركة الصحيحة إما لليسار أو لليمين هي لعبة يمكن أن تؤدي بعد ذلك إلى اللعبة الأولى. لعبة الداما، على سبيل المثال، تصبح حلزونية عندما يتم ترقية إحدى القطع، حيث يمكن أن تدور بلا نهاية بين مربعين أو أكثر. اللعبة التي لا تمتلك مثل هذه الحركات تسمى حلقة مجانية.

اختصارات اللعبة

أعداد

تمثل الأرقام عدد الحركات الحرة، أو ميزة الحركة للاعب معين. حسب الاصطلاح، تمثل الأرقام الموجبة ميزة لليسار، بينما تمثل الأرقام السالبة ميزة لليمين. يتم تعريفها بشكل متكرر مع كون 0 هو الحالة الأساسية.

0 = {|}

1 = {0 |} ، 2 = {1 |} ، 3 = {2 |}

−1 = {| 0} ، −2 = {| −1} ، −3 = {| −2}

لعبة الصفر هي خسارة للاعب الأول.

مجموع ألعاب الأرقام يتصرف مثل الأعداد الصحيحة، على سبيل المثال 3 + −2 = 1.

نجمة

النجمة ، المكتوبة بالشكل ∗ أو {0 | 0} ، هي فوز اللاعب الأول حيث يجب على أي لاعب (إذا كان أول من يتحرك في اللعبة) الانتقال إلى لعبة صفرية، وبالتالي الفوز.

∗ + ∗ = 0، لأن اللاعب الأول يجب أن يحول نسخة واحدة من ∗ إلى 0، ثم يتعين على اللاعب الآخر تحويل النسخة الأخرى من ∗ إلى 0 أيضًا؛ في هذه المرحلة، سيخسر أول لاعب، لأن 0 + 0 لا يعترف بأي تحركات.

اللعبة ليست إيجابية ولا سلبية؛ يقال إنها وجميع الألعاب الأخرى التي يربح فيها اللاعب الأول (بغض النظر عن الجانب الذي يتواجد فيه اللاعب) غامضة أو مشوشة مع 0 ؛ رمزياً نكتب ∗ || 0.

فوق

فوق ، مكتوبًا كـ ↑ ، هو موقف في نظرية اللعبة الاندماجية. في التدوين القياسي، ↑ = {0 | ∗}.

- ↑ = ↓ (أسفل)

الارتفاع موجب تمامًا (↑> 0)، ولكنه متناهٍ في الصغر. يتم تعريف فوق في Winning Ways لمسرحياتك الرياضية .

تحت

أسفل ، مكتوبًا كـ ↓ ، هو موضع في نظرية اللعبة الاندماجية. في التدوين القياسي، ↓ = {∗ | 0}.

- ↓ = (أعلى)

يكون الاتجاه السفلي سالبًا تمامًا (↓ <0)، ولكنه متناهي الصغر. يتم تعريف تحت في طرق الفوز لمسرحياتك الرياضية .

ألعاب «ساخنة»

ضع في اعتبارك اللعبة {1 | −1}. كلتا الحركتين في هذه اللعبة هي ميزة للاعب الذي يقوم بهما ؛ لذلك يقال أن اللعبة «ساخنة»؛ أكبر من أي رقم أقل من -1، وأقل من أي رقم أكبر من 1، وغامض مع أي رقم بينهما. هو مكتوب كـ ± 1. يمكن إضافته إلى الأرقام، أو ضربه بأرقام موجبة، بالشكل المتوقع ؛ على سبيل المثال، 4 ± 1 = {5 | 3}.

نيمبرز

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

انظر أيضًا

• تقليم ألفا-بيتا، خوارزمية محسّنة للبحث في شجرة اللعبة
• لعبة واسعة النطاق، شجرة لعبة غنية بالمكافآت والمعلومات المتاحة للاعبين
• نظام متعدد العوامل، وهو نوع من أنظمة الكمبيوتر لمعالجة المشكلات المعقدة
• زوغزوان، يكون مضطرًا للعب عندما يكون ذلك غير موات
• نيم
• سودوكو

 

مراجع اضافية

• Albert، Michael H.؛ Nowakowski، Richard J.؛ Wolfe، David (2007). Lessons in Play: An Introduction to Combinatorial Game Theory. A K Peters Ltd. ISBN:978-1-56881-277-9.
• Beck، József (2008). Combinatorial games: tic-tac-toe theory. Cambridge University Press. ISBN:978-0-521-46100-9.
• Berlekamp، E.؛ Conway، J. H.؛ Guy، R. (1982). Winning Ways for your Mathematical Plays: Games in general. Academic Press. ISBN:0-12-091101-9. 2nd ed., A K Peters Ltd (2001–2004), (ردمك 1-56881-130-6), (ردمك 1-56881-142-X)
• Berlekamp، E.؛ Conway، J. H.؛ Guy، R. (1982). Winning Ways for your Mathematical Plays: Games in particular. Academic Press. ISBN:0-12-091102-7. 2nd ed., A K Peters Ltd (2001–2004), (ردمك 1-56881-143-8), (ردمك 1-56881-144-6).
• Berlekamp، Elwyn؛ Wolfe، David (1997). Mathematical Go: Chilling Gets the Last Point. A K Peters Ltd. ISBN:1-56881-032-6.
• Bewersdorff، Jörg (2004). Luck, Logic and White Lies: The Mathematics of Games. A K Peters Ltd. ISBN:1-56881-210-8. See especially sections 21–26.
• Conway، John Horton (1976). On Numbers and Games. Academic Press. ISBN:0-12-186350-6. 2nd ed., A K Peters Ltd (2001), (ردمك 1-56881-127-6).
• Robert A. Hearn؛ Erik D. Demaine (2009). Games, Puzzles, and Computation. A K Peters, Ltd. ISBN:978-1-56881-322-6.

روابط خارجية

• قائمة روابط نظرية اللعبة الاندماجية في الصفحة الرئيسية لديفيد إيبشتاين
• مقدمة لألعاب وأرقام كونواي بواسطة ديرك شلايشر ومايكل ستول
• ملخص مصطلحات نظرية اللعبة التوافقية بقلم بيل سبايت
• ورشة عمل نظرية الألعاب الاندماجية ، محطة أبحاث بانف الدولية ، يونيو 2005