نظرية الألعاب (بالإنجليزية: Game theory)‏ وتسمى أيضاً نظرية المباراة، وتعرف بانها وسيلة من وسائل التحليل الرياضي لحالات تضارب المصالح للوصول إلى أفضل الخيارات الممكنة لاتخاذ القرار في ظل الظروف المعطاة لاجل الحصول على النتائج المرغوبة.

جون فون نيومان العالم الهنغاري الأمريكي في خلال اربعينيات القرن الماضي

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

بدايات نظرية الألعاب

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

تاريخ نظرية الألعاب

أسس علم نظرية الألعاب سنة 1944 على يد جون فون نويمان وأوسكار مورغن شتيرن واشتهر عن طريق تأليفهما كتاب The Theory of Games and Economic Behavior. سنة 1994 تحصل كل من جون ناش ورينارد سيلتين وجون هارسانيي على جائزة نوبل للاقتصاد وذلك لإسهاماتهم في مجال نظرية الألعاب.

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

اللعبة: اللعبة موقف يجب على اللاعبين (على الأقل اثنين) فيه اتخاذ قرار.

مسلمات  

  • اللاعبون يتصرفون بعقلانية أي أنهم يحاولون جعل احتمال وقوع عملية دفع (أي تفوق أو ربح) أكثر احتمالا.
  • اللاعبون يتصرفون استراتيجيا أي أنهم يحسبون أو يتكهنون حركة المنافس أو اللاعب الآخر ويدخلونها في حساباتهم.

تقسيم 1 

يمكن تقسيم الألعاب إلى:

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

ألعاب دينامكية:
يمكن للاعبين فيها أن يتخذوا قراراتهم الواحد تلو الآخر. (في العلوم السياسية يقصد بها الألعاب التي تتميز بالتغير المستمر في القواعد وأطراف اللعبة).

تقسيم 2 

ألعاب بمعلومات كاملة:
كل اللاعبين يعرفون نوايا (أي ما هي النتيجة التي يريد المنافس أن يصل إليها) منافسيهم ومنافسوهم يعرفون ذلك وهم يعرفون أن منافسيهم يعلمون ذلك.

ألعاب بمعلومات منقوصة:
واحد على الأقل من اللاعبين ليس له علم كامل بنوايا منافسيه.

تقسيم 3 

  • الألعاب التعاونية وهي الألعاب التي يلعب فيها اللاعبون على شكل فرق
  • الألعاب غير التعاونية وهي الألعاب التي يلعب فيها اللاعبون بشكل فردي.

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

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

الحركة

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

الخرج (النصيب)

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

الصيغة الشاملة والصيغة الطبيعية

يعتبر البحث في الفرق بين الصيغ الشاملة والصيغ الطبيعية من أهم دراسات نظرية الألعاب.

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

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

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

إن أبسط الألعاب بصيغتها الشاملة تتضمن كمًّا هائلاً من المنهجيات والتخطيط لذلك طوّر الباحثون نمطًا جديدًا من الألعاب دعيت بالألعاب بصيغتها الطبيعية، حيث يمكن حساب النتائج بشكل كامل.

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

كاملة المعطيات 

نقول عن اللعبة بأنها كاملة المعطيات إذا كانت جميع الحركات الممكنة معروفة لكل لاعب، الداما، والشطرنج هما مثالان جيدان للعبة بمعطيات كاملة، البوكر تعتبر لعبة لا يمتلك فيها اللاعبون إلا قدراً محدودًا من المعطيات في بداية اللعبة.

منهج نظرية الألعاب

المنهج أو الخطة هو قائمة اللاعب بالخيارات المثلى الممكنة في كل مرحلة من مراحل اللعبة، ويعتبر المنهج الذي يأخذ في الحسبان جميع الحركات الممكنة قبل اتخاذ القرار هو منهج لا يخيب، حيث لا مكان للأحداث المفاجئة بهكذا مناهج.

أنواع الألعاب

إن نظرية الألعاب تميز بين عدة أشكال من الألعاب، وفقاً لعدد اللاعبين ولظروف اللعب نفسها.

لعبة الشخص الواحد/اللعب الفردية

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

لعبة الشخصين/الثنائية

يعتبر نمط الألعاب الثنائية من أكثر الأنماط انتشاراً، ويتضمن العديد من الألعاب المألوفة مثل الشطرنج، الداما، أو أي لعبة تعتمد على فريقين اثنين، والمعضلات الأكثر صعوبة هي التي تتضمن أكثر من لاعب، كالألعاب الجماعية مثل: المونوبولي، البوكر، أو أي لعبة تتضمن لاعبين متعددين.

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

ألعاب صفرية المجموع

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

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

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

كما ترتبط نظرية الألعاب ارتباط وثيق بعلم الاجتماع وتستخدم على نطاق واسع في السياسة.

وبحسب اراء لعلماء عديدين فإن لنظرية الألعاب مع فيزياء الكم تطبيقات كثيرة لشرح الإدراك البشري وانماط التفكير غير المنطقي.

أمثلة مشهورة

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

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

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

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

نظرية الألوان الأربعة

حل الألعاب المتسلسلة باستخدام الاستقراء العكسي

يوجد أدناه لعبة تسلسلية بسيطة بين لاعبين. الملصقات التي تحتوي على Player 1 و Player 2 بداخلها هي مجموعات المعلومات للاعبين واحد أو اثنين، على التوالي. الأرقام الموجودة بين الأقواس في أسفل الشجرة هي المكافآت في كل نقطة على حدة. اللعبة متسلسلة أيضًا، لذا يتخذ اللاعب 1 القرار الأول (يسارًا أو يمينًا) ويتخذ اللاعب 2 قراره بعد اللاعب 1 (لأعلى أو لأسفل).

نظرية الألعاب

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

نظرية الألعاب

بعد هذا التخفيض، يمكن للاعب 1 زيادة أرباحه إلى أقصى حد الآن بعد أن أصبحت خيارات اللاعب 2 معروفة. والنتيجة هي توازن تم العثور عليه عن طريق الحث العكسي للاعب 1 باختيار “الصحيح” والاعب 2 باختيار “أعلى”. يوجد أدناه حل اللعبة مع مسار التوازن بخط عريض.

نظرية الألعاب

على سبيل المثال، يمكن للمرء بسهولة إعداد لعبة مشابهة لتلك المذكورة أعلاه باستخدام الشركات كلاعبين. يمكن أن تتضمن هذه اللعبة سيناريوهات إصدار المنتج. إذا أرادت الشركة 1 إطلاق منتج، فما الذي يمكن أن تفعله الشركة 2 ردًا على ذلك؟ هل ستصدر الشركة 2 منتجًا منافسًا مشابهًا؟

نظرية الألعاب

نظرية زيرميلو (نظرية الألعاب)

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

فردریش زيرميلو (Friedrich Zermelo)

استنتاجات نظرية زيرميلو

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

تاريخ النشر

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

 نُشرت ورقة زيرميلو الأصلية التي تصف النظرية، Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels ، باللغة الألمانية في عام 1913. قام كل من Ulrich Schwalbe و Paul Walker بترجمة ورقة زيرميلو إلى الإنجليزية في عام 1997 ونشروا الترجمة في ملحق زيرميلو والتاريخ المبكر لنظرية اللعبة.

أصبح كتاب زيرميلو “حول تطبيق نظرية المجموعات على نظرية لعبة الشطرنج” حديثًا لمجتمع الرياضيات ويمكن اعتباره أول ورقة بحثية معروفة عن نظرية اللعبة.

تفاصيل

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

ثم يعالج مشكلتين:

  1. ماذا يعني أن يكون اللاعب في مركز “رابح” وهل من الممكن تحديد ذلك بطريقة رياضية موضوعية ؟
  2. إذا كان اللاعب في مركز رابح، فهل يمكن تحديد عدد الحركات اللازمة لفرض الفوز؟

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

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

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

الهدف الثاني من قبل Konig هو أن الإستراتيجية “تفعل الشيء نفسه عند التواجد الأول للمركز كما في الثانية وبالتالي الفوز بحركات أقل” لا يمكن إجراؤها إذا حان دور Black للتحرك في هذا المركز. ومع ذلك، فإن هذه الحجة غير صحيحة لأن زيرميلو اعتبر موقفين مختلفين سواء كان الأسود أو الأبيض يتحرك.

مثال

يمكن تطبيق نظرية زيرميلو على جميع الألعاب ذات المرحلتين المحدودة مع معلومات كاملة وحركات متبادلة. يجب أن تستوفي اللعبة المعايير التالية: يوجد لاعبان في اللعبة؛ اللعبة معلومات كاملة. لعبة اللوح محدودة. يمكن للاعبين تبادل الأدوار؛ ولا يوجد عنصر فرصة موجود. صرح زيرميلو أن هناك العديد من الألعاب من هذا النوع ولكن تم تطبيق نظريته في الغالب على لعبة الشطرنج.

عند تطبيقها على لعبة الشطرنج، تنص نظرية زيرميلو على أن “إما الأبيض يمكن أن يفرض الفوز، أو يمكن أن يفرض الأسود الفوز، أو يمكن لكلا الجانبين فرض التعادل على الأقل”.

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

نظرية زيرميلو والاستقراء العكسي

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

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

هناك عدد من الأسباب وراء عدم وجود الاستقراء العكسي في ورقة زيرميلو الأصلية:

أولاً، أظهرت دراسة حديثة أجراها Schwalbe and Walker (2001) أن ورقة زيرميلو تحتوي على فكرة أساسية عن الاستقراء العكسي، لكن زيرميلو لم يقدم بيانًا رسميًا حول النظرية. كانت طريقة زيرميلو الأصلية هي فكرة عدم التكرار.

تم تقديم أول ذكر للتحريض المتخلف بواسطة László Kalmár في عام 1928. عمم كالمار عمل زيرميلو وكونيج في ورقته “في نظرية الألعاب المجردة”. كان كالمار معنيا بالسؤال: “في ظل مركز رابح، ما السرعة التي يمكن بها فرض الفوز؟”. أظهرت ورقته البحثية أن الفوز بدون تكرار ممكن بالنظر إلى أن اللاعب هو مركز رابح. كان دليل كالمار على عدم التكرار دليلاً على الاستقراء العكسي. في ورقته، قدم كالمار مفهوم اللعبة الفرعية والتكتيك. كانت حجته المركزية في كالمار هي أن المركز لا يمكن أن يكون مركزًا رابحًا إلا إذا تمكن اللاعب من الفوز بعدد محدود من الحركات. أيضًا، المركز الرابح للاعب A هو دائمًا مركز خاسر للاعب B.

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

نظرية الترتيب الجيد

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

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

تاريخ

اعتبر جورج كانتور أن نظرية التنظيم الجيد هي “مبدأ أساسي للفكر”. ومع ذلك، يعتبر من الصعب أو حتى المستحيل تصور ترتيب جيد لـ {R}؛ مثل هذا التصور يجب أن يدمج بديهية الاختيار. في عام 1904، ادعى جيولا كونيغ أنه أثبت أن مثل هذا الترتيب الجيد لا يمكن أن يوجد. بعد بضعة أسابيع، وجد فيليكس هاوسدورف خطأً في الإثبات. ومع ذلك، اتضح أن نظرية الترتيب الجيد تكافئ بديهية الاختيار، بمعنى أن أحدهما مع بديهيات زيرميلو وفرينكل كافيان لإثبات الآخر، في منطق الترتيب الأول (ينطبق الأمر نفسه على منطق زورن ليما).

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

إثبات التيار المتردد (AC)

يمكن إثبات أكسيوم الاختيار من نظرية الترتيب الجيد على النحو التالي.

لعمل داله اختيار لمجموعة من المجموعات غير الفارغة، E، خذ اتحاد المجموعات في E واسمها X. يوجد ترتيب جيد لـ X؛ دع R يكون مثل هذا الأمر. الداله التي تربط كل مجموعة S من E أصغر عنصر من S، كما هو مرتب بواسطة (التقييد على S لـ) R، هي داله اختيار للمجموعة E.

النقطة الأساسية في هذا الدليل هي أنه لا يتضمن سوى خيار تعسفي واحد، وهو خيار R؛ لن ينجح تطبيق نظرية الترتيب الجيد على كل عضو S من E على حدة، لأن النظرية تؤكد فقط وجود ترتيب جيد، ولن يكون اختيار الترتيب الجيد لكل S أسهل من اختيار عنصر.

منشور ذات صلة

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

السلة