الگوریتم خدا

بحث‌هایی که پیرامون حل پازل مکعب روبیک بوده‌است، سرچشمهٔ پیدایش نظریه‌ای به نام الگوریتم خدا شده‌است،Paul Anthony Jones, Jedburgh Justice and Kentish Fire: The Origins of English in Ten Phrases and Expressions, Hachette UK, 2014 ISBN 1-4721-1622-4. هرچند که بر روی سایر پازل‌های ترکیبی و بازی‌ریاضی‌ها نیز قابل اجرا است.See e.g. Rubik's Cubic Compendium by Ernö Rubik, Tamás Varga, Gerzson Kéri, György Marx, and Tamás Vekerdy (1987, Oxford University Press, ISBN 0-19-853202-4), p. 207: "...the Pyraminx is much simpler than the Magic Cube... Nicholas Hammond has shown that God's Algorithm is at most 21 moves (including the four trivial vertex moves). [More recently, three people have found God's Algorithm. The maximal number of moves is 15 (including the four vertex moves).]" در واقع، الگوریتم خدا به هر الگوریتمی که راه‌حلی با کمترین تعداد حرکات ممکن را ارائه می‌دهد، تلقی می‌شود. ایده پیدایش این الگوریتم، این است که می‌گوید یک موجود واقف بر همه چیز (omniscient being) وجود دارد که برای هر موقعیت داده شده‌ای، از یک گام بهینه برای آن موقعیت آگاه است.

 تعریف و راه‌حل 
این نظریه، برای پازل‌هایی قابل اجرا است که تعداد وضعیت‌های متفاوتی که می‌تواند داشته باشد، محدود است، با مجموعه‌ای از حرکات نسبتاً کوچک و معلوم که ممکن است روی این وضعیت‌ها قابل اجرا باشند و منجر به یک وضعیت جدید شوند. حل کردن یک پازل یعنی دستیابی به یک وضعیت معین نهایی که ممکن است فقط و فقط یک تک وضعیت یا یک عضو از مجموعه‌ای از وضعیت‌ها باشد.

یک راه‌حل را بهینه می‌گوییم اگر دنبالهٔ حرکات آن، کوتاهترین حالت ممکن باشد. این تعداد حرکات، با عنوان عدد خدا یا به شکل رسمی‌تر، مقدار کمین‌بیش نیز شناخته می‌شوند. در نتیجه، برای یک پازل، الگوریتم خدا، الگوریتمی است که پازل را فقط با راه‌حل‌های بهینه حل می‌کند.

 مثال‌ها 
بندانگشتی|مکعب روبیک

 پازل‌های مکانیکی 
 پازل‌های n تایی 
پازل ۱۵ تایی، در بدترین حالت می‌تواند با ۸۰ حرکت تک خانه‌ای یا ۴۳ حرکت چند خانه‌ای حل شود. برای حالت کلی آن که پازل n تایی است، از آنجایی که مسئلهٔ پیدا کردن یک راه‌حل بهینه برای آن، ان‌پی سخت است، هنوز مشخص نیست که آیا یک الگوریتم خدای کاربردی برای آن وجود دارد یا خیر، اگرچه بعید به نظر می‌رسد.

 برج‌های هانوی 
برای پازل برج‌های هانوی، برای هر تعداد دیسک داده شده، یک الگوریتم خدا وجود دارد، هرچند تعداد حرکات با افزایش تعداد دیسک‌ها به صورت نمایی زیاد می‌شود.

 مکعب روبیک 
در سال ۱۹۹۷، ریچارد کُرف الگوریتمی برای پیدا کردن راه‌حل‌های بهینه برای حل پازل مکعب روبیک ارائه کرد.Richard E. Korf, "Finding optimal solutions to Rubik's Cube using pattern databases", Proc. Natl. Conf. on Artificial Intelligence (AAAI-97), Providence, Rhode Island, Jul 1997, pp. 700–705. اگرچه در سال ۱۹۸۰، دیوید سینگ‌مستر حدس زده بود که کران بالای تعداد حرکات لازم برای حل مکعب روبیک ۲۰ است، ولی در سال ۱۹۹۵، کشف شد که کران پایین برای تعداد حرکات لازم برای حل یک مکعب روبیک ۲۰ است و در سال ۲۰۱۰ محاسباتی که توسط کامپیوترهای بزرگ انجام شد، ثابت کرد که برای حل هیچ وضعیتی به بیش از ۲۰ حرکت نیاز نیست. بنابراین، عدد خدا برای مکعب روبیک، ۲۰ است.

 عدد خدا 
برای مکعب روبیک، عدد خدا، بیشینه تعداد حرکات لازم برای حل هر یک از ۴۳٬۲۵۲٬۰۰۳٬۲۷۴٬۴۸۹٬۸۵۶٬۰۰۰ ترکیب‌های روبیک است و ثابت شده‌است که این عدد، برابر ۲۰ است. این عدد ممکن است کوچک بنظر برسد، اما به صورت تئوریک، این عدد باید حتی کمتر باشد. تنها حدود ۴۹۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰ ترکیب نیاز به تمام ۲۰ حرکت برای حل شدن دارد. هرچند که ۴۹۰ میلیون هم عدد بزرگی است، اما نسبت آن به ۴۳ کوینتیلیون وضعیت ممکن، تنها حدود ۰٫۰۰۰۰۰۱۱۳۲۸۹۵۵٪ است. یعنی احتمال اینکه بتوان به صورت تصادفی، وضعیتی تولید کرد که فقط و فقط در ۲۰ حرکت حل شود، نه بیشتر و نه کمتر، حدود ۱ در بیلیون است. اگرچه، تعداد ترکیب‌هایی که در ۱۹ حرکت حل می‌شوند، تقریباً ۱٫۵ کوینتیلیون است. به عبارتی، عدد خدا برای روبیک بیشتر به ۱۹ نزدیک است تا ۲۰، ولی اگر غیرممکن باشد حتی یک ترکیب را با کمتر از ۲۰ حرکت حل کرد، عدد خدا ۲۰ خواهد بود.

جدول زیر، تعداد وضعیت‌ها را برای فاصله‌های مختلف نشان می‌دهد:
فاصلهتعداد وضعیت‌ها۰۱۱۱۸۲۲۴۳۳۳٬۲۴۰۴۴۳٬۲۳۹۵۵۷۴٬۹۰۸۶۷٬۶۱۸٬۴۳۸۷۱۰۰٬۸۰۳٬۰۳۶۸۱٬۳۳۲٬۳۴۳٬۲۸۸۹۱۷٬۵۹۶٬۴۷۹٬۷۹۵۱۰۲۳۲٬۲۴۸٬۰۶۳٬۳۱۶۱۱۳٬۰۶۳٬۲۸۸٬۸۰۹٬۰۱۲۱۲۴۰٬۳۷۴٬۴۲۵٬۶۵۶٬۲۴۸۱۳۵۳۱٬۶۵۳٬۴۱۸٬۲۸۴٬۶۲۸۱۴۶٬۹۸۹٬۳۲۰٬۵۷۸٬۸۲۵٬۳۵۸۱۵۹۱٬۳۶۵٬۱۴۶٬۱۸۷٬۱۲۴٬۳۱۳۱۶حدود ۱٬۱۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰۱۷حدود ۱۲٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰۱۸حدود ۲۹٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰۱۹حدود ۱٬۵۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰۲۰حدود ۴۹۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰
جایگزین=|بندانگشتی|262x262پیکسل|نحوه پراکندگی تعداد وضعیت‌های تصادفی بر حسب تعداد حرکات مورد نیاز برای حل بهینه هربرت کوکیمبا
.

در سال ۲۰۰۹، هربرت کوکیمبا (Herbert Kociemba) از برنامه Cube Explorer و یک کامپیوتر با پردازنده Intel Core i7-920 (که اولین پردازنده Core i7 بود) و ۶ گیگابایت حافظه رم استفاده کرد تا ۱۰۰٬۰۰۰ وضعیت تصادفی را به صورت بهینه حل کند. به‌طور میانگین، برنامه هر روز ۷٬۰۰۰ مکعب را حل می‌کرد. در نهایت، میانگین طول حل بهینهٔ این مکعب‌ها، ۱۷٫۷ حرکت بود.
جایگزین=|بندانگشتی|262x262پیکسل|نحوه پراکندگی تعداد وضعیت‌های تصادفی بر حسب تعداد حرکات مورد نیاز برای حل بهینه توماس روکیکی
.

در ژانویه ۲۰۱۰ نیز توماس روکیکی (Tomas Rokicki) حتی ۱٬۰۰۰٬۰۰۰ مکعب را به صورت بهینه حل کرد.

همان‌طور که در نمودارها مشخص است، توزیع‌های به دست آمده توسط توماس روکیکی نیز مشابه هربرت کوکیمبا است.

 تاریخچه عدد خدا 
تحقیقات روی عدد خدا در سال ۱۹۸۱ آغاز شد، هنگامی که مارون تیستلثویت، با استفاده از الگوریتم پیچیده‌ای که خودش ابداع کرده بود، ثابت کرد که برای حل هر ۴۳ کوینتیلیون ترکیب مختلف مکعب روبیک، ۵۲ حرکت کافی است. به مرور زمان، متدهای بهینه‌تر برای حل این تعداد عظیم از ترکیب‌های محتمل در حرکات کمتر ابداع شد.

جدول زیر، تغییرات کران بالا و پایین عدد خدا برای مکعب روبیک را در گذر زمان نشان می‌دهد:
تاریخکران پایینکران بالااختلافیادداشت‌ها و پیوندهاژوئیه ۱۹۸۱۱۸۵۲۳۴مارون تیستلثویت (Morwen Thistlethwaite) ثابت کرد ۵۲ حرکت کافی است.دسامبر ۱۹۹۰۱۸۴۲۲۴هانس کلوسترمان (Hans Kloosterman) تعداد حرکات را به ۴۲ بهبود داد.می ۱۹۹۲۱۸۳۹۲۱مایکل رید (Michael Reid) نشان داد ۳۹ حرکت همواره کافی است.می ۱۹۹۲۱۸۳۷۱۹دیک وینتر (Dik Winter) آن را به ۳۷ حرکت کاهش داد، آن هم تنها یک روز بعد!ژانویه ۱۹۹۵۱۸۲۹۱۱مایکل رید با آنالیز الگوریتم دو فازه‌یِ کوکیمبا، کران بالا را به ۲۹ حرکت کاهش داد.ژانویه ۱۹۹۵۲۰۲۹۹مایکل رید ثابت کرد وضعیت "superflip" (گوشه‌ها درست و لبه‌ها در جای خودشان برعکس)، به ۲۰ حرکت نیاز دارد.دسامبر ۲۰۰۵۲۰۲۸۸سیلویو رادو (Silviu Radu) ثابت کرد ۲۸ حرکت همواره کافی است.آوریل ۲۰۰۶۲۰۲۷۷سیلویو رادو، کران بالایش را به ۲۷ حرکت کاهش داد.می ۲۰۰۷۲۰۲۶۶دَن کانکِل (Dan Kunkle) و جین کوپرمن (Gene Cooperman) ثابت کردند ۲۶ حرکت کافی است.مارس ۲۰۰۸۲۰۲۵۵توماس روکیکی کران بالا را به ۲۵ بهبود داد.آوریل ۲۰۰۸۲۰۲۳۳توماس روکیکی و جان ولبورن (John Welborn) آن را به تنها ۲۳ حرکت کاهش دادند.اوت ۲۰۰۸۲۰۲۲۲توماس روکیکی و جان ولبورن در ادامه آن را به ۲۲ حرکت رساندند.ژوئیه ۲۰۱۰۲۰۲۰۰توماس روکیکی، هربرت کوکیمبا، مورلی دیویدسون (Morley Davidson) و جان دثریج (John Dethridge) ثابت کردند عدد خدا برای مکعب روبیک، دقیقاً ۲۰ است.
در اوت ۲۰۱۴ نیز توماس روکیکی و مورلی دیویدسون، ثابت کردند عدد خدا برای حرکت‌های ربع چرخشی، ۲۶ است (حرکت ربع چرخشی، یعنی یکی از وجه‌های مکعب روبیک را ۹۰ درجه بچرخانیم، ۱۸۰ درجه چرخش خود شامل دو حرکت ربع چرخشی است و ۲۷۰ درجه چرخش نیز همان ۹۰ درجه چرخش از سوی دیگر است.).

 جستارهای وابسته 
 ماشین اوراکل

 منابع 

رده:الگوریتم‌های جستجو
رده:بازی‌های ریاضی
رده:بازی‌های فکری
رده:مکعب روبیک