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

تعريفًا بالموضوع، نظرية الألعاب الاندماجية بالإنجليزية (Combinatorial game theory) واختصارا (CGT)هي فرع من فروع الرياضيات وعلوم الكمبيوتر النظرية التي تدرس عادةً الألعاب المتسلسلة بمعلومات مثالية. اقتصرت الدراسة إلى حد كبير على الألعاب ثنائية اللاعبين التي لها موقع يتناوب فيه اللاعبون على التغيير بطرق محددة أو حركات لتحقيق شرط فوز محدد. لم تدرس في نظرية الألعاب الاندماجية تقليديًا ألعاب الحظ أو تلك التي تستعمل معلومات غير كاملة أو غير كاملة، مفضلة الألعاب التي تقدم معلومات مثالية تكون فيها حالة اللعبة ومجموعة الحركات المتاحة معروفة دائمًا من قبل كلا اللاعبين. ومع ذلك، مع تقدم التقنيات الرياضية، تتسع أنواع الألعاب التي يمكن تحليلها رياضيًا، وبالتالي تتغير حدود المجال باستمرار. سيحدد العلماء عمومًا ما يقصدونه بكلمة «لعبة» في بداية البحث، وغالبًا ما تختلف هذه التعريفات لأنها خاصة باللعبة التي يتم تحليلها ولا يُقصد منها تمثيل النطاق الكامل للمجال. ونتناول فيما يلي مزيدًا من التفاصيل.
في هذا الإطار، تتضمن الألعاب الاندماجية ألعابًا مشهورة مثل الشطرنج، لعبة الداما، وغو، والتي تعتبر غير تافهة، ولعبة اكس او، والتي تعتبر تافهة، بمعنى أنها «سهلة الحل». قد تحتوي بعض الألعاب الاندماجية كذلك على منطقة لعب غير محدودة ، مثل لعبة الشطرنج اللانهائية. في نظرية اللعبة الاندماجية، يتم تمثيل التحركات في هذه الألعاب وغيرها كشجرة ألعاب.
وعلى صعيد آخر، تتضمن نظرية الألعاب بشكل عام ألعاب الحظ، وألعاب المعرفة غير الكاملة، والألعاب التي يمكن للاعبين التحرك فيها في وقت واحد، وتميل إلى تمثيل مواقف صنع القرار في الحياة الواقعية.
ومن جهة أخرى، فكرة مهمة في نظرية الالعاب الاندماجية هي فكرة اللعبة التي تم حلها. مثلًا، تعتبر لعبة اكس او لعبة محلولة، حيث يمكن إثبات أن أي لعبة ستؤدي إلى التعادل إذا لعب كلا اللاعبين على النحو الأمثل. من الصعب الحصول على نتائج مماثلة للألعاب ذات الهياكل التجميعية الغنية. مثلًا، أُعلن في سنة 2007 أن لعبة الداما قد تم حلها — يؤدي اللعب الأمثل من كلا الجانبين كذلك إلى التعادل — ولكن هذه النتيجة كانت إثباتًا بمساعدة الكمبيوتر. ألعاب العالم الحقيقي الأخرى معقدة في الغالب بحيث لا تسمح بالتحليل الكامل اليوم، على الرغم من أن النظرية قد حققت بعض النجاحات الأخيرة في تحليل نهاية اللعبة. تطبيق نظرية الالعاب الاندماجية على مركز يحاول تحديد التسلسل الأمثل للحركات لكلا اللاعبين حتى تنتهي اللعبة، ومن خلال القيام بذلك اكتشف الحركة المثلى في أي مركز. في الممارسة العملية، هذه العملية صعبة للغاية ما لم تكن اللعبة بسيطة للغاية.
ومن جهة أخرى، نظرية الالعاب الاندماجية لها تركيز مختلف عن نظرية اللعبة «التقليدية» أو «الاقتصادية»، التي تم تطويرها في البداية لدراسة الألعاب ذات البنية الاندماجية البسيطة، ولكن مع عناصر الصدفة (على الرغم من أنها تعتبر كذلك الحركات المتسلسلة، انظر لعبة الشكل الشامل). بشكل أساسي، ساهمت نظرية الالعاب الاندماجية في طرق جديدة لتحليل أشجار اللعبة، مثلًا باستخدام أرقام سريالية، وهي فئة فرعية لجميع ألعاب المعلومات المثالية للاعبين. إن نوع الألعاب التي درستها نظرية الالعاب الاندماجية مهم كذلك في الذكاء الاصطناعي، لا سيما للتخطيط الآلي والجدولة. في نظرية الالعاب الاندماجية، كان هناك تركيز أقل على تحسين خوارزميات البحث العملية (مثل الكشف عن مجريات التقليم ألفا بيتا المضمنة في أغلب كتب الذكاء الاصطناعي)، ولكن تم التركيز بشكل أكبر على النتائج النظرية الوصفية (مثل مقاييس تعقيد اللعبة أو البراهين على وجود الحل الأمثل بدون تحديد خوارزمية بالضرورة، مثل حجة سرقة الإستراتيجية).
إضافةً إلى ذلك، قد يكون من المفيد التمييز بين «الألعاب الرياضية» الاندماجية التي تهم علماء الرياضيات والعلماء في المقام الأول للتفكير في حلها وحلها، و «ألعاب اللعب» الاندماجية التي تهم عموم السكان كشكل من أشكال الترفيه والمنافسة. ومع ذلك، يقع عدد من الألعاب في كلا الفئتين. نيم، مثلًا، هي لعبة لعب مفيدة في تأسيس نظرية الالعاب الاندماجية، وهي واحدة من أولى الألعاب المحوسبة. لا يزال يستعمل لعبة اكس أو لتعليم المبادئ الأساسية لتصميم لعبة الذكاء الاصطناعي لطلاب علوم الكمبيوتر.
كذلك، تشتمل الألعاب الاندماجية كذلك على ألغاز اندماجية للاعب واحد مثل سودوكو و
في هذا الإطار، لا لاعب آلي، مثل لعبة الحياة (حوسبة) على الرغم من التعريف الدقيق، يمكن القول إن «الألعاب» تتطلب أكثر من مشارك واحد.
تحت
وفي هذا السياق، ضع في اعتبارك اللعبة {1 | −1}. كلتا الحركتين في هذه اللعبة هي ميزة للاعب الذي يقوم بهما ؛ لذلك يقال أن اللعبة «ساخنة»؛ أكبر من أي رقم أقل من -1، وأقل من أي رقم أكبر من 1، وغامض مع أي رقم بينهما. هو مكتوب كـ ± 1. يمكن إضافته إلى الأرقام، أو ضربه بأرقام موجبة، بالشكل المتوقع ؛ مثلًا، 4 ± 1 = {5 | 3}.
ألعاب «ساخنة»
ومن جهة أخرى، يكون الاتجاه السفلي سالبًا تمامًا (↓ <0)، ولكنه متناهي الصغر. يتم تعريف تحت في طرق الفوز لمسرحياتك الرياضية .
- ↓ = (أعلى)
نيمبرز
وفي هذا السياق، اللعبة المحايدة هي لعبة تتوفر فيها نفس الحركات لكلا اللاعبين في كل مركز من اللعبة. مثلًا، يعتبر نيم غير متحيز ، حيث يمكن للآخر إزالة أي مجموعة من العناصر التي يمكن لأي لاعب إزالتها. ومع ذلك ، فإن الاستبداد ليس محايدًا ، لأن أحد اللاعبين يضع الدومينو الأفقية والآخر يضع الدومينو الرأسية. وبالمثل ، فإن لعبة الداما ليست محايدة ، لأن اللاعبين يمتلكون قطعًا ملونة مختلفة. لأي رقم ترتيبي، يمكن للمرء تحديد لعبة محايدة مع تعميم نيم حيث ، في كل نقلة ، يمكن لأي لاعب استبدال الرقم بأي رقم ترتيبي أصغر ؛ تُعرف الألعاب المحددة بهذه الطريقة باسم نيمبر . تنص نظرية سبراج-جراندي على أن كل لعبة محايدة تعادل نيمبر.
أمثلة
وفي هذا الصدد، الضفادع والضفادع - تتيح قيم اللعبة المختلفة. على عكس أغلب الألعاب الأخرى، يتم تمثيل الموضع بسهولة بسلسلة قصيرة من الأحرف.
علاوةً على ذلك، هاكنبوش أزرق - أحمر - أخضر يسمح بقيم إضافية للعبة ليست أرقامًا بالمعنى التقليدي، مثلًا، نجمة.
من جهة ثانية، هاكنبوش ازرق - احمر على المستوى المحدود، تسمح هذه اللعبة التوافقية الحزبية بإنشاء ألعاب تكون قيمها أرقامًا منطقية ثنائية. على المستوى اللانهائي، يسمح للفرد ببناء جميع القيم الحقيقية، فضلًا عن الكثير من القيم اللانهائية التي تقع ضمن فئة الأرقام السريالية.
في هذا الإطار، كانت لعبة غو الكلاسيكية مؤثرة على نظرية اللعبة الاندماجية المبكرة، ثم طور بيرلكامب وولف لاحقًا نظرية نهاية اللعبة ودرجة الحرارة لها (انظر المراجع). مسلحين بهذا، كانوا قادرين على بناء مواقف غو لعبة النهاية المعقولة التي يمكنهم من خلالها منح لاعبي غو الخبراء اختيار الجوانب ثم هزيمتهم في كلتا الحالتين.
ومن ناحية أخرى، نيم - لعبة نزيهة. هذا يسمح لبناء ارقام. (يمكن كذلك اعتبارها حالة خاصة باللون الأخضر فقط من هاكنبوش أزرق - أحمر - أخضر)
من جهة ثانية، قدم النص التمهيدي طرق الفوز عددًا كبيرًا من الألعاب، ولكن تم استخدام ما يلي كأمثلة تحفيزية للنظرية التمهيدية:
كذلك، لعبة أخرى تمت دراستها في سياق نظرية اللعبة الاندماجية هي لعبة الشطرنج. في عام 1953 كتب الان تورنغ عن اللعبة، «إذا كان بإمكان المرء أن يشرح بشكل لا لبس فيه باللغة الإنجليزية، بمساعدة الرموز الرياضية إذا لزم الأمر، وكيف يتم إجراء الحساب، فمن الممكن دائمًا برمجة أي كمبيوتر رقمي للقيام بهذا الحساب بشرط أن تكون سعة التخزين كافية». في ورقة بحثية صدرت عام 1950، قدر كلود شانون الحد الأدنى لتعقيد شجرة اللعبة في الشطرنج بـ10 120 ، واليوم يُشار إلى هذا برقم شانون . لا يزال الشطرنج دون حل، على الرغم من أن الدراسة المكثفة، بما في ذلك العمل الذي يتضمن استخدام أجهزة الكمبيوتر العملاقة، قد خلقت قواعد طاولة نهاية لعبة الشطرنج، والتي تظهر نتيجة اللعب المثالي لجميع الألعاب النهائية المكونة من سبع قطع أو أقل. يحتوي الشطرنج اللانهائي على تعقيد اندماجي أكبر من الشطرنج (ما لم يتم دراسة الألعاب النهائية المحدودة فقط أو المواقف المكونة مع عدد صغير من القطع).
وفي السياق ذاته، الاستبداد - تظهر الكثير من الألعاب الممتعة، مثل الألعاب الساخنة، كمواقع في الاستبداد، لأنه يوجد في بعض الأحيان حافز للتحرك، وأحيانًا لا. هذا يسمح بمناقشة درجة حرارة اللعبة.
نجمة
وفي هذا السياق، النجمة ، المكتوبة بالشكل ∗ أو {0 | 0} ، هي فوز اللاعب الأول حيث يجب على أي لاعب (إذا كان أول من يتحرك في اللعبة) الانتقال إلى لعبة صفرية، وبالتالي الفوز.
من جانب آخر، اللعبة ليست إيجابية ولا سلبية؛ يقال إنها وجميع الألعاب الأخرى التي يربح فيها اللاعب الأول (بغض النظر عن الجانب الذي يتواجد فيه اللاعب) غامضة أو مشوشة مع 0 ؛ رمزياً نكتب ∗ – 0.
ومن جهة أخرى، ∗ + ∗ = 0، لأن اللاعب الأول يجب أن يحول نسخة واحدة من ∗ إلى 0، ثم يتعين على اللاعب الآخر تحويل النسخة الأخرى من ∗ إلى 0 كذلك؛ في هذه المرحلة، سيخسر أول لاعب، لأن 0 + 0 لا يعترف بأي تحركات.
فوق
من جانب آخر، الارتفاع موجب تمامًا (↑> 0)، ولكنه متناهٍ في الصغر. يتم تعريف فوق في Winning Ways لمسرحياتك الرياضية .
- ↑ = ↓ (أسفل)
الملخص
ومن ناحية أخرى، باستخدام الاستبداد كمثال، قم بتسمية كل مربع من ستة عشر صندوقًا من أربعة في أربعة من قبل A1 للمربع العلوي الأيسر، C2 للمربع الثالث من اليسار في الصف الثاني من الأعلى، وهكذا. نستعمل مثلًا (D3، D4) للدلالة على موضع اللعبة حيث تم وضع دومينو عمودي في الركن الأيمن السفلي. لاحقًا، يمكن وصف الموضع الأولي في تدوين نظرية اللعبة الاندماجية كـ
اختصارات اللعبة
في هذا الإطار، تصف اللعبة أعلاه سيناريو لا يتبقى فيه سوى نقلة واحدة لأي من اللاعبين، وإذا قام أي من اللاعبين بهذه الخطوة، يفوز ذلك اللاعب. (تم حذف مربع مفتوح غير ذي صلة في C3 من الرسم التخطيطي.) تسمى {|} في قائمة نقل كل لاعب (المقابلة للمربع المتبقي الفردي بعد النقل) لعبة الصفر، ويمكن اختصارها في الواقع بـ 0. في لعبة الصفر، لا يمتلك أي لاعب أي حركات صحيحة؛ وهكذا، فإن اللاعب الذي يكون دوره عند ظهور لعبة الصفر يخسر تلقائيًا.
كذلك، اللعبة، في أبسط مصطلحاتها، هي قائمة «التحركات» المحتملة التي يمكن للاعبين القيام بها، وهما اليسار واليمين . يمكن اعتبار موقع اللعبة الناتج عن أي حركة بمثابة لعبة أخرى. تؤدي فكرة مشاهدة الألعاب من منظور تحركاتها المحتملة إلى ألعاب أخرى إلى تعريف رياضي تعاودي للألعاب وهو المعيار القياسي في نظرية الألعاب التوافقية. في هذا التعريف، تحتوي كل لعبة على العلامة {L | R} . L هي مجموعة مواضع اللعبة التي يمكن للاعب الأيسر الانتقال إليها، و R هي مجموعة مواضع اللعبة التي يمكن للاعب الأيمن الانتقال إليها؛ يتم تعريف كل موضع في L و R على أنه لعبة تستعمل نفس الترميز.
وعلى صعيد آخر، في لعبة كروس القياسية، يتناوب اللاعبون، ولكن يتم التعامل مع هذا التناوب ضمنيًا من خلال تعريفات نظرية اللعبة الاندماجية بدلاً من تشفيرها داخل حالات اللعبة.
في هذا الإطار، نوع اللعبة في الرسم البياني أعلاه له كذلك اسم بسيط؛ يطلق عليها لعبة النجمة، والتي يمكن كذلك اختصارها ∗. في لعبة النجوم، تؤدي الحركة الصالحة الوحيدة إلى لعبة الصفر، مما يعني أن كل من يأتي دوره خلال لعبة النجوم يفوز تلقائيًا.
وفي السياق ذاته، هناك نوع إضافي من الألعاب، غير موجود في الاستبداد، وهي لعبة لوبي ، حيث تكون الحركة الصحيحة إما لليسار أو لليمين هي لعبة يمكن أن تؤدي فيما بعد إلى اللعبة الأولى. لعبة الداما، مثلًا، تصبح حلزونية عندما يتم ترقية إحدى القطع، حيث يمكن أن تدور بلا نهاية بين مربعين أو أكثر. اللعبة التي لا تمتلك مثل هذه الحركات تسمى حلقة مجانية.
أعداد
ومن جهة أخرى، مجموع ألعاب الأرقام يتصرف مثل الأعداد الصحيحة، مثلًا 3 + −2 = 1.
لعبة الصفر هي خسارة للاعب الأول.
وفي السياق ذاته، تمثل الأرقام عدد الحركات الحرة، أو ميزة الحركة للاعب معين. حسب الاصطلاح، تمثل الأرقام الموجبة ميزة لليسار، بينما تمثل الأرقام السالبة ميزة لليمين. يتم تعريفها بشكل متكرر مع كون 0 هو الحالة الأساسية.
التاريخ
ومن جهة أخرى، يتم وضع الألعاب الاندماجية بشكل عام، بحسب الاتفاقية، في شكل يفوز فيه أحد اللاعبين عندما لا يتبقى لدى الآخر أي حركات. من السهل تحويل أي لعبة محدودة بنتيجتين محتملتين فقط إلى لعبة مكافئة حيث تنطبق هذه الاتفاقية. من أهم المفاهيم في نظرية الألعاب الاندماجية مفهوم مجموع لعبتين، وهي لعبة يمكن لكل لاعب فيها أن يختار التحرك إما في لعبة واحدة أو في الأخرى في أي نقطة من اللعبة، ويفوز اللاعب. عندما لا يكون لخصمه أي حركة في أي من المباراتين. تؤدي هذه الطريقة في الجمع بين الألعاب إلى بنية رياضية غنية وقوية.
وفي هذا السياق، في الستينيات من القرن الماضي، قدم الوين بيرليكامب وجون هورتون كونواي وريتشارد ك جوي معًا نظرية اللعبة الحزبية، حيث تم تخفيف اشتراط أن تكون المسرحية متاحة للاعب واحد متاحة لكليهما. نُشرت نتائجهم في كتابهم طرق الفوز لمسرحياتك الرياضية في سنة 1982. ومع ذلك، فإن أول عمل نُشر حول هذا الموضوع كان كتاب كونواي عام 1976 حول الأرقام والألعاب ، والمعروف كذلك باسم ONAG ، والذي قدم مفهوم الأرقام السريالية والتعميم على الألعاب. كانت على الأرقام والألعاب كذلك ثمرة للتعاون بين بيرلكامب وكونواي وجوي.
من جانب آخر، غو لعبة النهاية، والتي يمكن غالبًا أن تتحلل إلى مجموعات من ألعاب النهاية الأبسط المعزولة عن بعضها البعض في أجزاء مختلفة من اللوحة.
في هذا الإطار، نشأت نظرية الالعاب الاندماجية فيما يتعلق بنظرية الألعاب المحايدة، حيث يجب أن تكون أي لعبة متاحة للاعب واحد متاحة للآخر كذلك. إحدى هذه الألعاب هي نيم، والتي يمكن حلها بالكامل. نيم هي لعبة محايدة للاعبين، وتخضع لظروف اللعب العادية ، مما يعني أن اللاعب الذي لا يستطيع التحرك يخسر. في الثلاثينيات من القرن الماضي، أظهرت نظرية سبراج-جراندي أن جميع الألعاب المحايدة مكافئة للأكوام في نيم، مما يُظهر أن عمليات التوحيد الرئيسية ممكنة في الألعاب التي يتم النظر فيها على مستوى اندماجي، حيث تكون الاستراتيجيات التفصيلية مهمة، وليس مجرد المكافآت.
من جهة ثانية، صرح كونواي في ONAG أن الإلهام لنظرية الألعاب الحزبية كان مبنيًا على ملاحظته للمسرحية في
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟