اشاره :
درباره موفقیت کامپیوتر در شکست دادن قهرمانان بازی شطرنج حتماً شنیده‌اید. به راستی کامپیوتر چگونه شطرنج بازی میکند؟ این سؤال جالبی است. به نظر من بهترین پاسخ را میتوانید از برنامه‌نویسان بازیهای شطرنج کامپیوتری بپرسید. این مقاله تحقیقی در همین زمینه است. در اینجا کوشیده‌ام مدل برنامه‌نویسی شطرنج و شیوه تجزیه و تحلیل بازی از نگاه کامپیوتر را تشریح کنم. اطلاعاتی را که در اینجا آورده‌ام، همه از سایت برنامه‌نویسان بازیهای کامپیوتری، به‌ویژه برنامه‌نویسان بازی شطرنج، استخراج شده‌اند.
چرا بررسی شطرنج کامپیوتری؟
ممکن است بپرسید بررسی آناتومی یک برنامه شطرنج اصلاً چه فایده‌ای دارد؟ پاسخ را در دو سه نکته میتوانم خلاصه کنم. در وهله نخست، بررسی آناتومی یک بازی شطرنج از لحاظ تئوری هوش‌مصنوعی میتواند نمونه بسیار جالبی از کاربرد این علم تلقی شود. در بسیاری مواقع وقتی گفته میشود هوش مصنوعی، برای بسیاری از مردم واقعاً سؤال است که این هوش از کجا میآید و چگونه شکل میگیرد. شطرنج یکی از جاهایی است که میتوانید ببینید چگونه یک سری معادلات ریاضی که ظاهری ساده، اما باطنی پیچیده دارند، به تدریج در پیچ و خم پردازش‌های بعدی مبنای هوشمندی ماشین1 را فراهم میکنند.
گذشته از این، بررسی مکانیزم شطرنج‌بازيِ کامپیوتر یک موضوع تأمل‌برانگیز است و به شما نوعی بینش شبه فلسفی درباره تفاوت رویکرد انسان و ماشین نسبت به نوع خاصی از معماها میدهد. ضمن این‌که، دریچه ذهن شما را به روی برخی اشتباهات رایج ذهن انسان بازمیکند که منجر به تصمیم‌گیریهای اشتباه و در نتیجه پیامدهای نامطلوب میشوند. از این رهیافت میتوانید ببینید که از دیدگاه علمی یکی از نظریه‌های مربوط به مبنای اشتباه‌کردن انسان هنگام تصمیم‌گیری میان گزینه‌های مختلف چیست.
آگاهی از این مسئله میتواند برای هرکارشناس کامپیوتر، آن هم در دنیایی که یک اشتباه کوچک میتواند به مدد شبکه جهانی اطلاعات در عرض چند ثانیه سراسر کره زمین را درنوردد و همچون ویروس‌های مخرب کامپیوتری، پیامدهای وخیمی را ایجاد کند، مهم و آموزنده باشد.
این موضوع نکته دیگری را نیز روشن میکند و آن این‌که، چگونه برنامه‌نویسان باهوشی که توسعه‌دهنده مدل برنامه‌نویسی شطرنج بوده‌اند، به منطق این اشتباهات پیبرده‌اند و سعی کرده‌اند به کامپیوتر یاد دهند با پیش‌بینی این اشتباهات، از انسان پیش‌دستی کند. جالب اینجاست که در مدل برنامه‌نویسی شطرنج، دغدغه کامپیوتر نه سرمایه‌گذاری روی اشتباهات حریف، بلکه چاره‌جویی در مورد اشتباهات احتمالی خودش است! از آن جالب‌تر این‌که، بازی شطرنج جزء بازیهای اصطلاحاً <با اطلاعات کامل> طبقه‌بندی میشود. بازیهایی که هر دو طرف دستشان برای یکدیگر رو شده است.
بنابراین، وقتی میفهمیم که به‌رغم اطلا‌ع طرفین از وضعیت مهره‌های یکدیگر، این همه پیچیدگی در تجزیه و تحلیل وضعیت‌های پیش رو وجود دارد، میتوانید حدس بزنید علت این همه ناکامی آدمیزاد در پیش‌بینی سرنوشت بسیاری از تحولات چیست؛ آن هم هنگامی که دست حریف برایش رو نیست.
در نهایت، مطالعه و بررسی مدل برنامه‌نویسی شطرنج یک تمرین فکری خوب و آموزنده برای همه برنامه‌نویسان ماجراجوست و می تواند ذهن کاوشگر آنان را بیش از پیش ورزیده کند. به قول معروف، هم فال است و هم تماشا!
 |
اثر افق
کالبد یک نرم‌افزار شطرنج از قسمت‌های مختلفی تشکیل شده است که کمی جلوتر خواهم گفت، اما اجازه بدهید برای ورود به بحث، شما را با یکی از چالش‌های همیشگی برنامه‌نویسان شطرنج آشنا کنم تا ببینید کامپیوتر برای موفقیت در یک بازی شطرنج، با چه معماهای غامضی دست و پنجه نرم میکند.
لابد شنیده‌اید که کامپیوتر هنگام شطرنج بازی تا چند مرحله جلوتر را در ذهن خودش مرور میکند و پیامدهای هر یک از حرکت‌های فرضی را در هر مرحله ارزیابی میکند. واقعاً هم همین‌طور است.
حالا فرض کنید یک نرم‌افزار طوری برنامه‌ریزی شده است که تا هفت مرحله جلوتر را میتواند محاسبه و ارزیابی کند. تصور کنید یک کامپیوتر با استفاده از چنین الگویی ناگهان متوجه شود که ممکن است در پنج نوبت دیگر مُهرهِ وزیرِ خودش را از دست بدهد و حتماً میدانید مهره وزیر چقدر مهم است.
بنابراین، باید جایی در منطق نرم‌افزارِ شطرنج، به کامپیوتر گفته شده باشد که در تصمیم‌سازی برای حرکت بعدی خودت <به وضعیت مهره وزیر اولویت بده.> البته از لحاظ تئوريِ مدرن شطرنج، میتوان پرسید که آیا واقعاً ارزش یک مهره وزیر در سراسر یک بازی یکسان است؟ و آیا باید یک شطرنج باز در هر شرایطی به حفظ جان این مهره بیش از هر مهره دیگر اهمیت بدهد؟
اگر پاسخ منفی باشد، وضعیت خیلی پیچیده‌تر خواهد شد، ولی فعلاً بیایید برای ساده شدن صورت مسئله، فکر کنیم که منطق تصمیم‌سازی کامپیوتر چنین باشد. در آن صورت نتیجه بدیهی این منطق این خواهد بود که کامپیوتر شروع به بررسی سناریوهای مختلف نجات جان وزیر در پنج نوبت دیگر کند و در این میان به این نتیجه برسد که بهترین گزینه این است که مهره اسب خود را در همین نوبت قربانی کند تا با افزودن فلان حرکت در نوبت سوم، دستیابی حریف به این هدف را دست کم تا نوبت هشتم به تعویق بیندازد. اما مشکل اینجاست که این کامپیوتر میتواند تا هفت نوبت جلوتر را محاسبه کند. بنابراین، عملاً تا یک دست دیگر بازی نکند، نمیتواند پیش‌بینی کند در نوبت هشتم چه اتفاقی خواهد افتاد.
از دیدگاه کامپیوتر، عدم روِیت یک معضل در افق دیدش به معنی نبودن آن معضل است. بنابراین، وقتی با انجام‌دادن یک حرکت میتوان آن معضل را تا عمق هفت مرحله از میدان دید خارج کرد، شاید به این معنی باشد که مشکل حل شده است، ولی چنین نیست. چون در همان گام اول یک اسب فدا میشود، یک نوبت بازی انجام میشود و دوباره همان مشکل (تهدید شدن وزیر) در افق دید کامپیوتر ظاهر میشود. پس مشکل حل نشد و کامپیوتر اشتباه کرد.
<اثر افق> در شطرنج کامپیوتری که اولین بار توسط هانس برلینر مطرح شد، از این جهت جالب است که به‌گونه طنزآمیزی تبلور ماهیت بعضی از خطاهای انسانی نیز هست. به راستی خیلی از ما آدم‌ها دقیقاً به دلیل همین کوته‌بینی، اشتباه میکنیم. یعنی بارها در زندگی تصور میکنیم وقتی مشکلی در افق دیدمان نیست، یعنی آن مشکل وجود ندارد؛ در حالی که مشکل وجود دارد و کافی است یک گام به جلو برداریم تا آن را ببینیم، ولی تا آن گام را برنداریم، از دیدنش ناتوان هستیم. درست مثل زمانی که یک بطری نوشابه گازدار را ناگهان بدون حضورذهن باز میکنیم و تازه وقتی آن را باز کردیم و گازش بیرون جهید و پیراهنمان را کثیف کرد، یادمان میافتد که باید در بطری را آرام باز میکردیم.
اولین درسی که از اثر افق میتوان گرفت این است که پیدا کردن وضعیتی که نرم‌افزار بتواند قدرت نسبی نیروها را در وضعیت کنونی سبک و سنگین کند، اصلاً خیلی مهم نیست؛ زیرا این ارزیابی ماهیت پویا بودن نیروها را در طول زمان درنظر نگرفته است. ارزیابی کنونی به درد آرایش کنونی میخورد، ولی چون لحظه بعد آرایش نیروها عوض میشود، ارزیابی کنونی شاید به کلی بیهوده باشد!!
به زبان ریاضیات مهندسی، میتوان گفت که وقتی شرایط اولیه یک معادله ریاضی ثابت باشد، یک کامپیوتر میتواند این معادله را هرچند هم پیچیده باشد، به سادگی حل کند. اما اگر بلافاصله در ثانیه بعدی شرایط اولیه تغییر کند، آن هم تغییری که خودش تابعی از چگونگی اولین برخورد شما با معادله است، در آن صورت حل این معادله ممکن است از لحاظ نظری تا بینهایت به تعویق بیفتد.
درس دیگری که از این پدیده میتوان گرفت این است که دنبال کردن خط سیر تحولات در هرجهت تا عمق x مرحله کار بیهوده‌ای است. بعضی از مسیرها مهم‌ترند. این مسیرها را باید تا عمق مثلاً ده یا پانزده نوبت بازی دنبال کرد و بعضی دیگر را باید تا عمق پنج مرحله دنبال و بعد از آن را رها کرد. اشتباه است اگر همه مسیرها را تا عمق مثلاً هفت نوبت دنبال کنیم. در این صورت چگونه باید تشخیص دهیم کدام مسیر اهمیت استراتژیک بیشتری دارد و کدام‌یک از مسیرها کم اهمیت‌تر هستند؟
این چیزی است که یک انسان هوشمند گاهی به صورت خودآگاه و گاهی ناخودآگاه انجام می دهد. به همین دلیل وقتی مثلاً شیئی را در اتاقمان گم میکنیم، تمام اتاق را به شعاع سه متر زیر و رو نمیکنیم. این کار نادرست است. پس با خود میگوییم کجاها را باید دقیق‌تر بگردیم؟ کجاها را باید یک نگاه سطحی بیندازیم؟ شما از کجا میفهمید برخی مناطق داخل اتاقتان اهمیت بیشتری برای پیدا کردن یک شی گمشده دارد؟
نوعی از هوش مصنوعی در بازی شطرنج به همین ترتیب شکل میگیرد. در واقع این هوش مصنوعی بیشتر معطوف به هوشمندی در انتخاب مسیرهای مهم‌تر برای دنبال کردن تحولات هستند. خوشبختانه چندین الگوریتم ریاضی جالب تاکنون عرضه شده‌اند تا بتوان اثر افق را شکست داد و ماورای آن را دید. بسط‌های ویژه Deep Blue از جمله همین الگوریتم‌ها هستند. (احتمالاً بلافاصله می توانید حدس بزنید چرا کامپیوتر Deep Blue سرانجام توانست کاسپاروف، قهرمان جهانی شطرنج، را شکست دهد.)
آناتومی یک نرم‌افزار شطرنج
اثر افق یک موضوع مهم در معماری فکری یک نرم‌افزار شطرنج است، ولی تمامِ مسئله‌ای نیست که کامپیوتر باید حل کند. اثر افق فقط یک جنبه از مشکلات تکنیکهای جست‌وجو است و تکنیکهای جست‌وجو یکی از چهار ستون اصلی هر نرم‌افزار شطرنج هستند. کامپیوتر باید به حل سه مسئله محوری دیگر نیز فکر کند: چیدمان مهره‌ها، تولید حرکت، و ارزیابی، به ترتیب سه موضوع مهم دیگری است که هر نرم‌افزار شطرنج باید به آن فکر کند و در ادامه نیز به بررسی این چهار رکن میپردازیم.
 |
چیدمان مهره‌ها
چیدمان مهره‌ها، عبارت است از تصویرسازی کامپیوتر از صفحه بازی. کامپیوتر چگونه باید صفحه بازی را <ببیند>؟ چگونه باید بفهمد این مهره‌ها کجا هستند؟
چگونه باید فهمید الان پنج مهره سیاه، هفت مهره سفید را تهدید میکنند؟ نرم‌افزارهای شطرنج عمدتاً از تکنیکی به نام bitboard برای دیدن صفحه بازی استفاده میکنند.
بیت بورد که ظاهراً اختراع شطرنج بازان شوروی سابق است، متشکل از یک آرایه 64 بیتی است که متناظر با 64 خانه شطرنج درنظرگرفته شده‌اند.
نرم‌افزارهای امروزی شطرنج از تعداد بسیار زیادی بیت‌بورد برای به تصویر کشیدن وضعیت مهره‌ها در ذهن خود استفاده میکنند. هر بیت از این آرایه ممکن است صفر یا یک باشد. وضعیت <یک> به معنی اشغال بودن خانه و وضعیت <صفر> به معنی خالی بودن خانه متناظر در صفحه شطرنج است. مثلاً یک بیت‌بورد ممکن است مربوط به خانه‌هایی باشد که توسط فیل سیاه اشغال شده‌اند. یک بیت بورد دیگر ممکن است مربوط به خانه‌هایی باشد که مهره‌های سفید، مهره‌های سیاه را مورد حمله قرار داده‌اند و یک بیت بورد دیگر نشان دهد اسبی که در خانه 4e قرار دارد، کدام خانه‌ها را زیر نفوذ خود دارد.
تولید حرکت
<تولید حرکت> قسمت دیگری از وظیفه نرم‌افزار است و منظور از آن این است که هنگامی که نوبت بازی به کامپیوتر میرسد، قبل از این که تصمیم بگیرد چه کار کند، باید بداند حرکت‌های مجاز او کدامند. در وهله نخست ممکن است به نظر برسد این کار آسان است، ولی به یاد بیاورید که هر مهره شطرنج قوانین حرکتی خاصی دارد. مثلاً شاهی که در حالت کیش است، قابل حرکت دادن نیست.
همچنین فیل به صورت قطری حرکت میکند. اسب به صورت حرف L مانور میدهد. رخ حرکت‌های عمودی و افقی دارد و وزیر ترکیبی از قدرت حرکتی رخ و فیل را به صورت همزمان در اختیار دارد، اما از شیوه حرکتی منحصر به فرد اسب بیبهره است. بنابراین ترکیب قوانین حرکتی این مهره‌ها - آن هم با درنظر گرفتن این واقعیت که برخی خانه‌ها هم‌اکنون اشغال هستند - وضعیت پیچیده‌ای را ایجاد میکند که محاسبه همه حالت‌های مجاز، به شدت توان پردازشی کامپیوتر را طلب میکند.
خوشبختانه در مدل نرم‌افزاری شطرنج از قوانین این بازی چندین ساختار یا آرایش داده‌ای مختلف استخراج شده است که میتوانید آن‌ها را نوعی از <محاسبات قبلاً انجام شده> بنامید. این‌ها در واقع الگوهای آرایشی خاصی هستند که میتوانند مسیر محاسبه برای به دست آوردن تمام حرکت‌های مجاز بعدی را کوتاه کنند.
تکنیکهای جست‌وجو
<تکنیکهای جست‌وجو> قلب هر نرم‌افزار شطرنج هستند. منظور از <جست‌وجو> یافتن حرکت‌های خوب و مجاز بعدی است. مجاز بودنشان در مرحله تولید حرکت شناسایی شده است و ارزیابی میزان خوب یا بد بودن این حرکت‌ها و سرانجام انتخاب یکی از آن‌ها میماند. این کار به واقع مشکل است. چنان که دیدید، اثر افق یکی از مسائلی است که باید حل شود. جست‌وجو در پایه‌ایترین شکل آن با معادله‌ای به صورت b به توان n توصیف میشود که در آن b اصطلاحاً فاکتور انشعاب و n عمق حرکت است.
فاکتور انشعاب تعداد حرکت‌های مجاز از سوی هر دو حریف در هر نوبت بازی است و عمق عبارت از تعداد نوبت‌هایی است که قرار است به ارزیابی حرکت‌های طرفین بپردازیم. بنابراین، نتیجه این معادله یک منحنی نمایی است که به سرعت رشد میکند و تنوع فوق‌العاده زیادی را در انواع حالت‌های ممکن به وجود میآورد. خوشبختانه الگوریتم‌های خیلی خوبی برای محاسبه انواع حالت‌های پیش رو ابداع شده‌اند.
البته این الگوریتم‌ها برای رویارویی با مقولاتی مانند اثر افق طراحی نشده‌اند، بلکه صرفاً مسیر ارزیابی حالت‌های مختلف سود و زیان انجام دادن انواع حرکت‌های مجاز را کوتاه میکنند. از جمله الگوریتم‌های موفق میتوان به الگوریتم نگا اسکوت، الگوریتم MTD)f) و الگورتیم تکرارشونده آلفابتا اشاره کرد.
اما علاوه بر الگوریتم‌های اصلی، در محاسبه حرکت‌های بعدی باید به فکر راهکارهایی برای مقابله با اثر افق نیز بود. مثلاً تیم توسعه کامپیوتر Deep Blue مفهوم <بسط‌های ویژه> یا Singular Extensions را توسعه دادند. این تکنیک میگوید: واضح است که در بازی شطرنج بعضی حرکت‌ها خیلی مؤثرتر و مهم‌تر از حرکت‌های دیگرند و نباید خیلی وقت تلف کرد تا به درست بودن آن ها پی برد.
به تعبیر خودمان، نباید در مورد انتخاب این حرکت‌ها زیاد تأمل کرد. مثلاً ممکن است به این نتیجه برسید که با دو حرکت دیگر میتوانید وزیر حریف را بگیرید. تئوری بسط‌های ویژه میگوید وقتی به چنین موقعیت‌هایی برخورد میکنید، هوشمندانه‌تر این است که وقت بیشتری بگذارید و تا چند نوبت، بیشتر از مقدار پیش فرض خودتان برای محاسبه حرکت‌های بعدی، این مسیر را دنبال کنید؛ مبادا دام یا اشتباهی در کار باشد! این کار بهتر از این است که ماشین وار همه مسیرها را به یک اندازه دنبال کنید.
ارزیابی
سرانجام مسئله چهارم دیگری که باید کامپیوتر در فکر آن باشد، مسئله <ارزیابی> وضعیت کلی بازی است. چگونه کامپیوتر باید بفهمد که الان از حریفش جلو است یا عقب؟ آیا در شرف پیروزی است یا شکست؟ باید برای نجات از شکست یا به تعویق انداختن آن برنامه‌ریزی کند یا به فکر تسریع پیروزی قریب‌الوقوع خود باشد؟ معمای <ارزیابی بازی> از جمله مهم‌ترین مسائل پیش روی برنامه‌نویسان شطرنج است. مسئله <تکنیکهای جست‌وجو> حتی در پیچیده‌ترین شکلش در سرتاسر ساختار بازی شطرنج تابع یک سری قواعد عمومی است: اگرعمل A اتفاق بیفتد و سپس واکنش B روی دهد، آن‌گاه احتمال وقوع حالت C وجود دارد.
این مسیر ممکن است دوباره پس از دو نوبت بازيِ طرفین تکرار شود. در حالی که مسئله <ارزیابی> یک مسئله راهبردی و خاص هر مورد بازی شطرنج است و امکان ندارد آرایش کنونی بازی، تعداد مهره‌های طرفین و وضعیت قوت و ضعف آن‌ها پس از یک نوبت بازی طرفین مانند نوبت قبلی باشد. <ارزیابی> در ساده‌ترین شکلش شامل بررسی این واقعیت است که هر یک از دو حریف در هر مقطعی از بازی چند مهره دارند و این مهره‌ها صرف نظر از چیدمانشان چه ارزشی دارند. این در حقیقت نوعی ارزیابی کمّی از وضعیت بازی است.
تئوری شطرنج برای هر نوع مهره وزن مخصوصی قائل است. مثلاً میگویند وزیر نُه امتیاز میارزد، رخ پنج، فیل چهار، اسب سه و پیاده یک امتیاز. به این ترتیب نرم افزار میتواند از فرمول (Sum (Ni * Vi استفاده کند که در آن مجموعِ حاصل‌ضرب Ni در Vi به ازای هر نوع مهره برای یک حریف محاسبه میشود. در اینجا Ni تعداد مهره‌هایی از یک نوع و Vi ارزش هر نوع مهره است.
اما ارزیابی کمّی کافی نیست. باید دید این مهره‌ها از نظر عملی چقدر کارآمد هستند. شاید یک وزیر که بالقوه میتواند خطر بزرگی باشد، به جهت آچمز شدن در شرایطی که او را ناگزیر از پاسبانی از جان شاه کرده است، عملاً در مراحل میانی یا پایانی بازی کارایی محدودی داشته باشد. به هرحال برای ارزیابی بازی معادلات مختلفی نوشته شده است که در هر نرم‌افزار از بعضی از آن‌ها استفاده میشود. طبیعی است که هرچه این معادلات جامع‌نگرتر باشند، دقت نرم‌افزار بیشتر میشود. خود تکنیک ارزیابی چند رکن دارد: توازن کمی قوا، قدرت مانور و میزان نفوذ مهره‌ها روی خانه‌های مختلف صفحه بازی، توسعه بازی، آرایش پیاده نظام، و امنیت شاه، از جمله مهم‌ترین ارکان ارزیابی هستند.
به عنوان مثال، تئوری کلاسیک شطرنج تأکید دارد که مهره‌های ضعیف‌تر بازی مثل فیل و اسب باید هرچه سریع‌تر به وسط معرکه آورده شوند. شاه خوب است که هرچه سریع‌تر به فکر رفتن به قلعه باشد و مهره‌های رخ و وزیر بهتر است در جای خود آرام بنشینند تا بازی به لحظات استراتژیک و سرنوشت‌ساز خود نزدیک شود. در تئوری مدرن شطرنج به جنبه‌های پیشرفته‌تری از بازی نیز اندیشیده میشود.
مثلاً این‌که مهرهایی مانند اسب و فیل باید سریعاً در فکر فتح مرکز باشند تا هم از حملات وزیر حمایت کنند و هم فضا را برای مانور دادن رخ‌ها باز کنند. معادلات و تکنیکهای ارزیابی در حقیقت میتوانند به این مسئله پاسخ دهند که اگر کامپیوتر بخواهد از یک استراتژی معین برای پیروزی استفاده کند (مثلاً فتح مرکز)، چگونه باید میزان تحقق این اهداف میانی را ارزیابی و بررسی کند. تکنیکهای ارزیابی همچنین میتوانند به این مسئله فکر کنند که آرایش پیاده نظام چگونه است؟ مثلاً تا چه اندازه نزدیک بودن پیاده‌ها به یکدیگر شعاع عمل آن‌ها را محدود یا باز کرده است. چقدر شانس پیروزی برای وزیر شدن یک پیاده وجود دارد و مواردی از این قبیل.
جمع بندی
به این ترتیب میتوان مدل هوشمند مصنوعی در یک نرم‌افزار شطرنج را چنین خلاصه کرد: این هوشمندی چهار رکن دارد:
یکم: <بینایی> نرم‌افزار
دوم: آگاهی از قوانین بازی
سوم: هوشمندی در جست‌وجو برای یافتن بهترین حرکت بعدی
چهارم: هوشمندی در سنجش وضعیت کنونی و ارزیابی میزان تحقق استراتژی انتخاب شده برای رسیدن به پیروزی نهایی یا دستیابی به اهداف میانی
پی نوشت
لا‌زم به ذکر است که تلقی هوشمندانه بودن محاسبات نرم‌افزارهای شطرنج‌باز، محل بحث فراوان است و عده‌ای عقیده دارند که چنین نرم‌افزارهایی را نباید هوشمند به حساب آورد. در نتیجه در این نوشتار، هوشمند بودن نرم‌افزار شطرنج‌باز، نظر شخصی نویسنده است.
بهروز نوعی پور
منبع: ماهنامه شبکه - مهر ۱۳۸۵ شماره 69
نقل از افتابگردان