何回で満点とれる？【ちょまど問題に挑む人々】
-
- いいね！36
🍣魂🍣
@dolpen
ちょまど問題、正解数別にどんどん候補を分けていく11分木を作るとき、ノードごとにどの回答送れば候補が分かれて階層が小さくなるか、みたいなのを計算しまくるやつです。乱択100でも運が良ければ10いく ideone.com/lxRezG
2014-06-20 19:00:44
M. Morise (忍者系研究者)
@m_morise
ちょまど問題12手のアルゴリズム（修正版） ml.cs.yamanashi.ac.jp/media/chomado.…
2014-06-20 19:06:11
CFS6778
@CFS6778
ちょまど問題は13手がなんとかならんかなぁと思っている。(1111….)(2111….)(3211….)….(4444…3)(4444…4)のドミノ倒し戦法が出来ないかなぁと思っているが難しそう。
2014-06-20 20:29:29
M. Morise (忍者系研究者)
@m_morise
ちょまど問題12手のアルゴリズム（再修正版） ml.cs.yamanashi.ac.jp/media/chomado.… 多分これが一番早いと思います．
2014-06-20 20:45:38
🍣魂🍣
@dolpen
アルゴリズムはほぼ同じだから、全探索はちょくだいさんがやってくれるのを待つとして、今度は解候補の分割方法を、分割後の大きさが小さくなるようにする以外に何かいいアイデアはないかって話になるし、評価関数勝負が始まる。
2014-06-20 20:56:25
M. Morise (忍者系研究者)
@m_morise
さらにしつこくちょまど問題．4択が 1問：3手 2問：4手は手作業で解析し これらを組み合わせて N問（Nは偶数）：N＋2手 まではたどり着いたけど， 4問を全探索したら6未満になるのかは，未だに予想ができない．
2014-06-20 23:02:01
M. Morise (忍者系研究者)
@m_morise
シャワーを浴びながら考えていて気が付いた．ちょまど問題は，さっきの我輩のメソッドとは全く別のアプローチで頑張れば，10手が行けそうに見えてきた．
2014-06-20 23:29:56
暇なおじさん
@kakkies03
【ちょまど問題とは】 ・4択問題が10問。 ・全部の回答を終えると何問正解したかだけが分かる。 ・全問正解すれば終了 ・試行は何回でもできる。 最低何手かかるかという問題。
2014-06-21 00:09:59
かず(原材料に小麦粉を含む)
@kazzna
ちょまど問題、11以下にならない・・・。どうしたらもう一回減らせるんだろう？ github.com/kazzna/chomado
2014-06-21 00:41:31
@jsakamoto
@jsakamoto
ちょまど問題サーバ作ってみた chomado-problem-server.apphb.com「curl http://... -X POST -d "[1,2,3,4,1,2,3,4,1,2]" -H "content-type:application/json"」すると正答数返す #ちょまど問題
2014-06-21 01:08:36
こと💉💉💉💉
@coto_labo
きのうから「ちょまど問題」をぼんやりと考えている。以下、この問題について簡単なメモを書いてみる。素人考えで間違っている可能性がきわめて高いので、参考にされる方はご注意ください（そんな人いないと思うけど）。
2014-06-21 19:17:29
こと💉💉💉💉
@coto_labo
まず「ちょまど問題」の概要はtogetterまとめ、結城浩氏の解説などを参照。わたしがだらだら書くより、よほどわかりやすい。 togetter.com/li/682030 cs.hatenablog.jp/entry/2014/06/… note.mu/hyuki/n/n7b3e0…
2014-06-21 19:18:09
こと💉💉💉💉
@coto_labo
「ちょまど問題」についてツイッター上の議論をすこしおいかけてみたところ、この問題は"Black-peg Mastermind"という名前で知られているとのこと。 twitter.com/akkyhowa/statu… 論文はおそらくこれ。 snovit.math.umu.se/Personal/jaege…
2014-06-21 19:19:18
あっきー＠魔導師Lv.21
@akkyhowa
@chokudai ちなみに4色10個のBlack-peg Mastermindに関しては，2011年のGerold JägerとMarcin Peczarskiの研究で，6という下界と13という上界が与えられているようです． #ちょまど問題
2014-06-20 16:02:54
こと💉💉💉💉
@coto_labo
この"Mastermind"は「ヒット＆ブロー」という名前でも知られているようだけど、このよく知られているゲームでは、選択する答えが重複できないことになっている。「ちょまど問題」は重複を許すので、その点注意が必要。
2014-06-21 19:20:44
こと💉💉💉💉
@coto_labo
でまあ、専門家向けの文書なので素人にはさっぱりわからないのだけど、ぼんやりながめていると、p.3に手数の上界の表がある。ただしこの論文では正解を指定する最後の一手も手数に数えている。「ちょまど問題」関係の用語では「最後の一手」を手数に入れないようなのでここも要注意。
2014-06-21 19:23:40
こと💉💉💉💉
@coto_labo
「ちょまど問題」はこの論文の、p=10,c=4のとき。でその上界がp.5に、b(p,4)≦p+3と与えられている。早い話が「ちょまど問題」は最後の一手までふくめて13手以内で確定できるということらしい。
2014-06-21 19:26:04
こと💉💉💉💉
@coto_labo
ここからわたしがぼんやり考えたことをすこし書く。「ちょまど問題」は問題１０個のすべての正解を見つけないといけない。でも、全部を一度に探すのは大変なので前から順番に確定していくのが戦略としては考えやすい。結城浩氏解説の「２１手戦略」はまさにこれにそったもの。
2014-06-21 19:27:04
ちょまど@ ITエンジニア
@chomado
今深刻な #ちょまど問題 が世間を賑わしていますが、どう考えますか！ — おおお！嬉しいです！まあ『ちょまど問題』と呼ばれているものが拡がるのと同時に私のアホさも拡がっているわけですがそれでも嬉しいです！ ask.fm/a/ame1cc0p
2014-06-21 19:55:00