لعبة الأميرة والوحش

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

في كتابه "الألعاب التفاضلية " (1965)، عرّف روفوس إسحاق اللعبة على النحو التالي:

يبحث الوحش عن الأميرة، والوقت اللازم لذلك هو المكافأة. كلاهما في غرفة مظلمة تمامًا (بأي شكل)، لكن كل منهما يدرك حدودها. يعني الالتقاط أن المسافة بين الأميرة والوحش تقع ضمن نصف قطر الالتقاط، والذي يُفترض أنه صغير مقارنةً بأبعاد الغرفة. يتحرك الوحش، المفترض أنه شديد الذكاء، بسرعة معلومة. نمنح الأميرة حرية كاملة في الحركة. ^{[ 1 ]}

ظلت هذه اللعبة مسألة مفتوحة معروفة حتى حلّها شموئيل غال في أواخر سبعينيات القرن العشرين. ^{[ 2 ] [ 3 ]} تتمثل استراتيجيته المثلى للأميرة في الانتقال إلى موقع عشوائي في الغرفة والبقاء فيه لفترة زمنية مناسبة، لا قصيرة جدًا ولا طويلة جدًا، قبل الانتقال إلى موقع عشوائي آخر (مستقل) وتكرار العملية. ^{[ 3 ] [ 4 ] [ 5 ]} أما استراتيجية البحث المثلى المقترحة للوحش فتعتمد على تقسيم الغرفة إلى مستطيلات ضيقة، واختيار مستطيل عشوائيًا والبحث فيه بطريقة محددة، وبعد فترة زمنية معينة يتم اختيار مستطيل آخر عشوائيًا وبشكل مستقل، وهكذا.

يمكن لعب لعبة الأميرة والوحش على رسم بياني مُختار مسبقًا . وقد ثبت أنه لأي رسم بياني محدود، توجد استراتيجية بحث مختلطة مثلى تُؤدي إلى عائد محدود. وقد حُلّت هذه اللعبة بواسطة ستيف ألبيرن ، وبشكل مستقل بواسطة ميخائيل زيليكين، فقط للرسم البياني البسيط جدًا الذي يتكون من حلقة واحدة (دائرة). ^{[ 6 ] [ 7 ]} وقد تم تقدير قيمة اللعبة على الفترة [1] (رسم بياني بعقدتين بينهما رابط) بشكل تقريبي.

تبدو اللعبة بسيطة ظاهريًا، لكنها في الواقع معقدة للغاية. تضمن استراتيجية البحث البديهية، التي تبدأ من نهاية عشوائية وتجوب كامل النطاق بأسرع ما يمكن، زمن استيلاء متوقعًا قدره 0.75، وهي ليست الاستراتيجية المثلى. باستخدام استراتيجية بحث واختباء مختلطة أكثر تطورًا، يمكن تقليل زمن الاستيلاء المتوقع بنحو 8.6%. سيكون هذا الرقم قريبًا جدًا من قيمة اللعبة لو تمكن أحدهم من إثبات مثالية استراتيجية الأميرة ذات الصلة. ^{[ 8 ] [ 9 ]}

• ألعاب البحث
• قائمة الألعاب في نظرية الألعاب