درخت بازی :
که فرم گسترده هم خوانده می شود، نمایشی گرافیکی از یک بازی مرحله ای است که اطلاعاتی در مورد بازیکنان، نتایج نهایی، روش ها و مرتبهٔ حرکات فراهم می کند. درخت بازی تشکیل شده است از تعدادی رأس که نقاطی هستند که بازیکنان می توانند بر آن ها اقدام کنند، و این گره ها توسط یال، که نشان دهندهٔ اقداماتی است که ممکن است بر آن گره انجام شود، به هم متصل می شوند. اولین گره ( یا ریشه ) اولین تصمیمی که می بایست گرفته شود را نشان می دهد. هر مجموعه ای از یال ها از اولین گره به سرتاسر درخت، در آخر به گره ای نهایی می رسد، که نمایندهٔ انتهای بازی است. هر گرهٔ نهایی با نتیجه نهایی گرفته شده توسط هر بازیکن بر چسب گذاری می شود اگر بازی در آن گره پایان یابد.
استفاده از درخت برای نمایش فضای مسئله برای بازی ها اغلب مناسب است. گره ریشه شامل حالت شروع بازی می باشد. برای هر گره شامل وضعیت جاری، باید تصمیمی برای انتخاب بهترین حرکت بعدی اتخاذ شود. هر حرکت قانونی توسط یک شاخه از درخت نشان داده می شود. با استفاده از یک تابع ارزیابی، یک وضعیت از بازی ارزش گذاری می شود. گره های برگ، وضعیت های نهائی بازی را نشان می دهند که در اینجا می تواند یکی از مقادیر برد، مساوی یا باخت باشد.
در بعضی بازی ها، برد یک طرف برابر با باخت طرف دیگر است، بازی هایی مانند: ایکس او و شطرنج. برای این نوع بازی ها، می توان درخت بازی طراحی کرد. مثالی از درخت بازی اکس او:
این شکل قسمتی از بازی ایکس او است. هر گره یک موقعیت از بازی را نشان می دهد، و بچه های هر گره، حرکات مجاز در آن موقعیت هستند. برای علامت گذاری هر موقعیت، به وضعی که برای بازیکن ۱ مطلوب است عددی مثبت اختصاص می دهیم ( هر چه مثبت تر، مطلوب تر ) . به همین شکل، به وضعی که برای بازیکن ۲ مطلوب است عددی منفی اختصاص می دهیم ( هر چه منفی تر، مطلوب تر ) . در این مثال، بازیکن شماره ۱، ‘X‘ و بازیکن شماره ۲، ‘O‘ است و تنها سه علامتی که داریم، ۱+ برای برد ‘X‘و ۱ - برای برد ‘O‘، و ۰ برای تساوی است. توجه کنید که در اینجا علامت های آبی تنها با توجه به همان موقعیت به دست آمده اند. برای حساب کردن بقیه موقعیت ها، می بایست حرکاتی را پیش بینی کنیم که با استفاده از الگوریتم زیر به دست می آید.
به منظور ارزیابی میزان خوب بودن یک گره، تابع ارزیابی استفاده می شود. ( تابع هیوریستیک ) با استفاده از قانون مجموع صفر ( Zero - Sum ) می توان از یک تابع برای هر دو بازیکن به منظور ارزیابی موقعیت بازی بهره برد:
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفکه فرم گسترده هم خوانده می شود، نمایشی گرافیکی از یک بازی مرحله ای است که اطلاعاتی در مورد بازیکنان، نتایج نهایی، روش ها و مرتبهٔ حرکات فراهم می کند. درخت بازی تشکیل شده است از تعدادی رأس که نقاطی هستند که بازیکنان می توانند بر آن ها اقدام کنند، و این گره ها توسط یال، که نشان دهندهٔ اقداماتی است که ممکن است بر آن گره انجام شود، به هم متصل می شوند. اولین گره ( یا ریشه ) اولین تصمیمی که می بایست گرفته شود را نشان می دهد. هر مجموعه ای از یال ها از اولین گره به سرتاسر درخت، در آخر به گره ای نهایی می رسد، که نمایندهٔ انتهای بازی است. هر گرهٔ نهایی با نتیجه نهایی گرفته شده توسط هر بازیکن بر چسب گذاری می شود اگر بازی در آن گره پایان یابد.
استفاده از درخت برای نمایش فضای مسئله برای بازی ها اغلب مناسب است. گره ریشه شامل حالت شروع بازی می باشد. برای هر گره شامل وضعیت جاری، باید تصمیمی برای انتخاب بهترین حرکت بعدی اتخاذ شود. هر حرکت قانونی توسط یک شاخه از درخت نشان داده می شود. با استفاده از یک تابع ارزیابی، یک وضعیت از بازی ارزش گذاری می شود. گره های برگ، وضعیت های نهائی بازی را نشان می دهند که در اینجا می تواند یکی از مقادیر برد، مساوی یا باخت باشد.
در بعضی بازی ها، برد یک طرف برابر با باخت طرف دیگر است، بازی هایی مانند: ایکس او و شطرنج. برای این نوع بازی ها، می توان درخت بازی طراحی کرد. مثالی از درخت بازی اکس او:
این شکل قسمتی از بازی ایکس او است. هر گره یک موقعیت از بازی را نشان می دهد، و بچه های هر گره، حرکات مجاز در آن موقعیت هستند. برای علامت گذاری هر موقعیت، به وضعی که برای بازیکن ۱ مطلوب است عددی مثبت اختصاص می دهیم ( هر چه مثبت تر، مطلوب تر ) . به همین شکل، به وضعی که برای بازیکن ۲ مطلوب است عددی منفی اختصاص می دهیم ( هر چه منفی تر، مطلوب تر ) . در این مثال، بازیکن شماره ۱، ‘X‘ و بازیکن شماره ۲، ‘O‘ است و تنها سه علامتی که داریم، ۱+ برای برد ‘X‘و ۱ - برای برد ‘O‘، و ۰ برای تساوی است. توجه کنید که در اینجا علامت های آبی تنها با توجه به همان موقعیت به دست آمده اند. برای حساب کردن بقیه موقعیت ها، می بایست حرکاتی را پیش بینی کنیم که با استفاده از الگوریتم زیر به دست می آید.
به منظور ارزیابی میزان خوب بودن یک گره، تابع ارزیابی استفاده می شود. ( تابع هیوریستیک ) با استفاده از قانون مجموع صفر ( Zero - Sum ) می توان از یک تابع برای هر دو بازیکن به منظور ارزیابی موقعیت بازی بهره برد:
wiki: درخت بازی