لعبة محلولة

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

يمكن حل لعبة ثنائية اللاعبين على عدة مستويات : ^{[ 1 ] [ 2 ]}

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

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

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

أواري (لعبة من عائلة مانكالا )

تم حل نسخة لعبة أواري التي تسمح بإنهاء المباراة بـ"الضربات الكبرى" بشكل نهائي من قبل هنري بال وجون رومين في جامعة فريجي في أمستردام ، هولندا (2002). ويمكن لأي من اللاعبين إجبار المباراة على التعادل.

عيدان الطعام

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

توصيل أربعة

تم حلها لأول مرة بواسطة جيمس د. ألين في 1 أكتوبر 1988، وبشكل مستقل بواسطة فيكتور أليس في 16 أكتوبر 1988. ^{[ 3 ]} يمكن للاعب الأول فرض الفوز. تم حلها بشكل كامل بواسطة قاعدة بيانات جون ترومب ذات 8 طبقات ^{[ 4 ]} (4 فبراير 1995). تم حلها بشكل جزئي لجميع أحجام اللوحات حيث يكون مجموع العرض والارتفاع 15 كحد أقصى (وكذلك 8×8 في أواخر عام 2015) ^{[ 3 ]} (18 فبراير 2006). تم حلها لجميع أحجام اللوحات حيث يكون مجموع العرض والارتفاع 16 في 22 مايو 2024. ^{[ 5 ]} في عام 2025، تم حل اللوحة الكلاسيكية 7×6 بشكل كامل باستخدام جدول بحث للفوز والتعادل والخسارة. ^{[ 6 ]}

بيموكو مجاني

تم حلها بواسطة فيكتور أليس (1993). يمكن للاعب الأول أن يفرض الفوز دون قواعد الافتتاح. ^{[ 1 ]}

شبح

تم حلها بواسطة آلان فرانك باستخدام قاموس لاعبي سكرابل الرسمي في عام 1987. ^{[ 7 ]}

هيكساباون

تم حل متغير 3×3 بفوز للأسود، كما تم حل العديد من المتغيرات الأكبر حجماً. ^{[ 8 ]}

كالا

تم حل معظم المتغيرات بواسطة جيفري إيرفينغ، وجيرون دونكرز، وجوس أويترويك (2000) باستثناء متغير كالاه (6/6). وقد تم حل متغير (6/6) بواسطة أندرس كارستنسن (2011). وقد ثبتت أفضلية اللاعب الأول القوية في معظم الحالات. ^{[ 9 ] [ 10 ]}

لعبة L

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

المهراجا والجنود الهنود

هذه اللعبة غير المتكافئة هي فوز للاعب السيبوي إذا لعب بشكل صحيح.

نيم

تم حلها بشكل قاطع. ^{[ 11 ]}

لعبة موريس التسعة رجال

تم حلها بواسطة رالف جاسر (1993). يمكن لأي من اللاعبين إجبار المباراة على التعادل. ^{[ 12 ] [ 13 ]}

النظام والفوضى

يفوز اللاعب الأول (حسب الترتيب). ^{[ 14 ]}

أوهفالهو

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

بانكي

تم حل هذه المسألة ببراعة من قبل جيسون دوسيت (2001). ^{[ 15 ]} تنتهي المباراة بالتعادل. لا يوجد سوى حركتين أوليتين فريدتين إذا تم استبعاد الوضعيات المتطابقة. إحداهما تُجبر الخصم على التعادل، والأخرى تُعطيه فوزًا مضمونًا في 15 حركة.

بنتاغو

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

ربعي

تم حلها بواسطة لوك غوسينز (1998). لاعبان مثاليان سيتعادلان دائمًا. ^{[ 16 ] [ 17 ] [ 18 ]}

لعبة شبيهة بلعبة رينجو بدون قواعد افتتاحية

يُزعم أنه تم حلها بواسطة يانوس فاغنر وإيستفان فيراج (2001). ^{[ 19 ]} فوز اللاعب الأول.

تيكو

تم حلها بواسطة جاي ستيل (1998). اعتمادًا على الصيغة، إما أن يفوز اللاعب الأول أو أن تنتهي بالتعادل. ^{[ 20 ]}

رقصة موريس لثلاثة رجال

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

الفرسان الثلاثة

تم حلها بشكل قوي من قبل يوهانس لير في عام 2009، وحلها بشكل ضعيف من قبل علي العبريدي في عام 2017. ^{[ 21 ]} إنها انتصار للقطع الزرقاء (رجال الكاردينال ريشيليو، أو العدو). ^{[ 22 ]}

لعبة إكس أو

يمكن حلها بسهولة بالغة نظرًا لصغر شجرة اللعبة. ^{[ 23 ]} تنتهي اللعبة بالتعادل إذا لم تُرتكب أي أخطاء، مع العلم أنه لا يمكن ارتكاب أي خطأ في النقلة الافتتاحية.

لعبة ويثوف

تم حلها بشكل قاطع بواسطة دبليو إيه ويثوف في عام 1907. ^{[ 24 ]}

لعبة الداما الإنجليزية (الداما)

تم حل هذه النسخة من لعبة الداما (8×8) بشكل جزئي في 29 أبريل 2007، بواسطة فريق جوناثان شيفر . من وضعية البداية القياسية، يضمن كلا اللاعبين التعادل باللعب المثالي. ^{[ 25 ]} تحتوي لعبة الداما على مساحة بحث تبلغ 5×10^ ²⁰ وضعية لعب ممكنة. ^{[ 26 ]} بلغ عدد العمليات الحسابية 10 ^{^14} ، والتي أُجريت على مدى 18 عامًا. تطلّبت العملية استخدام ما بين 200 جهاز كمبيوتر مكتبي في ذروتها، ثم انخفض العدد إلى حوالي 50 جهازًا. ^{[ 27 ]}

فانورونا

تم حلها بشكل ضعيف من قبل مارتن شاد. المباراة انتهت بالتعادل. ^{[ 28 ]}

خسارة الشطرنج

تم حلها بشكل ضعيف في عام 2016 على أنها فوز للأبيض بدءًا من 1.  e3. ^{[ 29 ]}

عطيل (بأسلوب ريفيرسي)

تم حلها جزئيًا عام 2023 بواسطة هيروكي تاكيزاوا، الباحث في شركة Preferred Networks . ^{[ 30 ]} ومع ذلك، فإن استنتاجات البحث محل جدل. ^{[ 31 ]} من الوضعية الابتدائية القياسية على رقعة لعب 8×8، ستؤدي الحركة المثالية لكلا اللاعبين إلى التعادل. تُعدّ لعبة أوثيلو أكبر لعبة تم حلها حتى الآن، حيث يبلغ نطاق البحث فيها 10^ ²⁸ وضعية لعب محتملة.

البنتومينو

تم حلها بشكل ضعيف بواسطة إتش كيه أورمان. ^{[ 32 ]} إنه فوز للاعب الأول.

كيوبيك

تم حلها بشكل ضعيف من قبل أورين باتاشنيك (1980) وفيكتور أليس . يفوز اللاعب الأول.

سيم

حل ضعيف: الفوز للاعب الثاني.

الحملان والنمور

تم حلها بشكل ضعيف بواسطة يو جين ليم (2007). المباراة انتهت بالتعادل. ^{[ 33 ]}

الشطرنج

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

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

يذهب

تم حل رقعة الشطرنج 5×5 بشكل جزئي لجميع حركات الافتتاح في عام 2002. ^{[ 34 ]} وتم حل رقعة الشطرنج 7×7 بشكل جزئي في عام 2015. ^{[ 35 ]} يلعب البشر عادةً على رقعة شطرنج 19×19، وهي أكثر تعقيدًا بأكثر من 145 رتبة مقدارية من رقعة 7×7. ^{[ 36 ]}

عرافة

تُظهر حجة سرقة الاستراتيجية (كما استخدمها جون ناش ) أنه لا يمكن للاعب الأول أن يخسر أيًا من أحجام رقعة اللعب المربعة. وبالاقتران مع برهان استحالة التعادل، يتضح أن اللعبة تُحسم لصالح اللاعب الأول (أي أنها حل ضعيف للغاية). أما بالنسبة لأحجام رقعة لعب محددة، فالمعلومات المتوفرة أكثر: إذ تم حلها بشكل كامل بواسطة عدة حواسيب لأحجام رقعة تصل إلى 6×6. كما تم التوصل إلى حلول ضعيفة لأحجام رقعة 7×7 (باستخدام استراتيجية تبديل )، و8×8، و9×9؛ وفي حالة 8×8، تم التوصل إلى حل ضعيف لجميع حركات الافتتاح. ^{[ 37 ]} من غير المرجح إيجاد حل كامل لمسألة Hex على رقعة N × N ، حيث ثبت أن المسألة كاملة من فئة PSPACE . إذا لُعبت Hex على رقعة N ×( N +1)، فإن اللاعب الذي لديه أقصر مسافة للربط يمكنه دائمًا الفوز باستراتيجية إقران بسيطة، حتى مع عيب اللعب ثانيًا.

لعبة الداما الدولية

تم حلّ جميع وضعيات نهاية اللعبة التي تتراوح بين قطعتين وسبع قطع، بالإضافة إلى الوضعيات التي تضم 4×4 و5×3 قطع حيث يمتلك كل جانب ملكًا واحدًا أو أقل، والوضعيات التي تضم خمسة رجال ضد أربعة رجال، والوضعيات التي تضم خمسة رجال ضد ثلاثة رجال وملك واحد، والوضعيات التي تضم أربعة رجال وملك واحد ضد أربعة رجال. وقد حُلّت وضعيات نهاية اللعبة هذه في عام 2007 على يد إد جيلبرت من الولايات المتحدة. وأظهر التحليل الحاسوبي أن احتمالية انتهاء اللعبة بالتعادل عالية جدًا إذا لعب كلا اللاعبين بشكل مثالي. ^{[ 38 ]}

مورابارابا

تم حلها بشكل قوي بواسطة غابور إي. جيفاي (2015). يفوز اللاعب الأول في اللعب الأمثل. ^{[ 39 ]}

لعبة m ، n ، k

من السهل إثبات أن اللاعب الثاني لا يمكنه الفوز أبدًا؛ انظر حجة سرقة الاستراتيجية . تم حل جميع الحالات تقريبًا بشكل ضعيف عندما يكون k ≤ 4. بعض النتائج معروفة عندما يكون k = 5. تنتهي المباريات بالتعادل عندما يكون k ≥ 8.

• شطرنج الكمبيوتر
• كمبيوتر جو
• لعبة أوتيلو الحاسوبية
• تعقيد اللعبة
• خوارزمية الله
• نظرية زيرميلو (نظرية الألعاب)

• أليس، هل يمكن التغلب على بطل العالم؟ أحدث ما توصلت إليه تكنولوجيا ألعاب الكمبيوتر. في كتاب "مناهج جديدة لبحوث ألعاب الطاولة".

• التعقيد الحسابي للألعاب والألغاز بقلم ديفيد إبستين.
• يقوم أعضاء فريق GamesCrafters بحل ألعاب ثنائية اللاعبين بمعلومات كاملة وبدون أي فرصة.