5

ワードゲームゴーストをどのように解決できますか? Ghostは 2 人用の単語ゲームです。プレーヤーは順番に、成長する単語の断片に文字を追加します。

ランドール・マンローの引用

ゴーストをプレイするには、文字を交互に言います。最初に (a) 単語を綴るか、(b) 単語の先頭にならない文字列を作成した人が負けです。つまり、単語を交互に作成し、常に単語に向かって作業する必要がありますが、それを終わらせることはできません. プレイヤーが 1 文字と 2 文字を交互に使用するサンプル ゲーム:

GAME — プレイヤー 1 が「ゲーム」と綴ると負ける</p>

ABSORB — プレイヤー 2 は「ABSORB」と綴ると負けます</p>

BZ-「チャレンジ」 — プレイヤー 1 は、「Z」を見て、「チャレンジ」と言います。意味は「あなたは言葉に向かって構築していないと思います。「BZ」で始まる単語に名前を付けて、ただのでっち上げではないことを証明してください。」プレイヤー 2 はできず、負けます。もし彼ができれば、彼は勝つだろう.

その後、マンローは、フライト中に（特定の辞書に対して）ゲームを解いたことを自慢します。彼

  • 最初のプレイヤーが常に勝つことができると主張する
  • 最初のプレーヤーが勝利を保証するために使用できる短いクリブシートを展示します
  • 最初のプレーヤーが間違った場合に、2 番目のプレーヤーが勝つために使用できる短いクリブ シートを表示します。

たとえば、最初のプレーヤーが「L」で開始した場合、2 番目のプレーヤーは別の「L」で応答でき、最初のプレーヤーは「LLAMA」で負けることになります。

Munroe は彼のアルゴリズムやコードを共有しませんでした :( 彼はどのように Ghost を解決したのですか?

単語フラグメントの前に文字を追加できる、より難しいバリアントもあります。

4

3 に答える 3

4

辞書を解くには--

ルート ノードが文字ではないツリー構造を作成し、各子ノードは単語内の次の文字をツリーに追加した結果です。

リーフ ノードは完全な単語です (完全な単語でもある初期サブセットを持つ単語は破棄できます)。

完全なツリーを構築し、すべてのリーフ ノードを取得すると、奇数の文字を持つリーフ ノードがプレーヤー 2 の目標になり、偶数の文字を持つノードがプレーヤー 1 の目標になります。

レベルが上がります。特定のノードの下にあるすべてのノードがプレーヤー x のゴールである場合、そのノードもプレーヤー x のゴールになります。または、特定のノードの下にあるノードのいずれかがプレーヤー x のゴールであり、ノードがプレーヤー x のターンにヒットする場合、そのノードはプレーヤー x のゴールになります。

プレイヤー 1 の目標が 1 つのキャラクター ノードである場合、プレイヤー 1 は常にゲームに勝つことができます。

于 2012-07-05T16:31:49.843 に答える
1

辞書内のすべての単語からツリー (トライ) を構築します。

ツリー内のすべてのノードを、プレーヤー 1 または 2 の勝者として段階的にマークします。

  • リーフでは、ゲームの結果が既にわかっているので、単にそれらをマークします。
  • 葉のすべての子葉が満たされると、結果がわかります。次の動きをしているプレーヤーの勝者の子葉が少なくとも 1 つある場合、問題の親葉がその人の勝者であり、それ以外の場合は他のプレーヤーの勝者です。
  • これらの 2 つのステップに続くツリーのポストオーダー トラバーサルにより、すべてのツリーを埋めることができ、各ノードで各プレイヤーの勝利ステップを決定できます。

ルート ノード (空の単語) をチェックして、誰が勝利戦略を持っているかを確認します (他のプレイヤーが完全にプレーすると仮定します)。

于 2012-07-05T16:32:24.197 に答える
0

解決しました！私は1年前に前半をやりましたが、今日は簡潔な勝利戦略に剪定する方法を考えました

https://github.com/hickford/ghost

于 2012-07-05T22:39:43.277 に答える