تبلیغات
وبلاگ هوش مصنوعی موسسه آموزش عالی خیام مشهد - روش بازی شطرنج در کامپیوتر - 3

تولید حركت‌
<تولید حركت> قسمت دیگری از وظیفه نرم‌افزار است و منظور از آن این است كه هنگامی كه نوبت بازی به كامپیوتر می‌رسد، قبل از این كه تصمیم بگیرد چه كار كند، باید بداند حركت‌های مجاز او كدامند. در وهله نخست ممكن است به نظر برسد این كار آسان است، ولی به یاد بیاورید كه هر مهره شطرنج قوانین حركتی خاصی دارد. مثلاً شاهی كه در حالت كیش است، قابل حركت دادن نیست.

همچنین فیل به صورت قطری حركت می‌كند. اسب به صورت حرف ‌L مانور می‌دهد. رخ حركت‌های عمودی و افقی دارد و وزیر تركیبی از قدرت حركتی رخ و فیل را به صورت همزمان در اختیار دارد، اما از شیوه حركتی منحصر به فرد اسب بی‌بهره است. بنابراین تركیب قوانین حركتی این مهره‌ها - آن هم با درنظر گرفتن این واقعیت كه برخی خانه‌ها هم‌اكنون اشغال هستند - وضعیت پیچیده‌ای را ایجاد می‌كند كه محاسبه همه حالت‌های مجاز، به شدت توان پردازشی كامپیوتر را طلب می‌كند.

خوشبختانه در مدل نرم‌افزاری شطرنج از قوانین این بازی چندین ساختار یا آرایش داده‌ای مختلف استخراج شده است كه می‌توانید آن‌ها را نوعی از <محاسبات قبلاً انجام شده> بنامید. این‌ها در واقع الگوهای آرایشی خاصی هستند كه می‌توانند مسیر محاسبه برای به دست آوردن تمام حركت‌های مجاز بعدی را كوتاه كنند.

تكنیك‌های جست‌وجو
<تكنیك‌های جست‌وجو> قلب هر نرم‌افزار شطرنج هستند. منظور از <جست‌وجو> یافتن حركت‌های خوب و مجاز بعدی است. مجاز بودنشان در مرحله تولید حركت شناسایی شده است و ارزیابی میزان خوب یا بد بودن این حركت‌ها و سرانجام انتخاب یكی از آن‌ها می‌ماند. این كار به واقع مشكل است. چنان كه دیدید، اثر افق یكی از مسائلی است كه باید حل شود. جست‌وجو در پایه‌ای‌ترین شكل آن با معادله‌ای به صورت b به توان n توصیف می‌شود كه در آن b اصطلاحاً فاكتور انشعاب و n عمق حركت است.فاكتور انشعاب تعداد حركت‌های مجاز از سوی هر دو حریف در هر نوبت بازی است و عمق عبارت از تعداد نوبت‌هایی است كه قرار است به ارزیابی حركت‌های طرفین بپردازیم. بنابراین، نتیجه این معادله یك منحنی نمایی است كه به سرعت رشد می‌كند و تنوع فوق‌العاده زیادی را در انواع حالت‌های ممكن به وجود می‌آورد. خوشبختانه الگوریتم‌های خیلی خوبی برای محاسبه انواع حالت‌های پیش رو ابداع شده‌اند.

البته این الگوریتم‌ها برای رویارویی با مقولاتی مانند اثر افق طراحی نشده‌اند، بلكه صرفاً مسیر ارزیابی حالت‌های مختلف سود و زیان انجام دادن انواع حركت‌های مجاز را كوتاه می‌كنند. از جمله الگوریتم‌های موفق می‌توان به الگوریتم نگا اسكوت، الگوریتم MTD)f) و الگورتیم تكرارشونده آلفابتا اشاره كرد.

اما علاوه بر الگوریتم‌های اصلی، در محاسبه حركت‌های بعدی باید به فكر راهكارهایی برای مقابله با اثر افق نیز بود. مثلاً تیم توسعه كامپیوتر Deep Blue مفهوم <بسط‌های ویژه> یا Singular Extensions را توسعه دادند. این تكنیك می‌گوید: واضح است كه در بازی شطرنج بعضی حركت‌ها خیلی مؤثرتر و مهم‌تر از حركت‌های دیگرند و نباید خیلی وقت تلف كرد تا به درست بودن آن ها پی برد.

به تعبیر خودمان، نباید در مورد انتخاب این حركت‌ها زیاد تأمل كرد. مثلاً ممكن است به این نتیجه برسید كه با دو حركت دیگر می‌توانید وزیر حریف را بگیرید. تئوری بسط‌های ویژه می‌گوید وقتی به چنین موقعیت‌هایی برخورد می‌كنید، هوشمندانه‌تر این است كه وقت بیشتری بگذارید و تا چند نوبت، بیشتر از مقدار پیش فرض خودتان برای محاسبه حركت‌های بعدی، این مسیر را دنبال كنید؛ مبادا دام یا اشتباهی در كار باشد! این كار بهتر از این است كه ماشین وار همه مسیرها را به یك اندازه دنبال كنید.
ارزیابی‌
سرانجام مسئله چهارم دیگری كه باید كامپیوتر در فكر آن باشد، مسئله <ارزیابی> وضعیت كلی بازی است. چگونه كامپیوتر باید بفهمد كه الان از حریفش جلو است یا عقب؟ آیا در شرف پیروزی است یا شكست؟ باید برای نجات از شكست یا به تعویق انداختن آن برنامه‌ریزی كند یا به فكر تسریع پیروزی قریب‌الوقوع خود باشد؟ معمای <ارزیابی بازی> از جمله مهم‌ترین مسائل پیش روی برنامه‌نویسان شطرنج است. مسئله <تكنیك‌های جست‌وجو> حتی در پیچیده‌ترین شكلش در سرتاسر ساختار بازی شطرنج تابع یك سری قواعد عمومی است: اگرعمل A اتفاق بیفتد و سپس واكنش B روی دهد، آن‌گاه احتمال وقوع حالت C وجود دارد.

این مسیر ممكن است دوباره پس از دو نوبت بازیِ طرفین تكرار شود. در حالی كه مسئله <ارزیابی> یك مسئله راهبردی و خاص هر مورد بازی شطرنج است و امكان ندارد آرایش كنونی بازی، تعداد مهره‌های طرفین و وضعیت قوت و ضعف آن‌ها پس از یك نوبت بازی طرفین مانند نوبت قبلی باشد. <ارزیابی> در ساده‌ترین شكلش شامل بررسی این واقعیت است كه هر یك از دو حریف در هر مقطعی از بازی چند مهره دارند و این مهره‌ها صرف نظر از چیدمانشان چه ارزشی دارند. این در حقیقت نوعی ارزیابی كمّی از وضعیت بازی است.

تئوری شطرنج برای هر نوع مهره وزن مخصوصی قائل است. مثلاً می‌گویند وزیر نُه امتیاز می‌ارزد، رخ پنج، فیل چهار، اسب سه و پیاده یك امتیاز. به این ترتیب نرم افزار می‌تواند از فرمول (Sum (Ni * Vi استفاده كند كه در آن مجموعِ حاصل‌ضرب Ni در Vi ‌به ازای هر نوع مهره برای یك حریف محاسبه می‌شود. در اینجا Ni تعداد مهره‌هایی از یك نوع و Vi ارزش هر نوع مهره است.

اما ارزیابی كمّی كافی نیست. باید دید این مهره‌ها از نظر عملی چقدر كارآمد هستند. شاید یك وزیر كه بالقوه می‌تواند خطر بزرگی باشد، به جهت آچمز شدن در شرایطی كه او را ناگزیر از پاسبانی از جان شاه كرده است، عملاً در مراحل میانی یا پایانی بازی كارایی محدودی داشته باشد. به هرحال برای ارزیابی بازی معادلات مختلفی نوشته شده است كه در هر نرم‌افزار از بعضی از آن‌ها استفاده می‌شود. طبیعی است كه هرچه این معادلات جامع‌نگرتر باشند، دقت نرم‌افزار بیشتر می‌شود. خود تكنیك ارزیابی چند ركن دارد: توازن كمی قوا، قدرت مانور و میزان نفوذ مهره‌ها روی خانه‌های مختلف صفحه بازی، توسعه بازی، آرایش پیاده نظام، و امنیت شاه، از جمله مهم‌ترین اركان ارزیابی هستند.

به عنوان مثال، تئوری كلاسیك شطرنج تأكید دارد كه مهره‌های ضعیف‌تر بازی مثل فیل و اسب باید هرچه سریع‌تر به وسط معركه آورده شوند. شاه خوب است كه هرچه سریع‌تر به فكر رفتن به قلعه باشد و مهره‌های رخ و وزیر بهتر است در جای خود آرام بنشینند تا بازی به لحظات استراتژیك و سرنوشت‌ساز خود نزدیك شود. در تئوری مدرن شطرنج به جنبه‌های پیشرفته‌تری از بازی نیز اندیشیده می‌‌شود.

مثلاً این‌كه مهرهایی مانند اسب و فیل باید سریعاً در فكر فتح مركز باشند تا هم از حملات وزیر حمایت كنند و هم فضا را برای مانور دادن رخ‌ها باز كنند. معادلات و تكنیك‌های ارزیابی در حقیقت می‌توانند به این مسئله پاسخ دهند كه اگر كامپیوتر بخواهد از یك استراتژی معین برای پیروزی استفاده كند (مثلاً فتح مركز)، چگونه باید میزان تحقق این اهداف میانی را ارزیابی و بررسی كند. تكنیك‌های ارزیابی همچنین می‌توانند به این مسئله فكر كنند كه آرایش پیاده نظام چگونه است؟ مثلاً تا چه اندازه نزدیك بودن پیاده‌ها به یكدیگر شعاع عمل آن‌ها را محدود یا باز كرده است. چقدر شانس پیروزی برای وزیر شدن یك پیاده وجود دارد و مواردی از این قبیل.
جمع بندی‌
به این ترتیب می‌توان مدل هوشمند مصنوعی در یك نرم‌افزار شطرنج را چنین خلاصه كرد: این هوشمندی چهار ركن دارد:

یكم: <بینایی> نرم‌افزار
دوم: آگاهی از قوانین بازی‌
سوم: هوشمندی در جست‌وجو برای یافتن بهترین حركت بعدی
چهارم: هوشمندی در سنجش وضعیت كنونی و ارزیابی میزان تحقق استراتژی انتخاب شده برای رسیدن به پیروزی نهایی یا دستیابی به اهداف میانی


  • آخرین ویرایش:-
آخرین پست ها