حل الشطرنج - ويكيبيديا
حل الشطرنج هو مصطلح يشير إلى إيجاد استراتيجية مثالية في مباراة لعبة الشطرنج. والاستراتيجية المثالية في لعبة الشطرنج هي أي إستراتيجية يمكن لأحد اللاعبين من خلالها سواء اللاعب الأبيض أو اللاعب الأسود، أن يفرض الفوز، أو أن يفرض التعادل على اللاعب الآخر. يُستخجم المصطلح ذاته بشكل عام ليشير أيضًا إلى حل الألعاب الشبيهة بالشطرنج، والألعاب الاندماجية التي يكون بها معلومات كاملة مثل لعبة شطرنج كابابلانكا، والشطرنج اللانهائي، والتي يكون فيها دائما إستراتيجية مثالية يمكن تحديدها وفقاً لنظرية زارميلو. قد يشير مصطلح حل الشطرنج في بعض الأحيان أيضاً إلى إثبات أي من النتائج الثلاثة المحتملة (الأبيض يفوز، الأسود يفوز، التعادل) كنتيجة لمباراة شطرنج بين لاعبين مثاليين دون الكشف بالضرورة عن الاستراتيجية المثلى ذاتها، والتي يمكن أن تستخدم لتحقيق تلك النتيجة.[1]
ليس هناك حلاً كاملاً معروفاً للعبة الشطرنج يمكن الوصول إليه باستخدام أي من الحواس، ومن غير المُتوقّع أن يكون هناك حلاً دائماً للعبة الشطرنج في المستقبل القريب، ولا يزال هناك جدل علميّ حول ما إذا كان النمو الأسي الحالي لقوة الحوسبة سيستمر لفترة كافية تسمح بإيجاد حلول دائمة للعبة الشطرنج يومًا ما باستخدام البحث الشامل والذي يعني التحقق من جميع الاحتمالات.
لا يزال التقدم فيما يتعلّق بحل ألعاب الشطرنج حتى الآن محدوداً للغاية، وهناك فقط عدد قليل من القواعد التي تسمح بالوصول إلى نهاية مباراة لعبة الشطرنج المثالية بعدد صغير من القطع على طاولة اللعب، كما تم حل العديد من الألعاب الشبيهة بالشطرنج بشكل ضعيف. على الأقل هناك تقديرات محسوبة لتعقيد مسار اللعبة، والتي توفر نظرة شاملة للجهد الحسابي الذي قد يكون مطلوبًا لحل اللعبة.
النتائج الجزئيّة
[عدل]قواعد طاولة نهاية اللعبة
[عدل]تُعد قواعد طاولة نهاية لعبة الشطرنج امتدادات رجعيّة لعناصر اللعبة الأولية معروفة منذ العصور القديمة، ومُخزّنة في قاعدة بيانات منظمة قابلة للبحث. تستطيع قواعد طاولة نهاية اللعبة أن تنجح في حل لعبة الشطرنج بدرجة محدودة، حيث يمكن من خلالها أن تحدّد اللعب المثالي في عدد من الطاولات النهائية، والتي من بينها جميع طاولات اللعب النهائية غير البسيطة التي لا يزيد عدد القطع فيها عن سبع قطع من بينها الملكين والبيادق.[2]
تتمثل إحدى نتائج تطوير قاعدة طاولة نهاية اللعبة المكونة من سبع قطع في العثور على العديد من نهايات الشطرنج النظرية المثيرة للاهتمام. ولعل أحد الأمثلة على ذلك هو وضع الإماتة 546، والذي يؤدّي في حالة اللعب المثالي إلى إماتة ملك الخصم من خلال 546 حركة متجاوزاً قاعدة الخمسين حركة.[3] يفوق مثل هذا الموقف قدرة أي إنسان على حله، ولا يمكن أن يلعبه أي لاعب شطرنج بشكل صحيح أيضًا دون استخدام قاعدة طاولة نهاية اللعبة.
متغيرات لعبة الشطرنج
يقدم البديل الذي وصفه منظر المعلومات كلود شانون لأول مرة حجة حول القيمة النظرية للعبة الشطرنج: فهو يقترح السماح بنقلة التمرير. يمكن بهذا الشكل إثبات أن اللاعب الأول سيتعادل على الأقل، وبالتالي فإذا كان لللاعب الأول نقلة ناجحة، دعه يلعبها، وإذا لم يكن تُمرّر النقلة لللاعب الآخر. يواجه اللاعب الثاني الآن نفس الموقف بسبب تناظر الصورة المعكوسة للوحة الشطرنج، فإذا لم يكن لللاعب الأول نقلة ناجحة في المقام الأول، فإن اللاعب الثاني ليس لديه أي نقلة الآن. في أحسن الأحوال يمكن لللاعب الثاني أن يتعادل، ويمكن للاعب الأول على الأقل أن يتعادل، وبالتالي فإن اللعبة المثالية تؤدي إلى فوز أو تعادل اللاعب الأول.[4]
ساعدت طريقة متغيرات لعبة الشطرنج في حل العديد من الألعاب الأبسط من الشطرنج. حيث يمكن بسهولة حفظ إستراتيجية الفوز للون الأسود في لعبة شطرنج المهراجا والسيبوي. تمكن غاردنر جزئيّاً من حل لعبة الشطرنج المصغر، والتي تتكون من خمسة صفوف عرضية وخمسة أعمدة طولية، بشكل ضعيف كتعادل مستخدما متغيرات لعبة الشطرنج.[5] على الرغم من أن لعبة الشطرنج الخاسر تُلعب على لوحة تتكون من ثمانية صفوف عرضية وثمانية أعمدة طولية، إلا أن قاعدة الالتقاط الإجباري بها تحد بشكل كبير من تعقيدها وتمكّن التحليل الحسابي من حل هذا المتغير بشكل ضعيف باعتباره فوزًا لللاعب الأبيض.[6]
تُصبح احتماليّة حل ألعاب فردية ومحددة شبيهة بالشطرنج أكثر صعوبة مع زيادة حجم لوحة اللعب، كما هو الحال في متغيرات الشطرنج الكبيرة والشطرنج اللانهائي.[7]
تعقيد لعبة الشطرنج
[عدل]حدّد منظّر المعلومات كلود شانون في عام 1950 إجراءاً نظريًا يمكن من خلاله لعب لعبة مثالية من حيث المبدأ (أي حل الشطرنج)، فوفقاً لشانون يمكن من حيث المبدأ لعب لعبة شطرنج مثالية أو إنشاء آلة يمكنها القيام بذلك على النحو التالي:
إذا كان اللاعب في موضع معين فإنّه يحدد جميع التحركات الممكنة، ثم كل التحركات الممكنة للخصم، وما إلى ذلك، حتى نهاية اللعبة (في كل شكل). ووفقًا لقواعد الألعاب فإن نهاية اللعبة يجب أن تحدث بعد عدد محدود من النقلات (مثل قاعدة الخمسين حركة). تنتهي كل من هذه التغييرات بالفوز أو الخسارة أو التعادل. وبالبدء من النهاية بشكل عكسي، يمكن تحديد ما إذا كان أحد اللاعبين سيفوز حتماً في نهاية اللعبة، أم أنها ستنتهي بالتعادل أو بخسارة هذا اللاعب.
قدّر شانون بعد ذلك أن حل لعبة الشطرنج وفقًا لهذا الإجراء سيتطلب مقارنة نحو 10120 احتمالاً ممكنًا للعبة، أو وجود قاموس يشير إلى الحركة المثلى لكل موضع من بين 1043 موضعاً ممكناً تقريباً على لوحة اللعب (والتي يُقدّر عددها الآن بحوالي 4x1044 موضعاً).[4][8] بيد أنّ عدد العمليات الحسابية المطلوبة لحل لعبة الشطرنج قد يختلف اختلافًا كبيرًا عن عدد العمليات المطلوبة لتوليد شجرة لعبة الشطرنج بأكملها.
فإذا كان اللاعب الأبيض سيفوز حتماً، فستحتاج مجموعة فرعية فقط من شجرة اللعبة تقييمًا لتأكيد وجود فوز حتمي (أي بدون تفنيد حركات اللاعب الأسود). يفترض حساب شانون لتعقيد لعبة الشطرنج بالإضافة إلى ذلك أن متوسط طول اللعبة يبلغ 40 نقلة، ولكن لا يوجد أساس رياضي للقول إن الفوز الحتمي لأي من اللاعبين سيكون له أي علاقة بطول اللعبة. وعلى أرض الواقع، كانت بعض مباريات لعبة الشطرنج التي كان طرفيها من خبراء اللعبة (اللعب على مستوى العظماء) قصيرة تتكون من 16 نقلة على سبيل المثال. لهذه الأسباب، كان علماء الرياضيات ومنظرو اللعبة مترددين في التأكيد بشكل قاطع على أن حل لعبة الشطرنج مشكلة تستعصي على الحل.[4][9]
التنبؤات التي تتعلق بحل الشطرنج
[عدل]قدّر كلود شانون في عام 1950 بناءاً على تعقيد شجرة اللعبة 10120 احتمالاً لحل الشطرنج، والتي يمكن معالجتها باستخدام حاسوب يعمل بسرعة 1 ميغا هرتز، وهي السرعة التي كانت تفوق سرعة أقوى الحاسبات في ذلك الوقت حيث كانت أقوى الحاسبات في عام 1951 تستطيع تنفيذ 2000 عملية تقريبًا في الثانية أو 2 كيلو هرتز. كان هذا يعني أن العقدة الطرفية سوف يستغرق حلها 1090 عامًا إذا كان زمن الخطوة الأولى 1 ميكرو ثانية. وبالتالي، فإن حل الشطرنج كان على ما يبدو أبعد من أي تقنية كانت متاحة في ذلك الوقت.
رأى هانس واكيم بريمرمان أستاذ الرياضيات والفيزياء الحيوية بجامعة كاليفورنيا في بيركلي في ورقة بحثية قدمها عام 1965 أن سرعة وذاكرة وقدرة معالجة أي حاسوب في المستقبل ستكون مقيدة بحواجز فيزيائية محددة من بينها حاجز الضوء، والحاجز الكمومي، والحاجز الديناميكي الحراري. تشير هذه القيود، على سبيل المثال، إلى أنه لا يوجد جهاز حاسب على الإطلاق مهما بلغت قوته سيكون قادرًا على فحص الشجرة الكاملة لتسلسلات الحركة المحتملة للعبة الشطرنج.
إلا أن بريمرمان لم ينفي تماماً احتمال أن يتمكن الحاسوب يومًا ما من حل لعبة الشطرنج، ولكنه اشترط لجعل الحاسوب يلعب لعبة مثالية أو شبه كاملة، أنّه سيكون من الضروري إما تحليل اللعبة بالكامل، أو تحليل اللعبة بطريقة تقريبية ودمجها مع قدر محدود من البحث عن الأشجار. رأى بريمرمان أن الفهم النظري لمثل هذه البرمجة التجريبية لا يزال أمرًا صعباً للغاية.[10]
لم تغير التطورات العلمية الحديثة التي شهدها العالم منذ ذلك الحين هذه التقييمات بشكل كبير. تمكّن جوناثان شيفر في عام 2007 من إيجاد حلّ جزئيّ ضعيف للعبة الداما، والتي تحتوي تقريبًا على الجذر التربيعي لعدد المواضع الموجودة في لعبة الشطرنج.[11] وذكر جوناثان شيفر إن انجازاً علميّا مثل الحوسبة الكمومية سيكون ضروريًا قبل محاولة الوصول إلى حل الشطرنج، لكنه لا يستبعد هذا الاحتمال. أفاد جوناثان شيفر أيضاً إن الشيء الوحيد الذي تعلمه من جهوده التي استمرت 16 عامًا من حل لعبة الداما هو عدم التقليل من شأن التقدم التكنولوجي.[12]
المراجع
[عدل]- ^ Allis، V. (1994). "PhD thesis: Searching for Solutions in Games and Artificial Intelligence" (PDF). Department of Computer Science. جامعة ماسترخت. مؤرشف من الأصل (PDF) في 2020-11-22. اطلع عليه بتاريخ 2012-07-14.
- ^ "Lomonosov Tablebases". مؤرشف من الأصل في 2021-09-26. اطلع عليه بتاريخ 2013-04-24.
- ^ "Who wins from this puzzle?" A mate-in-546 chess position, with discussion (Post 1: Position, Post 7: Playable). نسخة محفوظة 2021-05-19 على موقع واي باك مشين.
- ^ ا ب ج Shannon، C. (مارس 1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine. 7. ج. 41 ع. 314. مؤرشف (PDF) من الأصل في 2010-03-15. اطلع عليه بتاريخ 2008-06-27.
- ^ A bot will complete this citation soon. Click here to jump the queue أرخايف:1307.7118.
- ^ Watkins، Mark. "Losing Chess: 1. e3 wins for White" (PDF). مؤرشف من الأصل (PDF) في 2021-08-28.
- ^ Aviezri Fraenkel؛ D. Lichtenstein (1981)، "Computing a perfect strategy for n×n chess requires time exponential in n"، J. Combin. Theory Ser. A، ج. 31، ص. 199–214، DOI:10.1016/0097-3165(81)90016-9
- ^ John Tromp (2021). "Chess Position Ranking". مؤرشف من الأصل في 2021-09-06.
- ^ http://www.chessgames.com Magnus Carlsen vs Viswanathlan Anand, King's Indian Attack: Double Fianchetto (A07), 1/2-1/2, 16 moves. نسخة محفوظة 2021-11-30 على موقع واي باك مشين.
- ^ Bremermann، H.J. (1965). "Quantum Noise and Information". Proc. 5th Berkeley Symp. Math. Statistics and Probability. مؤرشف من الأصل في 2001-05-27.
- ^ Schaeffer، Jonathan؛ Burch، Neil؛ Björnsson، Yngvi؛ وآخرون (14 سبتمبر 2007). "Checkers Is Solved". ساينس. ج. 317 ع. 5844: 1518–1522. Bibcode:2007Sci...317.1518S. DOI:10.1126/science.1144079. PMID:17641166. S2CID:10274228.(الاشتراك مطلوب)
- ^ Sreedhar، Suhas. "Checkers, Solved!". Spectrum.ieee.org. مؤرشف من الأصل في 2009-03-25. اطلع عليه بتاريخ 2009-03-21.