اشاره :
درباره موفقيت كامپيوتر در شكست دادن قهرمانان بازي شطرنج حتماً شنيدهايد. به
راستي كامپيوتر چگونه شطرنج بازي ميكند؟ اين سؤال جالبي است. به نظر من بهترين
پاسخ را ميتوانيد از برنامهنويسان بازيهاي شطرنج كامپيوتري بپرسيد. اين مقاله
تحقيقي در همين زمينه است. در اينجا كوشيدهام مدل برنامهنويسي شطرنج و شيوه تجزيه
و تحليل بازي از نگاه كامپيوتر را تشريح كنم. اطلاعاتي را كه در اينجا آوردهام،
همه از سايت برنامهنويسان بازيهاي كامپيوتري، بهويژه برنامهنويسان بازي شطرنج،
استخراج شدهاند.
چرا بررسي شطرنج كامپيوتري؟
ممكن است بپرسيد بررسي آناتومي يك برنامه شطرنج اصلاً چه فايدهاي دارد؟ پاسخ
را در دو سه نكته ميتوانم خلاصه كنم. در وهله نخست، بررسي آناتومي يك بازي شطرنج
از لحاظ تئوري هوشمصنوعي ميتواند نمونه بسيار جالبي از كاربرد اين علم تلقي شود.
در بسياري مواقع وقتي گفته ميشود هوش مصنوعي، براي بسياري از مردم واقعاً سؤال است
كه اين هوش از كجا ميآيد و چگونه شكل ميگيرد. شطرنج يكي از جاهايي است كه
ميتوانيد ببينيد چگونه يك سري معادلات رياضي كه ظاهري ساده، اما باطني پيچيده
دارند، به تدريج در پيچ و خم پردازشهاي بعدي مبناي هوشمندي ماشين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 ارزش هر نوع مهره است.
اما ارزيابي كمّي كافي نيست. بايد ديد اين مهرهها از نظر عملي چقدر كارآمد
هستند. شايد يك وزير كه بالقوه ميتواند خطر بزرگي باشد، به جهت آچمز شدن در شرايطي
كه او را ناگزير از پاسباني از جان شاه كرده است، عملاً در مراحل مياني يا پاياني
بازي كارايي محدودي داشته باشد. به هرحال براي ارزيابي بازي معادلات مختلفي نوشته
شده است كه در هر نرمافزار از بعضي از آنها استفاده ميشود. طبيعي است كه هرچه
اين معادلات جامعنگرتر باشند، دقت نرمافزار بيشتر ميشود. خود تكنيك ارزيابي چند
ركن دارد: توازن كمي قوا، قدرت مانور و ميزان نفوذ مهرهها روي خانههاي مختلف صفحه
بازي، توسعه بازي، آرايش پياده نظام، و امنيت شاه، از جمله مهمترين اركان ارزيابي
هستند.
به عنوان مثال، تئوري كلاسيك شطرنج تأكيد دارد كه مهرههاي ضعيفتر بازي مثل فيل
و اسب بايد هرچه سريعتر به وسط معركه آورده شوند. شاه خوب است كه هرچه سريعتر به
فكر رفتن به قلعه باشد و مهرههاي رخ و وزير بهتر است در جاي خود آرام بنشينند تا
بازي به لحظات استراتژيك و سرنوشتساز خود نزديك شود. در تئوري مدرن شطرنج به
جنبههاي پيشرفتهتري از بازي نيز انديشيده ميشود.
مثلاً اينكه مهرهايي مانند اسب و فيل بايد سريعاً در فكر فتح مركز باشند تا هم از حملات وزير حمايت كنند و هم فضا را براي مانور دادن رخها باز كنند. معادلات و تكنيكهاي ارزيابي در حقيقت ميتوانند به اين مسئله پاسخ دهند كه اگر كامپيوتر بخواهد از يك استراتژي معين براي پيروزي استفاده كند (مثلاً فتح مركز)، چگونه بايد ميزان تحقق اين اهداف مياني را ارزيابي و بررسي كند. تكنيكهاي ارزيابي همچنين ميتوانند به اين مسئله فكر كنند كه آرايش پياده نظام چگونه است؟ مثلاً تا چه اندازه نزديك بودن پيادهها به يكديگر شعاع عمل آنها را محدود يا باز كرده است. چقدر شانس پيروزي براي وزير شدن يك پياده وجود دارد و مواردي از اين قبيل.
جمع بندي
به اين ترتيب ميتوان مدل هوشمند مصنوعي در يك نرمافزار شطرنج را چنين خلاصه
كرد: اين هوشمندي چهار ركن دارد:
يكم: <بينايي> نرمافزار
دوم: آگاهي از قوانين بازي
سوم: هوشمندي در جستوجو براي يافتن بهترين حركت بعدي
چهارم: هوشمندي در سنجش وضعيت كنوني و ارزيابي ميزان تحقق استراتژي انتخاب شده براي رسيدن به پيروزي نهايي يا دستيابي به اهداف مياني
پي نوشت
لازم به ذكر است كه تلقي هوشمندانه بودن محاسبات نرمافزارهاي شطرنجباز، محل
بحث فراوان است و عدهاي عقيده دارند كه چنين نرمافزارهايي را نبايد هوشمند به
حساب آورد. در نتيجه در اين نوشتار، هوشمند بودن نرمافزار شطرنجباز، نظر شخصي
نويسنده است.
منبع : مجله شبکه