تعداد بازی های ممکن در شطرنج را بشناسید

شطرنج

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

احتمالاً مساله قدیمی دانه گندم و صفحه شطرنج را شنیده‌اید: «پادشاه هند به فردی که شطرنج را اختراع کرد گفت هر پاداشی که می‌خواهد بگوید. آن فرد درخواست کرد تا یک صفحه شطرنج بیاورند و گفت به ازای خانه اول ۱ گندم، به ازای خانه دوم ۲ گندم، به ازای خانه سوم ۴ گندم و بدین ترتیب به ازای هر خانه دو برابر قبلی گندم به او پاداش داده شود. پادشاه که فکر می‌کرد درخواست او ناچیز است فرمان داد سریعاً پاداش او را تهیه کنند اما درواقع با محاسبه معلوم شد تهیه آن از عهده هیچ‌کسی برنمی‌آید.» میزان گندمی که پاشاه باید به او می‌داد برابر با (۱ -۲۶۴) است به عبارتی ۱۸٬۴۴۶٬۷۴۴٬۰۷۳٬۷۰۹٬۵۵۱٬۶۱۵ دانه گندم، این مقدار گندم تمام سطح هندوستان را تا ارتفاع ۱۵ متر می‌پوشاند یا اگر این میزان گندم پشت‌هم چیده شود می‌تواند فاصله زمین تا ستاره آلفا قنطورس را که برابر ۴ سال نوری است، دو بار برود و بازگردد.

شطرنج

فرض کنید جمعیت زمین برابر با ۷ میلیارد نفر باشد و هر فرد زمینی با یک فرد فضایی از جهان دیگر، شطرنج یک دقیقه‌ای بازی کند، در پایان هر روز ۱۰٬۰۸۰٬۰۰۰٬۰۰۰٬۰۰۰ بازی انجام خواهد شد، بعد از گذشت یک سال تعداد بازی‌ها به عدد ۳٬۶۷۹٬۲۰۰٬۰۰۰٬۰۰۰٬۰۰۰ می‌رسد و بعد از یک میلیارد سال تعداد بازی‌های انجام شده برابر خواهد بود با ۱۰۲۴×۳٫۶۷۹۲. عدد بزرگی به نظر می‌رسد اما حتی اگر ما زمان بازی را به یک ثانیه کاهش بدهیم الهه‌ی شطرنج به خاطر مقدار ناچیز تعداد بازی‌هایی که تحلیل کرده‌ایم به ما خواهد خندید. در واقع یک واقعیت جالب وجود دارد که تعداد بازی‌های شطرنج از اتم‌های جهان قابل مشاهده بیشتر است.

می‌توان تعداد بازی‌های ممکن در شطرنج را برابر با «عدد شانون» درنظر گرفت. در سال ۱۹۵۰ «کلود شانون» در مقاله‌ای با نام «برنامه ریزی یک کامپیوتر برای شطرنج بازی کردن»، تشریح کرد که یک ماشین چگونه می‌تواند یک بازی شطرنج قابل قبول از خود به نمایش بگذارد. دراین مقاله او عدد ۱۰۱۲۰ را به عنوان تخمینی برای تعداد بازی‌های شطرنج ارائه کرد که اگر این عدد را با تعداد اتم‌های جهان قابل مشاهده که تقریباً برابر با ۱۰۸۰ است مقایسه کنیم در واقع در مقابل هر اتم در هستی میلیاردها بازی شطرنج وجود دارد.

چگونه شانون به این عدد رسید؟ در واقع او با مشاهده بازی‌های شطرنج در نظر گرفت که درهر موقعیت به طور متوسط ۳۰ حرکت قانونی می‌توان انجام داد به این ترتیب برای حرکت اول ۹۰۰ حالت به تنهایی ایجاد می‌شود. در شطرنج منظور از حرکت، حرکت سیاه و سفید با هم می‌باشد در واقع هر حرکت شامل دو نیم حرکت (ply) است با فرض اینکه متوسط تعداد حرکات یک بازی شطرنج برابر ۴۰ است تعداد بازی‌ها برابر با ۳۰۸۰ است که این مقدار تقریباً برابر با ۱۰۱۲۰ می‌شود.

شطرنج

قطعاً این عدد دقیق نیست و فقط یک تقریب برای بازی‌های زیر ۴۰ حرکت است. شانون برای اینکه توضیح دهد اگر یک کامپیوتر بخواهد با اطمینان کامل بازی کند و فرض شود بتواند هر بازی را در زمان یک میکرو ثانیه محاسبه کند، برای اینکه حرکت اولش را انجام دهد به ۱۰۹۰ سال زمان نیاز دارد.

اگر بخواهیم محاسبات را دقیق‌تر انجام دهیم، مهره‌های سفید برای نوبت اول ۲۰ حرکت ممکن دارند (۱۶ حرکت پیاده و ۴ حرکت اسب)؛ به همین ترتیب مهره‌های سیاه نیز برای نوبت دوم ۲۰ حرکت دارند. بنابراین تنها برای حرکت اول ۴۰۰ حالت مختلف وجود دارد. در نوبت سوم مساله کمی پیچیده‌تر شده و تعداد حالت‌ها به ۸۹۰۲ می‌رسد. در نوبت چهارم این مقدار برابر با ۱۹۷۷۴۲۱ است. به عبارتی تنها با دو حرکت، حدود دویست هزار حالت مختلف ایجاد می‌شود و این روند افزایشی ادامه خواهد داشت. به‌منظور رسیدن به پاسخ سؤال اصلی، ابتدا باید به این پرسش پاسخ دهیم که آیا تعداد حرکت‌های یک بازی شطرنج بی‌نهایت است؟

طولانی‌ترین بازی رسمی شطرنج در سال ۱۹۸۹ در «بلگراد» اتفاق افتاد که بعد از انجام ۲۶۹ حرکت و سپری شدن زمان ۲۰ ساعت و ۱۵ دقیقه به تساوی انجامید. با در نظر گرفتن قانون ۵۰ حرکت و قانون تکرار سه گانه به‌طور تئوری طولانی‌ترین بازی شطرنج شامل ۵۹۴۹ حرکت یا ۱۱۸۹۸ نوبت بازی است با توجه به روند افزایشی می‌توانید تصور کنید تعداد بازی‌ها در حرکت ۵۹۴۹ چقدر خواهد بود؟ هاردی ریاضیدان معروف انگلیسی این مقدار را برابر با ۱۰ به توان ۱۰۵۰ تقریب زد. عدد شانون که تخمینی برای ۴۰ حرکت است در مقابل آن بسیار ناچیز است.

شطرنج

هرچند پرسش ما تعداد بازی‌های ممکن ازنظر تئوری است اما مشخص است اکثر این بازی‌ها نامعقول و بی‌معنی هستند و شامل حرکت‌های بی‌معنی و بیهوده خواهند بود که در واقعیت هرگز اتفاق نمی‌افتند. پس بیایید تقریبی کمی معقول‌تر بزنیم فرض کنید در هر نوبت تعداد متوسط حرکت‌های معقول برابر ۳ و تعداد حرکت‌های یک بازی به‌طور متوسط برابر ۴۰ باشد. پس مقدار بازی‌های شطرنج برابر با ۳۸۰ خواهد بود. این مقدار حدوداً برابر است با ۱۰۴۰ . اگرچه این تعداد بازی معقول از اتم‌های جهان قابل‌مشاهده بیشتر نیست اما بازهم بسیار بزرگ است. همه انسان‌های روی زمین برای اینکه همه بازی‌های ممکن را انجام بدهند به تریلیون‌ها تریلیون سال نیاز دارند. از نگاه دیگر تمام بازی‌های شطرنج انجام‌شده در طول تاریخ تاکنون درصد بسیار ناچیزی از آن را تشکیل می‌دهد.

همان‌طور که «شانون» در قسمتی از مقاله‌اش بیان می‌کند، فرض کنید دو ابَرذهن که همه وضعیت‌ها را می‌دانند و هرگز اشتباه نمی‌کنند روبروی هم بنشینند و باهم شطرنج‌بازی کنند. آنگاه بعدازاینکه به‌صورت تصادفی رنگ خود را انتخاب کردند مدتی به مهره‌ها نگاه خواهند کرد و پس ازآن سه حالت ممکن است اتفاق افتد: ۱-نفر اول اعلام باخت کند؛ ۲- نفر دوم اعلام باخت کند؛ ۳- نفر اول پیشنهاد مساوی بدهد و نفر دوم قبول کند.

«آلن تورینگ» در سال ۱۹۵۰ اولین برنامه کامپیوتری شطرنج را نوشت و در سال ۱۹۹۷ «دیپ به لو» با توان پردازش دویست میلیون وضعیت در ثانیه، توانست «کاسپاروف» را شکست دهد و اولین پیروزی کامپیوتر بر یک قهرمان شطرنج را جشن بگیرد. از آن زمان مدت زیادی نمی‌گذرد. اکنون شطرنج برای سه الی هفت مهره و بعضی از وضعیت‌های هشت مهره‌ای (با در نظر گرفتن دو شاه به عنوان مهره) حل شده است. آیا زمانی خواهد رسید که توان محاسباتی به حدی برسد که شطرنج یک بازی حل شده محسوب شود؟ نظر شما در این مورد چیست؟

Zoomit

نظرات

اولین دیدگاه این مطلب را ثبت کنید

آگاه‌سازی از
680

wpDiscuz