درخت بازی

300px
درخت بازی :
که فرم گسترده هم خوانده می‌شود، نمایشی گرافیکی از یک بازی مرحله‌ای است که اطلاعاتی در مورد بازیکنان، نتایج نهایی، روش‌ها و مرتبه حرکات فراهم می‌کند. درخت بازی تشکیل شده‌است از تعدادی راس که نقاطی هستند که بازیکنان می‌توانند بر آن‌ها اقدام کنند، و این گره‌ها توسط یال، که نشان دهنده اقداماتی است که ممکن است بر آن گره انجام شود، به هم متصل می‌شوند. اولین گره (یا ریشه) اولین تصمیمی که می‌بایست گرفته شود را نشان می‌دهد. هر مجموعه‌ای از یال‌ها از اولین گره به سرتاسر درخت، در آخر به گره‌ای نهایی می‌رسد، که نماینده انتهای بازی است. هر گره نهایی با نتیجه نهایی گرفته شده توسط هر بازیکن بر چسب گذاری می‌شود اگر بازی در آن گره پایان یابد.
استفاده از درخت برای نمایش فضای مسئله برای بازی‌ها اغلب مناسب است. گره ریشه شامل حالت شروع بازی می‌باشد. برای هر گره شامل وضعیت جاری، باید تصمیمی برای انتخاب بهترین حرکت بعدی اتخاذ شود. هر حرکت قانونی توسط یک شاخه از درخت نشان داده می‌شود. با استفاده از یک تابع ارزیابی، یک وضعیت از بازی ارزش گذاری می‌شود. گره‌های برگ، وضعیت‌های نهائی بازی را نشان می‌دهند که در اینجا می‌تواند یکی از مقادیر برد، مساوی یا باخت باشد.
مثال
در بعضی بازی‌ها، برد یک طرف برابر با باخت طرف دیگر است، بازی‌هایی مانند: ایکس او و شطرنج. برای این نوع بازی‌ها، می‌توان درخت بازی طراحی کرد. مثالی از درخت بازی اکس او:
این شکل قسمتی از بازی ایکس او است. هر گره یک موقعیت از بازی را نشان می‌دهد، و بچه‌های هر گره، حرکات مجاز در آن موقعیت هستند. برای علامت گذاری هر موقعیت، به وضعی که برای بازیکن ۱ مطلوب است عددی مثبت اختصاص می‌دهیم (هر چه مثبت‌تر، مطلوب‌تر). به همین شکل، به وضعی که برای بازیکن ۲ مطلوب است عددی منفی اختصاص می‌دهیم (هر چه منفی‌تر، مطلوب‌تر). در این مثال، بازیکن شماره ۱، ‘X‘ و بازیکن شماره ۲، ‘O‘ است و تنها سه علامتی که داریم، ۱+ برای برد ‘X‘و ۱- برای برد ‘O‘، و ۰ برای تساوی است. توجه کنید که در اینجا علامت‌های آبی تنها با توجه به همان موقعیت به دست آمده‌اند. برای حساب کردن بقیه موقعیت‌ها، می‌بایست حرکاتی را پیش‌بینی کنیم که با استفاده از الگوریتم زیر به دست می‌آید.
تابع ارزیابی
به منظور ارزیابی میزان خوب بودن یک گره، تابع ارزیابی استفاده می‌شود. (تابع هیوریستیک)می‌توان از یک تابع برای (Zero-Sum) با استفاده از قانون مجموع صفر
هر دو بازیکن به منظور ارزیابی موقعیت بازی بهره برد:
برای من خوب و برای حریف بد است. n موقعیت F(n)> ۰
برای من بد و برای حریف خوب است. n موقعیت F(n) > ۰
برد حریف F(n)
=بتا بود، بهترین حرکت حریف موقعیتی بدتر از بهترین حرکت ما ایجاد می‌کند، بنابراین نیازی به ارزیابی این حرکت نیست.
alpha-beta(player, board, alpha, beta):
if game over in current board position:
return winner
children = all legal moves for player from this board
if max turn:
for each child:
score = alpha-beta(other player,child,alpha,beta)
if score> alpha then alpha = score # we have found a better best move
if alpha>= beta then return alpha # cut off
return alpha # this is our best move
else min turn:
for each child:
score = alpha-beta(other player,child,alpha,beta)
if score = beta then return beta # cut off
return beta # this is the opponents best move
این الگوریتم مقداری مشابه با minimax اما در زمانی سریع‌تر برمی‌گرداند.
پیچیدگی درخت بازی
بازی‌هایی که گراف بزرگتری دارند دارای پیچیدگی بیشتری هستند و در نظریه بازی‌ها سخت‌تر می‌باشند. مثلا شطرنج نمونه‌ای از پیچیده‌ترین بازی‌ها با پیچیده‌ترین درخت بازی است.
در بسیاری از بازی‌ها تعداد حرکات ممکن، محدود است. برای مثال، در بازی ایکس او، بازیکنان با قرار دادن علامت X یا O بر صفحه بازی، نه موقعیت می‌توانند ایجاد کنند. بعد از قرار دادن یکی از این علامات، بازی با یک حرکت پیش رفته‌است.
درخت بازی ایکس او با نه شاخه آغاز می‌شود، زیرا بازیکن اول از بین نه خانه خالی می‌تواند یکی را انتخاب کند. با انتخاب هر یک از این نه خانه، بازیکن دوم می‌تواند در یکی از هشت خانه باقی‌مانده علامت زند، بنابراین هر یک از این نه گره هشت شاخه دارند. با ادامه این کار می‌توان درختی با ۳۶۲،۸۸۰ = !۹ برگ ساخت، که برخی متعلق به برد بازیکن اول، و برخی متعلق به برد بازیکن دوم و بقیه مربوط به تساوی آن دوست.
ایکس او می‌تواند در پنج مرحله به پایان رسد، در صورتی که بازیکن اول تمام علامت‌ها را در یک ردیف بگذارد. به همین دلیل درخت بازی شامل شاخه‌هایی است که در مکان‌هایی بسیار کوتاه‌تر از عمق کامل آن بریده شده‌اند.
برای یافتن بهترین حرکت ممکن از الگوریتم minimax استفاده می‌شود.
شش میلیون حالت ممکن ایکس او برای به خاطر سپردن بازیکنان بسیار زیاد است، اما برای کامپیوترهای مدرن ناچیز می‌باشد. به همین دلیل این بازی با توجه به استانداردهای نظریه بازی، «سخت» در نظر گرفته نمی‌شود. بسیاری از بازی‌های جالب مانند شطرنج، دارای درخت‌های بازی‌ای هستند که تعداد حالات ممکن آن‌ها بسیار بیشتر از تعداد کل اتم‌ها در جهان است. این نوع بازی‌ها در ریاضی «سخت» خوانده می‌شوند، به این دلیل که، راهی برای حفظ تمامی حالات ممکن شطرنج نیست.
راه حل عمومی این نوع بازی‌ها، ساخت قسمتی از درخت است که بیانگر وضعیت کنونی می‌باشد. برای مثال ممکن است یک برنامه بازی شطرنج، از قالب کنونی صفحه، درختی با یک میلیون نتیجه ممکن بسازد، و الگوریتم آلفا بتا را به این قسمت از درخت اعمال کند. البته ممکن است سیستم، حرکتی را انتخاب کند که تمام نتایج حاصل در مرحله بعد منجر به باخت شود. این موضوع به تاثیر افقی معروف است که تمام تغییرات مهم در جایی خارج از عمق درختی که جستجو شده‌است اتفاق افتد. به همین دلیل بسیاری از برنامه‌های شطرنج بزرگترین درخت ممکن را (با توجه به میزان حافظه و زمان) می‌سازند.
سرعت کامپیوترهای مدرن این مشکل را تا حدی رفع کرده‌است، حتی برنامه‌های شطرنج غیر نخبه می‌توانند در برابر همه به جز بهترین بازیکنان انسانی پیروز شوند.
تعداد موقعیت‌های قانونی و پیچیدگی درخت بازی برای بعضی بازی‌ها
ایکس او – ۳٫۶*۱۰^۶ موقعیت
شطرنج – ۱۰^۵۰ موقعیت – ۱۰^۵۸ پیچیدگی
تخمین پیچیدگی درخت بازی شطرنج
عدد شانون (۱۰ به توان ۱۲۰) تخمین پیچیدگی درخت بازی شطرنج است.
این عدد اولین بار به وسیله کلود شانون پدر تئوری اطلاعات محاسبه شد. بر طبق نظر وی، به‌طور متوسط در هر بازی ۴۰ حرکت انجام می‌شود و هر بازیکن یک حرکت را بین۳۰ حرکت انتخاب می‌نماید. (اما در واقع ممکن است برخی حرکات انتخابی در حد صفر باشد مثلا در موارد پات یا کیش و مات یا تا ۲۱۸ حرکت افزایش یابد).
بنابراین ۳۰*۳۰ به توان ۴۰ یا به عبارتی ۹۰۰ به توان ۴۰ بازی شطرنج ممکن است. این تعداد درحدود ۱۰ به توان ۱۲۰ است. پیچیدگی درخت بازی شطرنج اکنون درحدود ۱۰به توان ۱۲۳ (تعداد پوزیسیون‌های قانونی در بازی شطرنج بین ۱۰ به توان ۴۳ و ۱۰ به توان ۵۰) تخمین زده می‌شود. به عنوان مقایسه، تعداد اتم‌ها در جهان بین ۱۰*۴ به توان ۷۵ و۱۰*۶ به توان ۷۹ تخمین زده می‌شود.