معمای زندانی ها

توی یکی از درسام یه معمایی رو دیدم که روی اون معما خیلی کارای جالبی شده و  نتیجه گیری های جالبی روش شده. اون معما اینه:به دو تا زندانی که با هم جرمی رو مرتکب شده اند و گیر افتاده اند و در سلول های جداگانه نگه داری میشند، گفته می شه:
- اگر یکی از شما اعتراف کنه و دیگری نه، کسی که اعتراف کرده آزاد میشه و دیگری برای سه سال زندانی میشه.
- اگر هر دو اعتراف کنید، هر کدوم برای دو سال زندانی میشید.
- اگر هیچ کس اعتراف نکنه، هر دو برای یک سال باید در زندان بمونید.
[caption id="attachment_62" align="aligncenter" width="300" caption="معمای زندانی"][/caption]
یه کمی فکر کنید و ببنید شما اگه جای یه کدوم از اونها بودید چی کار می کردید؟
خوب! به نظر می رسه میشه به این سوال یه جواب منطقی داد و اون اینه که بهتره اعتراف کنیم. یعنی رفتار منطقی اعتراف کردنه. بگذارید اعتراف کردن رو اسمش رو بذاریم همکاری نکردن با زندانی دیگه یا defect یا مختصرا D و اعتراف نکردن رو بگذاریم cooperate یا مختصرا C.
این معمایی که در بالا خوندید، یه معمای سخت در علم هوش مصنوعی توزیع شده (یا چند عامله - یعنی چند تا عامل هوشمند داریم که جوری باید برنامه نویسی/پیاده سازی بشند که با هم همکاری کنند) است! دلیلش رو می تونید حدس بزنید.
توی این معما می بینید که انسانی عمل کردن، لزوما منطقی عمل کردن نیست چون اینجا همه ی انسان ها منطقی عمل نمی کنند. اینجا این چالش پیش میاد که عامل ها/ربات هایی که ما می خوایم بسازیم واقعا باید منطقی عمل کنند یا انسانی؟
اینجا کلی مساله ی پیچیده پیش میاد که وقت ندارم بنویسمشون، اما بعد احتمالا به این فک می کنید که همه ی انسان ها، انسانی عمل می کنند؟! مثلا دولت ها انسانی عمل می کنند؟ به این مثال که شبیه مساله ی بالاست توجه کنید:
همه ی دولت های دنیا به هم قول می دند که سلاح های هسته ای خودشون رو نابود کنند. بعد چی می شه؟؟
شما باشید چی کار می کنید؟ C یا D ؟!!
پس به این نتیجه می رسیم که هوش مصنوعی گاهی باید انسانی عمل کنه گاهی هم نه!! اگه روبات هامون صرفا منطقی عمل کنند چی میشه؟!
یکی از جالب ترین توسعه های معمای زندانی ها اینه که این معما رو چند بار پشت سر هم تکرار کنیم! یعنی به عنوان یه بازی با امتیازای زیر:

u(D,D) = 2, u(D,C) = 5, u(C,C) = 3, u(C,D) = 0

بعد بیایم بین دو تا عامل هوشمند هی بازی رو تکرار کنیم و امتیاز بدیم. این بازی هم می تونی تعداد تکرار ناشناخته داشته باشه یا شناخته شده.
در ۱۹۸۰، دانشمندی به نام Robert Axelrod که یه دانشمند سیاست بود، تورنمنتی رو با حضور دانشمندای حوزه های سیاست، روان شناسی، اقتصاد و تئوری بازی ها ترتیب داد. هر دو رقیبی این بازی رو در ۵ دوره ی ۲۰۰ راندی بازی کردند. هر گروه شرکت کننده برنامه ی کوچکی رو برای این بازی می نوشت. این برنامه ها از ۵ تا ۱۵۲ خط بودند.
نکته ی مهم این بود که همه ی حریف ها با هم بازی می کردند.
حالا شما فکر کنید که چه جوری این کارو انجام می دادی؟ توجه کنید که حریف شما در هر مرحله کاملا ناشناس و حتی نمی دونید چه الگوریتم هایی در تورنمنت شرکت کردند فقط می دونید که حریفتون در مرحله های قبل بازی چه کاری انجام داده.
معروف ترین الگوریتم ها اینها بودند:
All-D: این الگوریتم فقط بدون توجه به اینکه حریف چه کاری کرده فقط defect می کرد.
RANDOM:  معلومه دیگه! تصادفی!
TIT-FOR-TAT: در مرحله ی اول cooperate و در مراحل بعد هر کاری که حریف در مرحله ی قبل کرده. این برنامه ۵ خط از زبان فرترن بود.
TESTER: در مرحله ی اول حریف رو با defect کردن تست می کرد. اگر حریف در مرحله ی بعد با defect تلافی می کرد، متعاقبا  TIT-FOR-TAT رو بازی می کرد. اگر حریف defect نمی کرد، به صورت تکراری دو بار cooperate می کرد و بعد defect.
JOSS: در واقع همان TIT-FOR-TAT بود با این تفاوت که ۱۰ درصد از زمان ها به جای cooperate، یک defect می کرد.
یکی از این استراتژی ها هم برنده ی تورنمنت شد! به نظرتون کدوم استراتژی؟؟
استراتژی سوم!! البته توجه کنید که همه ی استراتژی ها با هم روبرو شدند و گرنه به طور واضحی استراتژی سوم از استراتژی اول شکست می خورد.
بگید بهم که شما چه استراتژی ای داشتید؟
در پست بعدی دو تا معمای جدید رو مطرح می کنم که اون ها هم جالبند.