人生で初めて公開したWebアプリNumeron appの紹介 - 11月 24, 2018 こんにちは、ぐぐりら(@guglilac)です。 今年の夏に、初めてwebアプリを公開したのですが、あんまりその詳細とかを紹介してきませんでした。 (作った直後にインターンが立て続けに入っていたのが原因なのですが。。。) これです。 Numeron App せっかく作ったので、そこで使った技術やアルゴリズムの紹介をする記事を書きたいと思います。 (追記) herokuの無料プランの関係で、今回作ったNumeron appは公開を停止しました。 この記事は仕組みのみの紹介となります。 よろしくお願いいたします。 ## 何を作ったの?? 先ほどリンクをのせましたが、再掲します。 [Numeron App](https://numeron-app.herokuapp.com) Numeron appという名前のwebアプリというかゲームを作りました。 といってもかなり単純な数当てゲームです。 numeronという名前は、このゲームを扱ったTV番組でつけられていた名前です。 [Numer0n - Wikipedia](https://ja.wikipedia.org/wiki/Numer0n) やったことがある/見たことがある方も多いかもしれませんね。 3桁の数字をお互い決めて、交互にその数字を当てあうゲームです。 コールされた数字がどれぐらい正解に近いかどうかの情報が相手から与えられるので、それを手がかりに答えを探っていくというのが基本的な流れになります。 ルールを確認するための一人用チュートリアルのページも作ってあります。 こちらになります。 [Reactで数当てゲーム(NumerOn)を作ってみた(遊べるよ!)](http://www.smartbowwow.com/2018/04/reactnumeron.html) ここで練習して、慣れてきたらCPU対戦([Numeron App](https://numeron-app.herokuapp.com)) するとたのしめます。 ## 何を使って作ったの?? 使用技術はこんなかんじ。 * React * Flask * Python * heroku ### React フロントエンドはReactを使って作りました。 今年の春ごろに友達とアプリ作ってた時に自分はReactをやっていて、その練習にと思って数当てゲームの枠は先にあらかじめ作っていました。(CPU対戦はこの時期は未実装) 数当てゲームはよくプログラミングの入門書とかに載っている練習問題で、新しいプログラミング言語を学ぶ時はよく数当てゲームをつかって練習します。 で、夏休みに入って一人対戦では寂しいのでせめてCPUと戦えるようにしたら楽しいかも、と思ってCPUのアルゴリズムを考えて実装し、強そうだったのでアプリに組み込みました。 春頃作ったフロント側はコードとしてはGitHubにはおいておらず、Code Penというサービス上で動かしていただけだったので、それをまず持ってきてAPIを叩いてCPUのコールを取得するように改造する工程が必要でした。 Reactの環境構築もこれがはじめてでした。(友達と作ってた時はdockerで完全に整えてもらったのをビルドしただけだった & Code Penは環境構築いらずのサービスなので。。。) ### Flask サーバー側は、PythonのフレームワークであるFlaskで作りました。 Flaskはちょっとしたことをすぐできるので好きで、いくつか記事も書いています。 ぼくのかんがえるさいきょうのFlaskアプリのディレクトリ構成 Reactでレンダリングやユーザーの入力をうけて、CPUの次の一手はReact側からAPIを叩いて取得します。 友達とアプリを作ってた時はサーバー側を任せっきりだったので、ここで初めてReactとサーバー側を連携させる部分を実装したのですが、結構はじめてで苦労しました。笑 CPUのアルゴリズムは機械学習とかは用いていないので、Pythonである必要はないのですが、なんとなく一番慣れているPythonを使いました。 サーバー側もJavascriptでかけるやつを試してみたい気もしたのですが、まあまたの機会に。 ### heroku できたアプリはherokuで公開しました。 アプリひとつだけなら無料プランでもいけるので、初心者にはありがたいです。 GitHubリポジトリを登録しておくと、変更があったら自動で変更を本番環境に反映してくれるし、すごいんですね。 はじめてアプリが公開された時はとてもうれしかったです。 ## CPU対戦用のアルゴリズムはどうなってる?? 3桁、0~9に制限して計算量が小さいものを扱うことにします。 コール、とはゲーム中で相手の数字を宣言する行為のこととしましょう。 基本的には、選択情報量を計算して一番情報が得られそうなコールを行う、という戦略がよさそうです。 選択情報量は、「コール$X$を行った時に平均的にどれだけの情報が得られるかの期待値」 を指すこととします。 選択情報量はエントロピーともいうので、以下ではエントロピーとかきます。 ざっくりいうと あるコール$X$をしたときに、どれくらい答えが絞れるか、がエントロピーでした。 コール$X$にたいしてエントロピー$I(X)$を以下のように定義します。 判定結果(1H1Bなど)の集合$Y$, 判定結果を$A$とする。$A \in Y$ コール$X$に対して判定$A$が得られる確率を$P(A|X)$とすると、 $I(X)=-\sum_{A \in Y}P(A|X)\log P(A|X)$ と定義します。 確率$P(A|X)$は $X$をコールしたとした時の答え候補のジャッジを全て調べて、得られた判定集合から割合を計算すればいいですね。 さて、このエントロピー$I(X)$が最大になるコール$X$をすれば一番答えが絞られそうなコールができるわけなので、効率よく答えを絞り込んでいくことができそうです。 ですが、エントロピーを計算する範囲($X$の属する集合)を、現時点で答えになりうるものに絞るべきかどうかは自明ではなさそう。 答えでは絶対にありえないけど、めちゃめちゃ情報が得られる可能性の高いコールと、答えにはなりうるけどあんまり候補が絞れないようなコールを比較したりする必要がありそうです。 つまり * これまでの判定から答えとしてあり得るものの中で情報量が最大のもの の他に * 全て(今までの判定結果から間違っているとわかるコールもふくめて)のコールのなかから情報量が最大のもの というアイデアも存在するのでは、と思いました。 しかし、同じ情報量であれば当たる可能性の高い方がいいので、当たる可能性も考慮したいのはもちろん。 ということで、新たな判断指標を提案。 $index(X)=\lambda\frac{1}{|ans\ candidates|}+ I(X)$ として、全て(今までの判定結果から間違っているとわかるコールもふくめて)のXについてindexを計算して最大となるXをコールする。$\lambda$はハイパーパラメータです。 ハイパーパラメータのチューニング実験を行ってみて、良さそうなハイパーパラメータを決めました。 結構$\lambda$のあたいは小さい方が良かったので、純粋に答え候補の集合の中からエントロピー最大を持ってくるので良かった説はあります。。笑 実験ではハイパーパラメータありにしましたが、実際に動かしているアルゴリズムは答えの候補となるコール集合についてのみエントロピーを計算するようにしています。 ## CPU部分のソースコード 一部分だけ載せようと思います。 ```python:util.py """Utility用のクラスやメソッド.""" from collections import Counter import math CHARS = "0123456789" # 使用できる文字の種類 DIGITS = 3 # 桁数 class Judgement(): """Judgement Class.""" def __init__(self, hit=0, bite=0): """Initialize. hit:位置も数字も同じである桁数 bite:位置は違うけれど含まれてはいる個数 """ self.hit = hit self.bite = bite def __repr__(self): """表示用.""" return "{}H{}B".format(self.hit, self.bite) def __eq__(self, other): """HitとBiteがそれぞれ等しければ等価. :param other: Judgement instance :return :boolean """ return self.hit == other.hit and self.bite == other.bite def __ne__(self, other): """__eq__の逆. :param other: Judgement instance :return :boolean """ return not(self.hit == other.hit and self.bite == other.bite) def __hash__(self): """Judgement classを辞書のキーにするために必要.""" return int(str(self.hit) + "1000" + str(self.bite)) def judge(num1, num2): """二つの数字列を比較して判定を行う. :param num1,num2:str,str :return: Judgement """ jg = Judgement() for i in range(DIGITS): for j in range(DIGITS): if num1[i] == num2[j]: if i == j: jg.hit += 1 else: jg.bite += 1 return jg def is_valid_number(num): """入力として不適当な数字列かを判定する. :param num:str :return: boolean """ if len(num) != DIGITS: return False else: for i in range(DIGITS): if num[i] not in CHARS: return False if num.count(num[i]) != 1: return False return True def entropy(num_list, num): """コールした数字のエントロピーを計算する. :param num_list:list of str. 答えの候補のみ含む. :param num: str. コールした数字列. :return: entropy(float) """ n = len(num_list) judges = [judge(cand, num) for cand in num_list] dicts = Counter(judges) prob = [v / n for v in dicts.values()] return sum([-p * math.log(p) for p in prob]) ``` ```python:cpu.py """CPU class.""" from solver.utils import * from itertools import permutations from random import choice, shuffle class Numeron_CPU(): """CPU class.""" def __init__(self): """Initialize.""" self.candidates = ["".join(e) for e in list(permutations(CHARS, DIGITS))] def update_candidates(self, num, j): """新しくコールした数字列と判定結果を用いて答え候補を更新する. :param num: str. 新しい答え. :param j: Judgement class.判定結果 """ self.candidates = [ ans_cand for ans_cand in self.candidates if judge(ans_cand, num) == j] return def call_num(self): """数字をコールする. :return: num(str) """ scores = [entropy(self.candidates, e) for e in self.candidates] return self.candidates[scores.index(max(scores))] ``` ## まとめ 初めて公開したWebアプリであるNumeron appの紹介記事でした。 React,Flask,Python,herokuなどいろいろ使って勉強になりました。 こんな感じで、数理的な部分と開発の両方が混ざったものを扱っていきたいな、と思いました。 読んでくださってありがとうございます。 CPUをぜひ倒してみてください。 [Numeron App](https://numeron-app.herokuapp.com) この記事をシェアする Twitter Facebook Google+ B!はてブ Pocket Feedly コメント Unknown2019年7月9日 20:46こんにちは。授業でプログラミングの勉強をしていて、こちらのCPUのプログラミングについてもっと詳しく聞きたいです。具体的にCPUの部分の答えを絞るところのソースコードが見たいです!返信削除返信ぐぐりら2019年7月10日 22:31コメントありがとうございます!基本的には記事中にあげたコードでCPUの実装は全てです。記事中にはすでに答えではないとわかっているものも候補に入れている(λを使っているところ)のですが、あまり性能が改善してなかったので、単純にエントロピー最大の数字をコールするようにしていたはずです。。ここにコードをすべて置いてあるのでよろしければhttps://github.com/habroptilus/numeron/tree/master/solver削除返信返信返信コメントを追加もっと読み込む... コメントを投稿
こんにちは。授業でプログラミングの勉強をしていて、こちらのCPUのプログラミングについてもっと詳しく聞きたいです。
返信削除具体的にCPUの部分の答えを絞るところのソースコードが見たいです!
コメントありがとうございます!
削除基本的には記事中にあげたコードでCPUの実装は全てです。
記事中にはすでに答えではないとわかっているものも候補に入れている(λを使っているところ)のですが、あまり性能が改善してなかったので、単純にエントロピー最大の数字をコールするようにしていたはずです。。
ここにコードをすべて置いてあるのでよろしければhttps://github.com/habroptilus/numeron/tree/master/solver