ParsX.com

vahid

how a computer play chess
كامپيوتر چگونه شطرنج بازي مي كند ؟
اگر تا بحال شطرنج بازي كرده باشيد احتمالا اولين روزهايي كه بازي شطرنج رو ياد گرفتيد به خاطر مياوريد . اگر هم به خاطر نمي آوريد حتما تابحال نحوه يادگيري بازي شطرنج يك نفر را ديده ايد .
براي يادگيري ابتدا نام مهره ها ، بعد نحوه حركت و نحوه حمله مهره ها و در آخربعد از اينكه كاملا با مهره ها آشنا شديد شروع به بازي مي كنيد . ابتدا مهره سفيد شروع به بازي مي كند و بعد هم مهره سياه اما نهايتا به راحتي مي باختيد و بعد از هر باخت يا بعد از هر از دست دادن مهره با جملاتي از قبيل "واي ! اصلا حواسم نبود " يا " عجب ! چه جالب " و جملاتي از اين قبيل هيجان خودتون رو از اين بازي نشون مي داديد.
مغز انسان به گونه اي طراحي شده كه با تمرين و ادامه كار مخصوصا در بازي شطرنج به مهارت ويژه اي مي رسد . يعني شما اگر يك هفته است كه شطرنج بازي مي كنيد . بازي شما با روز اول قابل مقايسه نيست . چون مدام تكنيك هاي جديدي با هر بازي ياد گرفته ايد . شايد هم انقدر مشتاق شده ايد كه شروع به خواندن كتابهاي شطرنج باز هاي حرفه اي كرده ايد و تكنيك هاي حرفه اي تري ياد گرفته ايد .
از جملات بالا نتيجه مي گيريم كه بازي شطرنج براي انسان به ميزان زيادي از تفكر و تجزيه و تحليل آن هم در سطح بالا نياز دارد . اما نكته جالب اينجاست كه كامپيوتر براي بازي شطرنج هيچ يك از اعمال فوق را انجام نمي دهد . شايد بعضي به اشتباه فكر كنند كه كسي كه بازي شطرنج كامپيوتري را نوشته است خود يك شطرنج باز حرفه ايست . اما بايد بدانيد كه بهيچ وجه اينگونه نيست .
ظاهرا بازي شطرنج از آن دسته بازي هايي است كه بسيار زياد نياز به تفكر و تجزيه و تحليل و در نهايت تصميم دارد و ظاهرا منحصر به بشر است . اين درحاليستكه كامپيوتر بدون قدرت فكر كردن و تجزيه و تحليل به قدري در بازي شطرنج مهارت دارد كه بزرگترين شطرنج باز هاي دنيا هم از بردن آن عاجز هستند .
دراين مقاله متوجه مي شويم كه كامپيوترها بهيچ وجه مشابه بشر شطرنج بازي نمي كنند . يعني براي بازي شطرنج اصلا فكر نمي كنند . بلكه با كمك توابع و فرمول هاي رياضي شروع به انجام يك سري محاسبات مي كنند و در نتيجه مهره مورد نظر را حركت مي دهند . حال هر چه سرعت كامپيوتر در انجام اين گونه محاسبات بيشتر باشد قدرت كامپيوتر براي بازي كردن نيز بيشتر مي شود . در اين مقاله اشاره اي جهت آشنايي با يكي از الگوريتم هاي معروف و پركاربرد بازي شطرنج مي كنيم تا متوجه شويد كه چه فرآيندي در پيروزي كامپيوتردرمقابل بشر موثر است .
براي شروع به يك تخته بازي با ابعاد 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 را انجام داد . منتظر مي ماند تا مهره سياه نيز حركت خود را انجام دهد . پس از آن دوباره درختي به شكل فوق درست مي كند و به ادامه بازي مي پردازد . البته اين الگوريتم با روشهايي چون هرس آلفا بتا قابليت هاي بالاتري از لحاظ سرعت و حجم حافظه مصرفي پيدا مي كند كه از تشريح جزئيات بيشتر خودداري مي كنيم .
بنابراين به اين نتيجه رسيديم كه كامپيوتر براي بازي شطرنج بهيچ وجه راجع به برد يا باخت فكرنمي كند بلكه با انجام عمليات محاسباتي از طريق تابعي كه تشريح كرديم به حل مساله مي پردازد . تا اينكه صفحه شطرنج را به نفع خودش در حالت "خوب" يا "بد" برساند . در اين بين الگوريتم هاي ديگري نيز براي حل مساله صفحات شطرنج وجود دارند كه علاقمندان مي توانند براي اطلاعات بيشتر به جستجو در اين زمينه بپردازند .
وحيد آقامحمدي .