الگوریتم شطرنج در رایانه ها چگونه کار میکند! - 1

الگوریتم شطرنج

الگوریتم شطرنج و آموزش انسانی:

اگر تا به حال شخصی را مشاهده کرده اید که برای اولین بار مشغول یادگیری شطرنج است، می دانید که یک انسان شطرنج را با توانایی های بسیار محدود شروع می کند. هنگامی که یک بازیکن الگوریتم شطرنج و قوانین اساسی رفتار هر مهره را درک کرد، می تواند شطرنج بازی کند. با این حال بازیکن جدید خیلی خوب بازی نمی کند. هر شکست زودرس برای این بازیکن جای تعجب ندارد عبارت هایی مانند “اوه، من به این فکر نکردم!” یا “ای کاش من این مهره را حرکت نمی دادم!” جزوی از فرآیند بهبود الگوریتم شطرنج این بازیکن آماتور است.

ذهن انسان این تجربیات را به خود جذب می کند، کنش ها و واکنش های مختلفی را که در صفحه شطرنج رخ می دهد، ذخیره می کند، ترفند ها و نیرنگ های خاصی را کشف می کند و به طور کلی هر بار یک حرکت متفاوت ظریف در بازی را مشاهده می کند، برای دفعات بعد به این خواهد اندیشید که چگونه از آن بهره ببرد. این فرآیند نیز قسمتی عمده از الگوریتم شطرنج مورد استفاده یک انسان است. با پیشرفت سطح مهارت، بازیکن اغلب کتاب هایی را می خواند تا الگوریتم شطرنج در بازی های بهترین بازیکنان را کشف کند. اینگونه استراتژی ها و تاکتیک ها برای هدایت بازیکن در هر بازی توسعه می یابد.

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

الگوریتم شطرنج در رایانه ها:

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

در این مقاله، به این سوال نگاهی گذرا خواهیم انداخت. آنچه درخواهید یافت این است که رایانه ها در واقع به مانند مردم شطرنج بازی نمی کنند. رایانه ای که شطرنج بازی می کند دارای یک خط فکر و استراتژی نیست. در عوض، یک سری محاسبه ها را از طریق مجموعه ای از فرمول ها بدست خواهد آورد که باعث می شود حرکت های خوبی در بازی داشته باشد. همانطور که رایانه ها سریعتر و قدرتمند تر می شوند، کیفیت این حرکت های محاسبه شده نیز بهتر و بهتر می شود. الگوریتم شطرنج در رایانه ها در حال حاضر همانند بهترین بازیکن های شطرنج روی کره زمین هستند، حتی اگر این فرآیند را کاملا کورکورانه انجام دهند.

الگوریتم شطرنج

پیشرفته ترین وضعیت های بازی در الگوریتم شطرنج رایانه بسیار پیچیده است، اما همه این محاسبات کورکورانه است و در بطن ماجرا بسیار ساده است. بیایید بگوییم شما با یک صفحه شطرنج که برای شروع یک بازی چیده شده است رو به رو هستید. هر بازیکن 16 مهره دارد. قطعا می دانید که مهره های سفید شروع کننده بازی هستند. سفید 20 حرکت احتمالی دارد:

الگوریتم شطرنج - 1
  1. مهره های پیاده یا سرباز که 8 عدد می باشند هرکدام می توانند در دو وضعیت قرار بگیرند. برای مجموع این مهره ها 16 حالت احتمالی پدید خواهد آمد.
  2. مهره های اسب یا Knight نیز که دو عدد هستند هرکدام دو وضعیت را برای شروع پیش رو دارند که در مجموع 4 وضعیت احتمالی را ایجاد خواهند کرد.

پیشرفته ترین وضعیت های بازی در الگوریتم شطرنج رایانه بسیار پیچیده است، اما همه این محاسبات کورکورانه است و در بطن ماجرا بسیار ساده است. بیایید بگوییم شما با یک صفحه شطرنج برای شروع یک بازی چیده شده است رو به رو هستید. هر بازیکن 16 مهره دارد. قطعا می دانید که مهره های سفید شروع کننده بازی هستند. سفید 20 حرکت احتمالی دارد، طبیعی است که مهره های سیاه نیز همین احتمالات را برای حرکات خود دارند:

  1. مهره های پیاده یا سرباز که 8 عدد می باشند هرکدام می توانند در دو وضعیت قرار بگیرند. برای مجموع این مهره ها 16 حالت احتمالی پدید خواهد آمد.
  2. مهره های اسب یا Knight نیز که دو عدد هستند هرکدام دو وضعیت را برای شروع پیش رو دارند که در مجموع 4 وضعیت احتمالی را ایجاد خواهند کرد.
الگوریتم شطرنج

در الگوریتم شطرنج نگاه یک کامپیوتر به شطرنج اینگونه است. تمامی حرکات ممکن در هر قدم و قدم های بعدی را به صورت یک درخت باینری مرتب می کند. در این درخت، 20 حرکت احتمالی برای رنگ سفید وجود دارد. 20 حرکت نیز برای مهره های سیاه درنظر می گیریم.بنابراین طبق محاسبات احتمالی داریم: 20 * 20 = 400 

سپس برای قدم بعدی 400 * 20 = 8000 حالت وجود دارد. بعد از آن 8000 * 20 = 160،000 حالت با توجه به حرکت مهره سیاه رنگ پدید خواهد آمد. اگر بخواهید تمام درخت را برای تمام حرکات احتمالی در الگوریتم شطرنج به طور کامل توسعه دهید، تعداد کل موقعیت های پیش آمده در یک بازی حدود 10 به توان 120 حالت خواهد بود. قطعا پردازش این تعداد حالت برای هر بازیکنی غیرممکن است ولی داستان برای الگوریتم شطرنج یک کامپیوتر متفاوت خواهد بود.

10pow120

ناگفته پیداست که این رقم بسیار بزرگ است. به عنوان مثال، از زمان BigBang تنها 1026 ضرب در 10 به توان 9 ثانیه گذشته است. تصور می شود که فقط 10 به توان 75 اتم در کل جهان وجود داشته باشد. وقتی فکر می کنید کهکشان راه شیری دارای میلیارد ها ستاره نظیر خورشید است و میلیاردها کهکشان وجود دارد، می توانید ببینید که این تعداد زیادی اتم در خود دارد. این تعداد با تعداد حرکات احتمالی در بازی شطرنج اصلا قابل قیاس نیست. بنابراین برای ما یقین شده است که شطرنج یک بازی کاملاً پیچیده است. بنابراین یک الگوریتم شطرنج نیز کاری پیچیده در پیش دارد.

پیشتر گفتیم که هیچ بازیکنی نمی تواند کل درخت را تحلیل کند. اما اکنون لازم به ذکر است که حتی هیچ رایانه ای قرار نیست کل درخت را محاسبه کند. کاری که یک الگوریتم شطرنج سعی می کند که انجام دهد ایجاد درخت برای یک یا 10 یا 20 حرکت آینده است.

با فرض اینکه حدود 20 حرکت ممکن برای هر موقعیت در صفحه وجود داشته باشد، یک درخت با پنج سطح شامل 3،200،000 موقعیت است. یک درخت با 10 سطح در حدود 10،000،000،000،000 (10 تریلیون) موقعیت دارد. عمق درختی که کامپیوتر می تواند محاسبه کند توسط سرعت پردازنده کامپیوتر در حال انجام بازی کنترل می شود. سریعترین رایانه های شطرنجباز می توانند میلیون ها موقعیت در بازی را در هر ثانیه محاسبه و ارزیابی کنند.

به محض تولید یک درخت توسط یک الگوریتم شطرنج، رایانه باید موقعیت هر مهره را ارزیابی کند. یعنی کامپیوتر باید به مهره های روی صفحه نگاه کند و تصمیم بگیرد که آیا ترتیب مهره ها “خوب” است یا “بد”. روش انجام این کار با استفاده از یک تابع ارزیابی است. ساده ترین عملکرد ممکن فقط تعداد مهره های موجود در هر طرف است. اگر رایانه با مهره های سفید بازی می کند و موقعیت خاصی از صفحه دارای 11 مهره سفید و نه مهره سیاه است، ساده ترین عملکرد ارزیابی ممکن است اینچنین باشد:

2=11-9

بدیهی است که برای الگوریتم شطرنج، این فرمول خیلی ساده است، زیرا بعضی از مهره ها از بعضی دیگر ارزش بیشتری دارند. بنابراین فرمول ممکن است وزنی را برای هر نوع مهره اعمال کند. همانطور که برنامه نویس در مورد آن فکر می کند، او عملکرد ارزیابی را با اضافه کردن مواردی مانند موقعیت صفحه، کنترل جریان بازی، آسیب پذیری پادشاه ، آسیب پذیری وزیر حریف و تعداد زیادی پارامتر دیگر، پیچیده می کند. هر چقدر تابع پیچیده شود به یک عدد متراکم تبدیل می شود که نشان دهنده “خوبی” آن موقعیت در صفحه و دقت الگوریتم است.

الگوریتم شطرنج برای درخت هایی با سه سطح:

نمودار زیر درخت های مختلفی برای سه سطح را نشان می دهد که سه حرکت در این درخت ها به جلو به نظر می رسد و ارزش موقعیت های نهایی چیدمان صفحه را ارزیابی کرده است، درخت بهینه در این الگوریتم از نوع Perfect است:

درخت سه مرحله ای

رایانه با مهره سفید بازی می کند. بعد از آن مهره سیاه حرکت کرده و موقعیت چیدمان صفحه را در بالای درخت ترک کرده است. در این درخت، رنگ سفید می تواند سه حرکت احتمالی ایجاد کند. از هر یک از این سه حرکت ممکن، رنگ سیاه می تواند سه حرکت احتمالی دیگر ایجاد کند. از هر یک از آن نه موقعیت در صفحه، رنگ سفید می تواند دو حرکت احتمالی ایجاد کند. (در بازی واقعی، تعداد کل حرکات از هر موقعیتی حدود 20 حرکت است، اما ترسیم آن بسیار دشوار است.)

این رویکرد را الگوریتم minimax می نامند زیرا در هنگام حرکت به سمت بالا درخت، بین حداکثر ها و حداقل ها متناوب است. با استفاده از تکنیکی به نام هرس آلفا و بتا، الگوریتم می تواند حدود دو برابر سریعتر اجرا شود و به حافظه بسیار کمتری نیاز دارد. همانطور که می بینید، این فرایند کاملاً مکانیکی است و هیچ فکری نمی برد. این یک محاسبه است که به سادگی یک تابع ارزیابی را برای تمام موقعیت های ممکن در صفحه بازی برای یک درخت با یک عمق خاص اعمال می کند.

جالب اینجاست که این نوع تکنیک بسیار خوب عمل می کند. در یک رایانه با سرعت کافی، الگوریتم شطرنج می تواند به اندازه کافی قدم های بعدی را پیش بینی کند تا یک بازی بسیار خوب انجام دهد. اگر تکنیک های یادگیری را اضافه کنید، عملکرد ارزیابی را بر اساس بازی های گذشته اصلاح می کنند،این مبحثی است که تحت عنوان یادگیری ماشین در هوش مصنوعی بررسی می شود. با این الگوریتم دستگاه حتی می تواند با گذشت زمان پیشرفت کند. برای نمونه بازی گری کاسپاروف با رایانه ای با هوش مصنوعی را می توان مثال زد که نهایتا این رایانه با اصلاح حرکات خود این بازیکن افسانه ای را شکست داد. 

احمد ساروخانی
احمد ساروخانی

  • چنانچه دیدگاهی توهین آمیز باشد و متوجه اشخاص مدیر، نویسندگان و سایر کاربران باشد تایید نخواهد شد.
  • چنانچه دیدگاه شما جنبه ی تبلیغاتی داشته باشد تایید نخواهد شد.
  • چنانچه از لینک سایر وبسایت ها و یا وبسایت خود در دیدگاه استفاده کرده باشید تایید نخواهد شد.
  • چنانچه در دیدگاه خود از شماره تماس، ایمیل و آیدی تلگرام استفاده کرده باشید تایید نخواهد شد.
  • چنانچه دیدگاهی بی ارتباط با موضوع آموزش مطرح شود تایید نخواهد شد.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

مطالب مرتبط

لینک کوتاه نوشته
0

سبد خرید چسبان