شطرنج حرفه ای

تاریخ ثبت مقاله: 1390/02/25

 

اگر تا بحال شطرنج بازی کرده باشید احتمالا اولین روزهایی که بازی شطرنج رو یاد گرفتید به خاطر میاورید . اگر هم به خاطر نمی آورید حتما تابحال نحوه یادگیری بازی شطرنج یک نفر را دیده اید . برای یادگیری ابتدا نام مهره ها ، بعد نحوه حرکت و نحوه حمله مهره ها و در آخربعد از اینکه کاملا با مهره ها آشنا شدید شروع به بازی می کنید . ابتدا مهره سفید شروع به بازی می کند و بعد هم مهره سیاه اما نهایتا به راحتی می باختید و بعد از هر باخت یا بعد از هر از دست دادن مهره با جملاتی از قبیل "وای ! اصلا حواسم نبود " یا " عجب ! چه جالب " و جملاتی از این قبیل هیجان خودتون رو از این بازی نشون می دادید. مغز انسان به گونه ای طراحی شده که با تمرین و ادامه کار مخصوصا در بازی شطرنج به مهارت ویژه ای می رسد . یعنی شما اگر یک هفته است که شطرنج بازی می کنید . بازی شما با روز اول قابل مقایسه نیست . چون مدام تکنیک های جدیدی با هر بازی یاد گرفته اید . شاید هم انقدر مشتاق شده اید که شروع به خواندن کتابهای شطرنج باز های حرفه ای کرده اید و تکنیک های حرفه ای تری یاد گرفته اید . از جملات بالا نتیجه می گیریم که بازی شطرنج برای انسان به میزان زیادی از تفکر و تجزیه و تحلیل آن هم در سطح بالا نیاز دارد . اما نکته جالب اینجاست که کامپیوتر برای بازی شطرنج هیچ یک از اعمال فوق را انجام نمی دهد . شاید بعضی به اشتباه فکر کنند که کسی که بازی شطرنج کامپیوتری را نوشته است خود یک شطرنج باز حرفه ایست . اما باید بدانید که بهیچ وجه اینگونه نیست . ظاهرا بازی شطرنج از آن دسته بازی هایی است که بسیار زیاد نیاز به تفکر و تجزیه و تحلیل و در نهایت تصمیم دارد و ظاهرا منحصر به بشر است . این درحالیستکه کامپیوتر بدون قدرت فکر کردن و تجزیه و تحلیل به قدری در بازی شطرنج مهارت دارد که بزرگترین شطرنج باز های دنیا هم از بردن آن عاجز هستند . دراین مقاله متوجه می شویم که کامپیوترها بهیچ وجه مشابه بشر شطرنج بازی نمی کنند . یعنی برای بازی شطرنج اصلا فکر نمی کنند . بلکه با کمک توابع و فرمول های ریاضی شروع به انجام یک سری محاسبات می کنند و در نتیجه مهره مورد نظر را حرکت می دهند . حال هر چه سرعت کامپیوتر در انجام این گونه محاسبات بیشتر باشد قدرت کامپیوتر برای بازی کردن نیز بیشتر می شود . در این مقاله اشاره ای جهت آشنایی با یکی از الگوریتم های معروف و پرکاربرد بازی شطرنج می کنیم تا متوجه شوید که چه فرآیندی در پیروزی کامپیوتردرمقابل بشر موثر است . برای شروع به یک تخته بازی با ابعاد 8*8 نیاز داریم . هر یک از طرفین 16 مهره در اختیار دارند . فرض را بر این بگیریم که مهره های سفید برای کامپیوتر و مهره های سیاه برای ما باشد . همانطور که می دانید شروع بازی با مهره سفید است ، بنابراین کامپیوتر اقدام به حرکت مهره سفید می کند . اما اینکه کدام مهره را حرکت دهد جای بحث دارد . می دانیم که مهره سفید یا سیاه برای شروع بازی هر کدام می توانند 20 حرکت انجام دهند : • 8 حرکت برای سربازها اگر یک خانه به جلو بروند ، 8 حرکت دیگر اگر همان سربازها دو خانه به جلو بروند . • دو حرکت برای هر یک از اسب ها (دو اسب) که در جمع 4 حرکت می شود . بنابراین هر مهره سفید یا سیاه برای شروع می تواند یکی از 20 حرکت ممکن را انتخاب کند . حال فرض کنیم کامپیوتر بدون توجه به ارزش حرکات ؛ یکی از این 20 حرکت را انتخاب می کند و بازی را شروع می کند . بعد از این حرکت نوبت به مهره مشکی می رسد ، مهره مشکی هم می تواند یکی از 20 حرکت مورد نظر خود را انجام دهد . دوباره نوبت به کامپیوتر می رسد تا مهره دوم خود را حرکت دهد . اما اینبار بسته به اینکه کدام یک از مهره ها را در حرکت قبل حرکت داده است می تواند به تعداد 20 حرکت یا کمتر یا بیشتر را انتخاب نماید . و دوباره مهره مشکی هم بسته به حرکت قبلی خودش می تواند مهره ها را تکان دهد . نکته کار اینجاست که کامپیوتر از کجا بداند کدام یک از این 20 حرکت یا کمتر یا بیشتر را انجام دهد . کامپیوتر برای حل این مساله با درست کردن درختی در حافظه خود تمامی حرکات ممکن را انجام می دهد تا بهترین نتیجه را بدست بیاورد . فرض می کنیم به این ترتیب باشد که برای حرکت اول برای هر کدام از 20 حرکت یک بار بازی را تمام می کند باین ترتیب که بعد از حرکت دادن مهره در حافظه خود فرض را بر این می گیرد که طرف مقابل کدام مهره را حرکت خواهد داد و اگر حرکت داد خودش کدام مهره را حرکت بدهد تا در نهایت بازی را ببرد . یعنی اگر در مرحله اول امکان 20 انتخاب را دارد مهره مشکی می تواند بسته به حرکت مهره سفید 20*20 حرکت انجام دهد . بنابراین در حرکت دوم خود می تواند 400*20 حرکت را انتخاب کند و دوباره مشکی 8000*20 انتخاب و به همین ترتیب این تعداد حرکات ممکن پیش بینی می شود تا بازی تمام شود . عدد حاصل عدد یک بهمراه 120 عدد صفر در جلوی آن خواهد بود . این عدد 10120 در مقابل عددی مانند تعداد کل اتم های دنیا که معادل 1075 می باشد بسیار بزرگ است . بنابراین متوجه می شوید که بازی شطرنج تا چه حد می تواند پیچیده باشد . اما واقعیت اینستکه هیچ کامپیوتری نمی تواند کل درخت مورد نظر را ایجاد کند . و تمام 10120 حرکت ممکن را انجام دهد . بلکه کامپیوتر به جای تمام کردن کل بازی می تواند 3 یا 5 یا حتی 10 تا 20 حرکت بعدی را انجام دهد (‌پیش بینی کند) . اگر فرض را بر این بگیریم که برای هر حرکت مهره در بازی تنها 20 انتخاب داریم برای ایجاد یک درخت 5 مرحله ای که بتواند 5 حرکت جلوتر را پیش بینی کند 320000 حرکت ممکن باید بررسی شود . همچنین اگر بتوان یک درخت 10 مرحله ای ایجاد کرد بنابراین می توان 10000000000000 ( 10 تریلیون) حرکت ممکن را بررسی کرد . بنابراین در اینجاست که سرعت کامپیوتر برای بازی شطرنج مشخص می شود . هرقدر سرعت کامپیوتر برای بازی بیشتر باشد حرکات اینده بهتری در نتیجه با قدرت بیشتری پیش بینی می شود . اما واقعیت اینجاست که پرسرعتترین کامپیوتر شطرنج باز دنیا تنها می تواند تا چند میلیون حرکت را در هر ثانیه پیش بینی کند . اما کار به همین جا تمام نمی شود پس از تولید درخت کامپیوتر باید به ارزیابی موقعیت های درست شده بپردازد و اینکه تشخیص دهد که کدام حرکت را انجام دهد تا بهترین حرکت ممکن باشد . اولین گام برای ارزیابی تعداد مهره هایی ست که کامپیوتر در صفحه شطرنج خواهد داشت . برای انجام این کار به کمک یک تابع ارزیابی می تواند تعداد مهره هایی که هر یک از طرفین بعد از حرکت مهره خواهند داشت را محاسبه کند . به کمک تابع ارزیابی می تواند تشخیص دهد که حرکتی که انجام دهد "خوب" است یا "بد" . اگر خوب است مهره را حرکت می دهد و اگر بد حرکت دیگری را انتخاب می کند . مثلا اگر کامپیوتر در انتهای حرکت 11 مهره خواهد داشت و حریف 9 مهره در نهایت دو مهره( 2=9-11 ) بیشترخواهد داشت که این نتیجه "خوب" دارد . البته تابع فوق برای بازی شطرنج بسیار ساده است و تنها ملاک برای بازی تعداد مهره ها نیست . همانطور که همه می دانیم هر کدام از مهره ها برای خود ارزشی دارند . موقعیت و محل مهره ها نیز قابل توجه است . اینکه آیا شاه ما در خطر کیش هست یا خیر . وزیر ما در خطر از دست رفتن می باشد یا خیر و موارد دیگر . اینجا وظیفه برنامه نویس است که فرضا با ارزش گذاری روی مهره ها با اعداد بتواند ارزش مهره ها را مشخص کند مثلا قلعه معادل 5 سرباز است . فارغ از اینکه تابع ما چه پیچیدگی های دیگری می تواند داشته باشد . مهم اینستکه تابع ما در نهایت چه عددی بر می گرداند . که این تابع نشانگر میزان خوب یا بد بودن حرکتی است که قرار است انجام شود . برای تشریح بیشتر مساله سعی می کنیم یک درخت سه مرحله ای که قابلیت درست کردن سه حرکت آینده را دارد را بکشیم و مساله را روی آن دنبال کنیم . فرض را براین می گیریم که در هر حالت هر یک از مهره ها می توانند تنها سه حرکت انجام دهند . کامپیوتر مهره سفید است و می تواند یکی از سه حرکت ممکن را انجام دهد . اگر هر یک از سه حرکت ممکن را انجام دهد مهره گردان مشکی هم میتواند سه حرکت انجام دهد ( در عمل تعداد حرکات بیشتر است که بدلیل بزرگ شدن درخت از کشیدن تمامی حالات صرف نظر می کنیم ) . بعد از حرکت مهره های سیاه مهره های سفید هم میتوانند دو حرکت انجام دهند . (پایین ترین مرحله درخت ) . parsx اما برای تحلیل درخت کامپیوتر از پایین ترین گره ( برگ) شروع به محاسبه می کند از سمت چپ پایین عدد بین دو برگی که ارزش 8 و 2 دارند عدد 8 انتخاب می شود این بآن دلیل است که از آنجایی که مهره سیاه حریف است باید پرارزشترین حرکت را انتخاب کرد ( مهره سیاه = ماکسیمم) از بین برگ های 4 و 8 هم 8 را انتخاب می کند و بهمین ترتیب تا درخت به شکل زیر در می آید : حال که به انتخاب حرکت مشکی رسیدیم باید مقادیر مینیمم را در مرحله دوم یعنی عمق 3 ( مهره های مشکی ) انتخاب کنیم یعنی بصورت قراردادی حرکات مهره های سفید که خودش می باشد باید کمترین ارزش را داشته باشند بنابراین از سمت چپ بین سه عدد 887 عدد 7 برای مهره سفید سمت راستی قرار می گیرد و برای بعدی عدد 5 و بعدی عدد 4 بنابراین شکل درخت به شکل زیر در می آید : همانطور که از شکل پیداست نوبت به انتخاب برای حرکات سفید است بنابراین باید دوباره ماکسیموم مقادیر را انتخاب کنیم . اکنون کامپیوتر آماده انتخاب مقدار ماکسیموم از بین سه عدد 754 می باشد بنابراین کامپیوتر حرکتی که ارزش 7 دارد را انتخاب می کند ( ماکسیموم) . parsx الگوریتم حل این مساله به الگوریتم minimax مشهور است که در این مساله ما مهره های سفید را ماکسیموم و مهره های سیاه را مینیموم نامیدیم و به صورت یک در میان از بین اعداد به ترتیب اعداد ماکسیموم و مینیموم را انتخاب می کنیم . بعد از آنکه کامپیوتر حرکت به ارزش 7 را انجام داد . منتظر می ماند تا مهره سیاه نیز حرکت خود را انجام دهد . پس از آن دوباره درختی به شکل فوق درست می کند و به ادامه بازی می پردازد . البته این الگوریتم با روشهایی چون هرس آلفا بتا قابلیت های بالاتری از لحاظ سرعت و حجم حافظه مصرفی پیدا می کند که از تشریح جزئیات بیشتر خودداری می کنیم . بنابراین به این نتیجه رسیدیم که کامپیوتر برای بازی شطرنج بهیچ وجه راجع به برد یا باخت فکرنمی کند بلکه با انجام عملیات محاسباتی از طریق تابعی که تشریح کردیم به حل مساله می پردازد . تا اینکه صفحه شطرنج را به نفع خودش در حالت "خوب" یا "بد" برساند . در این بین الگوریتم های دیگری نیز برای حل مساله صفحات شطرنج وجود دارند که علاقمندان می توانند برای اطلاعات بیشتر به جستجو در این زمینه بپردازند . نویسنده:محمد نباتی منبع:www.parsx.com

نظرات

نام

ایمیل   (نمایش داده نخواهد شد)

نظر

مجید کبیری در تاریخ ۲۷/۲/۱۳۹۰ مقاله خیلی خوبی است.اگردرخت حافظه را ترسیم میکرد کاملتر میشد.