कैदी दुविधा: आप अकेले हैं (नहीं)

मैंने हाल ही में कैदियों के बारे में एक पोस्ट पढ़ी, जिसमें समुदाय की दिलचस्पी थी।
इस पोस्ट में मैं बर्कले के एआई पाठ्यक्रमों में ऑनलाइन अध्ययन के बाद प्राप्त अनुभव के आधार पर, गेम थ्योरी की ओर से इस समस्या पर एक नज़र डालना चाहता हूं। इस इकाई का उपयोग करने के बाद, समस्या स्पष्ट और हल हो जाती है।

यदि आप एक निर्णय पेड़ का निर्माण करते हैं, तो आपको निम्नलिखित योजना मिलेगी:

जहां मैं और OH कैदी हैं
लाल रेखाओं का अर्थ है दूसरे कैदी के खिलाफ गवाही देना
मौन हरी रेखाएँ
ए, बी, सी, डी - चार संभावित परिणाम
A - दोनों प्रमाण देते हैं
बी - मैं गवाही देता हूं, वह चुप है
सी - मैं चुप हूं, वह गवाही देता है
डी - हम दोनों चुप हैं

अब हम पेऑफ फ़ंक्शन को परिभाषित करते हैं:
मेरे लिए, फ़ंक्शन f1 = -m होगा
इसके लिए f2 = -n के बराबर होगा

जहाँ m और n कारावास के वर्षों की संख्या प्राप्त करते हैं, मेरा और यह, क्रमशः, कार्यों को नकार के साथ लिया जाता है, क्योंकि हम सलाखों के पीछे बैठना चाहते हैं
यहाँ m और n स्वतंत्र चर हैं, क्योंकि हमारे पास एक गैर-शून्य राशि वाला एक खेल है, अन्यथा फ़ंक्शन इस तरह दिखेंगे:
मेरे लिए, f1 = -m
उसके लिए, f2 = m
यहाँ दूसरा कैदी हमें लंबे समय तक बैठना चाहता है और मी को कम करने की कोशिश करता है।

उदाहरण के लिए विकी से डेटा को संभावित परिणामों के बारे में लें, फिर:
ए = -2; - 2
बी = 0; - 10
सी = -10; 0
डी -1 है; -1
पहली और दूसरी संख्या कहां है, मेरा लाभ और उसका क्रमशः
हमें निम्नलिखित योजना मिलती है जिसे हमें हल करना होगा:


अब इस समस्या को हल करने का प्रयास करते हैं और तय करते हैं कि हमें क्या कदम उठाना चाहिए। सबसे पहले, मिनिमैक्स एल्गोरिथ्म का प्रयास करें, जो कि हमारे मामले में मैक्सिमैक्स के रूप में होगा, क्योंकि दोनों खिलाड़ी अपनी जीत को अधिकतम करने की कोशिश कर रहे हैं। हमें निम्न परिणाम मिलते हैं:

जैसा कि हम देखते हैं, दूसरा खिलाड़ी हमेशा विश्वासघात करेगा, क्योंकि वह अपनी जीत को अधिकतम करने की कोशिश करता है। मुझे विश्वासघात भी चुनना चाहिए - उसी कारण से।


यह मैक्सिमैक्स एल्गोरिथ्म वास्तविक दुनिया में अच्छी तरह से काम नहीं करता है, क्योंकि यह हमेशा खराब परिणाम के लिए तैयार होता है। ऐसी स्थितियों में, अपेक्षित अधिकतम एल्गोरिथ्म (अपेक्समैक्स) बेहतर है। यह एल्गोरिथ्म इस बात को ध्यान में रखता है कि खिलाड़ी अपने लिए सबसे लाभप्रद कदम नहीं चुन सकते हैं।
मान लीजिए कि HE 50% मामलों में विश्वासघात करता है, तो:
हमारे विश्वासघात का लाभ 0.5 * (- 2) + 0.5 * (0) = -1 के बराबर होगा
हमारी चुप्पी 0.5 * (- 10) + 0.5 * (- 1) = -5.5 जीतना
या आरेख में समान:


जैसा कि आप देख सकते हैं, यहां तक ​​कि अधिक उपयुक्त एल्गोरिथ्म के साथ, एक चमत्कार नहीं हुआ और यह हमारे लिए धोखा देने के लिए अधिक लाभदायक है। यहां तक ​​कि अगर उसकी चुप्पी की संभावना बढ़ जाती है, तो भी इन शर्तों के तहत धोखा देना अधिक लाभदायक है। यदि हम जानते हैं कि महामहिम हमेशा चुप रहेंगे, तो हम विश्वासघात का चयन करेंगे।

ऐसा क्यों? हमने कहां गलत समझा?
हम एक बहुत ही महत्वपूर्ण विवरण पर विचार करना भूल गए - पेऑफ फ़ंक्शन। लेकिन क्या होगा अगर HIS भाग्य हमारे प्रति उदासीन नहीं है, और हमारा उसके प्रति उदासीन नहीं है? फिर भुगतान कार्य निम्नानुसार होंगे:
f1 = -m -n
f2 = -m -n
जहाँ m और n क्रमशः कारावास के वर्षों की संख्या है, मेरा और उसका, क्रमशः
फिर हमें निम्नलिखित योजना मिलती है, लेकिन यह एक शास्त्रीय कार्य नहीं होगा, क्योंकि एक भी शर्त पूरी नहीं होगी:

और अब सब कुछ मौलिक रूप से बदल रहा है, अधिकतम के लिए एमई के लिए समाधान चुप हो जाएगा, क्योंकि मैं -4 के बीच का चयन करूंगा; - बाईं ओर (-4) और (-2) दाईं ओर (-2);
और उसके विश्वासघात के 50% के साथ अपेक्षित अधिकतम के लिए, आपको मिलता है:
मेरे विश्वासघात के लिए लाभ -7 है
मेरी चुप्पी जीत के लिए -6
इसलिए, हम चुप हैं।
एक चौकस हाबायुज़र ध्यान देगा कि यदि एचआईएस विश्वासघात की संभावना बढ़ जाती है, तो यह मेरे लिए विश्वासघात के लिए अधिक लाभदायक होगा।

आप इन संभावनाओं को कैसे जानते हैं? उन्हें पिछले अनुभव के आधार पर पाया जा सकता है।
मान लीजिए कि वह 10 में से 9 मामलों में पहले चुप था, इसलिए, हम उसे विश्वासघात का 10% मौका देते हैं
वास्तविक दुनिया में सच है, ये संभावनाएं बड़ी संख्या में कारकों पर निर्भर करती हैं और उन्हें ढूंढना मुख्य समस्याओं में से एक है।

यह भी याद रखने योग्य है कि भुगतान कार्यों का एक अलग रूप हो सकता है, उदाहरण के लिए, मेरे लिए अधिक स्वार्थी:
f1 = -m / 2 - एन
यहां हम HIM को याद करते हैं, लेकिन वैसे भी, अगर 2 साल या ME 1 पर बैठने के बीच कोई विकल्प है, तो मैं दूसरा विकल्प पसंद करूंगा।
यह सुविधा ढूंढना भी कठिन है।

निष्कर्ष:

यह डिवाइस आपको ऐसी किसी भी स्थिति का मूल्यांकन, प्रस्तुत और हल करने की अनुमति देता है, आपको बस इनपुट डेटा को प्रतिस्थापित करने की आवश्यकता है।

मेरा मानना ​​है कि कैदी की दुविधा अपर्याप्त इनपुट की दुविधा है। अगर हम जानते हैं कि वह किस संभावना के साथ विश्वासघात करेगा कि हम कैसे स्वार्थी हैं और कितना स्वार्थी है, तो हम निर्णय को सही के बहुत करीब ले सकते हैं।