خوارزمية الله

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

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

الألغاز الميكانيكية

الألغاز​

يمكن حل لغز الخمسة عشر في 80 حركة لقطعة واحدة [ 6 ^{] أو 43} حركة لعدة قطع ^{[ 7 ]} في أسوأ الحالات. أما بالنسبة لتعميمه، لغز n ، فإن مشكلة إيجاد الحل الأمثل له تُصنف ضمن مسائل NP-hard ^{[ 8 ]،} لذا فليس من المعروف ما إذا كان هناك خوارزمية مثالية عملية لحله.

أبراج هانوي

بالنسبة للغز أبراج هانوي ، توجد خوارزمية إلهية معروفة لأي عدد معين من الأقراص. ويزداد عدد الحركات بشكل أُسّي مع ازدياد عدد الأقراص .${\displaystyle 2^{n}-1}$) . ^{[ 9 ]}

مكعب روبيك

نُشرت خوارزمية لتحديد الحد الأدنى لعدد الحركات اللازمة لحل مكعب روبيك عام 1997 على يد ريتشارد إي. كورف . ^{[ 10 ]} مع أنه كان معروفًا منذ عام 1995 أن 20 هو الحد الأدنى لعدد الحركات اللازمة للحل في أسوأ الحالات، فقد أثبت توم روكيكي عام 2010 أنه لا يوجد أي تكوين يتطلب أكثر من 20 حركة. ^{[ 11 ]} وبالتالي، فإن 20 هو حد أعلى دقيق لطول الحلول المثلى. وكان عالم الرياضيات ديفيد سينغماستر قد افترض، بتسرع، أن هذا العدد هو 20 عام 1980. ^{[ 4 ]}

بعض الألعاب الشهيرة ذات القواعد والحركات البسيطة والمحددة بدقة، لم يُكتشف لها خوارزمية مثالية للفوز. ومن الأمثلة على ذلك لعبتا الشطرنج والجو . ^{[ 12 ]} تتزايد احتمالات الفوز في كلتا اللعبتين بسرعة مع كل حركة. يبلغ العدد الإجمالي للاحتمالات الممكنة حوالي 5 × 10⁴⁴ [13 ] للشطرنج ^{و10¹⁸⁰ (على لوحة 19 × 19)} للجو ، [14] وهو عدد هائل لا يسمح بإيجاد حل باستخدام تقنية الحوسبة الحالية (قارن ذلك بمكعب روبيك الذي تم حله بصعوبة بالغة، والذي يبلغ حوالي 5 × ^{10⁴⁴ [ 13 ]} للشطرنج و10¹⁸⁰ (على لوحة 19 × 19) للجو، ^{[ 14 ]} وهو عدد كبير جدًا بحيث لا يسمح بإيجاد حل شامل له باستخدام تقنيات الحوسبة الحالية (قارن ذلك بمكعب روبيك الذي تم حله بصعوبة بالغة، والذي يبلغ حوالي 5 × 10⁴⁴ [14]).4.3 × 10^ ¹⁹ وضعية ^{[ 15 ]} . وبالتالي، فإن تحديد خوارزمية الله لهذه الألعاب باستخدام القوة الغاشمة أمرٌ غير ممكن. مع أن حواسيب الشطرنج قد بُنيت قادرة على هزيمة حتى أفضل اللاعبين البشريين، إلا أنها لا تحسب اللعبة حتى نهايتها. على سبيل المثال، بحث برنامج ديب بلو 11 نقلة فقط للأمام (مع احتساب نقلة كل لاعب كنقلتين)، مما قلل مساحة البحث إلى 10^ ¹⁷ فقط . ^{[ 16 ]} بعد ذلك، قيّم كل وضعية بحثًا عن ميزة وفقًا لقواعد مستمدة من اللعب البشري والخبرة.

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

من جهة أخرى، لطالما كان يُشتبه في أن لعبة الداما (الشطرنج) تُحسم بالتعادل من قِبل ممارسيها المحترفين. ^{[ 19 ]} في عام 2007، أثبت شيفر وآخرون ذلك من خلال حساب قاعدة بيانات لجميع المواضع التي تحتوي على عشر قطع أو أقل، مُقدمين خوارزمية مثالية لجميع نهايات لعبة الداما، والتي استُخدمت لإثبات أن جميع مباريات الداما التي تُلعب بشكل مثالي تنتهي بالتعادل. ^{[ 20 ]} ومع ذلك، فإن لعبة الداما التي تحتوي على عشر قطع أو أقل فقط5 × 10 ²⁰ موضعًا ^{[ 21 ]} وأقل من ذلك،3.9 × 10 ¹³ ، في قاعدة البيانات، ^{[ 22 ]} هي مشكلة أسهل بكثير للحل - من نفس رتبة مكعب روبيك.

لا يُحدد حجم مجموعة مواقع قطع الأحجية بشكل كامل إمكانية وجود خوارزمية إلهية. فمثلاً، يمكن أن تحتوي أحجية برج هانوي، التي تم حلها بالفعل، على عدد عشوائي من القطع، ويتزايد عدد المواقع بشكل أُسّي مع ازدياد عدد القطع.${\displaystyle 3^{n}}$ومع ذلك، فإن خوارزمية الحل قابلة للتطبيق على أي مشكلة مهما كان حجمها، مع زيادة وقت التشغيل تدريجيًا.${\displaystyle 2^{n}}$[ ^{23 ]​}

• آلة أوراكل
• تدبير إلهي
• الأدلة من الكتاب
• مجموعة مكعب روبيك
• لعبة محلولة

• باوم، إريك ب.، ما هو الفكر؟، مطبعة معهد ماساتشوستس للتكنولوجيا، 2004، رقم ISBN 0262025485.
• ديفيس، داريل ن.؛ شلبي، ت.؛ بيربانك-غرين، ب.، "الحياة الاصطناعية، والوكلاء، ولغة غو"، في محمديان، مسعود، آفاق جديدة في الذكاء الحسابي وتطبيقاته ، ص  125-139، دار نشر IOS، 2000، رقم ISBN 9051994761.
• Fraser, Rober (ed); Hannah, W. (ed), The Draught Players' Weekly Magazine , vol. 2, Glasgow: JH Berry, 1885.
• جوينر، ديفيد (2002). مغامرات في نظرية الزمر . مطبعة جامعة جونز هوبكنز. ISBN 0-8018-6947-1.
• مور، كريستوفر؛ ميرتنز، ستيفان، طبيعة الحوسبة ، مطبعة جامعة أكسفورد، 2011، رقم ISBN 0191620807.
• روثنبرغ، غادي، التحفيز، خوارزمية الله، والشيطان الأخضر ، مطبعة جامعة أمستردام، 2009، رقم ISBN 9056295896.
• شايفر، جوناثان؛ بيرش، نيل؛ بيورنسون، ينجفي؛ كيشيموتو، أكيهيرو؛ مولر، مارتن؛ ليك، روبرت؛ لو، بول؛ سوتفين، ستيف (14 سبتمبر 2007). "تم حل لعبة الداما" (ملف PDF) . مجلة ساينس . 317 (5844): 1518-1522 . رمز Bibcode : 2007Sci...317.1518S . doi : 10.1126/science.1144079 . ISSN 0036-8075 . PMID 17641166 .  
• سينغماستر، ديفيد، ملاحظات حول مكعب روبيك السحري ، دار بنغوين للنشر، 1981، رقم ISBN 0-907395-00-7.
• سينغماستر، ديفيد، "القيمة التعليمية للمكعب السحري المجري"، وقائع المؤتمر الدولي الرابع للتعليم الرياضي ، الذي عُقد في بيركلي، كاليفورنيا، في الفترة من 10 إلى 16 أغسطس 1980، الصفحات  307-312، دار بيركهاوزر بوسطن للنشر، 1983، رقم ISBN 978-0-8176-3082-9.