ما هي خوارزمية الأمثل للعب كلمة الجلاد اللعبة ؟

Question

لنفترض أننا يلعبون اللعبة الجلاد.خصمي وأنا على حد سواء الوصول إلى قاموس خلال المباراة.خصمي يختار كلمة من القاموس مع معرفة الخوارزمية التي سوف تستخدم لتخمين له كلمة السر.مرة واحدة خصمي وقد اختار كلمة أنا أعطيت فقط لطول الكلمة.أستطيع أن أخمن الرسالة التي أعتقد سوف تكون في كلمة واحدة ، و إذا كان في كلمة خصمي يعرف جميع المواقف من تلك الرسالة في هذه الكلمة.إذا أعتقد أن الرسالة التي ليس في الكلمة التي تحسب خطأ واحد.إذا أنا يمكن أن تخمين كلمة من قبل الكثير من الأخطاء فزت.

خصمي هو الهدف ينبغي أن يكون اختيار الكلمة التي يزيد عدد الأخطاء (التخمينات غير صحيحة) لقد جعل قبل أن أتمكن من تخمين كلمة.هدفي هو التقليل منها.(تقليديا ، إذا كان عدد من الأخطاء > بعض العدد ثم تخسر اللعبة, ولكن يمكننا الاسترخاء هذا القيد.)

النظر في ثلاثة خوارزميات رسالة التخمين.هذه هي أهمها فكرت, ولكن ربما يكون هناك أكثر من ذلك ، وأرحب البديل الأفكار.في كل ثلاث خوارزميات, وسوف تكون الخطوة الأولى في جمع قائمة من الكلمات التي هي نفس طول كلمة السر.ثم لكل حرف في الأبجدية عدد الكلمات في القاموس الذي يحتوي على تلك الرسالة.على سبيل المثال, ربما 5000 تحتوي على "a" ، 300 تحتوي على "ب" ، وهلم جرا.هنا هو في بايثون:

    alphabet = list('abcdefghijklmnopqrstuvwxyz')

    while not found:
        probabilities = dict.fromkeys(alphabet, 0)

        for word in dictionary:
            for letter in word:
                if letter in alphabet:
                    probabilities[letter] += 1

        # now we have the letter frequencies

بعد التي هو فيها ثلاث خوارزميات تتباعد.

1. في أول خوارزمية ، ونحن تخمين الرسالة التي أكبر عدد من الكلمات المتبقية تحتوي على.حتى لو 5000 الكلمات المتبقية تحتوي على "a" و لا غيرها من الحروف في العديد من الكلمات ، فإننا سوف نختار "أ" في كل مرة.إذا كان "أ" هو الصحيح ، وهذا يعطينا المعلومات الموضعية التي يمكننا تصفية قائمة أخرى.على سبيل المثال ، قد مرشح القائمة عن كل الكلمات تلك المباراة ".أ..".(النقاط الحروف.) إذا كان "أ" غير صحيح ، نحن تصفية جميع الكلمات التي تحتوي على "a".في حال وجود عنق رسالتين تم العثور عليها في عدد متساو من الكلمات أو الحروف يتم اختيارها حسب الترتيب الأبجدي.حتى إذا كنا نعرف كلمة المباريات ".ays" سوف مجرد تخمين الكلمات في الترتيب الأبجدي.

2. هذا هو فقط مختلفة قليلا من أول خوارزمية.بدلا من اختيار الترتيب الأبجدي ، في حالة التعادل نختار الحروف بشكل عشوائي.هذا له فائدة أن الخصم لا يعرف ماذا سوف تختار.في أول استراتيجية "أشعة" هو دائما أفضل من "أيام".هذا يتجنب هذه المسألة.

3. في هذه الحالة نختار الحروف مع احتمال يتناسب مع عدد الكلمات التي تحتوي على تلك الرسالة.في البداية عندما نحن أحصينا عدد الكلمات التي تحتوي على "a" و التي تحتوي على "ب" و ذلك منذ "أ" حدث في أكبر عدد من الكلمات في استراتيجيات 1 و 2 اخترنا "أ" 100% من الوقت.بدلا من ذلك, سوف لا تزال تختار "أ" عدد وافر من الوقت ، ولكن عدد قليل من المرات ونحن سوف اختيار "z" على الرغم من أن يمكن العثور عليها في 10x أكثر من الكلمات.لدي شكوكي حول هذه الاستراتيجية كونها الأمثل ولكن انه كان يستخدم في البحوث في عام 2010.

لذلك لدي سؤالان:

1. ما هو الأمثل رسالة التخمين الاستراتيجية التي يجب أن تستخدم على افتراض أن خصمي يعلم أنني سوف تستخدم هذه الاستراتيجية?في هذا نريد أن نقلل متوسط عدد التخمينات أن تخمين كلمة سر.
2. عن كلمة معينة ، ويقول "يدفع" ، ما هو متوسط عدد الأخطاء M يجب أن يكون من المتوقع أن تجعل ؟ هل هناك مغلقة شكل طريقة لحساب م ، بدلا من تشغيل هذه المحاكاة عدة مرات ، حيث بلغ متوسطها النتائج ؟

التوضيحات

• أي قاموس يمكن استخدامها.على سبيل المثال ، هذا قاموس اللغة الإنجليزية مع 84k الكلمات..مجموعات فرعية من القواميس التي يتم اختيارها بعناية للغموض يمكن أيضا أن تكون مثيرة للاهتمام ولكن هي خارج نطاق هذا السؤال.
• لا توجد قيود على حجم كلمة طالما الكلمة في القاموس.والحازر سوف تعرف حجم كلمة قبل أن يبدأ التخمين.
• فقط عدد من الأخطاء في المسائل التي هي مستقلة عن حجم كلمة.كنت لا تحصل على المزيد من الفرص من أجل كلمات أطول أو أقل فرص أقصر منها.
• أنا مهتم فقط في التقليل من متوسط عدد من الأخطاء.إذا كان هناك اثنين الأمثل الخوارزميات التي لها مكافئ صغير متوسط عدد من الأخطاء ، وكلاهما مقبول.
• من حيث المبدأ من الممكن أن يكون هناك حالة حيث اختيار حرف واحد (أقول "ب") يؤدي إلى مزيد من المعلومات من الآخر (أقول "a") على الرغم من "أ" يحدث في أكثر الكلمات الممكنة من "ب" لا.انا منفتح على هذا الاحتمال في الممارسة العملية أيضا.ثلاثة خوارزميات هو موضح أعلاه تفترض أن لا يحدث هذا يرجع ذلك إلى حقيقة أن تخمين الصحيح يميل إلى تسفر عن مزيد من المعلومات من أحد غير صحيحة (أيالموضعية المعلومات حول الحرف الصحيح هو عادة أفضل من "هذه الرسالة ليست في كلمة").ولكن خوارزمية الأمثل لا تحتاج إلى جعل هذا الافتراض.

Answer 1

فمن الممكن لحساب الاستراتيجية المثلى ، ولكن الحساب قد تكون مكثفة إلى حد ما, وأنا لست متأكدا ما إذا كان سوف تعطيك الكثير من الربح أكثر من بسيطة الاستدلال.سأشرح كيف أدناه.الفكرة الرئيسية هو استخدام البرمجة الديناميكية.

القطعية استراتيجيات

اسمحوا لي أن أبدأ أولا مع الحالة الخاصة القطعية استراتيجيات اختيار الحرف الذي لتخمين المقبل ، كما أنها أسهل لتحليل.هذا سيتيح لنا الودية قبل أن ننتقل إلى العشوائية استراتيجيات (التي ربما تكون متفوقة).

الدولة من اللعبة في أي لحظة يمكن تلخيصها من قبل الزوج $(g,r)$, حيث $g$ هو مجموعة من الرسائل التي قد تفكر حتى الآن ، $r$ هو الردود (أي تسلسل من الفراغات و رسائل من $g$ وأن تكون مرئية لاعب).أمر من الماضي التخمينات لا يهم (والذي هو السبب في أنه يكفي أن يكون لديك مجموعة $g$ من الماضي التخمينات).ونحن سوف نقول ان كلمة $w$ يتسق مع $(g,r)$ إذا كان لا يزال ممكنا ، أي إذا كان الخصم هو كلمة $w$ و جعل التخمينات في $g$, ثم سوف تحصل على استجابة $r$.

السماح $p(g,r)=1$ إذا كان من الممكن أن يفوز من هنا ، إذا بدءا من الدولة $(g,r)$.وهذا يعني أن هناك استراتيجية للفوز:حيث لا يهم أي كلمة الخصم يفكر في (طالما أنها تتفق مع $(g,r)$), عدد التخمينات خاطئة قمت بها حتى الآن, بالإضافة إلى عدد وجعل لكم في المستقبل مع هذه الاستراتيجية ، لن يتجاوز الحد الأعلى.وإلا تحديد $p(g,r)=0$.

الآن يمكنك حساب $p(g,r)$ مع البرمجة الديناميكية باستخدام تكرار علاقة

$$p(g,r) = \bigvee_a \bigwedge_{(ز'r')} p(g'r'),$$

حيث $a$ نطاقات على جميع الحروف لا في $g$ (أي كل الاحتمالات والتي رسالة إلى تخمين المقبل) ، $(ز'r')$ نطاقات على كل الردود المحتملة إذا كنت تخمين $a$ التالي (أي ، $g'=غ\كأس \{a\}$, ونحن مجموعة أكثر من كل الكلمات $w$ التي تتفق مع $(g,r)$ وحساب الرد $r$ إلى التخمينات $g'$ إذا كانت الكلمة $w$).

على وجه الخصوص, أقترح عليك حساب $p(g,r)$ باستخدام البحث المتعمق الأول و التحفيظ.ثم ، $p(\emptyset, - - \cdots -)$ سوف أقول لكم ما إذا كان من الممكن الفوز في الحد الأعلى ، بغض النظر عن كلمة الخصم يختار.من خلال تتبع حساب المتخلفة ، يمكنك إعادة بناء الاستراتيجية المثلى.

هل هذا ممكن ؟ أتوقع أنه هو.أعتقد عدد ممكن من الدول $(g,r)$ ليست كبيرة جدا.(على وجه الخصوص ، يمكنك تجاهل الدول $(g,r)$ حيث كنت قد قدمت بالفعل الكثير من التخمينات غير صحيحة ، أي الدولة حيث لا يوجد سوى كلمة واحدة هي متسقة مع تلك الدولة تلقائيا الفوز, لذلك لا تحتاج إلى مزيد من التحليل.) كما الأمثل نظرا الدولة $(g,r)$, يمكنك محاولة تعداد كل الكلمات $w$ التي تتفق معهم ومحاكاة بعض ثابت ارشادي و تحقق ما إذا كان سيفوز في كل كلمة ؛ أنا لست بحاجة إلى أن تفعل أي مزيد من العمق أولا اجتياز ويمكنك على الفور مارك $p(g,r)=1$.أيضا, أنت فقط تحتاج إلى النظر في التخمينات $a$ التي تظهر في كلمة واحدة على الأقل يتفق مع $(g,r)$.

لذلك ينبغي أن تكون واضحة جدا لحساب الأمثل القطعية الاستراتيجية.

العشوائية استراتيجيات

يمكننا تتبع نفس الأسلوب في التعامل مع العشوائية الاستراتيجيات لكن الأمر معقد أكثر من ذلك.دعونا الآن $p(g,r)$ للدلالة على احتمال الفوز من هنا إذا أردنا استخدام الاستراتيجيات المثلى من هنا.يمكننا مرة أخرى حساب هذا باستخدام البرمجة الديناميكية.

الفرق الرئيسي هو في تكرار علاقة حيث نحسب $p(g,r)$ من كميات $p(g'r')$ حيث $(ز'r')$ مجموعة أكثر من جميع الدول التي يمكن أن تحدث بعد التخمين خطاب واحد.هنا لدينا لعبة بسيطة لعبة اثنين من لاعب.أولا نختار التوزيع الاحتمالي على الحروف في $g$.ثم الخصم يرى التوزيع لدينا ، يختار التوزيع على الكلمات $w$ التي تتفق مع $(g,r)$.لدينا مردود (مقدار الخصم يفقد) يساوي احتمال أن نفوز من هنا على إعطاء تلك الخيارات.لاحظ أن هذا يمكن حسابها من $p(g'r')$ القيم.اتضح أنه منذ نذهب أولا و الخصم يرى لدينا خيار الخصم لا يحتاج إلى العشوائية الاستراتيجية ؛ فإنها يمكن أن تفعل بشكل جيد على قدم المساواة مع حتمية استراتيجية ، أي عن طريق اختيار كلمة واحدة $w$ على أساس التوزيع لدينا.ثم إذا كنا شكل مصفوفة $م$ حيث $M_{w,أنا}$ يحمل احتمال الفوز إذا اخترنا الرسالة $i$ القادم والخصم يختار كلمة $w$;يمكننا ملء $M_{w,أنا}$ كما $p(g'r')$ حيث $g'=غ \كأس \{أنا\}$ و $r$ هو الرد تخمين $g'$ إذا كانت الكلمة $w$.ثم نسعى إلى حل الأمثل المشكلة $$\max_v \min_w (Mv)_w = -\min_v \max_w -(Mv)_w = -\min_v \|-Mv\|_\infty.$$ هذا يمكن حلها باستخدام البرمجة الخطية.لذا يمكننا حساب $p(g,r)$ باستخدام البرمجة الخطية من القيم $p(g'r')$ حيث $g'$ هو أحد أكبر من $g$.

وضع كل هذا معا ، سنستخدم اجتياز أول عمق مع التحفيظ (أو البرمجة الديناميكية) باستخدام البرمجة الخطية في كل خطوة لحل 2 لعبة لاعب.هذا يعطينا الأمثل العشوائية استراتيجية لعب الجلاد.

مما أدى حساب قد تكون مكلفة جدا ، كما أنه يتطلب مليارات أو تريليونات من الخطوات ، حيث حل البرنامج الخطي في كل خطوة.لذلك أنا لا أعرف ما إذا كان واقعيا أن استخدامه في الممارسة العملية.

بعض التحسينات ممكنة ، كما اقترح @j_random_hacker.يمكنك أولا حساب $p(g,r)$ بالنسبة القطعية الاستراتيجيات ؛ ثم أنت بحاجة فقط للنظر في العشوائية استراتيجيات الدول $(g,r)$ حيث $p(g,r)=0$.

ارشادي استراتيجيات

يمكنك سرد بعض معقول الاستدلال على اختيار الاستراتيجية.هنا هو واحد من الكشف عن مجريات الأمور.نظرا الدولة $(g,r)$, تعداد كل الاحتمالات القادمة تخمين $a \لافي g$.دعونا نركز على حرف واحد ، $a$.ثم لكل $(ز'r')$ التي يمكن أن تحدث على النحو التالي الدولة بعد التخمين $a$ (حتى $g'=غ\كأس \{a\}$) عدد الكلمات $w$ بما يتفق مع $(ز'r')$;اتخاذ أقصى أكثر من هذه الأرقام ، واستخدام ذلك الاعتماد المرتبطة $a$.عن مجريات الأمور الاستراتيجية هو اختيار الرسالة $a$ التي تعول هو أصغر.

الحوسبة العدد المتوقع من الأخطاء

يمكنك حساب العدد المتوقع من الأخطاء معين العشوائية الاستراتيجية باستخدام البرمجة الديناميكية.تفاصيل مماثلة أعلاه ، ولكن تكرار علاقة يصبح أكثر بساطة:يصبح

$$p(g,r) = \min_w \mathbb{E}[p(g'r')],$$

حيث $w$ يتراوح فوق كل الكلمات متسقة مع $(g,r)$, ، $(ز'r')$ هو التوزيع على الدولة القادمة إذا كانت الكلمة $w$ و الحرف التالي خمنت يتم اختياره من قبل الاستراتيجية الخاصة بك.بالنظر إلى استراتيجية الخاص بك و كلمة $w$, ، فمن السهل لحساب التوزيع على التخمينات وبالتالي الحصول على التوزيع التالي الدول, لذلك فمن السهل لحساب $\mathbb{E}[p(g'r')]$.