نظرية الألعاب التوافقية

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
📷 يحتوي على 4 صور
الموسوعة الحرة
علماء الرياضيات يلعبون لعبة كونان في ورشة عمل حول نظرية الألعاب التوافقية

نظرية الألعاب التوافقية فرع من الرياضيات وعلوم الحاسوب النظرية ، تُعنى بدراسة الألعاب المتسلسلة ذات المعلومات الكاملة . وقد ركزت الأبحاث في هذا المجال بشكل أساسي على ألعاب اللاعبين، حيث يتطور الوضع من خلال حركات متناوبة ، تخضع كل منها لقواعد محددة، بهدف تحقيق شرط فوز معين. وعلى عكس نظرية الألعاب الاقتصادية ، تتجنب نظرية الألعاب التوافقية عمومًا دراسة ألعاب الحظ أو الألعاب التي تنطوي على معلومات غير كاملة ، مفضلةً بدلاً من ذلك الألعاب التي يكون فيها الوضع الحالي ومجموعة الحركات المتاحة معروفة دائمًا لكلا اللاعبين. [ 1 ] ومع ذلك، مع تطور التقنيات الرياضية، يتسع نطاق الألعاب القابلة للتحليل، وتستمر حدود هذا المجال في التطور. [ 2 ] عادةً ما يُعرّف الباحثون مصطلح "اللعبة" في بداية أوراقهم البحثية، بتعريفات مُخصصة للعبة المحددة قيد التحليل، بدلاً من أن تعكس النطاق الكامل للمجال.

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

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

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

الاختلاف مع نظرية الألعاب التقليدية

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

تاريخ

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

في ستينيات القرن العشرين، قدّم كلٌّ من إلوين ر. بيرلكامب ، وجون هـ. كونواي، وريتشارد ك. غاي، نظرية اللعبة الحزبية ، التي تُخفف فيها شرط إتاحة اللعب المتاح لأحد اللاعبين لكلا اللاعبين. نُشرت نتائجهم في كتابهم " طرق الفوز في ألعابك الرياضية" عام ١٩٨٢. مع ذلك، كان أول عمل منشور في هذا الموضوع هو كتاب كونواي " حول الأعداد والألعاب" (On Numbers and Games) الصادر عام ١٩٧٦ ، والمعروف أيضًا باسم ONAG، والذي قدّم مفهوم الأعداد السريالية وتعميمه على الألعاب. وكان كتاب "حول الأعداد والألعاب" ثمرة تعاون بين بيرلكامب، وكونواي، وغاي.

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

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

أمثلة

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

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

لعبة أخرى دُرست في سياق نظرية الألعاب التوافقية هي الشطرنج . في عام 1953، كتب آلان تورينج عن اللعبة: "إذا أمكن شرح كيفية إجراء عملية حسابية بوضوح تام باللغة الإنجليزية، مع الاستعانة بالرموز الرياضية عند الحاجة، فمن الممكن دائمًا برمجة أي حاسوب رقمي لإجراء تلك العملية الحسابية، شريطة أن تكون سعة التخزين كافية." [ 8 ] في ورقة بحثية نُشرت عام 1950، قدّر كلود شانون الحد الأدنى لتعقيد شجرة لعبة الشطرنج بـ 10^ 120 ، ويُشار إلى هذا اليوم باسم عدد شانون . [ 9 ] لا يزال الشطرنج لغزًا لم يُحل، على الرغم من أن الدراسات المكثفة، بما في ذلك العمل الذي يتضمن استخدام الحواسيب العملاقة، قد أنشأت قواعد بيانات لنهايات لعبة الشطرنج ، والتي تُظهر نتيجة اللعب الأمثل لجميع نهايات اللعبة التي تحتوي على سبع قطع أو أقل. يتميز الشطرنج اللانهائي بتعقيد توافقي أكبر من الشطرنج العادي (إلا إذا اقتصرت الدراسة على نهايات اللعبة المحدودة، أو المواقف المركبة التي تحتوي على عدد قليل من القطع).

ملخص

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

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

{(أ1،أ2)،(ب1،ب2)،...|(أ1،ب1)،(أ2،ب2)،...}.{\displaystyle \{(\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 \}.}

في لعبة Cross-Cram القياسية، يتناوب اللاعبون الأدوار، ولكن يتم التعامل مع هذا التناوب ضمنيًا من خلال تعريفات نظرية الألعاب التوافقية بدلاً من أن يتم ترميزه داخل حالات اللعبة.

{(أ1،أ2)|(أ1،ب1)}={{|}|{|}}.{\displaystyle \{(\mathrm {A} 1,\mathrm {A} 2)|(\mathrm {A} 1,\mathrm {B} 1)\}=\{\{|\}|\{|\}\}.}

تصف اللعبة أعلاه سيناريو لا يتبقى فيه سوى حركة واحدة لكل لاعب، وإذا قام أي منهما بهذه الحركة، فإنه يفوز. (تم حذف المربع المفتوح غير ذي الصلة في C3 من الرسم التوضيحي). يُطلق على الرمز {|} في قائمة حركات كل لاعب (المقابل للمربع الوحيد المتبقي بعد الحركة) اسم " لعبة الصفر " ، ويمكن اختصاره إلى 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.

اللعبة ∗n هي رمز للعبة {0, ∗, …, ∗(n−1)| 0, ∗, …, ∗(n−1)}، وهي تمثل أيضًا لعبة نيم العادية مع كومة واحدة من n عنصرًا. (لاحظ أن ∗0 = 0 و ∗1 = ∗).

صعوداً وهبوطاً

يمثل السهم العلوي ، الذي يُكتب ↑، وضعية في نظرية الألعاب التوافقية. [ 10 ] في الترميز القياسي، ↑ = {0|∗}. ويُطلق على معكوسه السهم السفلي .

−↑ = ↓ ( أسفل )

الاتجاه للأعلى موجب تمامًا (↑ > 0)، والاتجاه للأسفل سالب تمامًا (↓ < 0)، وكلاهما متناهي الصغر . يُعرّف الاتجاهان للأعلى والأسفل في كتاب " طرق الفوز في ألعابك الرياضية" .

ألعاب "ساخنة"

لنفترض اللعبة {1|−1}. كلا الحركتين في هذه اللعبة تُعدّان ميزة للاعب الذي يقوم بهما؛ لذا تُسمى اللعبة "ساخنة"؛ فهي أكبر من أي عدد أقل من −1، وأصغر من أي عدد أكبر من 1، ومُبهمة مع أي عدد بينهما. تُكتب على الصورة ±1. لاحظ أن هناك فئة فرعية من الألعاب الساخنة، يُشار إليها بـ ±n للعبة عددية ما n، وهي لعبة التبديل. يمكن جمع ألعاب التبديل مع الأعداد، أو ضربها بأعداد موجبة، بالطريقة المتوقعة؛ على سبيل المثال، 4 ± 1 = {5|3}.

الأرقام

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

الأعداد "الأصغر" - الأبسط والأصغر وفقًا للترتيب المعتاد للأعداد الترتيبية - هي 0 و ∗.

انظر أيضاً

ملحوظات

  1. ↑ دروس في اللعب، ص 3
  2. يُعد تحليل توماس س. فيرغسون للعبة البوكر مثالًا على توسع نظرية الألعاب التوافقية لتشمل الألعاب التي تتضمن عناصر الحظ. كما يُعد البحث في لعبة نيم ثلاثية اللاعبين مثالًا على دراسة تتجاوز نطاق الألعاب ثنائية اللاعبين. ولعل تحليل كونواي، وغاي، وبيرلكامب للألعاب الحزبية هو أشهر توسع لنطاق نظرية الألعاب التوافقية، إذ نقل هذا المجال إلى ما هو أبعد من دراسة الألعاب المحايدة.
  3. ↑ ديمين، إريك د .؛ هيرن، روبرت أ. (2009). "لعب الألعاب باستخدام الخوارزميات: نظرية الألعاب التوافقية الخوارزمية" . في ألبرت، مايكل هـ.؛ نوفاكوفسكي، ريتشارد ج. (محرران). ألعاب بلا فرصة 3. منشورات معهد أبحاث العلوم الرياضية. المجلد  56. مطبعة جامعة كامبريدج. الصفحات 3-56 . arXiv : cs.CC/0106019 . 
  4. ↑ شيفر، ج.؛ بيرش، ن.؛ بيورنسون، ي.؛ كيشيموتو، أ.؛ مولر، م.؛ ليك، ر.؛ لو، ب.؛ سوتفين، س. (2007). "تم حل لعبة الداما". مجلة ساينس . 317 (5844): 1518-1522 . رمز Bibcode : 2007Sci...317.1518S . CiteSeerX 10.1.1.95.5393 . doi : 10.1126/science.1144079 . PMID 17641166. S2CID 10274228 .   
  5. ↑ فرانكل، أفيزري (2009). "الألعاب التوافقية: ببليوغرافيا مختارة مع مقدمة موجزة". ألعاب بلا حظ 3. 56 : 492.
  6. ↑ جرانت، يوجين ف.؛ لاردنر، ريكس (2 أغسطس 1952). "حديث المدينة - هو" . مجلة نيويوركر .
  7. ↑ راسل، ستيوارت ؛ نورفيج، بيتر (2021). "الفصل 5: البحث التنافسي والألعاب". الذكاء الاصطناعي: منهج حديث . سلسلة بيرسون في الذكاء الاصطناعي ( الطبعة الرابعة). بيرسون للتعليم، ص 146-179 . ISBN   978-0-13-461099-3.
  8. ↑ آلان تورينج. "الحواسيب الرقمية المطبقة على الألعاب" . جامعة ساوثهامبتون وكلية كينجز كامبريدج. ص 2. 
  9. ↑ كلود شانون (1950). "برمجة حاسوب للعب الشطرنج" (ملف PDF) . المجلة الفلسفية . 41 (314): 4. مؤرشف من الأصل (ملف PDF) بتاريخ 2010-07-06.
  10. ↑ إي. بيرلكامب؛ جيه إتش كونواي؛ آر. جاي (1982). طرق رابحة في لعبك الرياضي . المجلد الأول. دار النشر الأكاديمية. ISBN  0-12-091101-9.إي. بيرلكامب؛ جيه إتش كونواي؛ آر. جاي (1982). طرق رابحة في لعبك الرياضي . المجلد  الثاني. دار النشر الأكاديمية. ISBN 0-12-091102-7.

مراجع