برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: در بعضی بازی‌ها، برد یک‌طرف برابر با باخت طرف دیگر است، بازی‌هایی مانند: ایکس او و شطرنج. برای این نوع بازی‌ها، می‌توان درخت بازی طراحی کرد. مثالی از درخت بازی اکس او: این شکل قسمتی از بازی ایکس او است. هر گره یک موقعیت از بازی را نشان می‌دهد، و بچه‌های هر گره، حرکات مجاز در آن موقعیت هستند. برای علامت‌گذاری هر موقعیت، به وضعی که برای بازیکن ۱ مطلوب است عددی مثبت اختصاص می‌دهیم (هر چه مثبت‌تر، مطلوب‌تر). به همین شکل، به وضعی که برای بازیکن ۲ مطلوب است عددی منفی اختصاص می‌دهیم (هر چه منفی‌تر، مطلوب‌تر). در این مثال، بازیکن شماره ۱، 'x' و بازیکن شماره ۲، 'o' است و تنها سه علامتی که داریم، ۱ + برای برد 'x'و ۱ - برای برد 'o'، و ۰ برای تساوی است. توجه کنید که در اینجا علامت‌های آبی تنها با توجه به همان موقعیت به دست آمده‌اند. برای حساب کردن بقیه موقعیت‌ها، می‌بایست حرکاتی را پیش‌بینی کنیم که با استفاده از الگوریتم زیر به دست می‌آید. به منظور ارزیابی میزان خوب بودن یک گره، تابع ارزیابی استفاده می‌شود. (تابع هیوریستیک) با استفاده از قانون مجموع صفر (zero-sum) می‌توان از یک تابع برای هر دو بازیکن به منظور ارزیابی موقعیت بازی بهره برد: برای من خوب و برای حریف بد است. n موقعیت f (n) > ۰ برای من بد و برای حریف خوب است. n موقعیت f (n) > ۰ برد حریف f (n) << ۰ هدف از جستجو در درخت بازی، تعیین حرکتی (نه یک راه‌حل) برای بازیکن max بطوری‌که امتیاز او را (بدون توجه به حرکات min) ماکزیمم کند. پیچیدگی زمانی: (o (b^m (چرا که شبیه جستجوی عمقی کامل می‌باشد) پیچیدگی فضایی: از مرتبه خطی ((o (m یا (o (bm) بازیکن max همواره فرض می‌کند که بازیکن min حرکتی را انجام می‌دهد که امتیازش را ماکزیمم کند و امتیاز max را مینیمم کند. امتیاز هر گره از طریق امتیاز فرزندانش مشخص می‌شود: مقدار گره max برابر ماکزیمم مقدار فرزندانش است. مقدار گره min برابر مینیمم مقدار فرزندانش است. حال که راهی برای نمایش بازی‌های خود داریم، چگونه می‌توانیم بهینه‌ترین حرکت را به دست آوریم؟ فرض می‌کنیم حریف ما هوشمند است، یعنی می‌تواند مانند ما حرکات را محاسبه کند و با انتخاب بهینه‌ترین حرکت، بازی خوبی ارائه دهد. یک الگوریتم برای محاسبه بهترین حرکت، الگوریتم minimax است: گره شروع بازی را با برچسب max ایجاد کن. گره‌های سطوح بعدی …
برداشت:
درخت بازی : که فرم گسترده هم خوانده می‌شود ، نمایشی گرافیکی از یک بازی مرحله‌ای است که اطلاعاتی در مورد بازیکنان ، نتایج نهایی ، روش‌ها و مرتبهٔ حرکات فراهم می‌کند . درخت بازی تشکیل شده‌است از تعدادی رأس که نقاطی هستند که بازیکنان می‌توانند بر آن‌ها اقدام کنند ، و این گره‌ها توسط یال ، که نشان دهندهٔ اقداماتی است که ممکن است بر آن گره انجام شود ، به هم متصل می‌شوند . اولین گره (یا ریشه) اولین تصمیمی که می‌بایست گرفته شود را نشان می‌دهد . هر مجموعه‌ای از یال‌ها از اولین گره به سرتاسر درخت ، در آخر به گره‌ای نهایی می‌رسد ، که نمایندهٔ انتهای بازی است . استفاده از درخت برای نمایش فضای مسئله برای بازی‌ها اغلب مناسب است .