برنده همیشگی بازی دوز باشید!
امروز قصد داریم روشی ارائه بدهیم که با استفاده از آن همیشه برنده بازی دوز باشید، قرار است با طراحی یک مِتّد و پیاده سازی یک الگوریتم معروف و با انجام هوشمندانه ترین حرکات، بازی را پیش بینی کنیم و پیروز میدان باشیم.
بازی tic tac toe یا همان دوز شامل یک جدول ۳*۳ میباشد. دو بازیکن با کاراکتر های X و O به نوبت در آن بازی میکنند و در هر نوبت یک بازی کن یکی از خانه های جدول را انتخاب میکند و آن را علامت گذاری میکند، در نهایت اگر یک بازیکن بتواند سه خانه کنار هم را (به صورت اَریب یا صاف) با کاراکتر خود علامت گذاری کند برنده بازی است، بدیهی است که در نهایت سه حالت بیشتر نداریم این که یکی از دو بازیکن برنده بازی باشد و یا بازی مساوی بشود. یک تابع Utility یا عایدی بازی برای بازی تعریف میکنیم به این صورت:
- X برنده باشد که در این صورت مقدار تابع برابر است با ۱+
- Y برنده باشد که در این صورت مقدار تابع برابر است با ۱-
- مساوی بشود که در این صورت مقدار تابع برابر است با ۰
از آنجایی که دو بازیکن سعی در برد بازی یا حداقل مساوی کردن آن دارند بازیکن X همیشه تلاش میکند تا مقدار تابع را بیشینه و بازیکن Y همیشه تلاش میکند تا مقدار تابع را کمینه کند(در اصطلاح به بازیکن X ماکسیمایزر و به Y مینیمایزرمیگویند). حال چگونه میتوانیم در هر State از بازی بهترین حرکت را برای بازیکن پیدا کنیم؟ کافیست با الگوریتم minimax و بازگشت از فرزندان به سمت ریشه در درخت، تمامی State ها را ارزیابی کنیم. در ادامه بیشتر راجع به این روش توضیح خواهیم داد.
در عکس زیر فرض کنید بازی به به مرحله ۰ کشیده شده است و نوبت بازیکن X میباشد. برای تصمیم گیری حرکت بازیکن X (و البته پیش بینی نتیجه بازی) باید از حالت صفر شروع و تمام حالات را بسازیم و سپس از پایین ترین نود ها به سمت ریشه حرکت کنیم.
بیایید از پایینترین گره(node) شروع کنیم، برای مثال در حالت ۱۰ بازی تمام شده و مقدار تابع عایدی برابر صفر است و از آنجایی که در حالت چهارم فقط یک حرکت ممکن برای X (حرکت ۱۰) داریم، بنابراین میتوان نتیجه گرفت تابع عایدی در حالت چهارم نیز برابر صفر است. همچنین برای حالت ۱۱ و ۵ نیز همین شرایط را داریم و از آنجایی که عایدی ۱۱ برابر یک (یعنی برنده شدن X ) است،عایدی حالت ۵ نیز برابر یک میباشد.
حال به حالت (State) ۱ نگاه کنید. در این حالت تنها دو حرکت ممکن وجود دارد که پیشتر گفتیم عایدی آنها صفر و یک میباشند. از آنجایی که در حالت ۱ نوبت بازیکن O میباشد، بازیکن O تلاش میکند که عایدی را مینیمم کند، پس در صورت انجام دادن بهترین بازی خود، حالت ۴ را انتخاب میکند بنابراین عایدی حالت ۱ برابر صفر میباشد. و به همین صورت برای حالات ۲ و ۳ نیز با محاسبه عایدی فرزندان میتوان عایدی این نودها را نیز حساب که به ترتیب عایدی آنها صفر و یک هستند.
پس از محاسبه عایدی تمام فرزندان حالت صفر، حال نوبت به محاسبه عایدی این نود میشود. حالت صفر سه فرزند دارد که عایدی آنها صفر، صفر و یک هستند. در واقع این مقادیر به ما نشان میدهد که با انجام حرکت هرکدام از نودهای فرزند نود صفر، در بدترین حالت عایدی همان نود نصیب ما میشود. میدانیم که در حالت صفر نوبت بازیکن X میباشد که ماکسیمایزر هست و مقدار تابع Utility را ماکسیمم میکند پس حالت سوم را انتخاب خواهد کرد تا برنده بازی باشد.
در این مثال دیدیم که اگر در چنین حالتی باشیم X حتما برنده بازی است حال تمام حالات بازی را از ابتدا تصور کنید، میبینید که به سادگی میتوان این بازی را به یک بازی بی مزه تبدیل کرد و متوجه شد که بازیکن اول همیشه برنده بازی است یا در بد ترین حالت بازی مساوی میشود، میدانیم از تعداد حالات دوز محدود هست و مجموع تمام نود(node) های آن چیزی کم تر ده هزار هست پس به سادگی میتوان با یک برنامه درخت تمامی حالات را محاسبه کرد و بازی را پیش بینی کرد، یادتان باشد در بازی هایی که تعداد حالات آن محدود است میتوان برنده بازی را در صورت هوشمندانه بازی کردن مشخص کرد، مگر این که تعداد حالات آن آنقدر زیاد باشد(مانند بازی شطرنج) که حتی با پیشرفته ترین کامپیوتر های امروزی نیز محاسبه آن سالها به طول بیانجامد!
پس برای بازی هایی مانند شطرنج چه کار باید بکنیم؟ چطور میتوان بهترین حالت را پیش بینی کرد؟ در مقاله های بعدی با ما همراه باشید..
مطالب زیر را حتما مطالعه کنید
ساز و کار بازیها
نظریه بازیها (مقدمه)
4 Comments
Join the discussion and tell us your opinion.
دیدگاهتان را بنویسید لغو پاسخ
برای نوشتن دیدگاه باید وارد بشوید.
با تشکر از مقاله مختصر و مفیدتون ، فکر کنم که در شطرنج از روش بیشترین سود استفاده میشه
نمیشه اموزش دوز ایستاده رو بزارید؟
خیلی مقاله خوبی بود متشکرم
منتظر مقالات بعدیتون هستم