【Help!!】某パズル系ゲームの攻略アルゴリズム

下記の問題を解ける方へ
↓ここの中毒患者たちを助けてください
水玉潰し
http://pya.cc/pyaimg/pimg.php?imgid=22468
　
《問題提起》
「1回の起爆で全壊するために、仕掛ける水滴は最小いくら必要かを求める定式的方法」と
いう問題をここに提起する。私はその数学的解の存在を予見している。
このコメントが残っている限り、解を掲載する予定であ・・・んぁ、誰だ君らは！な、なにすｒあｗｓでｆｒｔｇｙふじこｌｐya!；＠ 06-06-10 14:40
　
上記問題の解「定式的方法」があれば、仕掛け方と起爆すべき場所も分かると思われますが・・・

総当りだ！

hoshu

この板の住民には難しすぎる・・・か？

なんかこれ、チューリング機械を作れるんじゃないかな？
算術的で非可逆なのでそんなに自明じゃないかも知れないけど、
二つの道筋を作って、どっちの道をたどるかみたいなのを考えると
論理演算とか状態記憶とかできそうだね。
で、結局停止問題に帰着すると。

14551915228366851806640624=(5^36)-1通りのステージがありうる

いくつかの場合では解は自明である

{0,1,2,3,4}^36の上に定義された非常に特殊な演算として定義される

飽きた

この板のクオリティは>6-7の程度ですか、そうですか。

まず1の《問題提起》はちょっとおかしい。
というのは、もしゲームの目的がより先の面に進む事
であるならば、「一回の起爆で全壊する」というのはその場合に
とるべき最善の手段であるとは限らない。

というか連鎖時のドロップの増え方がよくわかんないだけなんだけど・・・orz

一度にn個つぶすと[n/3]滴増える。( [ ]はガウス記号）

私は各面の最初で中央の４×４の中で６個連鎖するようにしてから
コンスタントにレベル20越えができるようになった。

>>10 この程度の観察眼ねぇ・・・この板も落ちたな

シークエンスが逆行しないから、問題としては難しくない。
ドロップがどう増えるかは、除外して考えてもいいだろう。

page

「一回の起爆で全壊」アルゴリズムには、まだ遠く及ばないが、
「一回の起爆でなるべく多く破壊」するための基本パターン、
即ち、破壊効果の高い「ベターな仕掛け方」「ベターな起爆場所」を考えてみよう。

1. 記号の定義
○：　あと1滴の雫で破壊する水滴。
□：　あと2滴の雫で破壊する水滴。
△：　あと3滴の雫で破壊する水滴。
・：　あと4滴の雫で破壊する水滴。
◎：　起爆候補の水滴。

2. 攻略の前提条件（ゲームルール）
(1) ミッション
　ステージ上のすべての水滴を破壊するとステージ・クリアー。
　より高いステージまでクリアーしていくほどプレイヤーが評価される、一種の戦略ゲームである。
(2) アクション
　プレイヤーは雫ストック（ゲームスタート時に10滴）をもっている。
　一度のアクションで、ステージに散りばめられた水滴の、どこか1箇所に1滴だけ雫を落とせる。
　すると、その水滴は成長又は破壊する。
　破壊された水滴からは、上下左右の各向きに1滴ずつ雫が飛び散る。
　飛び散る雫は、ステージを囲む壁または《すぐ隣》の水滴にぶつかるまで、等速直線運動する。
　そして、同じ行又は同じ列において《すぐ隣》の水滴が存在すれば、いわゆる破壊の連鎖が生じ
得ることになる。
　ここで《すぐ隣》の水滴とは、隣接している場合はもちろんのこと、スペースでいくら隔てた水滴
でも含まれる。ちゃんと飛散してぶつかるため。
　プレイヤーは、こうした雫の運動と水滴の成長又は破壊が終了するまで、次のアクションはできず
画面を見守ることになる。

3. 基本的戦術
(1) 破壊の連鎖が起こるための必須条件
　ステージのどこかに、あと1滴の雫で破壊する《すぐ隣》の水滴（○）が存在する水滴（○）。
　そのような○のペアが存在することが、破壊の連鎖が起こるための必須条件である。
　起爆候補としては後者の水滴（○）。（が、両者は等価のため前者でも起爆候補といえる。）
　なお二つの○の間に障害となる水滴（○以外）が存在しても、そこを雫が移動する瞬間に障害
が破壊されていれば、雫は無事に通過し、連鎖が起こることになる。

(2) 基本的な仕掛け方と起爆場所
　(1)より下記パターンが考えられる。以下、◎が起爆候補の水滴（○）である。

起爆パターン#1:
◎○
※これは右向きに破壊するパターンだが、左向きも同様に成り立つ。
以下、連鎖方向が横方向のパターンを主に記すが、縦方向も同様に成り立つ。

(3) 一つの水滴を破壊するまで成長させるための必須条件
　(1)、(2)より、□や△や・をターゲットとする下記パターンが考えられる。
起爆パターン#2:
○◎□
起爆パターン#3:
○○◎△
起爆パターン#4:
○○○◎・

以上は、このゲームの攻略にあたっての基本中の基本。
諸君の健闘を祈る。

>18の応用

応用#n:
○◎□○

応用#n+1:
○◎△
　○○

応用#n+2:
○◎・○
　○○○

機種依存無視で、�@�A�B�C使いたい気分。
ズレないしな。

１０が言ったことに賛成
確かに一度で全部消せたとしても
結果的にストックの量が必ず増えるってことじゃないからね
たとえすべての増すが埋まっていたとしても
一度で連鎖して得られるストックは１２
毎回１２以下でその状態が作れることはない！

簡単なプログラム作ってみた。
自力では最高レベル24くらいだが、
プログラムの助けを借りて、
ただいまレベル25で残り水滴86個。
どこまでいけるかな・・・

>>21も、面白いことをいうな。
つまり、>>10のいうように下記の命題を主張するのだな。

（命題）
¬　（最少数の雫でクリアする　⇒　一回の起爆で全壊する）

証明せよ。

>10　
>より先の面に進む事であるならば、「一回の起爆で全壊する」というのはその場合に
>とるべき最善の手段であるとは限らない。

ありえないステージだけど、○の状態の粒が斜めに2個だけ並んでる状態だったとする。
無理やり一回で連鎖させようとすると、5粒使用で連鎖+1粒でトータル-4
素直に一個づつ潰せば-2で済む。
普通のステージでもある特定の列に並んでる水が少なすぎると似たような状況が起こると思われる・

場違いは承知でお願いします。問題提起は最小の水滴投下で全壊ですが、
重症患者としては、ストックを効率的に増やす方法もご教示いただけると
大いなる救済になります。救い給え、できれば凡人にも分る方法で・・・

命題>>23の反例を挙げたか>>24　やるじゃんね
　
「より高いステージまでクリアーしていく」というミッションのためには、
>>1の問題提起は確かに修正を要する。
現状の>>1は上記ミッションのために最大の連鎖を求めている。
つまり、>>1は下記命題が前提となる。
　
（命題）
一回の起爆で全壊する　⇒　最大のストック増加でクリアする
　
>>1の願望としては下記命題を前提としたようだが、この命題は>>24で否定された。
（命題）
一回の起爆で全壊する　⇒　最少の雫消費でクリアする
　
（命題）
最少の雫消費でクリアする《定式的方法》は何か。
　
その《定式的方法》は必要十分条件であることの証明が、この板の住民としては求められる。
鍵となるのは恐らく、
（一回の起爆に限らず）ステージクリアするための最小の雫消費数を求める定式的方法。

>>22
どういうアルゴリズムなの？

>>27
単純に全部やってみるだけです。
ただし、1さん式で、最後に起爆する手しか読んでいません。
(途中で起爆するのを全部読んでいたら計算時間が厳しいと予想）

10手くらいまでなら一瞬。じっと待ってれば15手くらいまで読めます。

現在レベル47で残り水滴48。そろそろ17手かかるなんてのが出てきてジリ貧。
計算時間も厳しい。

>>28
>単純に全部やってみる
数学的というより、それは算数レベルだな。
まず「ステージクリアするための最小の雫消費数」が水滴配列から計算できて、
次に「具体的な仕掛け方、起爆場所が定式的に見つかる」、ような気がしてならない。

>>28
もっと具体的にはどんな？？（よかったらだけど、プログラム内容でもＯｋ）

>18の
>二つの○の間に障害となる水滴（○以外）が存在しても、そこを雫が移動する瞬間に障害
>が破壊されていれば、雫は無事に通過し、連鎖が起こる
　
このケースをカウントするのは、ちょっとやっかいそう。
移動する瞬間ってことは、連鎖の経過時間まで計算しなくてはならないことになる。
そこまでしないシンプルな計算が先だろうな。

>>20は気分というが、案外それは、解決方向のアイデアかもしれない。
>>16を下記のように更新する。
1. 記号の定義
�@, ○：　あと1滴の雫で破壊する水滴。
�A, □：　あと2滴の雫で破壊する水滴。
�B, △：　あと3滴の雫で破壊する水滴。
�C, ・：　あと4滴の雫で破壊する水滴。
◎：　起爆候補の水滴。

ちなみに◎は、さしずめ「0」（ゼロ）の丸囲み表記と考えられるが・・・定義は変わらない。

起爆パターン#1〜#4は、それぞれ以下のようになる。

#1:
◎�@
#2:
�@◎�A
#3:
�@�@◎�B
#4:
�@�@�@◎�C

基本の起爆パターン#1〜#4>>32を応用して、縦か横の方向にだけ注目したパターンを考えよう。
以下、連鎖方向が横方向のパターンを主に記すが、縦方向も同様に成り立つ。

・・・とパターンを挙げるつもりだったが、以下、あらゆるパターンを問題形式にして考察しよう。
良問を求む！ただし、ステージ枠は縦横6ます迄であることを条件とする。

問題：
以下の水滴配列に対して、ベストな起爆場所（一滴の雫でなるべく多く破壊できる起爆場所）はどこか？
適当な�@を◎に変えて示せ。

問題例：
Q. �@�@�A
回答例：
A. �@◎�A　（全壊）

Q1.
�@�@�@�A�A
　
Q2.
�@�@�@�@�B�A
　
Q3.
�A�@�@�@�A
　
Q4.
�A�@�@�@�@�B
　

A1.
�@�@◎�A�A

A2.
�@�@�@◎�B�A

A3.
�A�@�@◎�A　�A◎�@�@�A

A4.
�A�@�@�@◎�B　

Q1.
�@�A�@�@�B

Q2.
�@�A�@�@�A�B

Q3.
�@�@�A�@�@�B

>>34
A1.はＯｋ（全壊）。
A2.〜A4.は誤り。
Q2.〜Q4.の正解においては、いずれも全壊可能。

訂正：　A2.〜A4.もＯｋ（全壊）。>>34

>>34
A1.
�@�A◎�@�B　（全壊）

A2.
�@�A�@◎�A�B　（全壊）

A3.
�@�@�A◎�@�B　（全壊）

皆さんは列単位で話を進めているようですけど
もっと幅を広めたほうがよいかと
たとえば
○：あと１
△：あと２

　　　　　　　　　　　○△
　　　　　　　　　　　○○

っていう状態があれば周りがすべて△であっても
全部一回で消えるってご存知でしたか？
このようにひとつの列だけで考えるより
縦横両方について考えたほうがいいと
思いますよ。

>>34
A3.に追加すべき。
�A�@�@◎�A　�A◎�@�@�A
追加：　�A�@◎�@�A

つヒント 「低次元から高次元へ」　>>38
　
そろそろ一次元問題も尽きたかな。
応用範囲を二次元に拡張しようか。

その前に、>>33から始まる一次元問題を整理するか。
リナンバーよろ。
↓

Q1.
�@�@�@�A�A
A1.
�@�@◎�A�A　（全壊）
　
Q2.
�@�@�@�@�B�A
A2.
�@�@�@◎�B�A　（全壊）
　
Q3.
�A�@�@�@�A
A3.
�A�@�@◎�A　�A�@◎�@�A　�A◎�@�@�A　（いずれも全壊）
　

Q4.
�A�@�@�@�@�B
A4.
�A�@�@�@◎�B　（全壊）
　
Q5.
�@�A�@�@�B
A5.
�@�A◎�@�B　（全壊）
　
Q6.
�@�A�@�@�A�B
A6.
�@�A�@◎�A�B　（全壊）
　
Q7.
�@�@�A�@�@�B
A7.
�@�@�A◎�@�B　（全壊）

Q8.
�A�@�@�@�B
　
Q9.
�B�@�@�@�@�B
　
�@〜�Bのみで成る一次元全壊問題としては、出尽くしたかな？
�Cが入った一次元全壊問題は、こんなに数がないだろう。

A8.
�A�@�@◎�B　(全壊)

A9.
�B�@◎�@�@�B　�B�@�@◎�@�B　(いずれも全壊)


�Cが入る場合
Q10.
�B�@�@�@�@�C

A10.
�B�@◎�@�@�C　（全壊）

>>46の訂正：
全壊はない。
�B�@◎�@�@�C
↓
＊＊＊＊＊�@

ここで>>32に下記のように定義を追加した。
1. 記号の定義
�@, ○：　あと1滴の雫で破壊する水滴。
�A, □：　あと2滴の雫で破壊する水滴。
�B, △：　あと3滴の雫で破壊する水滴。
�C, ・：　あと4滴の雫で破壊する水滴。
◎：　起爆候補の水滴。
＊：　スペース（又は破壊済み水滴）。

＞45の訂正
出題ミスです。

Q10.
誤�B�@�@�@�@�C　　正�A�@�@�@�@�@�C

スミマセン

↑さらに訂正

Q10.　
正 �A�@�@�@�@�C

申し訳ありません。

>>48
一個多いような

�A�@�@�@◎�C

プログラムは55面で死亡。終盤はきつかった。

�B�B�C＊�B�@
＊＊�C�C�A＊
�@�C�C�B�C�A
＊＊＊�B�C�C
＊�B�B�B�B＊
�B�A�C�C�A�B

レベル52より。16滴追加すると17滴目で全滅できます。
どこに追加してどこを発火させますか？

むー、自分もなんか作ってみるか・・・

ところで
◎�@
�@�@
という状況では、右下の粒は上から来る粒と左から来る粒のどちらで連鎖しますか？
一般に同時に連鎖候補の粒が接触した場合どういう風に連鎖するのかはもう既出？

>>52

はい、そこが曖昧です。
同時に衝突した場合、

(1) 両方吸収される。
(2) どちらかが吸収され、どちらかがそのまますり抜ける。
(2)の場合、どちらが先に衝突したと判定されるのか。

また、衝突して破裂した場合に遅延が生じるのか否か、という問題もあります。
遅延が生じるならば、衝突の世代が子と孫のように異なる場合に
タイミングのずれが生じます。

プログラムは、
・破裂時水滴は同時ではなく(微小な時間差を持って)右上左下の順に
(0, pi/2, pi, 3pi/2)生成される。
・遅延は0
と仮定して組んでみましたが、これで正しいかどうかは分かりません。

>>52
それこそ論より証拠。
そのケースを実際に作って、雫がどう出てくるか、連鎖をやってみれば？

◎�@＊　　＊�@◎　　＊�C＊　　＊�C＊
�@�@�C　　�C�@�@　　�C�@�@　　�@�@�C
＊�C＊　　＊�C＊　　＊�@◎　　◎�@＊
　 ↓　　　　　↓　　　　　↓　　　　　↓
＊＊＊　　＊＊＊　　＊�A＊　　＊�A＊
＊＊�B　　�B＊＊　　�B＊＊　　＊＊�B
＊�A＊　　＊�A＊　　＊＊＊　　＊＊＊　

＊�C＊　　　＊�C＊�C＊
�@�@�C　　　�C�@�@�@�C
◎�@＊　　　＊�@◎�@＊
�@�@�C　　　　　　↓
＊�C＊　　　＊�A＊�A＊
　　↓　　　　�A＊＊＊�A
＊�@＊　　　＊＊＊＊＊
＊＊�B
＊＊＊　　
＊＊�A
＊�A＊

>>55から分かる事
上＞左右＞下

＊�C＊　　　＊�C＊�C＊
�@�@�C　　　�C�@�A�@�C
◎�A＊　　　＊�@◎�@＊
�@�@�C
＊�C＊
暇な人これの調査希望　

＊�C＊　　　＊�C＊�C＊
�@�@�C　　　�C�@�A�@�C
◎�A＊　　　＊�@◎�@＊
�@�@�C　　　　　　↓
＊�C＊　　　＊�B＊�B＊
　　↓　　　　�@＊＊＊�A
＊�@＊　　　＊＊＊＊＊
＊＊�B
＊＊＊　　
＊＊�B
＊�A＊

うお、これが正しいとすると、上＞左＞右＞下の順序で優先的に連鎖ですね。
つまり、下右左上の順で微少時間差で発射すれば、２２さんシミュレータは
完璧にシミュレートしてると考えて間違いなさそう

雫の出る優先順序があって、>>58のように分かったとする。
さて、その「微小時間差」（タイマーコントロールかもしれないし、コマ割かもしれない）って、どれだけのもんだろ？
フラッシュのプログラム（多分ブラックボックス）を覗くしかない！？誰もできないか・・・

優先順位の問題はなかなか難しいですね。
実は作ったプログラムと実際のゲームとはときどき挙動がずれます。

これで、上＞左＞右＞下が確定なら話は早いんですが、
そう簡単でもない気がします。

◎�@＊
�@�@�C
＊�C＊
　 ↓
＊＊＊
＊＊�B
＊�A＊

例えばこの図ですが、中央ブロックにぶつかる２つの滴は、

右→下
下→右

ですが、方向によって遅延が異なったとしてもこの場合
どちらも右＋下ですから遅延は結局同じになってしまいそうです。

だとすると、プログラム上の微妙な都合（例えばどっちが
配列の若い番号に登録されているか）みたいな事情でどちらが
優先されるか決まってしまっている疑いすら出てきます。

実際問題としては、全壊を読みきっていながら挙動が異なって
どこかで止まってしまうような場合、残った水滴もほぼ連鎖形に
なっていて一撃で全壊できることが多く、ゲームをクリアする目的には
さほど大きな支障にはなっていません。

とまぁ、二次元問題になると、やっかいになるんだな。まさに>>31で指摘したポイント。
これは一次元問題（>>42-50）までは意識せずによかったが、二次元問題を真剣に議論する
には、避けて通れないポイントだろうか。
>>60
ゲーム設計上の仕様があるかどうかはさておき、プログラムの構造上は、自然と何らかの
優先順位が出来上がっていると思われる。
それがどんなものか、「実験的に」確認するしかなかろう。
（すると数学板の問題ではなくなるけど。）

あー、そうか微小時間差が累積して結局同じになっちゃうわけか・・・
あ、じゃあ、水玉の形が微妙にいびつで上のほうが飛び出してるとかはどうですか？
２２さんのはそういう拡張はすぐ出来そうですか？

age

しばらく留守にしてたら静かだなあ。

http://kashi.dip.jp/~kashi/mizutama/

↑こんなページを作ってみました。
とりあえず試験公開。

>>62
仕様変更は難しくないです。ただ、厳密に水滴の位置を管理
するような拡張は、計算時間の問題で厳しいかも知れません。

なんだか仕様が知れんとやる気がうせる。

>>22>>64 乙。
あら？そのページにある：
＞プログラムは、一撃で全壊できる最小手数解を計算するものです。
って、それはこのスレの>>1の趣旨に沿っているわけね？
厳密な意味で最小かどうかは、知らんけど

んー　GUIなかなかいいけど。（クリックしたときの反応が遅い）
実際のステージからの自動取り込みができればいいなぁ（希望）。
　
あと、アルゴリズムに関しては、オープンソースにするとグングン改良されるんだろうね。
惜しい。

厳密な最適解では無いかも知れません。原因は２つあります。

・例の水滴のタイミング問題。
・プログラムは「一撃で全壊」する場合しか考えていない。
n手でもっとも多く破壊する方法を計算する場合、n-1手目までは
　発火しないものとしている。
　つまり、途中で小さな発火をさせた方が全体として少ない手数で
　終了するような場合があるとすれば、それを見逃している。

プログラムは、「n手でもっとも多く破壊する方法を計算する関数」
を作り、それをn=1, 2, 3と全壊するまで増やしていくような構造です。

「n手でもっとも多く破壊する方法を計算する関数」は、
n-1滴をどこも破壊しないように盤面に追加する全ての組み合わせを
考え、それぞれについて全ての満タン水滴を発火させてみて
破壊された水玉の最大数を求めます。

ソースの公開はまだ保留です。あまりきれいじゃないし。
まあ、これだけ情報があれば書くのは難しくないと思います。

>>68乙。
しかしロジックがベタすぎて、拍子抜けの感を否めない。
計算機使うからって、力技すぎると思う。
自分で作ってもないのに言うのはなんだけど。
このスレがこの板にあること、そして上に繰り広げられているスレの流れは
無意味なのか！？orz

>>69

このスレでいろいろ解析していた方には申し訳ないけれども、
個人的には問題を見た瞬間から、きれいな構造があるような
問題には思えませんでした。
一次元問題の解析が二次元問題の解決に寄与するような気もしませんでした。

力技が最善と判断してのいきなりプログラミングです。

CGI版を作るにあたって、数秒で計算を終わらすために問題が
難しい場合は最適解を諦めてそれなりの解を出す必要があったのですが、
むしろこっちが難しかったです。

連鎖する順序を経路として捉えると
最適経路問題のバリエーションでしかないように思える

力技が正解なんじゃね？

連鎖仕様がはっきりしないのは思考パズルとしてもちょっと魅力が無いね

ある１つの水玉から出発して、縦横に直線を描く。
その直線上にある水玉からさらに、縦横に直線を描く。
この手順を十分な回数繰り返したとき、縦横の直線によって
結ばれあう水玉の組を”ループ”と呼ぶ事にする。

任意の図形の水玉たちは幾つかのループに分類される。
１つのループで構成される図形を１ループ図形
２つのループで構成される図形を２ループ図形
・・・（以下同様
と、呼ぶ事にする。

補題　任意の図形は１ループ図形〜６ループ図形のどれかである。
（証明略

予想　１ループ図形には一回の起爆で全壊する最善手が存在する。

>>71
＞連鎖仕様がはっきりしない
はっきりしない、って確証あり？過去のレスをよく読んでないけど。。。

はっきりしてるのは当たり前だが、ここでははっきりしない部分がある。

日本語でおｋ

そのままだ。

31=40の偉そうさと22さんの謙虚さの対比が面白い。

おまえらはそんなんもわからゎ

んにゃなんでもなかとです

シミュレータ本家でも流行りだしてるｗ

ソルバーの威力体感。しかしやっぱり自動読み込みできないとめんどくさくてしょうがないｗ

>>72
の予想は22サイトの用語で言うと、
「”連結問題”は一回の発火で全壊する”最小手数解”が存在する」
となるみたいです。
というかたぶん正しそう。
そして、問題のパターン数からして大部分は連結問題だし、
実際のゲーム上で、非連結問題が出ることがあるのかどうか自体があやしい・・・

ちなみに非連結問題でも一回の発火で全壊した方が最小手数になるパターンはある。
例えば
�@
�@
�@
�@
＊�@�@�@�@
という図形は
�@
�@
�@
�@
�C◎�@�@�@
と発火すれば-2+3=+1
だが、それぞれ発火すると-2+2=0で、それぞれ発火したほうが損。
しかし、こういう場合はかなり稀で、実際は非連結問題は２回以上で
発火した方が得になりそう。
盤面がもっと相当に大きかったら非連結問題もかなり重要になってきそうだった気がする・・・

>>81

なるほど。「何も無い空間に一滴垂らす」んですね。
何も無いところに水玉を生成して得になることは無いと思って
無視してたんですが、この例はちゃんと得しますね。

手数こそどっちも二手で同じですが、連鎖する分ボーナスが違うと。

>>80

画像認識はさすがに面倒。誰か作ってｗ

>>79 ドコ？

age

hosh

>>22の解説、ちょっとまだ読む気がしないけど
http://kashi.dip.jp/~kashi/mizutama/preadd-new.html
　
Solverについて思うところは、
　
1) 多分現在の手法はベタすぎて、>>1のいう「最小いくら必要かを求める定式的方法」は
実現してないのでは？
このゲーム、各ステージをクリアするのに、そもそも持ち手が「理論上」足りているかを
《先ず》知りたい。
仕掛け方より起爆点よりも何より、《先ず》その最小数を表示してくれれば、ゲームのやる気につながる。
（逆に仕掛け方や起爆点は表示しなくてもいいくらい。ゲームプレイヤーとしては）
　
2) ゲームステージからの自動読み込みでしょ、やっぱ。
技術的には「画像認識」なんて大げさなものかいな（笑）。
あとは気概の問題？
ソフト技術人が、機能、性能の中途半端さ（UIにおけるソレを含む）をよしとするようじゃ、
その真価の発揮は十分の一以下だとおもふ。

＞(通算○○○○回ご利用頂きました。)
(´-`).｡ｏＯ（そんなに多くの回数、こんな面倒な入力をさせたの？中途半端なUIはオソロシス）

>>86
まあ、例のタイミング問題が解決していない以上、厳密に
どうこう言える段階じゃ無いんですが・・・

タイミング問題がはっきり解決した、あるいは微妙なタイミングの
影響が出ない問題と仮定して・・・

Solverの解は、「事前追加行われなければ」間違いなく最小手数の
全壊解です。それより手数の少ない全ての盤面について発火させて
確認してるわけですから。

Web版は手数のかかりそうな問題に対しては自動的に事前追加を
行いますので、事前追加が発動してしまった場合は、それが
最小手数かどうかは分かりません。

事前追加を行わない、必ず最小手数を求めるプログラムは手元にありますが、
これをWebに採用するのは自分のサーバが大変なことになりますので
無理です。問題によっては評価盤面が100億通り以上、解が出るまで
10時間以上なんてことになります。

なお、全壊解、すなわち途中で全く発火させずに最後に発火させる
解しか考慮していないので、途中で小さな発火を行った方が
全体として手数が少なくなる可能性はあります。
連結問題ならそのような盤面は無さそうな気はするんですが、
証明の仕方が思いつかないです。

>>86

UIについてですが、画像読み込みは少しは考えましたが、
そもそもいいインターフェースが思いつきませんでした。
クリップボードの画像をブラウザにコピペする手段は無いので、
クリップボードの画像をいったん適当な画像ソフトに読み込ませて
ファイルとしてセーブし、そのファイルをアップロードさせる、
という方法もありますが、これは今のよりもっと面倒な気がする・・・

まあ、アルゴリズムに興味があっただけで、UIには興味が無い
(第一まともなUIを作る知識も無い)ので、これ以上は勘弁してください。
Javascriptも生まれて初めて使ったんです。

�@
�@
�A�A
　 �@
　 �A
この形って分割すれば最小0手、一撃で壊そうと思ったら1手必要じゃないか？

他にも、一撃で全消しするだけの余力が無い時とか、
面開始時の残数によって最善手が変わる事もあり得るな。
理論値と比べると1手損するけど途中で発火しないと足りなくなる時とか。。。

>>90
な、なるほど! 90番さん神。

素直に消せば2手ですが、一撃全壊は3手かかりますね。

実は途中発火を考えるようにプログラムを変更するのは
易しい(ほんの数箇所いじるだけ)なのですが、
こちらはものすごく遅くて実用になりません。
今ちょっと走らせてみたところ、

5手以内の問題: 一瞬
6手の問題: 10秒くらい。
7手の問題: 1分くらい。
8手の問題: 7分くらい。

てな感じで、後半の難しいところはとても実用時間では解けません。
(同じ8手の問題を途中発火無しなら2秒ほど。)

途中発火を無しと仮定すると、水滴を追加する順序に意味が
無くなって純粋にどれをふくらますかの組み合わせだけになりますが、
途中発火があると順序に意味が出てくるので評価すべき盤面の
数が爆発的に増大してしまうためです。

最適解の保障は無くなるけど・・・水玉を発生させる事と、
途中発火をした時にボーナスのロスが発生することを
禁止すれば良いんじゃないか？

水玉の数が2（mod3）の時に1個発生させる最適解があるかもしれないが非常に稀だと思う

>>93

水玉の発生は禁止してます。
(というか、プログラムを作成したときは発生が可能なことを知らなかった。)

ボーナスもどうせ一撃全壊しか考えてないので全く考慮してません。
純粋に使った水滴数が最小になる解を考えています。
先の90の例は、ボーナスを考えなくても途中発火させた方が手数が
少ないですね。

�@�@�A
�@
�@
�@
�A　 　 �@
上が一段開いてる時、左上の端に1個追加してからその右下で起爆するのが最善手になる

なんか90と95の言ってる意味が分からない・・・

>>86
ゲーム本体ならまだしも
ゲーム解析装置にインターフェースの質を求めるのは
あまりにも勘違いだと思うんだが・・・ｗ

>>95は

＊＊＊＊
�@�@�A＊
�@＊＊＊
�@＊＊＊
�@＊＊＊
�A＊＊�@

を

�C＊＊＊
�@◎�A＊
�@＊＊＊
�@＊＊＊
�@＊＊＊
�A＊＊�@

にするってことだな
これでボーナスがいっこ増えるのよ

>>98
あ、ほんとだ、左上を置かないと一個損するわけか・・・

＊＊＊＊
�@◎�A＊
�@＊＊＊
�@＊＊＊
�@＊＊＊
�@＊＊�@

コレでも「２手全壊」には変わりないけど、「最適解」ではなくなると・・・

９０も良く見たら理解できました、
良く思いつくなー・・・

定義なんてすきずきの場合もあるが：
>>22のSolverの解説、
http://kashi.dip.jp/~kashi/mizutama/program.html
で、
＞それぞれ大きさ1,2,3,4の「水玉」
　
と、安易に《大きさ》なんてイメージに訴える概念で定義しているけど、
ここの流れでいう�C�B�A�@といった定義（>>47）の方が、
いろいろと考えやすいんじゃないか。
　
いまのところ「タイミング問題」の障壁故に、
>>1の求める「数学的解」としての「定式的方法」は、お預けなんだろうけど。
　
　とかいってみるテスト

･･･単なる名前の付け替えじゃ?

1は数学的解なんか本当に求めてるのか？
このスレが停滞してたときにゲ制板にリンク貼ってたのは1じゃないの？

1はもう飽きてどっかいった

http://helm.lu/cube/6x6x6/
これを解いてくれ

うを、それ公式には売ってないやつだね。
でも、基本は全部3x3x3につまってるから、
解くだけならたぶんそれほど難しくないと思う。・・・

3x3x3が解けるのが大前提だけど、まああれだ、
メタマジックゲームとか参考になるらしいよ
http://q.hatena.ne.jp/1138303093

つうかConwayか誰かのnxnxnの解法についての論文があるとか聞いたけど
（ただ注意しなきゃならんのは、純粋数学では元に戻す為に10000000000手かかっても
解法は解法だし、寧ろそういう解法のほうがエレガントであることだが）

ちょいと>>55-58を眺めてたんだけど、

◎�@＊
�@�@�C　これの
＊�C＊
　 ↓
＊＊＊
＊＊�B　ここの結果と
＊�A＊

＊�C＊
�@�@�C
◎�@＊
�@�@�C　これの
＊�C＊
　 ↓
＊�@＊
＊＊�B
＊＊＊
＊＊�A　ここの結果が違うのが疑問だったので、
＊�A＊

改めて調べてみたところ、上のケースの結果が間違っていて、�Aと�Bが逆だった。

ということで、最初の4つのケースを書き直すと、

◎�@＊　　＊�@◎　　＊�C＊　　＊�C＊
�@�@�C　　�C�@�@　　�C�@�@　　�@�@�C
＊�C＊　　＊�C＊　　＊�@◎　　◎�@＊
　 ↓　　　　　↓　　　　　↓　　　　　↓
＊＊＊　　＊＊＊　　＊�A＊　　＊�A＊
＊＊�A　　�B＊＊　　�B＊＊　　＊＊�B
＊�B＊　　＊�A＊　　＊＊＊　　＊＊＊

上＞左　　右＞上　　右＞下　　左＞下

これをまとめて、
「ある一点に対して複数の水滴が同時に到達した場合、処理の優先順位は、右＞上＞左＞下」
（到達点から見た水滴の到来方向）
になる。

で、この「右＞上＞左＞下」を前提とすると>>57の右側のケースで矛盾が生じる（左＞右）が、
これも改めて調べたところ間違っていて、実際は�@と�Aが逆で、

＊�C＊�C＊
�C�@�A�@�C
＊�@◎�@＊
　　 ↓
＊�B＊�B＊
�A＊＊＊�@
＊＊＊＊＊

だった。
これなら右＞左なので、「右＞上＞左＞下」に矛盾しない。

少なくとも俺がやった限りにおいて>>55>>57の結果は正しいはずだ。
それぞれ二回チェックしたし、書き込みミスも無いはず。
>>107で指摘された矛盾に気付いたからこそそれを書き込んだわけで。

何の証拠にもならんが一応上げておく。
ttp://kasamatusan.sakura.ne.jp/cgi-bin2/src/ichi43654.jpg.html

うは、マジだ。
その画像の通り中央でやったら下が�A右が�Bになったよ。
俺は左上の隅でやってたんだけど、こっちはやっぱり下が�B右が�Aになる。
ttp://kasamatusan.sakura.ne.jp/cgi-bin2/src/ichi43658.jpg.html

端でやった場合、�Cの隣の�@に水滴が到達する前に発火点隣の壁に水滴がぶつかるけど、
それが関係してたりするんかな。

とりあえず間違いとか言ってすまんかった。>>109

>>110だったorz

>>111
いや、こっちの語調も無駄にきつかったしお気になさらず。

しかしどんなルールで決まってんだろうね、これ。
ますますわかんなくなってきたよ。

まとめると

左上端でやると>>108
中央でやると>>55

ということですか？まあ、新発見ではあるけど、
これってゲームのルールとしてどうなんだろう・・・

うーん、推測だけど、水滴がどこかにぶつかると、
どこかで遅延なりズレが生じる、みたいなことがあるんじゃないかなぁ。
>>55の

＊�C＊
�@�@�C
◎�@＊
�@�@�C
＊�C＊
　　↓
＊�@＊
＊＊�B
＊＊＊
＊＊�A
＊�A＊

これは、壁際ではないけど、壁の変わりに水玉にぶつかってるから、
>>108の方の結果になってる、みたいな。

なんにしても微妙な仕様であることは確かだね。
もはや数学的な話ではないし……。

このゲームのメーカ製作は以下にあり。ググッて見つけたよ。
誰か、例の「タイミング問題」について、問い合わせてみそ。
（ただし英語だろうけど）
>>22さん、ＨＰにて紹介よろ。
ttp://www.teamtaylormade.com/Software/puzzlegames.shtml

>>116 訂正
×　メーカ製作
○　メーカ
　

ターンの中では移動中の水玉が発生した順に処理が行われる
ただし、移動中の水玉が消滅しても隙間が詰められる事は無いので
どれかが消滅してから新たに発生した場合は処理順序が逆転することがある・・・
ってのが一番自然な処理だと思った。

何となくだけど・・・このパズルGAが向いてる気がする。
全消し前提にして手数を評価にするか手数を固定して消した数で評価するかして。

235

22さんの解法プログラム、バージョンアップしてるね

しばらく書き込みが途絶えてました。

新型solverの解説を軽く書いてみました。

http://kashi.dip.jp/~kashi/mizutama/

より人間に近いというか、とりあえず発火させて見て
様子を観察し、連鎖が継続するように水滴を「事前追加」
することを繰り返す、という考え方がベースになってます。

お疲れ様です〜

165

282

859

「タイミング問題」>>116の件が、解消されなさそうですね。
メーカに問い合わせれば、解消するかもしれませんが。
　
先ほど久々にやってみて思ったのですが、このゲーム、その問題が解消すれば、
「定式的方法」までは無理でも、例えば将棋でいうところの駒の挙動が明確になり、
対PCや複数プレイヤーでの対戦モードなんかがあるゲームに発展できそう。
どこかのソフト屋からパクッて出さないかな。
　
そなれば、羽生さんに一局対戦してもらいたいなぁ。

あけおめ

なるべく飛散した雫が無駄にならないようにする
ってアプローチは？

age

428

336

ひさびさあそんでおもしろかったので
あげさせてもらうよ

夏ｶｼｽ

あげちゃえ

＞解析演習の田中視英子？
だれですかそれ？
私が学生の頃は、斉藤と松本二三蔵だったぞ。

　　　数独　　　
http://science6.2ch.net/test/read.cgi/math/1129393797/

760

http://pya.cc/pyaimg/pimg.php?imgid=53794

こんなものが。

king愛してる

Reply:>>142 不可能を発見し続け、最後に残った可能なものが答えだ。

856

二年五日十一時間。

419

902

age

805

うるさい。

536

928

386

三年。

157

このゲームはpyaで遊んでたな
ざっとしか読んでないけど
�@�@�A
とある時に、左の�@と右の�@とどちらを発火させるかで
結果が変わるけど>>55とか、その辺曖昧でしょ

もう人いないかな

その>>55がまだ見てたりするわけだが。

いくらなんでも読み飛ばしすぎ。その辺のレスで
やってる事はそんな見れば明らかなレベルのことじゃないよ。
曖昧さを排除して調べてみてもゲームの仕様としてやや
不可解な点があるってのが>>107-114あたりでの結論。

ああ、◎が起爆候補の水滴なのか、良く読んでなかった、すまん
同時に到達したらどちらの�@からの破片が
優先してヒットするかっていう話なわけね

そこは一応解明されているとすると
連鎖によってストックがどう増えるかっていうのは
解明されてんの？

それがわかってるとするとこんなアルゴリズムを思いついた

各盤面に相当する最小完全ハッシュ値(>>6のサイズになる)を使えば
自然数を1つの盤面に対応させることが出来る

盤面数(6*6)×垂らす回数のサイズの配列(例えばmax100滴垂らすとすれば36*100のサイズの配列)
(i,j)にn回垂らした時の盤面に相当する最小完全ハッシュ値と、その結果のストックの値の組をいれる
(盤面の計算とストック値の計算は既知としている)

※
　n滴垂らしたときの盤面は(n-1)滴垂らした時の盤面の中で
　ストック値が最大になった物だけから探索する(このi,jは記録する)
　またn=0の時は与えられた問題と、持ち越しのストック値

あるnでクリアの盤面に相当する最小完全ハッシュ値と
ストック値の組が求まったら
そのnの中で最大のストック値を持つnを解とする。(同じ手数でより良いストック値があるかもしれないので)
これによって、最短手順よりもストック値が大きくなることを重視した解が得られる
また、その時の手順は、※で記録しておいた(i,j)のリストになる

※の部分がヒューリスティクスで計算量はかなり減ると思うが
これだと最適値にはならないケースがあるだろうな
　例えば、ストックは増えないが1滴クッションを入れることで
　結果的に最終結果のストック値が大きくなるような場合

読み直してみると日本語が不自由だな。まぁいいや

保守

949

309

301

253

569

506