موضوع مقاله: درخت بازی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت بازی | مقدمه: درخت بازی تشکیل شده‌است از تعدادی رأس که نقاطی هستند که بازیکنان می‌توانند بر آن‌ها اقدام کنند، و این گره‌ها توسط یال، که نشان دهندهٔ اقداماتی است که ممکن است بر آن گره انجام شود، به هم متصل می‌شوند. | ## بخش 1: درخت بازی | هر مجموعه‌ای از یال‌ها از اولین گره به سرتاسر درخت، در آخر به گره‌ای نهایی می‌رسد، که نمایندهٔ انتهای بازی است. هر گرهٔ نهایی با نتیجه نهایی گرفته شده توسط هر بازیکن بر چسب گذاری می‌شود اگر بازی در آن گره پایان یابد. برای هر گره شامل وضعیت جاری، باید تصمیمی برای انتخاب بهترین حرکت بعدی اتخاذ شود. گره‌های برگ، وضعیت‌های نهائی بازی را نشان می‌دهند که در اینجا می‌تواند یکی از مقادیر برد، مساوی یا باخت باشد. مثال در بعضی بازی‌ها، برد یک طرف برابر با باخت طرف دیگر است، بازی‌هایی مانند: ایکس او و شطرنج. هر گره یک موقعیت از بازی را نشان می‌دهد، و بچه‌های هر گره، حرکات مجاز در آن موقعیت هستند. برای علامت گذاری هر موقعیت، به وضعی که برای بازیکن ۱ مطلوب است عددی مثبت اختصاص می‌دهیم (هر چه مثبت تر، مطلوب تر). به همین شکل، به وضعی که برای بازیکن ۲ مطلوب است عددی منفی اختصاص می‌دهیم (هر چه منفی تر، مطلوب تر). در این مثال، بازیکن شماره ۱، ‘X‘ و بازیکن شماره ۲، ‘O‘ است و تنها سه علامتی که داریم، ۱+ برای برد ‘X‘و ۱- برای برد ‘O‘، و ۰ برای تساوی است. توجه کنید که در اینجا علامت‌های آبی تنها با توجه به همان موقعیت به دست آمده‌اند. برای حساب کردن بقیه موقعیت‌ها، می‌بایست حرکاتی را پیش‌بینی کنیم که با استفاده از الگوریتم زیر به دست می‌آید. تابع ارزیابی به منظور ارزیابی میزان خوب بودن یک گره، تابع ارزیابی استفاده می‌شود. (تابع هیوریستیک)با استفاده از قانون مجموع صفر (Zero-Sum) می‌توان از یک تابع برای هر دو بازیکن به منظور ارزیابی موقعیت بازی بهره برد: برای من خوب و برای حریف بد است. پیچیدگی زمانی: (O(b^m (چرا که شبیه جستجوی عمقی کامل می‌باشد) پیچیدگی فضایی: از مرتبه خطی O(m یا (O(bm) بازیکن Max همواره فرض می‌کند که بازیکن Min حرکتی را انجام می‌دهد که امتیازش را ماکزیمم کند و امتیاز Max را مینیمم کند. امتیاز هر گره از طریق امتیاز فرزندانش مشخص می‌شود: مقدار گره Max برابر ماکزیمم مقدار فرزندانش است. فرض می‌کنیم حریف ما هوشمند است، یعنی می‌تواند مانند ما حرکات را محاسبه کند و با انتخاب بهینه‌ترین حرکت، بازی خوبی ارائه دهد. برای گره‌های غیر برگ تا رسیدن به گره ریشه، با استفاده از قانون Minimax یک مقدار انتساب بده: مقدار گره Max برابر ماکزیمم مقدار فرزندانش است. اگر بازی در موقعیتی خاص تمام شود، دیگر چیزی برای محاسبه نیست و minimax علامت بازی را برمی‌گرداند. | ## بخش 2: درخت بازی | در غیر این صورت، minimax به تمام بچه‌های ممکن سر می‌زند، و (با بازگشتی خواندن خود)، هر حرکت ممکن را می‌سنجد و بعد از آن، بهترین حرکت را انتخاب می‌کند. برای بازی ساده‌ای مانند ایکس او، این زمان زیاد نیست – زیرا جستجوی تمام موقعیت‌های ممکن، امکان‌پذیر است. در حقیقت، برای اینکه تمام بازی‌ها را به‌طور کامل جستجو کنیم، ابتدا می‌بایست سفری بین ستاره‌ای تدارک ببینیم، زیرا پیش از پایان تحلیل یک حرکت، خورشید نابود شده و زمین دیگر وجود نخواهد داشت؛ بنابراین، تمام بازی‌های کامپیوتری تا تعدادی حرکت بعدی را جستجو می‌کنند، ولی نه تا پایان آن را. بهینه‌سازی الگوریتم یک عمل بهینه‌سازی برای الگوریتم بالا وجود دارد که به ما این امکان را می‌دهد که حداکثر عمق جستجو را افزایش دهیم. برای فهم این ایده به این شرح توجه کنید: نوبت حرکت ماست و حرکتی (حرکت الف) را محاسبه کرده‌ایم که بیش‌ترین سودمندی را برایمان داشته‌است. اکنون در حال تحلیل حرکت دوم هستیم (حرکت ب)، و می‌بینیم حریف می‌تواند در اولین پاسخ خود، موقعیتی خنثی به وجود آورد! در اینجا، می‌دانیم بهترین کار در صورتی که حرکت ب را انجام داده باشیم، رسیدن به موقعیتی خنثی است، در حالی که قبل از آن حرکت الف را داشته‌ایم که خود تضمین گر موقعیتی بهتر است. الگوریتم MiniMax بازی‌های چند نفره در بازی دو نفره دو بازیکن وجود داشت و دو مقدار تولید شده توسط تابع سودمندی که با توجه متضاد بودن این نتایج توانستیم آن‌ها را به یک مقدار در هر نوبت تبدیل کنیم. استفاده از یک بردار برای نمایش وضعیت بازی به جای یک مقدار در بازی چند نفره تابع سودمندی مقادیر مختلفی را در این بردار به ازای هر برگ تولید می‌کند که هر یک از این مقادیر از دید بازیکن خاصی می‌باشد. برای حل این مشکل، راه حل پیشنهادی عدم بسط گره‌هایی است که مقدار آن‌ها تأثیری در تصمیم نهائی ندارد. برای این منظور، کارایی الگوریتم Minimax را می‌توان با استفاده از هرس آلفا بتا افزایش داد. الگوریتم آلفا بتا اکنون ما از دو مقدار آلفا و بتا برای تحلیل هر گره استفاده می‌کنیم، و این الگوریتم را هرس آلفا بتا می‌نامیم. آلفا ارزش بهترین حرکتی از ماست که محاسبه کرده‌ایم و بتا نیز ارزش بهترین حرکت برای حریف است که آن را خود محاسبه کرده‌ایم. هر زمان که آلفا>=بتا بود، بهترین حرکت حریف موقعیتی بدتر از بهترین حرکت ما ایجاد می‌کند، بنابراین نیازی به ارزیابی این حرکت نیست. پیچیدگی درخت بازی بازی‌هایی که گراف بزرگتری دارند دارای پیچیدگی بیشتری هستند و در نظریهٔ بازی‌ها سخت‌تر می‌باشند. برای مثال، در بازی ایکس او، بازیکنان با قرار دادن علامت X یا O بر صفحه بازی، نه موقعیت می‌توانند ایجاد کنند. درخت بازی ایکس او با نه شاخه آغاز می‌شود، زیرا بازیکن اول از بین نه خانه خالی می‌تواند یکی را انتخاب کند. با انتخاب هر یک از این نه خانه، بازیکن دوم می‌تواند در یکی از هشت خانهٔ باقی‌مانده علامت زند، بنابراین هر یک از این نه گره هشت شاخه دارند. | ## بخش 3: درخت بازی | با ادامهٔ این کار می‌توان درختی با ۳۶۲٬۸۸۰ = !۹ برگ ساخت، که برخی متعلق به برد بازیکن اول، و برخی متعلق به برد بازیکن دوم و بقیه مربوط به تساوی آن دوست. ایکس او می‌تواند در پنج مرحله به پایان رسد، در صورتی که بازیکن اول تمام علامت‌ها را در یک ردیف بگذارد. به همین دلیل درخت بازی شامل شاخه‌هایی است که در مکان‌هایی بسیار کوتاه‌تر از عمق کامل آن بریده شده‌اند. شش میلیون حالت ممکن ایکس او برای به خاطر سپردن بازیکنان بسیار زیاد است، اما برای کامپیوترهای مدرن ناچیز می‌باشد. به همین دلیل این بازی با توجه به استانداردهای نظریه بازی، «سخت» در نظر گرفته نمی‌شود. بسیاری از بازی‌های جالب مانند شطرنج، دارای درخت‌های بازی ای هستند که تعداد حالات ممکن آن‌ها بسیار بیشتر از تعداد کل اتم‌ها در جهان است. این نوع بازی‌ها در ریاضی «سخت» خوانده می‌شوند، به این دلیل که، راهی برای حفظ تمامی حالات ممکن شطرنج نیست. راه حل عمومی این نوع بازی‌ها، ساخت قسمتی از درخت است که بیانگر وضعیت کنونی می‌باشد. برای مثال ممکن است یک برنامه بازی شطرنج، از قالب کنونی صفحه، درختی با یک میلیون نتیجه ممکن بسازد، و الگوریتم آلفا بتا را به این قسمت از درخت اعمال کند. البته ممکن است سیستم، حرکتی را انتخاب کند که تمام نتایج حاصل در مرحلهٔ بعد منجر به باخت شود. این موضوع به تأثیر افقی معروف است که تمام تغییرات مهم در جایی خارج از عمق درختی که جستجو شده‌است اتفاق افتد. به همین دلیل بسیاری از برنامه‌های شطرنج بزرگترین درخت ممکن را (با توجه به میزان حافظه و زمان) می‌سازند. سرعت کامپیوترهای مدرن این مشکل را تا حدی رفع کرده‌است، حتی برنامه‌های شطرنج غیر نخبه می‌توانند در برابر همه به جز بهترین بازیکنان انسانی پیروز شوند. تعداد موقعیت‌های قانونی و پیچیدگی درخت بازی برای بعضی بازی‌ها ایکس او – ۳٫۶*۱۰^۶ موقعیت شطرنج – ۱۰^۵۰ موقعیت – ۱۰^۵۸ پیچیدگی تخمین پیچیدگی درخت بازی شطرنج عدد شانون (۱۰ به توان ۱۲۰) تخمین پیچیدگی درخت بازی شطرنج است. بر طبق نظر وی، به‌طور متوسط در هر بازی ۴۰ حرکت انجام می‌شود و هر بازیکن یک حرکت را بین۳۰ حرکت انتخاب می‌نماید. (اما در واقع ممکن است برخی حرکات انتخابی در حد صفر باشد مثلاً در موارد پات یا کیش و مات یا تا ۲۱۸ حرکت افزایش یابد). پیچیدگی درخت بازی شطرنج اکنون در حدود ۱۰به توان ۱۲۳ (تعداد پوزیسیون‌های قانونی در بازی شطرنج بین ۱۰ به توان ۴۳ و ۱۰ به توان ۵۰) تخمین زده می‌شود. | ## جمع‌بندی | به عنوان مقایسه، تعداد اتم‌ها در جهان بین ۱۰*۴ به توان ۷۵ و۱۰*۶ به توان ۷۹ تخمین زده می‌شود.