--------(--)

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
2008-12-24(Wed)

ギルクエパズル

お墓が一つお墓が二つ

まじめにギルド対抗戦をやろうと調査してみた.
ギルド対抗戦3段階のためのメモとおまけ









記事を作っている途中に,ギルクエパズル最短攻略の支援ツールを持ってるサイトを見つけた.

Maple伊勢の館:データ,ツール,育成



最初は,情報の薄いブログ等が引っかかるのを避けるため,
『ギルクエ3段階 最短攻略』などのワードでgoogle検索していた.

あまりいい情報が出てこないから自分で計算しよう,と思って自力計算し,
4手で終わるという結論にたどり着いたのだが,記事作成中にふと1単語で調べてみた.

ギルクエ3段階

冒頭のツールサイトはここでようやく見つかった.

途中まで記事を作ってしまったし,上のサイトを知らなかった人もいると思うので,
それを紹介する意味もあろうと思い,今日の記事を続ける.

結局,「検索すれば誰かが作ってる」としても,
適切なワードを指示できるかどうかの方がネックだったりする.


___



情報量

情報量(Wikipediaより抜粋)

あるできごと(事象)が起きた際,それがどれほど起こりにくいかを表す尺度.事象Eが起こる確率をP(E)とするとき, 事象 E が起こったことを知らされたとき受け取る(選択)情報量I(E) を

情報量
と定義する.

起こりにくい事象(=生起確率が低い事象)の情報量ほど,値が大きい.




情報量のイメージについてはトランプの例がよく出されるので,JISもそれに従う.

ここに,ジョーカーを抜いた52枚のトランプデッキがある.
今,Aさんがカードを一枚引くとしよう.

もちろんAさんはそのカードが何なのかは知らない.

<Aの持っている情報量はこの時点で0である>


Aさんは引いたカードを見て,そのカードがスペードのAであることを確認した.
Aさんの引いたカードがスペードのAである確率はもちろん1/52である.

<Aはカードを見ることで, 1/52に当る情報量を取得した>



ここにBさんがいる.
BさんはAさんの引いたカードの中身は知らない.

<Bの持っている情報量はこの時点で0である>

ここでAさんはBさんに,引いたカードのスートがスペードであることを教えたとする.
BさんはAさんの引いたカードがなんなのかは正確には分からないが,
少なくともスペードの13枚のうちのどれかであることは分かった.

<Bはスートを聞くことで, 1/4に当る情報量を取得した>



もう一人Cさんがいる.
CさんもAさんの引いたカードの中身は知らない.

<Cの持っている情報量はこの時点で0である>

ここでAさんはCさんに,引いたカードの数字がエースであることを教えたとする.
CさんはAさんの引いたカードがなんなのかは正確には分からないが,
少なくともエースの4枚のうちのどれかであることは分かった.

<Cは数字を聞くことで, 1/13に当る情報量を取得した>


この時点での情報量は,Aが1/52,Bが1/4,Cが1/13である.


最後,BはCにスートがスペードであることを教えた.
これでCはAの引いたカードがスペードのエースであることを特定できる.

<CはBからスートを聞くことで, 1/4に当る情報量を取得し,
 自分の持っていた1/13とあわせて1/52の情報を取得した>





難しいことは今日は言わないが,
① 情報は確率で決まっている
② 情報には大小がある
③ 情報は演算が可能である

④ 平たく言うなら上の対数式で定義されている


なんで対数を使うのかというと,上のCの例.
Cは最初にAから1/13の情報を受け取り,次にBから1/4の情報を受け取っている.
その二つの情報を掛け合わせると,{1/13 × 1/4 = 1/52}
独立な確率の重ね合わせは,掛け算によって行うことが出来る.

対数は掛け算を足し算に変換する機能があるので,掛け算の多い計算に都合がよい.
(この一文の意味が分からなかった場合は,対数を習うまで我慢してほしい)





ギルド対抗戦3段階

ギルクエ3段階についてのおさらいをする.

3段階
① 4つの石像の前に,それぞれ一つずつ「正解の」お供え物を並べる
② 供物は「勲章 書 食事 酒」の4種類あり,それぞれが4つずつある
③ 複数使う供物もあり,逆に一つも使わない供物もある
④ 正解はランダムで決められる
⑤ 7回以内に正解の組み合わせを当てなければならない
⑥ 間違った場合は,毎回3つのヒントをもらうことが出来る
3つのヒント
・ 現在の組み合わせのうち,既に正解しているものの数
・ 現在の組み合わせのうち,場所のみ合っていないものの数
・ 現在の組み合わせのうち,場に置かれていないものの数



要は4種類のアイテムを4つの石像の前において正解を当てるパズルだ.
よけいな情報は少なければ少ないほどよい.今後はアイテムを以下の数字で呼ぶ.

供物



ちなみに『4種類のアイテムを4つの石像の前に並べる』
これをクリアするにはどれだけの情報量が必要か?

これを一発で当てられる可能性はE = 1/ 256

I ( E ) = log 2 256 = 8 bit


bitは対数の底を2としたときの情報の単位だ.
ギルクエ3段階をクリアするには8bitの情報が必要である







正解パターン

256パターンは全てが等価なわけではない.
例えば,4つ全部同じものである組み合わせは,{1111},{2222},{3333},{4444}の4通りしかない.
今,4つ同じものが出る組み合わせを{AAAA}と一くくりにする.

同様に,単にアイテムを入れ替えただけのパターンを同じものとみなして整理すると,


パターン絵柄パターン数
AAAA供物4通り
AAAB48通り=4 2×4
AABB36通り=4 2×4 2
AABC144通り=4×4 C 2×3 P 2
ABCD24通り=4!


実は5パターンしか存在しない.
最も多いのはAABCのパターンである.






ヒントの組み合わせ

一発成功すれば問題ないが,失敗した場合はヒントをもらえる.
ヒントは(正解の数,間違った数,見当たらない数)で,当然その3つのヒントを足すと4になる.

組み合わせは以下

ヒント(正解の数,間違った数,見当たらない数)
正解の数000001111222334
間違った数01234012301200
見当たらない数432103210210100
呼び方0040130220310401031121211302022112203013 1400


単純に考えれば,ヒントは全部で15パターンあるわけだが,
(正解3つ,間違い1つ)の組み合わせはありえないので,正確には14パターンとなる.


なお,ヒントの持ちうる最大の情報量は,

I ( E ) = log 2 14 = 3.81 bit
8 bit / 3.81 bit = 2.10回

14通りのヒントにおいてはそれがいかなる名ヒントでも,
3回未満での全パターン識別,および4回未満のクリアは不可能



まだ何も具体的なパターン検証にはいっていないが,既に最低4回かかることが証明された.
冒頭で述べたように実際に4回で終わらせる手段は存在するので,3段階は4手ということになる.





1回目のチャレンジ

さて,3段階クリアには8ビットの情報が必要だといった.1回目は完全ノーヒントなわけだが,
第一手も256パターンありえる中で,一体どのパターンが最善なのだろうか?



実は正解パターンが5パターンに分類されるのと同様,第1手目も5パターンしか存在しない.
ならば5パターンをしらみつぶしで調べればいい.


 一手目パターン
AAAAAAABAABBAABCABCD







0048116161 
013 463216 
022 19244224
031  82048
040  129
1031085132184
112 42564636
121 15204060
130   48
2025439342924
211 12162024
220 3456
3011212121212
40011111
平均情報量(bit)4.493.893.573.343.73
最大情報量(bit)6.755.675.815.525.91


白マスの数字は,「それぞれの1手目パターンに対して得られる可能性のあるヒントパターンの数」である.例えばAAAAと置いたとき,『一つも見当たらない』という回答が戻ってくるパターンは81通りある.

平均情報量は,各列の数字の対数を取って平均値を求めたもの,
最大情報量は,各列の対数の最大値である.

最終的に情報量が0ビットになるとクエストクリアだ.
「よいヒント」というのは,平均情報量や最大情報量がより小さくなるヒントである.


その意味で,1回目の最善パターンはAABCだということになる.

AABC
供物


ちなみに,5パターン中,唯一ずば抜けて効率の悪いのはAAAA
そのほかはあまり差がないといえば差がないだろうか.


ちなみに1回目の最善操作による残りの情報量は5.52ビット
0回目の8ビットから引き算してみると,

8-5.52=2.48<log 2 14

ちゃんと14ヒントの限界情報量を下回っていることに注目




2手目以降の最善を求めてもよいが,冒頭のサイトに優秀なツールがあるのに,
わざわざJISが再計算する必要性も低い.


効率解を求めるここで本線は終了,残りはコラムとする







判別不能条件

Q1.正解がAAAAとAAABのいずれかとする.
一発で見分けるにはどういう配置にすればいいだろうか.


正解の候補があらかじめ絞られているときに,いかに少ないヒントでクリアするか,
という頭の体操だと思ってほしい.

これは簡単だ.


正解配置AAAA
AAAA400
AAAB301


当たり前ながら,候補が二つしかない場合は必ず1発で見分けることが出来る.





じゃあ,条件が3つ以上になった場合は?

Q2.AAAB,AAAC,AAADを一発で判別せよ.
Q3.一発で判別不能な3つのパターンの組合せを発見せよ.
  もしくはそのような組は存在するか?



Q2.AACB
AAAA202
AAAB301
AAAC211


簡単だが,一応回答は白抜きで.


3つの組の解答に入る前に,判別不可能解は4つの組だと簡単に作ることが出来る.

以下の6つのうちどの4つを選んでも,1発での判別は不能である

XABC  XBAC  XCAB 
XACB  XBCA  XCBA


Xは,全ての組で統一されていれば,A~Dいずれでも構わない
例)AABC,ABAC,ACAB,AACBは1回のヒントでは判別不能




① 「見当たらない」がヒントとして死んでいる
 → 「間違い+正解=4」で固定のため,ヒントは「正解の数」のみ

② 1文字目の正解不正解は全て同じのため,正答数0を候補から除く.
 400,310,220,130を各パターンに1対1対応させないとクリアできない

③ 310(正答3間違い1)のパターンはありえない

④ 正解4,2,1の3種類のヒントで4パターンの判別は不可能


【6つのうちの4つ】で,その6つのパターンも対称性が保たれているところがポイント.
ヒントが14あっても,「見当たらない」をつぶすとヒントが3つになってしまう.
だから4つは判別できない.

X+{αβγ}型が1ヒント不可能パターンのコアパーツ.
基本的に1ヒントで解けないものはコアパーツをベースに発展する.
5つに増やすと以下も1ヒントでは解けない例だ.

X+{αβY} と Y+{αβX} の食い合い型
5組で判別不能になる.

例) CD,CDB,DBC,CAD,CDA
コアパーツが喰いあう形をしている.1ヒントでは判別不能





3つの組のケースに戻ろう

3つの組は1回のヒントで判別可能だろうか?

必ず判別可能なヒントが存在する

詳しい証明は省くが,
① 他と異なる組合せをもった組が存在するとき
② 3組とも同じ文字を使い,かつ3組とも一致する文字配置がないとき
③ 3組とも同じ文字を使い,かつある1文字が3組で一致するとき

それらが判別可能なことを順次証明していけばよい





Q4.
ヒント1回の場合,最小4パターンで判別不能な解が作成できることを確認できた

では,ヒント2回で判別不能な解を作成するには,最小何パターン用意すればいいだろうか?
また,その見つけた解が対称になっていることを確認せよ.


あえて解は示さない.

頭の体操なので,時間があるときにやってみるといい.
この手の問題は解が対称的になっていて,見た目にも美しい.
知的好奇心を満足するには十分すぎるほどの問題だと思う.

なお,ヒント3回だと256パターン全て判別できるようになる.






ちなみにオルクエ封印の部屋は?

封印の部屋


ギルクエ3段階は,7ターン用意されていながら4ターンクリアが可能なのは分かった.
では似たようなクエストであるオルクエ封印の部屋はどうなんだろうか?


ルールを確認すると,
① 3つの足場に計5人載る
② 各足場に載るべき人数を当てる
③ 正解はランダムで決められる
④ 正解を7回以内に当てる
⑤ 間違えたときは,正解した足場の数をヒントとして提示される


ギルクエの簡単バージョンだ.
答えを先に言ってしまうと,封印の部屋は5回未満での判別,
および6回未満で全パターン制覇は出来ない.



これもちゃんと理由がある.

ギルクエ3段階は,【わずか4パターンで二つのヒントが必要】な「コアパターン」が存在した.
オルクエも,少数パターンでヒントを浪費するコアパターンが存在する



さて,なぜオルクエ封印の部屋は5回未満で全パターンのクリアが出来ないのか?

Q5.オルクエ封印の部屋で,ヒント4回では判別不能なパターンの組合せを用意せよ
A5.
例)050,140,230,320,410,500
仮にその6パターン以外は出ないとあらかじめ分かっていたとしても,
それらを判別するためにヒントが5回必要である








カテゴリー タイトル 投稿日
     
次回      
前回 MTS手数料2008年11月24日
全職スキル振り ― 総目次




comment form

管理者にだけメッセージを送る

comment

No title

初めが○1X2
二回目も○1X2
三回目がX3
四回目もX4
ここまでで全てがわかるので、
五回目でクリア

これあってますか?
俺オルクエは60回以上やって、やりながら覚えたので、今回考えるだけだったので、大変でした。なんかキャラ見ながらの方が考えれます。

ちなみに
311
302 212 221

302
320 212 401

320
212 401

212
401

401
クリア

どうですか?JISさんなら、これの意味わかりますよね。
間違ってても気にしません。答え待ってます。

*これってヒント4回で全パターンわかってるのでは?

No title

ちなみに、みんなも出来るオルクエ封印の部屋の簡単な攻略法は

はじめに311にのる。

X3なら122、それがX3なら、500、050、005、203、302をやればいい。122がX2○1なら、140、023、032をやればいい。

初めがX2○1なら、302、320、212、410、221、401、をやればいい。

X1○2はない。
初めが○3はクリア。

7回以内にクリアできるやろ。頑張れ学生。

No title

うわぁすごい
情報量の計算なんかも自前の知識としてもってたのに、こんな考え方なんて全然出てきませんでした。
単にテストで点を取れても無意味ってことですね。
しかし最短4手でいけたとしても、実際の場面でそれを考えて実行するのはおそらく非現実的でしょうね。
ツール化して使うにしても、入力する手間よりもわかりやすい手法でどんどんヒントをもらった方が結果的には早かったりしますし。

No title

わーい 2話連続ひっそり出演(´ω`)ノ

ちなみに オルクエにしろギルクエにしろ規定回数以内にクリア出来たら他の事を一切考えない紫煙でした(・ω・)b

恙なくクリア出来るから良いんだっ!

No title

いうえお

No title

打消]あいうえお[/打消

No title

ギルクエの場合は、持ち越しをする場合としない場合とでやり方が変わってきます。

酒と食を持ち越す場合はたしかにAABCから始めるのが最善かも知れませんが、持ち越しをしない場合は酒と食が集まるまでの時間で、紋章と書のAAAAパターン検証が終わります。

なので、まずは書と紋章の必要数量を先に調べて置いてその後に、集まりやすい酒を絡めた検証をし、食が来る頃にはほぼ絞り込めた状態に持って行くのが効率的なやり方になると思われます。

記事が理解できないので「情報量」についてググってみたら、指数・対数関数に確率の知識が必要みたいですね(・・;)

数学嫌いの自分にはハードルが高いようですorz

JISさんは理系人間ですか?

先程コメントした者ですが、Wikipediaより「情報量」についてわかり易く解説してるサイトを見つけたので貼って置きます。

http://www.buturigaku.net/main03/Information/Information001.html

No title

昨日まであったコメントが幾つか消えてますね

自分に都合の悪いコメントはすぐに消しちゃうんですね 
まぁ文脈で必死に知的さアピールしてますけど、そんなので騙されるのはおこちゃまな低能だけです。

まぁこのコメントも暇でPC付けっぱなしのJISさんにはすぐ消されちゃうんだろうけど(笑)

No title

なんかいたるところに打ち消しが・・・

No title

オルクエのは手抜きか?

例)4手ですべて判別
 1st 500
 2nd 140
 3rd 023
 4th ここで正解数が下記の3パターンとなった場合のみ分岐,後は2パターンに絞れている
  正解数変化パターンが
   110->230
   001->032
   011->113
    ->ここで外れても正解数で判別可能

しかし,これ通りする事はまずない
ぎるさんが書いてるが,ヒントの数を貰った方が手っ取り早い
ギルクエの正解パターン数が256なのに対し
オルクエはたったの21パターンだからだ

--------------------------------------------------------------

>ななしさん
見かたがよくわからないが
 1st 311
 2nd 302
 3rd 320
 4th 212
 5th 401
のパターンの場合,下記組合せの出力が一緒になると思われる
 (131,041)
 (104,005)
 (140,050,023)
 (113,014)
 (203,032)
 (410,221)

初めて

こんにちわいつも見てます。
ところでoあんず飴osのメインキャラの名前知ってますよね?

No title

①一例をあげただけです、JISさんやNon titleさん のような理解できる方は、わかると思ったので。
②上手く説明をまとめれなかった。
③長々と全てを書いてもよかったが、それなら、おもしろくないと思いまして。多分わからない人は、読まないし。
④他の人にも、考えてほしかった。
⑤JISさんが、答え書かないから。

こんなところですね。

No title

>>Non title さん

なんかよくわからなくなってきました。

俺のやり方は、俺の経験からきてるので、俺はやりやすいです。
何故か、初め500より、311の方がやりやすかったので、そういうことになりました。

JISさんの誰にでもわかりやすい説明期待してます。

No title

重箱の隅ですが、

>なお,ヒントの持ちうる最大の情報量は,
最大の平均情報量(エントロピー)が適切ではないでしょうか。
最大情報量ですと、14のヒントの組み合わせそれぞれは等確率ではないはずなので大きくなります(正解パターン400で8bit)。
最大エントロピーは全てのパターンが(ありえませんが)等確率の場合で、 -log_2 1/14 = 3.81 bitでよいと思います。
すると次節の、
問題のエントロピーをより小さくするパターンを選ぶ = より大きいエントロピーを持つパターン(一様分布に近いAABC)を選ぶ
に繋がります。
表の最大情報量は場合の数の対数ではなく、確率の対数ですので、全て正解400の1/256が最も高い情報量8bitになります。
正解の8bitを選びたいのですが狙って選べないから最も高い平均情報量を使うわけですね。

>平均情報量は,各列の数字の対数を取って平均値を求めたもの
平均という言葉がややこしいので確認というか補足です。
それぞれの生起確率をpとすると- 1/Total Σlog p ではなく -Σp log pですね。

個人的にこういうパズルは苦手ですねぇ…。
ルディクエの箱のように総当りでいくのが楽でいいです。
カウンター
カレンダー
06 | 2017/07 | 08
- - - - - - 1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31 - - - - -
最近の記事
最近のコメント
目次

全ての記事を表示する

月別アーカイブ
新着サイト
ブログ内検索
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。