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

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