ギルクエ第三段階攻略法の整理してみる~用語とか2

※この記事は,ルネサンス以前に書かれた記事です.ルネサンス後に通用する場合は十分ご注意ください※

ギルクエ第三段階攻略法のまとめの一環として,用語,概念の整理をしてます.

一行目がタイトルを蒸し返すような説明口調で恐縮です.メイプルさーちさんのRSS情報には記事のタイトルが載らず,何の話か分かり難いので,こういう説明を繰り込む処置を取ることにしました.申し訳ありませんが,お付き合いください.

前回は「手/フィルタ」について述べました.

ゲームをプレイする立場にいれば,次郎の「手」は比較的受け入れ易い用語だと思います.が,Holithy☆さんの「フィルタ」は,視点を変えないと分かり難いでしょうか.視点を変えてしまえば,これほどしっくり来る用語は他にないと思うのですがねぇ.

まず,賢者の噴水は四種四桁重複ありですので,全部で256通りの組み合わせがあります.正解はそのうちのどれかです.初手で「勲勲勲勲」を試すとすると,返ってくるヒントは「10,20,30,40,00」の5種類のうちのどれかになります(10は,正しいが1,間違いが0の意味).「10」が返ってくるのは,勲を一つだけ含む組み合わせです.「20」は同じく二つ,「30」は三つ,「40」は四つ(つまり正解).「00」は一つも含まない組み合わせです.

このように,初期状態では「正解の可能性のある組み合わせ」は256通りだったものを,初手で「勲勲勲勲」を試すことで,上記五つの部分集合に分けることができるのです(*1).別の手を試せば,別の複数の部分集合に分けられます.このように「正解の可能性のある組み合わせ」を部分集合に振り分けるルールが「手」であり,それゆえに,「フィルタ」という呼び名が相応しいのです.

しかし,ギルクエをプレイするだけのよいこのお友達に,このフィルタの概念を理解しろと言うのは酷な話ですので,へたれブログでは極力「手」を使うことにします.

 

さて,今回は「ヒント/パターン」について詰めてみましょう.

Holithy☆さんは明確に「パターン」と概念を持っていますが,実は次郎はそれに似た概念を強く意識してはいませんでした.Holithy☆さんの言う「パターン」を言葉で表そうとすると,「ヒント,ヒントの履歴」にでもなるのかな?ってところです.また,次郎法,次郎法V2を考えていた時に「パターン」という言葉をよく使っていましたが,これは「正解の可能性のある部分集合を特徴づけるもの」であって,Holithy☆さんのいう「パターン」とは似てもない非なるものです.

「ヒント,ヒントの履歴」が「パターン」だと言えば,まあ,当たらずと言えど遠からずでしょう.しかし,「パターン」はもっと広い概念を持つことができるはずです.「パターン」を「ヒント,ヒントの履歴」と見ることは,「パターン」の一側面しか見ていないことになるのではないかと思います.つまり,次郎もまだよく理解しきっていないのです.

この「パターン」という概念をHolithy☆さんが先に明確に持っていたというのは,凄い事です.やるべきことは,「正解の可能性のある集合に対してフィルターをかませて,最終的に要素が1の部分集合に分割する」ことです.これを逐次解法でやっていれば,常に「現時点での部分集合」が分かっているわけですので,過去のヒント履歴がなんであるかは,それほど重要視されません.というか,「現時点での部分集合」それこそが過去のヒント履歴の産物だからです(次郎法でもそうでしたから,強い意味のある概念として受け止めておりませんでした.他の文献を当たっても似たようなものです.もちろん,ゲーム用語としても定着した呼び名はありません).

現時点での部分集合は過去のフィルタとパターンで決定します.そして,次のフィルタは現時点での部分集合で決まります.つまり,過去のフィルタとパターンだけで次のフィルタが決まります.どのフィルタが最適化を検討するときは,やはり部分集合から判断するしかありませんが,それが決まってしまえば(というか,それを決めるのが賢者の噴水の解法を決めることですから)フィルタとパターンだけあれば十分という事です.

Holithy☆さんはパターンを二桁の数値で表現してます.最初は正しい数,見当たらない数の二桁でしたが,現在はヒットアンドブローの一般的な表現に従って,正しい数と間違っている数の二桁に移行しています.ただ,記号化方法については「一般的」と言えるものはないようで,Holithy☆さんの記法でいう「21」は「HHB」「H2B1」「BBW」などと書かれています.最後のB,WはBlackとWhiteのことで,Mastermindが正しい数だけ黒いピンを立て,間違いの数だけ白いピンを立てるルールことになっていることに由来するものでしょう.あのクヌースが1976年に書いたマスターマインドの解法に関する論文では,「BBW」の記法を使っています(*2).

ここからはHolithy☆さんの独自の記法になりますが,ヒントの履歴を”-”(ハイフン)で区切って,先頭に”p”をくっつけました.ハイフンで区切るのは見た目分かり易くするためです.最初は”h”をつけていましたが,”h12-10-12”みたいなパターンができると,一部のスプレッドシートが日付と勘違いしてしまって,資料整理に不便だったからだそうです.

フィルタ適用のルールが決まってしまうと,パターンだけで十分だという実例をお見せしましょう.

“p20-00-20-20-20-40” (次郎法)

はい,正解は?「勲食食勲」です.

  1. 初手「勲勲勲勲」,ヒント「2名正しい,2名見当たらない」→勲二つ確定
  2. 二手「書書書書」,ヒント「4名見当たらない」→書なし
  3. 三手「食食食食」,ヒント「2名正しい,2名見当たらない」→食二つ確定,勲と食のツーペアが確定
  4. 四手「勲勲食食」,ヒント「2名正しい,2名見当たらない」→ニコニコではない
  5. 五手「勲食勲食」,ヒント「2名正しい,2名見当たらない」→交互でもない,中二が確定
  6. 六手「勲食食勲」,クリア!

という流れを表しています.

ね?すごいでしょ.

さて,「手」と「パターン」を押さえたので,次回は本丸の「次回表」を取り上げます.

 

 

*1:「いやいや,どんな手を試しても常に14通りの部分集合に分割できる.この例では他の部分集合がφだっただけでしょ.」と思った人,あなたが正しいです.でも,そこまで分かってるなら,この記事読む必要ないですよね?そういう人をターゲットにした記事じゃありませんので.

書いてて自分でもわかってるんですが,「知ってる人にはバカバカしくて,知らない人には難し過ぎる」説明に陥ってます.済みません.

 

*2:Donald E. Knuth: The Computer as Master Mind, J. Recreational Mathematics Vol. 9, No. 1, pp. 1-6 (1976-77).

マスターマインドの解法に関する日本語の文献を読みたい方は,例えばこんなのもありました.

田中哲朗 "数当てゲームMOOの最小質問戦略と最強戦略" 第3回ゲームプログラミングワークショップ報告集, pp. 202 — 209(1996)

よいこのお友達の生まれる前から,この問題の研究は進んでいたんですよ~

広告

コメント / トラックバック2件 to “ギルクエ第三段階攻略法の整理してみる~用語とか2”

  1. Holithy☆ Says:

    パターンのことを果てしなく簡単に説明すると
    「賢者の噴水は俺達に任せろ」でドロップボックスを押したときに出てくる選択肢ですね!
    要はヒントです。ヒントそのものです。
    当初は正しい数と見当たらない数をバラバラに書くのが面倒という横着から始まったのですが
    次郎さんとの対話の中でかなり重要な概念に成長して行き驚いています。

    *1・・・!
    一見ものすごく枝葉末節な指摘に見えて解析時には注意が重要だったりします
    でもたしかにその当りは自分の担当箇所ですな!

    *2
    おー,私がやったこと,とっくにやられてたんですねw
    このpdfの目的は平均手数を中心とした手数分散を小さくすることだと感じました。
    こういう形での評価はやっていないようですが。
    2番に書かれてるのはセパナで分類してからそれを謎の関数で評価・・ふむ・・
    正直なんだかよくわからん評価関数ですね!むずい!
    んで3番だとNP系について軽く触れてから完全総当りに理論展開されてると。
    にしても動的戦略2番が複雑すぎて笑えた

    • 次郎宗光 Says:

      Holithy☆さん,いつもコメントありがとうございます.

      パターンの説明ありがとうございます.ちょっと難しく考え過ぎていたようで,お恥ずかしい限りです.

      こちらもHolithy☆さんとのやり取りを通して,多くの収穫がありました.解法を分かりやすくまとめる方法は,Holithy☆さんの次回表が簡潔で一番だと私も思っています(ただあのような記号の羅列にアレルギー反応を示す人もいるので,うちのようなインターフェイスが存在できるわけですけど).

      Mastermindは爆発的にヒットしたゲームなので,探すといろんな文献が出てきます.けど,「四種四桁重複あり」という限定された条件での完全攻略法はありません.似たような業績が過去にあろうとも,Holithy☆さんは自分の力で問題に挑戦して,最高の解に辿り着いたのですから,そこは凄い事ですよ.ホント.

      それに,あのような文献を見ても,それで明日のギルクエで役に立てる人がどれほどいるでしょうか?Holithy☆さんの次回表のようにまとめられた結果があるから,うちのインターフェイスも実装も可能になるわけですから!


コメントを書く:匿名のコメントも歓迎しますが,名前欄が空欄だと自動的に承認待ちになってしまいます.名前欄には,なるべく文字を入れて下さい.

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。