19

ハングマンというゲームでは、貪欲な文字頻度アルゴリズムは、勝率が最も高いアルゴリズムと同等でしょうか?

正しい答えを推測する可能性を高めるために、残りの命の保存を犠牲にする価値がある場合はありますか?

問題のさらなる明確化:

  • 推測するために選択された単語は、既知の辞書から取得されています。
  • N 個の命が与えられているので、N 個の間違いを犯さずに単語のすべての文字を推測できる確率を最大化する必要があります (つまり、正しい推測の数に制限はありません)。
  • この演習のために、辞書内の各単語の確率は等しくなります (つまり、単語はランダムに選択されます)。
    • より困難な演習は、悪意のある全知の単語選択者に対する戦略を考え出すことです (ここでそれを求めているわけではありません)。

動機: この質問は、 http: //www.datagenetics.com/blog/april12012/index.html での興味深い議論に触発されています。

彼らは、単語ゲーム「ハングマン」を最適に解くためのアルゴリズムを提案しています。

彼らの戦略は次のように要約できます（明確化のために編集）：

  • 単語が特定の辞書から引き出されたと仮定できます
  • 私たちは単語の文字数を知っています
  • 文字数が正しくない単語を辞書からすべて削除します。
  • 辞書の残りのサブセット内の単語数が最も多い、まだ推測されていない文字を選択します。
  • この手紙が現われれば、私たちはその場所を知っています。
  • この文字が出現しない場合、単語には出現しないことがわかります。
  • この正しいパターンに正確に適合しない辞書サブセット内のすべての単語を削除し、繰り返します。
  • 2 つ (またはそれ以上) の文字が同じ頻度で出現する場合、アルゴリズムは位置のより深い分析を実行して、どちらが優先されるかを判断します (それが妥当な場合)。

各段階で、残りの可能な単語の最大数に出現する文字 (以前は推測されていません) を推測しています。

このアルゴリズムを気に入る動機はいくつかあります。人が命を失う可能性は常に最小限です。

しかし、これが必ずしも最善の解決策であるとは限らないことに気がつきました: (一定数の生活の中で) 単語を推測しようとしている場合、最も頻繁に出現する文字が最も有用な文字であるとは限りません。残りの使用可能な単語を区別します。

ただし、可能な限り命を失うことを回避するのが適切であるように思われるため、よくわかりません. 最適な戦略によって、勝つためのより良い機会のために命を犠牲にすることができるでしょうか?

質問: この貪欲なアルゴリズムは、勝利の可能性が最も高いアルゴリズムと同等でしょうか? そしてそれを証明できますか？

ディクショナリとゲームの例は、反証を示すのに理想的です。

4

8 に答える 8

10

次のディクショナリを想定します: ABC ABD AEF EGH. (推測されていない文字は大文字にします。)
ライフが 1 つしかないと仮定します (証明が非常に簡単になります...)。

上で提案されたアルゴリズム:

から始めてA、(1/4) 負けるかaBC aBD aEF(3/4) 残ります。
推測Bして負ける (1/3) か、残っているabC abD(2/3)。負けるか (1/2) 勝つか (1/2) かを当て
ます。 勝つ確率: 3/4 * 2/3 * 1/2 = 1/4.CD

別のことを試してください：

から開始するとE、(1/2) 負けるか、(1/2) 残りAeF eGHます。
これで、何を推測して勝つかがわかります。
勝つ確率: 1/2。

明らかに、提案されたアルゴリズムは最適ではありません。

于 2012-03-30T21:36:50.633 に答える
8

「ハングマン」のゲームとは何かについて、いくつかの重要な仮定をしなければなりません。

  • 推測する必要がある単語は 1 つだけですか、それともフレーズを推測する必要がありますか?
  • いくつかの単語は他の単語よりも可能性が高いですか?

覚えておくべきことの 1 つは、正しい文字を選択すれば、推測を失うことはないということです。

1 単語 & 等確率のケースの解決策を提供します。2 単語のケースは、現在の辞書のデカルト積に等しい新しい辞書を作成することなどによって一般化できます。他よりも可能性が高いケースは、少しの確率で一般化できます。

アルゴリズムを定義する前に、リダクションの概念を定義します。文字 L1、L2、L3、...LN をすべて 1 回で推測する場合、辞書をより小さな辞書に減らします。一部の単語が削除され、さらに一部の文字も削除される可能性があります。たとえば、辞書が{dog, cat, rat}あり、 を推測aした場合、推測が真の場合は {d,g} を除外し、偽の場合は {c,r,t} も除外します。

最適なアルゴリズムは次のとおりです。

  • ゲームツリーを考える
  • [#guesses left == 1] のすべてのノードを確認します。
  • ノードがない場合、ゲームは不可能です。ノードがある場合、それがあなたの答えです

もちろん、それがどのゲームでも解決する方法であり、ほとんどの場合、指数関数的なサイズ要件のために扱いにくいものです。これを完全に再現しない限り、最適化することはできません。また、2 つ以上先を「見ない」戦略でこれを再現できるとは思えません。ただし、次のように最適な戦略を近似することを試みることができます。

各ステップで次の手順を繰り返します。

  • 各文字を検討してください: 期待されるペナルティごとに期待される辞書削減を最大化する文字を選択してください: つまり、( frac words with L#words without L+frac words without L#words with L )/( # words without L/ # words total) を最大化する文字 L を選択してください... すべての場合、これは無限になる可能性があることに注意してください。単語には特定の文字が含まれています。この場合、ペナルティはないので推測してください。
  • 推測して、更新されたボードの状態を取得します
  • 新しいボードによって無効にされたすべての単語を削除します

もちろん、あなたの辞書に複数の2^[max number of guesses]エントリがある場合、「ハングマン」ゲームは等確率の世界ではほとんど不可能なので (辞書が非常に制約されていない限り)、不等確率の世界で作業する必要があります。この世界では、あなたが行う除去の量を最大化するのではなく、「期待される驚き」(エントロピーとも呼ばれます) を最大化します。各単語に事前確率を関連付けます (たとえば、単語が「putrescent」である確率が 0.00001 で、単語が「hangman」である確率が 0.002 であるとします)。サプライズは、ビット単位で測定されたチャンス (チャンスの負の対数) に等しくなります。推測に対する答えは、文字がないか、1 文字か、または複数の文字 (多くの可能性) のいずれかになります。したがって：

  • 可能な推測ごとに、その推測がもたらす効果を検討します
  • 推測の可能な結果ごとに、その結​​果の確率を検討します。たとえば、3 文字の単語の「A」を推測した場合、セット内の考えられる結果をそれぞれ考慮する必要があります{A__, _A_, __A, AA_, A_A, _AA, AAA}。各結果について、ベイズの規則と新しい可能な辞書を使用して確率を計算します (たとえば、_A_:{cAt, bAt, rAt, ...}andA__:{Art, Ark, Arm, ...}などの辞書がある場合)。これらの新しい辞書のそれぞれには、次の形式の尤度比もありsize(postOutcomeDictionary dictionary)/size(preOutcomeDictionary)ます。この比率の負の対数は、選択によって伝えられる情報量 (ビット単位) です。
  • したがって、予想されるコストごとに、得られる情報量 (ビット単位) の比率を最大化する必要があります (コスト ペナルティは、失敗した場合は 1、失敗した場合は 0 です)。推測ごと、および推測の結果ごとに得られる情報ビットは ですbitsGainedFromOutcome[i] = -log(size(postOutcomeDictionary)/size(preOutcomeDictionary))。これらの加重合計を取りsum{i}( prob(outcome[i])*bitsGainedFromOutcome[i] )、次に、間違っている確率で割ります: prob(outcome=='___')。
  • 最小の文字を選択しsum{i}( prob(outcome[i])*bitsGainedFromOutcome[i] )/prob(outcome=='___')ます。これが無限大の場合、失うものは何もなく、自動的に選択されます。

あなたの質問に答えるには：

> Hangman というゲームでは、貪欲な文字頻度アルゴリズムは、勝率が最も高いアルゴリズムと同等でしょうか?

明らかにそうではありません: 辞書が

cATs
bATs
rATs
vATs
sATe
mole
vole
role

aあなたのアルゴリズムはまたはを推測しますt。これにより、5/8 の確率で無料で辞書が 5/8 サイズに縮小され、3/8 の確率で辞書が 3/8 サイズに縮小され、コストは 1 になります。最も多くの情報を明らかにする文字。この場合、S を推測する必要があります。これは、4/8 の確率で無料で辞書を 4/8 サイズに縮小し、1/8 の確率で無料で辞書を 1/8 サイズに縮小し、3/ 8 の確率で、コスト 1 で辞書を 3/8 サイズに縮小します。これは厳密に優れています。

編集:英語の辞書の例(上記)を使用して、これが人為的ではないことを示したいと思い、非厳密な平等にとらわれることなく例から推定できると想定しました。ただし、明確な反例があります。2000 語あります。A1000語には、そもそも文字が含まれています。他の 1000 語には、他の場所にB埋め込まれた s の一意の組み合わせが含まれています。たとえば、、、、、、、などです。 は、ランダム?B???に選択された文字を表します??B??。最初の ? には 1 つの単語 (? が「A」) を除いて sがないため、 s の頻度は s の頻度より厳密に大きくなります。提案されたアルゴリズムは???B?????B?BB???B?B??AABA{50%: Choices_halved, 50%: Choices_halved & lose_one_life} という結果になりますが、このアルゴリズムではB、{50%: YOU_WIN, 50%: Choices_halved & lose_one_life} という結果になる選択が指示されます。パーセンテージはごくわずかに四捨五入されています。(いいえ、2 文字の単語が「頻度」に 2 回寄与することはありませんが、非常識な定義の下であったとしても、単語を で開始することで、この例を簡単に変更できますAAA...A。)

(コメントに関して: この例では、確率を互いに任意に近づけることができるため、「999/2000」などの厳密な平等について文句を言うのは不合理です。)

(これは面白い補足説明を指摘しています: 辞書が時々絞首刑執行人を不可能にするほど大きい場合、戦略は推測できるとは思わない推測を破棄する必要があります。たとえば、残りの手数が 2 つしかない場合、可能な限り高い確率の仮定を行うべきであり、2 回以上の移動に相当する驚きのビットを持つサブツリーを排除します。)

于 2012-03-30T14:30:41.943 に答える
3

文字を推測する代わりに単語を推測しようとするあなたの考えについては、最初の試行またはそのようなものから単語を推測するいくつかの孤立したケースがあるかもしれませんが、これは平均的なケースでそのアルゴリズムを改善しません. 期待確率についてです。

(Lajos によって投稿されたバージョンで) そのアルゴリズムに行うことができるいくつかの改善は、試行される文字のより多くの情報に基づいた選択です。
これは、もう 1 つの重みを追加することで実現できます。各単語の使用法を言語の語彙と見なします。

たとえば、技術、医療、法律などの単語は、可能性がはるかに低くなります。

この辞書を取り上げます (使用法の重みの例をいくつか示します)。

frost    6
guilt    5
genes    1
fever    2
meter    1

eこれが最も頻度の高い文字であるため、選択されます。これは、医学用語のみを残すことを意味しますが、これは非常にありそうもないことです。しかし、決定が下された場合：

weight(letter) = w * frequency +
              (1 - w) * sum( usage_weight(word) where letter in word )

その場合、ほとんどの場合、t選択されます。

理由（としましょうw = 0.2）：

weight(e) = 0.2 * 3   +   0.8 * (1 + 2 + 1)
          = 3
weight(r) = 0.2 * 3   +   0.8 * (1 + 2 + 6)
          = 7.8
weight(t) = 0.2 * 3   +   0.8 * (1 + 5 + 6)
          = 10.2

注: もちろん、frequency / num_words正確な重量測定を行うために、正規化された重量を使用する必要があります。

注: このアルゴリズムは対戦相手に適応させることができ、また適応させる必要があります。

  • 人間と対戦するときは、より一般的な単語の重みが高くなります
  • AI と対戦する場合は、難易度によって異なります。
    • 易しいレベルでいつもの言葉を目指す
    • 難しいレベルで珍しい言葉を目指す
于 2012-03-30T13:22:29.510 に答える
3

ハングマンを最適に解決するスクリプトを作成しました[github]。

私の基本的な戦略はこれです：

  • ..e. のような文字が試行されたパターンの場合: e,s,t
  • n 桁のみの単語 (この場合は 5) と照合します
  • 可能な単語のリストを作成する
    • 提供された情報から正規表現を作成します
    • この場合、それは[^est][^est]e[^est][^est]
    • この正規表現に一致する単語の単語リストを解析します
  • 各単語を循環し、すべての文字が出現する回数を数えます
  • あなたの最適な次の推測は、最も可能性の高い文字です
于 2012-03-31T19:53:15.057 に答える
0

いいえ、この貪欲なアルゴリズムはまったく最善ではありません。より良い解決策を提供することでそれを証明できます。

各ステップで、文字の数といくつかの文字を知っています。指定された位置に指定された文字があり、その長さが問題の単語の長さと一致する単語セットからすべての単語を選択します。選択した単語のサブセットから最も頻繁に使用される文字を選択し、与えられた文字について推測します。推測するたびに、推測された文字は推測済みとしてマークされ、今後再び推測されることはありません。このようにして、質問で説明されている貪欲なアルゴリズムよりも、生存の可能性がはるかに高くなります。

編集：

質問が明確になり、さらなる仕様が作成された後、アルゴリズムが最適であるという結論に達しました。

すべての正しい推測 (「良い文字」) を含み、間違った推測 (「悪い文字」) を含まない、指定された長さの単語が n 個ある場合、x 個の単語がまだ可能な単語の文字の頻度を見ることができます。最も頻度の高い文字を選択します。y 個の単語にその文字が含まれていたとします。

この場合、この推測の信頼率は y/n であり、他の文字の信頼率よりも大きく、生存の可能性が高くなります。したがって、そのようなステップが最適です。この精神でステップだけの一連のステップを作ると、一連のステップも最適になるので、このアルゴリズムが最適です。

ただし、追加情報 (単語の説明、または同じ単語が短期間に 2 回発生する可能性など) がある場合、このアルゴリズムは追加情報 (セット内のすべての単語) に基づいて強化できます。の単語には適合値 (追加情報に基づく確率) があり、単語内のすべての文字タイプは適合スコアに基づいて重み付けされます。

于 2012-03-30T12:46:04.703 に答える
0

答えは、貪欲なアルゴリズムが最善ではない理由を明確に示していますが、貪欲な道から外れた場合にどれだけ良くなるかについては答えていません.

コンピューターの対戦相手と対戦している場合、すべての単語が同じように可能性が高いと仮定すると. 4 文字の場合、6 命中の場合、2 番目に人気のある文字を単純に見るオプションがある場合、勝つ確率は 55.2% から 58.2% に増加し、もう 1 文字チェックする場合は 59.1% に増加します。

コード: https://gist.github.com/anitasv/c9b7cedba324ec852e470c3011187dfc

ENABLE1 (172820 語を含むスクラブル辞書) を 2 から 6 文字、0 から 10 の命、および 1 貪欲から 4 貪欲で使用して完全に分析すると、次の結果が得られます。もちろん、ライフが 25 の場合、すべての戦略は 100% の勝率と同等であるため、ライフが 10 を超えることはありません。貪欲度が 4 を超えると、確率がわずかに向上します。

letters, lives, 1-greedy, 2-greedy, 3-greedy, 4-greedy


2 letters 0 lives   3.1%    3.1%    3.1%    3.1%
2 letters 1 lives   7.2%    7.2%    7.2%    8.3%
2 letters 2 lives   13.5%   13.5%   13.5%   14.5%
2 letters 3 lives   21.8%   21.8%   22.9%   22.9%
2 letters 4 lives   32.2%   33.3%   33.3%   33.3%
2 letters 5 lives   45.8%   45.8%   45.8%   45.8%
2 letters 6 lives   57.2%   57.2%   57.2%   57.2%
2 letters 7 lives   67.7%   67.7%   67.7%   67.7%
2 letters 8 lives   76%     76%     76%     76%
2 letters 9 lives   84.3%   84.3%   84.3%   84.3%
2 letters 10 lives  90.6%   91.6%   91.6%   91.6%


3 letters 0 lives   0.9%    1.1%    1.1%    1.1%
3 letters 1 lives   3.4%    3.8%    3.9%    3.9%
3 letters 2 lives   7.6%    8.4%    8.6%    8.8%
3 letters 3 lives   13.7%   15%     15.1%   15.2%
3 letters 4 lives   21.6%   22.8%   23.3%   23.5%
3 letters 5 lives   30.3%   32.3%   32.8%   32.8%
3 letters 6 lives   40.5%   42%     42.3%   42.5%
3 letters 7 lives   50.2%   51.4%   51.8%   51.9%
3 letters 8 lives   59.6%   60.9%   61.1%   61.3%
3 letters 9 lives   68.7%   69.8%   70.4%   70.5%
3 letters 10 lives  77%     78.3%   78.9%   79.2%


4 letters 0 lives   0.8%    1%      1.1%    1.1%
4 letters 1 lives   3.7%    4.3%    4.4%    4.5%
4 letters 2 lives   9.1%    10.2%   10.6%   10.7%
4 letters 3 lives   18%     19.4%   20.1%   20.3%
4 letters 4 lives   29.6%   31.3%   32.1%   32.3%
4 letters 5 lives   42.2%   44.8%   45.6%   45.7%
4 letters 6 lives   55.2%   58.2%   59.1%   59.2%
4 letters 7 lives   68%     70.4%   71.1%   71.2%
4 letters 8 lives   78%     80.2%   81%     81.1%
4 letters 9 lives   85.9%   87.8%   88.4%   88.7%
4 letters 10 lives  92.1%   93.3%   93.8%   93.9%


5 letters 0 lives   1.5%    1.8%    1.9%    1.9%
5 letters 1 lives   6.1%    7.5%    7.9%    8%
5 letters 2 lives   15.9%   18.3%   18.9%   19.2%
5 letters 3 lives   30.1%   34.1%   34.8%   34.9%
5 letters 4 lives   47.7%   51.5%   52.3%   52.5%
5 letters 5 lives   64.3%   67.4%   68.3%   68.5%
5 letters 6 lives   77.6%   80.2%   80.6%   80.8%
5 letters 7 lives   86.9%   88.6%   89.2%   89.4%
5 letters 8 lives   92.8%   94.1%   94.4%   94.5%
5 letters 9 lives   96.4%   97.1%   97.3%   97.3%
5 letters 10 lives  98.2%   98.6%   98.8%   98.8%


6 letters 0 lives   3.2%    3.7%    3.9%    3.9%
6 letters 1 lives   12.6%   14.3%   14.9%   15%
6 letters 2 lives   29.2%   32.2%   32.8%   33%
6 letters 3 lives   50.1%   53.4%   54.2%   54.4%
6 letters 4 lives   69.2%   72.4%   73.1%   73.2%
6 letters 5 lives   83.1%   85.5%   85.9%   86.1%
6 letters 6 lives   91.5%   92.9%   93.2%   93.2%
6 letters 7 lives   95.8%   96.5%   96.7%   96.8%
6 letters 8 lives   97.9%   98.3%   98.4%   98.5%
...
于 2020-01-03T12:26:18.540 に答える
-1

残りの有効な単語をほぼ同じサイズの2セットに分割する文字を選択します。位置情報を使用すると、2セット以上になる可能性があります。セットのサイズが1になるまで繰り返します。これが最良の方法です。証明は演習として残されています。

于 2012-03-30T12:55:22.760 に答える