ハングマンワードゲームをプレイするための最適アルゴリズムは何ですか？

Question

ゲームをプレイしているとします hangman 。私の対戦相手と私は両方ともゲーム中に辞書にアクセスできます。私の対戦相手は、私が彼の秘密の言葉を推測するために使用するアルゴリズムの知識を持って辞書から単語を選びます。私の対戦相手が単語を選んだら、私は単語の長さだけを与えています。私はその言葉の中にいると思う手紙を推測することができます、そしてそれが言葉の中にあるならば、私の対戦相手はその単語のその文字のすべての位置を識別します。私が言葉の中にない手紙を推測した場合、それは1つの間違いとして数えられています。私があまりにも多くの間違いの前に勝つことができるならば。

私の対戦相手の目標は、間違いの数を最大にする単語を選ぶことです（不正な推測）私は言葉を推測できるようになる前に行ってください。私の目標はそれらを最小限に抑えることです。 （伝統的に、間違いの数がある場合は、いくつかの数字である場合はゲームを失いますが、その制約をリラックスさせることができます。）

手紙推測のための3つのアルゴリズムを考えます。これらは私が考えた主なものですが、おそらくもっと多くのものがあります、そして私は歓迎します。 3つのアルゴリズムすべてで、最初のステップは秘密の単語と同じ長さの単語のリストを集めることです。次に、アルファベット内の文字ごとに、その文字を含む辞書内の単語数を数えます。例えば、5000は「a」、300は「B」などを含む。ここでそれはPythonにあります：

    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

. その後、3つのアルゴリズムが発散する場所です。

1. 最初のアルゴリズムでは、残りの単語のほとんどの数が含まれている文字を推測します。だから5000の残りの単語に「A」が含まれていて、そのさまざまな文字が含まれていない場合は、毎回「A」を選びます。 「a」が正しい場合、これは私たちがリストをさらにフィルタリングできる位置情報を提供します。たとえば、 ".. .."と一致するすべての単語でリストをフィルタリングすることができます。 （ドットは不明です。）「a」が正しくない場合は、 "A"を含むすべての単語を除外します。同数の単語にネクタイがある場合には、文字がアルファベット順に選択されます。だから私たちが言葉が「.ay」と一致することを知っていれば、私たちはただアルファベット順の言葉を推測します。

2. これは最初のアルゴリズムとはわずかに異なるだけです。常にアルファベット順序付けを選択する代わりに、Tieの場合はランダムに文字を選択します。これは私たちの対戦相手が私たちが選ぶものを知らないという利点を持っています。最初の戦略では、「光線」は常に「日」より優れています。これはその問題を回避します。

3. この場合は、その文字を含む単語の数に比例した確率で文字を選びます。 「A」を含む単語の数と「B」を含む単語の数を集計したとき、「A」が開始された戦略1と2では、「A」が見つかりました。 「100％の時間。代わりに、私たちはまだ複数の時間を選択しますが、10倍の単語で見つかったとしても "z"を選ぶでしょう。私はこの戦略が最適であるが疑わしいがそれは2010年の研究で使用されました

だから私は2つの質問があります：

1. 私がこの戦略を知っていると仮定して私がこの戦略を知っていると仮定してを使うべき最適なレター推測戦略は何ですか？これで私たちは秘密の言葉を推測するのにかかる推測の平均数を最小にしたいです。
2. 与えられた単語の場合、「支払う」と言って、Misce Miskの平均数は何ですか？このシミュレーションを何度も実行して結果を平均化するのとは対照的に、mを計算する閉形式の方法はありますか？

明確化

• 英語辞書を使用できます。たとえば、この英語辞書84K単語。あいまいさのために慎重に選択された辞書のサブセットもまた面白いかもしれませんが、この質問の範囲外です。
• 単語が辞書内にある限り、単語サイズに制約はありません。推測は、彼が推測を始める前に単語のサイズを知っています。
• 単語サイズとは無関係の間違いの総数だけです。もっと長い単語のためのより多くのチャンスを取得しない、またはより短いもののためのチャンスが少ないです。
• 私は平均間違い数を最小限に抑えることに興味があります。等価に小さい平均間の間違いを有する2つの最適なアルゴリズムがある場合、両方とも許容可能である。
• 原則として、「B」よりも可能な単語よりも「A」が発生していても、1文字（「B」）を選択する状況がある状況がある場合は可能です（「A」）。します。私は実際にもこの可能性にも開かれています。上記の3つのアルゴリズムはTHと仮定します

正しい推測が間違ったものよりも多くの情報を生み出す傾向があるという事実のためには起こりません（すなわち、正しい文字に関する位置情報は通常、「この文字は「この文字は単語にはありません」）。しかし、最適なアルゴリズムはこの仮定をする必要はありません。

Answer 1

最適な戦略を計算することは可能ですが、計算はかなり集中的なものであり、それが単純なヒューリスティックであなたに大きな利益を与えるかどうかわからない。私は以下の方法を説明します。主なアイデアは動的プログラミングを使用することです。

決定論的戦略

次にどの文字を推測するのかを選択するための特別なケースで最初に始めましょう。これにより、ランダム化戦略（おそらく優れているでしょう）に進む前に、私たちに暖かさを与えます。

任意の時点でのゲームの状態は、ペア $（g、r）$ によって要約することができます。ここで、 $ g $ はこれまでに推測された文字のセットで、 $ r $ は応答です（つまり、からの空白と文字のシーケンスです。 $ G $ プレイヤーに表示されます）。過去の推測の順序は関係ありません（つまり、SPAN Class="Math-Container">過去の推測の$ G $ を持っているのに十分です）。 $ w $ は、 $（g、r）$ と一致しているとします。可能なまま、対戦相手の単語が $ w $ の場合、 $ g $ の推測を行う場合それから、応答が $ r $ 。

$ p（g、r）= 1 $ ここから勝つことが、state $（g、r）$ 。それは勝つための戦略が存在することを意味します。対戦相手がどの単語であっても $（g、r）$ x / span>と一致している限り） 、これまでに行った間違った推測の数と、この戦略で将来的に行った番号は、上限を超えない。それ以外の場合は、 $ p（g、r）= 0 $ 。

$ p（g、r）$ を繰り返しリレーション

を使って、動的プログラミングで$ p（g、r）$

$$ p（g、r）=bigvee_a \ bigwedge_ {（g '、r'）} p（g '、r'）、$$

ここで、 $ A $ $ g $ に含まれていません（つまり、すべての可能性があります。次の通り）、および $（g '、r'）$ $ $を推測すると、可能なすべての応答に沿って範囲で及びます。 $ 次の（つまり、 $ g '= g \ cup \ {a \}} $ 、そして私たちはすべての単語を覆って $ W $ $（g、r）$ と一致し、応答を計算します> $ g '$ を推測するための$ r' $ は $ w $ の場合。

特に、 $ p（g、r）$ を、最初の検索とメモリを使用して計算します。その後、 $ p（\ emptyset、 - - - \ cdots - ）$ は、相手が選択されていても、上限に勝つことが可能であるかどうかをあなたに伝えます。 。計算を後退させることによって、あなたは最適な戦略を再構築することができます。

これは実現可能ですか？私はそれが期待しています。可能な状態の数 $（g、r）$ が大きすぎないと思います。 （特に、状態 $（g、r）$ を無視することができます。ここで、誤った推測が多すぎると、1つの単語だけが一致している様子その状態は自動的に勝利であるため、 $（g、r）$ を指定して、最適化として、列挙を試すことができます。すべての単語 $ w $ は、それらと一致していて、いくつかの固定ヒューリスティックをシミュレートし、それが各単語に対して勝つかどうかを確認します。もしそうであれば、それ以上の深さの最初のトラバーサルをする必要はなく、 $ p（g、r）= 1 $ にすぐにマークすることができます。また、 $ A $ $ a $ を考慮する必要があります。 $（g、 r）$ 。

だから最適な決定論的戦略を計算するのはかなり簡単であるべきです。

ランダム化戦略

ランダム化戦略を処理するために同様の方法に従うことができますが、もう少し関与しています。ここから最適な戦略を使用すると、 $ p（g、r）$ がここから勝利する可能性を表します。動的プログラミングを使用して再度計算することができます。

鍵の違いは、 $ p（g、r）$ を計算します $を計算する繰り返し関係です。 p（g '、r'）$ ここで、 $（g '、r'）$ OCCの可能性があるすべての状態に及びます

もう1つの手紙を推測した後、次にウル。ここで私たちはシンプルな2プレイヤーゲームを持っています。まず、 $ g $ ではない文字にわたって確率分布を選択します。それから対戦相手は私たちの配布を見て、 $ w $ の配信を選択します。 $（g、r） $ 。私たちのペイオフ（そして対戦相手が失う量）は、それらの選択が与えられたことに私たちがここから勝つ可能性に等しい。これは $ p（g '、r'）$ 値から計算できることに注意してください。それは私たちが最初に行ってから対戦相手が私たちの選択を見ているので、相手は無作為化戦略を必要としません。それらは、私たちの配布に基づいて、決定論的な戦略、すなわち、単一の単語 $ w $ を選ぶことによって同等によくすることができます。次に、Matrix $ m $ を作成した場合、 $ m_ {w、i} $ の確率を保持します。 winning $ i $ nextとword $ w $ を選択します。 $ m_ {w、i} $ を記入することができます $ p（g '、r'）$ $ g '= g \ cup \ {i \} $ と $ 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 $ 。

発見的戦略

戦略を選択するための合理的なヒューリスティックをいくつかリストしました。これがもう1つの発見的です。状態 $（g、r）$ を考えると、次の推測 $ a \ notin g $ 。単一文字 $ a $ に焦点を当てましょう。その後、 $ a $ <$ $ <$ $ <$ <$ < $ ごとに、 $（g '、r'）$ / SPAN>（span class="math-container"> $ g '= g \ cup \ {a \} $ ）、 $の数を数えます。 $（g '、r'）$ と一致しています。これらの数値を超える最大値を取り、 $ a $ に関連付けられているカウントとして使用します。ヒューリスティックな戦略は、その数が最小の文字 $ a $ を選択することです。

予想される間違い数を計算する

動的プログラミングを使用して、特定のランダム化戦略の期待数を計算できます。詳細は上記に似ていますが、再発関係が簡単になります。

になります

$$ p（g、r）=min_w \ mathbb {e} [p（g '、r'）]、$$

ここで、 $ w $ は、 $（g、r）$ と一致するすべての単語を渡します。 $（g '、r'）$ は、単語が $ w $ そして推測された次の手紙はあなたの戦略によって選ばれます。あなたの戦略と $ w $ を考えると、推測時の配布を計算し、それによって次の状態での配布が得られますので、 $ \ mathbb {e} [P（g '、r'）] $ 。