Numer0nを解くプログラムを作ってみた
1.概要
こんにちは、おにぎりです。皆さんは"Numer0n"を知っていますか、簡単にいうと各桁が重複しない3桁の数字を当てるゲームです。数字があっていて場所が違う場合は"EAT"、数字があっていて場所が同じ場合は"BITE"という風に言います。例えば相手の番号が 213 でコールした数が 319 だったら、相手が 1EAT-1BITE という風に答えます。
説明が下手ですいません(笑)詳しくはwikiでも見てください(Numer0nの基本ルール)
そして、今回はその相手の数字を当てるプログラムをC言語で作ったのでブログを書いてみました。
2.アルゴリズム
プログラムを作る上で一番重要なアルゴリズムを考えます。とりあえず、定石というものがないのであり得ない可能性を省いていくプログラムを考えます。また、EATとBITEを書くのが長いので、□EAT-○BITE だったら □E○B という風に書きます。
条件1. 0E0B のときにその数の可能性を無くす。
例えば 123 で 0E0B だったとき
すべての桁で1,2,3の可能性がなくなります。 これは簡単ですね。
条件2. 0BITE のときにその桁以外のその数の可能性を無くす。
例えば 123 で 0BITE だったとき十の位と一の位で 1
百の位と一の位で 2
百の位と十の位で 3 の可能性がなくなります。
条件3. 0EAT のときにその桁のその数の可能性を無くす。
例えば 123 で 0EAT だったとき百の位で 1
十の位で 2
一の位で 3 の可能性がなくなります。
条件4. □EAT のときにその桁のその数の可能性を上げる。
例えば 123 で 1EAT だったとき百の位で 1
十の位で 2
一の位で 3 の可能性のパラメータを上げます。
条件5. ○BITE のときにその数の可能性を上げる。
例えば 123 で 1BITE だったときすべての桁で 1,2,3 の可能性のパラメータを上げます。(この時の増分は 条件4 の時より少なくします)
条件6. EATとBITEの合計が3のときにその数の以外の可能性を下げる。
例えば 123 で 1E2B だったとき
すべての桁で 0,4,5,6,7,8,9 の可能性がなくなります。
とりあえず、絞り込みの条件はこんなものです。
ここまでやって、ふと思いました
「絞り込んでから、新しい数字作るのどうやるんだ…」
ある程度ランダム要素を含ませないとアルゴリズムの設計上同じ数字がコールされやすいので、パラメータから有り得そうな数字を生成しなければならないが、その方法が思いつかない！！！
「ランダム…？」
「ランダムってことは、モンテカルロ法で行けるんじゃね…？」
ということで、 みんな大好きモンテカルロ法の出番です！！！アルゴリズム考えるのが面倒くさすぎていろいろ試してみたけど、風呂入ったらモンテカルロ法で行けんじゃねって思った— おにぎり (@riceball0712) 2018年1月11日
とりあえず、さっき作ったパラメータを実数の確率形式にします。乱数を使ってその確率から数字を3桁選びます。
また、 すべてのEATとBITEの合計が3になるまでは、数字がすべてかぶらないようにします。(動いてるの見てもらったほうがわかりやすいかも)
あと、2E0B が複数回出るとそれぞれの値を比較し、最低1桁決定させています。
アルゴリズムの内容はこんなものです。
3.プログラム
他人に見せる気が無かったので凄い汚いですが一応ソースコードを貼っておきます。一応動作してるところも貼っておきます。
ちなみに運がいいとすぐ終わります。Numer0n解くプログラム作ったんだけど結構精度良くなった pic.twitter.com/QaOoLpFzTe— おにぎり (@riceball0712) 2018年1月14日
ちなみに運がいいとすぐ終わる pic.twitter.com/OOW36mE0Cd— おにぎり (@riceball0712) 2018年1月14日
4.課題点&感想
・数字を選ぶ時に、一の位から決定をしているので他の位の方が確率が高くても、その数字を選んでしまう可能性がある。>>数字を選ぶ時に条件を追加すればもっと効率が良くなるかも…？
・モンテカルロ法なので、時間がかかるときは試行回数が14回ほど掛かってしまう
>>こればかりはどうしようもない、他のアルゴリズムにすれば解決できるかも(やりたくない…)
・ちゃんと計測したわけじゃないから分からないけど、答えが出るまで平均6手ぐらい
な気がする
・ディープラーニングとかでやってみたい(小並感)
徹夜で書いて誤字脱字が酷かったので、今見て分かった誤字脱字や表現の修正、追記をしました。
返信削除