موضوع مقاله: استنتاج معکوس | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # استنتاج معکوس | مقدمه: استنتاج معکوس روند استنتاج رو به عقب در مسائل و موقعیت‌ها با مراحل محدود، جهت به‌دست آوردن اقدام بهینه در هر مرحله است. | ## بخش 1: استنتاج معکوس | در ریاضیات این نوع استنتاج یکی از اصلی‌ترین راه‌حل‌های حل مسائل پویا از جمله معادله بلمن می‌باشد. در نظریه بازی‌ها نیز از استنتاج معکوس برای پیدا کردن تعادل نش زیربازی کامل استفاده می‌کنند که در بازی‌های پویا کاربرد دارد. استنتاج معکوس اولین بار توسط بنیان‌گذاران نظریه بازی‌ها، جان فون نیومن و اسکار مورگنشترن در سال ۱۹۹۶ به کار برده شد. نام‌های دیگری که برای این استنتاج در زبان فارسی استفاده می‌شود، استقرای معکوس یا استقرای عقب‌گرد می‌باشد. روند اجرای استنتاج معکوس روند استنتاج معکوس به صورت تجزیه و تحلیل یک بازی از آخرین مرحله به ابتدای آن است و در هر مرحله استراتژی که مغلوب است، حذف می‌شود و استراتژی برنده در گام بعدی بازی تحلیل می‌شود. در واقع در هر مرحله فرض می‌شود، هر بازیکن با انتخاب عقلانی استراتژی که سود بیشتری دارد را انتخاب می‌کند. در صورتی که بازیکن اول در مرحله اول W و بازیکن دوم در مرحله دوم C را انتخاب کند، بازیکن اول در مرحله سوم حق انتخاب بین دو استراتژی Y و Z را دارد. سود هر بازیکن در رأس‌های نهایی درخت ذکر شده‌است که اولین عدد (عدد سمت راست) سود بازیکن اول و دومین عدد، سود نفر دوم است. برای به دست آوردن تعادل نش زیربازی کامل در این بازی، که تعادلی است که هر بازیکن بهترین پاسخ را در هر مرحله به اقدام حریف انجام می‌دهد، از این استنتاج به این صورت استفاده می‌کنیم که از آخرین راس (راس با ارتفاع بیشتر از ریشه) شروع می‌کنیم. پس با انتخاب عقلانی، استراتژی اول را انتخاب می‌کند و استراتژی Z مغلوب این استراتژی است. در مرحله دوم، بازیکن دوم در دو راس باید تصمیم گیرد، در راس دوم، بیشترین سود این بازیکن انتخاب B است و در راس اول C. گام‌های اجرای استنتاج معکوس هدف ما داشتن مقادیر نتیجه (سود یا ضرر) احتمالی برای هر بازیکن در هر راس می‌باشد، در ابتدا به هیچ راس میانی مقداری اختصاص نیافته و برگ‌های درخت (راس‌های نهایی) نیز دارای مقدار نتیجه برای تمام بازیکنان (استراتژی پروفایل) هستند. گام‌های زیر را انجام می‌دهیم: راسی که مقداری ندارد و تمام رأس‌های فرزند و تابع‌اش در درخت مقدار گرفته‌اند، را انتخاب می‌کنیم و V می‌نامیم. | ## بخش 2: استنتاج معکوس | (در هر مرحله حتماً همچنین راسی وجود دارد) بازیکن متناظر این راس برای مثال بازیکن شماره n می‌باشد. از بین رأس‌های فرزند این راس، که مقدار نتیجه (سود یا ضرر) بازیکنان به آن اختصاص یافته، راسی که بیشترین سود را برای بازیکن n دارد را می‌یابیم. (در واقع بازیکن n این استراتژی متناظر راس با بیشترین سود برای خود را انتخاب می‌کند) در صورتی که راس V، راس ریشه درخت می‌باشد بازی تمام شده و این مقدار تخصیص داده شده به V، تعادل کامل زیر بازی می‌باشد و در غیر اینصورت دوباره به ترتیب گام‌های بالا را انجام می‌دهیم. محدودیت‌های استفاده از این روش استفاده از این روش برای برخی بازی‌ها کاربرد ندارد. بازی‌های نامتناهی این روش استنتاج تنها برای بازی‌های محدود و متنهایی کاربرد دارد. یک بازی پویا (ترتیبی)، محدود است، اگر درخت بازی آن که شکل فرم گسترده بازی است، تعداد راس محدودی داشته باشد. برای مثال این بازی را در نظر بگیرید: بازی ترتیبی بین دو بازیکن داریم که در هر مرحله یک بازیکن ۱ یا ۲ انگشت را بالا می‌آورد. یک بازیکن می‌بازد در صورتی که به تعدادی که بازیکن دیگر در مرحله قبل بالا آورده، انگشت بالا بیاورد. این بازی با جمع صفر با درنظرگیری انتخاب عقلانی در هر مرحله، هیچگاه به انتها نمی‌رسد، پس در درخت فرم گسترده آن، تعداد نامتناهی مرحله و راس خواهیم داشت. بازی‌های تکراری نتیجه نهایی به دست آورده از این روش، با فرض انتخاب عقلانی بازیکنان به دست می‌آید و احتمالاً در دنیای واقعی با انتخاب‌های ساده لوحانه و غیرمنطقی، نتایج متفاوت با سود کمتر یا بیشتر از این نتیجه به دست بیاید. مثلاً در بازی هزارپا که شکل ساده شده آن به این صورت است که k واحد پول به دو نفر عرضه می‌شود و با اجرای ۹۹ بار این بازی که در آن هر سری یک نفر از این دو نفر پول را بین خود و دوستش تقسیم می‌کند و نفر دوم نیز یا قبول می‌کند که به همان میزانی که نفر اول تصمیم گرفته تقسیم کنند یا کلا رد می‌کند که در صورت رد کردن، به هیچ‌کدام پولی نمی‌رسد. طبق استنتاج معکوس، بازیکن دوم هر طوری‌که بازیکن اول تقسیم کند و برای او بیشتر از ۱ واحد پول در نظر بگیرد را قبول می‌کند (چون سودش از صفر که از رد کردن تقسیم‌بندی به دست می‌آید، بیشتر است) بازیکن اول نیز برای به دست آوردن بیشترین سود، از بین انتخاب ۰ تا k - 1، مسلماً k - 1 را انتخاب می‌کند. در حالی که با اجرای ۹۹ بار این بازی، حالت تعادل تقسیم‌بندی به صورت k/2, k/2 است. | ## بخش 3: استنتاج معکوس | بازی‌هایی که تعداد حالات برد زیادی دارند همچنین در بازی‌هایی مثل شطرنج یا چکرز که تعداد حالت نهایی برد فراوانی دارد، استفاده از این روش کارایی ندارد و تنها در صورتی که یک حالت نهایی و ممکن برای برد وجود داشته باشد، کارایی دارد. مثال‌هایی از کاربرد استنتاج معکوس از استنتاج معکوس در حل بسیاری از مسائل که به بازی قابل مدل کردن هستند، می‌توان استفاده کرد. کاربردی در سیاست در سال ۱۹۶۲، اتحادیه جماهیر شوروی تصمیم گرفت که موشک‌های هسته‌ای خود را در کوبا قرار دهید، رئیس‌جمهور وقت ایالت متحده آمریکا، جان اف کندی در برابر این اقدام، سه اقدام می‌توانست انجام دهد. خروشچف در برابر اقدام آمریکا، تهدید به تشدید وضعیت کرد ولی در نهایت شوروی راضی به خارج کردن موشک‌ها از کوبا شد و آمریکا نیز کوبا را از محاصره خارج کرد. در مرحله دوم و در نیز آمریکا از بین سودهای انتخابی این مرحله که برای حمله هوایی ۴، برای محاصره دریا ۵ و بدون اقدام، ۲ است، محاصره دریا را انتخاب می‌کند و در مرحله اول، نیز شوروی اقدام قرار دادن موشک‌ها در کوبا را که بیشترین سودش در آن است، را انتخاب می‌کند. کاربردی در نظریه بازی‌ها بازی دونفره‌ای را در نظر بگیرید که با شمارش اعدادی از ۱ تا ۵۰ هر بازیکن که مجاز به گفتن عدد ۵۰ بود و آن را گفت، برنده است. منوال بازی به این صورت است که برای شروع نفر اول یک عدد بین ۱ تا ۱۰ می‌گوید مثلاً a، بازیکن دوم نیز باید عدد بین a تا a + 10 بگوید. سپس نفر اول نیز عددی بین ۱۰ عدد پس از عدد انتخابی بازیکن قبلی انتخاب می‌کند، تا یکی ۵۰ بگوید. در این بازی اگر بازیکن شروع‌کننده، با کمک استنتاج معکوس، بازی را تحلیل کند، برنده بازی می‌تواند باشد. اگر بازیکن اول با تحلیل اینکه باید بازیکن دوم را ملزم به انتخاب عددی بین ۴۰ تا ۴۹ کند، چرا که با انتخاب هر یک از این اعداد، در دور بعدی می‌تواند ۵۰ را بگوید، عدد ۳۹ را باید انتخاب کند. برای انتخاب عدد ۳۹، باید بازیکن دوم را مجبور کند عددی بین ۲۹ تا ۳۸ را انتخاب کند، تا دور بعدی مجاز به انتخاب ۳۹ شود. باز هم به صورت بازگشتی در دور قبلی باید بازیکن دوم عددی از ۱۸ تا ۲۷ انتخاب کند، برای الزام بازیکن دوم باید ۱۷ را انتخاب کند و برای انتخاب ۱۷، باید نفر دوم عددی بین ۷ تا ۶ را انتخاب کند، که برای این کار بازیکن اول در دور اول بازی ۶ را انتخاب می‌کند. | ## جمع‌بندی | پس بازیکن اول با انتخاب به ترتیب ۶، ۱۷، ۲۸، ۳۹ و ۵۰ در هر مرحله بازی قادر به بردن این بازی است.