機械学習周りのプログラミング中心。 イベント情報
ポケモンバトルAI本電子書籍通販中
第28回世界コンピュータ将棋選手権(WCSC28)関係者の皆様、お疲れさまでした。
私は将棋ソフト「ねね将棋」を参加させました。大会の模様は別途記事を書きたいと考えていますが、取り急ぎ、ソースコードを公開いたしました。
やねうら王ライブラリを使用しつつ過去の資産を流用した都合で3つのリポジトリに分断されてしまっています。
https://github.com/select766/ipqueue
セットアップが面倒なので、将棋ソフトの実用品としてはおすすめしません。次回こそはもう少し扱いやすい構成にしたいと思っています。
MCTSの探索部をシングルスレッドにした点が他の参加者から興味を持たれました。この辺りに関する工夫を中心に、ソースコードの解説記事を執筆するつもりです。 探索部コアはuser-search_mcts_async.cppに入っています。
第28回世界コンピュータ将棋選手権まで1か月を切りました。開発者の皆様いかがお過ごしでしょうか。
開発がうまくいかないので現実逃避として、将棋におけるディープラーニング評価関数の雰囲気を知ってもらうため、「ねね将棋mini」というアプリを開発しました。
アプリとはいっても、インストールは不要でWebブラウザ上で動作します。こちらからご覧ください。https://select766.github.io/neneshogi_mini/ 1MB程度のロードが発生しますが、最新のWebブラウザが載っていればスマホでも動作します。
ディープラーニングを使うと、局面を受け取って次の適切な指し手を予測するDNNモデル（ディープニューラルネットワーク）を学習することができます。 DNNの表現力は大きく、先の展開を探索しなくても既存の将棋AIの指し手を40%程度の確率で当てることができます。 そこで、ねね将棋のために学習したDNNで（探索なしに）指し手を選択し、自己対局するアプリが「ねね将棋mini」です。 ディープラーニングの棋風といえるほどのものがあるかはわかりませんが、探索がないのにうまい感じに寄せたりするのは見ていて面白いですよ。
この記事では、ねね将棋miniを構成する技術要素を解説します。
主な要素は次の通りです。
局面（盤上の駒配置、持ち駒、王手かどうか等）を入力とし、各指し手の確率を出力するモデルです。構造としてはConvolutional Neural Networkです。
以下の棋譜を利用させていただきました。 depth10で作った110億局面の教師データ、期間限定で公開します
ねね将棋miniでは複雑さの違う2種類のモデルを提供していて、"small1"では35%、"large1"では40%程度の確率で学習元の棋譜の指し手を当てられる（その指し手の確率が最大となる）ようです。 "small1"だと圧縮した状態で1MBを切るサイズとなっています。
ねね将棋miniでは、生成済みの棋譜をダウンロードするのではなく、Webブラウザ上でDNNを実行し、1手ずつ指し手を生成しています。 初公開バージョンはAI同士の自動対局のみなので生成済み棋譜のダウンロードでもよいのですが、今後人間との対局機能を追加したいと考えています。 その際にはユーザの指し手に呼応してDNNの実行をする必要があります。 DNNの実行が可能なサーバを準備するとなると無料のものはほぼなく、AWS等にお金を払い続けなければなりません。 そこで、アプリを実行するユーザ側の端末上でDNNを実行することにしました。この方式であれば、サーバからは静的なモデルファイルを配布するだけでよくgithub pagesにて無料で公開することができました。 ディープラーニング関連のことをやろうとするとNVIDIA社のGPUを用意し、CUDAのセットアップをして云々という面倒な環境構築が頭をよぎりますが、 Webブラウザの機種非依存の標準機能だけを用いて動作するようになっているため簡単に試すことができます。
DNNの学習自体はChainerフレームワークで行ったのですが、WebDNNというフレームワークによりWebブラウザ上で動作する形に変換することができます。 計算の最適化、モデルの圧縮機能等も搭載されています。今回は使用しませんでしたが、GPUを利用する機能も含まれています。 Chainerモデルの変換は特に難しいことはなく、本体部分は10行程度のpythonコードで書けました。 https://github.com/select766/neneshogi_mini/blob/master/model_convert/model_convert.py
既存のモデルクラスを読み込み、学習したパラメータをセットします。
def load_model(model_config):
model = Model(**model_config["options"])
chainer.serializers.load_npz(model_config["path"], model)
return model
ダミーのデータを流し、計算グラフを取り出します。move, valueというのは方策と状態価値関数（評価値）の2つを出力とするモデルだからです。 train=Falseとし、batch normalizationを無効にしていないとおかしくなるので注意。
def get_graph(model):
dummy_input = np.zeros((1, 86, 9, 9), dtype=np.float32)
x = chainer.Variable(dummy_input)
with chainer.using_config("train", False): # disable batch normalization
move, value = model.forward(x)
graph = ChainerConverter().convert([x], [move, value])
return graph
ブラウザに読み込ませるデータを生成します。ブラウザ上の計算環境としてWebGPU, WebGL, WebAssembly等が選べます。試してみたところWebAssemblyで十分な速度が出たのでこれを使いました。
exec_info = generate_descriptor("webassembly", graph, constant_encoder_name="eightbit")
output_dir = f"../docs/webdnn_model/{model_config['name']}"
exec_info.save(output_dir)
特に変わったところもないモデルなので、すんなりと変換ができました。
JavaScriptで駒の配置や合法手の列挙等が必要なので、Shogi.jsというライブラリを利用しました。盤面の状態はシンプルに配列で表現されていて使い始めるのは簡単でした。
駒の動ける範囲の生成まではあるのですが、王手放置のチェックが実装されていませんでした。探索の指し手生成としては非効率ですが、速度は今回問題にならないため簡単な実装をしました。アイデアは、指した後に手番でなくなる側が王手をかけられていれば王手放置（開き王手を含む）ということです。手番でない側の駒の動きを生成し、その中に相手玉の位置が入っていれば王手放置、という実装になっています。
if (piece.color !== color) {
let moves = this.getMovesFrom(i, j);
for (let k = 0; k < moves.length; k++) {
let move = moves[k];
if (move.to.x === kingPos.x && move.to.y === kingPos.y) {
return true;
}
}
}
将棋盤とDNNをくっつけ、最後にユーザーインターフェースを実装して出来上がりです。
DNNの入力は86×9×9のテンソルになっています。テンソル上のインデックスをT(c,y,x)としたとき、座標(2, 3)に手番側の飛車があればT(6, 2, 3)=1というように値をセットします。
WebDNNの入力は6966(=86×9×9)要素の配列となっており、直接値をセットしようとするとT[6 * (9 * 9) + 2 * 9 + 3] = 1のようにインデックス計算が煩雑になります。
そこで、ndarrayというライブラリを用いて抽象化しました。先ほどの値のセットは次のようにわかりやすくなりました。
let array = ndarray(raw_array, [86, 9, 9]); array.set(6, 2, 3, 1);
DNNの出力も、入力と同じような状況です。合法手それぞれの確率を取り出すことができるので、それに従ってランダムに手を選ぶようにしました。 最大確率の手を指すのが一番強いはずですが、それだと毎回同じ進行になってしまうため、ある程度展開がばらけつつ不自然にもならないようなパラメータを選択しました。
UI部分は極力シンプルに実装しました。10×10のテーブルに駒の文字を入れて盤面の表現にしました。後手番の駒の文字は上下逆にする必要がありますが、画像としては用意せずにCSSで文字を回転させました。
やはり対人戦ができたほうが面白いと思います。そんなに複雑ではないので近日中に実装できればと思います。
このデモに組み込まれているものより強いモデルをお持ちの方、リポジトリをforkして自分だけのデモを作ってみてはいかがでしょうか。
一発ネタです。長らくブログを書いていなかったので生存確認を兼ねて。
駅で電車同士を乗り換える時、階段を使って別のホームに行く場合と、同じホームで向かい側に止まっている電車に乗り換えたり、後続の電車を待ったりする場合がありますよね。 新潟駅では新幹線と在来線を同じホームで乗り換えられるように工事中ということで、同じホームで電車を乗り継げるというのは利便性に重要なことだと認識されています。 そのようなニュースを見ていると、ある駅を出発して、同じホームでの乗り換えだけでどこまでたどり着けるのかが気になりました。
今回は首都圏の路線で考えます。地上の路線は、同じ平面上に多数のホームが並んでいて、うまく乗り継いでいけば様々な路線に行けそうです。 一方で地下鉄は同じ駅でも路線ごとに深さが違っている場合が多く、階段なしにほかの路線へ乗り換えられる駅はあまりありません。しかし、首都圏では地上を走る他社線への直通が多く、直通先で乗り継げばなんとかなるかもしれません。
今回の目標は、銀座線浅草駅を出発点として、同一ホーム上での乗り換えを繰り返すだけでどの地下鉄路線(東京メトロ線・都営地下鉄線)に乗り換えられるか、を調べることと設定しました。 階段を使えないルンバの気持ちになって考えてみましょう*1。
条件を定式化します。微妙なケースは今回存在しませんでした。
調べ方ですが、路線図を見ながら接続駅の構内図を検索し、ある路線と別の路線が乗り換え可能かを調べていきます。2018年3月時点の情報に基づきます。駅名から、駅の構内図等へのリンクを張っています。
それでは出発です。
PASMOエリアの路線図 を見ながらだとわかりやすいです。
特段意味はないのですが、日本初の地下鉄の起点である銀座線浅草駅を出発点に選びました。
銀座線は他社との直通がありません。しかしいきなり詰み、ではありません。地下鉄としては珍しく、同一ホーム上で別路線との乗り換えが可能です。 赤坂見附で丸ノ内線、表参道で半蔵門線と同一ホームで乗り換えられます。
丸ノ内線も同様に他路線との直通がなく、ここで行き止まりです。なお、赤坂見附から支線の方南町へは直通列車がありませんが、中野坂上で乗り換え可能です。
半蔵門線は渋谷から東急田園都市線と直通しており、ここから多数の路線につながります。
東急田園都市線は二子玉川で東急大井町線と乗り換えが可能、東急大井町線は大岡山で東急目黒線と乗り換えが可能です。 東急目黒線は目黒にて南北線・三田線と直通しています。
銀座線浅草からここまでを図にすると、次のようになります。
②では、同一路線の反対方向の線路に移るために適当な駅（中央林間等）で折り返します。
南北線はさらに埼玉高速鉄道線に直通していますが、そこまでで行き止まりです。三田線も同様に行き止まりです。
東急目黒線は田園調布にて東急東横線と乗り換えが可能、東急東横線は副都心線と直通しています。
副都心線は小竹向原～和光市で有楽町線と線路を共用しており、有楽町線へもつながります。 副都心線からは東武東上線・西武池袋線への直通列車があり、西武のほぼすべての路線（孤立している西武多摩川線を除く）に乗り換えが可能でした。気が向いたら郊外私鉄同士のつながりも可視化したいところです。
東急東横線は中目黒にて日比谷線と乗り換えが可能です。以前は直通がありましたが、今は乗り換えが必要になっています。
半蔵門線と新宿線は九段下で乗り換えが可能です。一応半蔵門線と新宿線は別会社なので、2013年までは壁で仕切られていました。参考
ここまで、東急線の助けだけで多くの路線に同一ホームで乗り換えられることがわかりました。地下鉄13路線のうち、9路線を制覇できました。
残っているのは、東西線・千代田線・浅草線・大江戸線です。東西線・千代田線は、ともにJRの路線に直通しています。JRの広大なネットワークにどこか「穴」があれば、これらの路線に乗り換えられそうです。
今までに到達した路線から、JRに抜けるルートはないのでしょうか？1件だけ見つけました。東武とJRを直通する特急スペーシアの利用です。
半蔵門線は東武伊勢崎線（スカイツリーライン）に直通しています。途中で東武日光線・東武日光行きの電車に乗り換えることが可能で、楡木(にれぎ)等で折り返すことにより栃木の浅草方面ホームに到達できます。ここでJR新宿行きの特急スペーシアに乗車でき、栗橋駅でJR線に入り、JR湘南新宿ラインの経路を通って大宮駅に到達します。
なお、栗橋駅はこの直通列車に乗る以外では東武とJRで改札が分離されており、またこの列車ではSuica/PASMOが利用できないという特殊仕様になっています。
別解として、福島県まで北上する必要がありますが東武日光線→東武鬼怒川線→野岩鉄道→会津鉄道→JR只見線→JR磐越西線→JR東北本線という経路も可能かもしれません。
さて、無理やりながらJR線に入ることができました。
スペーシアきぬがわ号はJR湘南新宿ラインの経路で大宮に到着するので、3番線か4番線に到着するものと考えられます。ここでJR上野東京ラインに乗り換え、新橋へ行きます。 新橋で逆方向の上野東京ライン(常磐線直通)に乗り換えられます。
常磐線は複々線で、上野東京ラインから常磐線に直通する列車は快速線、一方で千代田線からの直通列車は各駅停車線を走行します。 最後のポイントは、松戸の3・4番線で常磐快速線から常磐線各駅停車に乗り換える点です。ほかの駅では快速と各駅停車のホームが別になっており乗り換えられません。
常磐線各駅停車から千代田線への直通列車に乗れば、千代田線に入ることができます。10路線目もなんとかなりました。
東西線はJR中央・総武線各駅停車と直通しており、千代田線と同じように考えれば乗り換えられます。しかし中央線系統は意外にも他のJR路線との独立性が高く、容易には入れません。
記事公開時点では難所としていましたが、twitterで@surrogatepairさんに教えてもらいました。
> 湘南新宿ライン→横須賀線→総武快速線→特急新宿わかしお（新宿行き）→秋葉原→中央線各駅停車
— さろげーと(#9,b13) (@surrogatepair) May 21, 2018
> 1日数本しかない列車が必要
わかしおを使わなくても津田沼駅3・4番線から行けないでしょうか？
この情報を踏まえた解は次のようになります。
まず、スペーシアきぬがわ号を浦和で降り、同じ方向の湘南新宿ライン（大船方面横須賀線直通）に乗り鎌倉に行きます。次に逆方向の総武快速線直通列車に乗り換え、稲毛で折り返し、津田沼3番線に到着します。向かい側4番線が各駅停車なので、ここでJR中央・総武線各駅停車に入ることができました。稲毛など適当な駅で西方向に折り返し、中野を通り過ぎて高円寺などで東西線直通列車に乗り換えます。
結果として、快速と各駅停車がホームを共用する特別な駅を使う、という解法で千代田線も東西線も解けることがわかりました。@surrogatepairさんありがとうございました。
記事公開時点での想定解を残しておきます。
数少ない直通列車を使う以外では解が見つかりませんでした。その一例を紹介します。
まず、スペーシアきぬがわ号を浦和で降り、同じ方向の湘南新宿ライン（大船方面）に乗り渋谷に行きます。 次に逆方向の特急成田エクスプレス（中央快速線直通、高尾行き）に乗り換え、吉祥寺で逆方向（東京方面）の中央線快速電車に乗り換えます。 御茶ノ水で中央線各駅停車に同じホームで乗り換えられます。錦糸町など適当な駅で西方向に折り返し、中野を通り過ぎて高円寺などで東西線直通列車に乗り換えます。
中央線各駅停車に入る方法はいくつか別解があります。
- 高崎線→倉賀野→八高線→高麗川→八高線・青梅線・中央快速線直通電車→中央線各駅停車
- 大宮駅から武蔵野線・中央快速線経由の「むさしの号」を利用
- 湘南新宿ライン→横須賀線→総武快速線→特急新宿わかしお（新宿行き）→秋葉原→中央線各駅停車
ですがどれも1日数本しかない列車が必要となり、どうも不完全燃焼でした。
これでどうにか東西線に入ることができました。地下鉄13路線のうち11路線制覇です。
大江戸線は郊外への直通もなく、完全に孤立しています。
浅草線は、両端で京急線・京成線に直通しており、広いネットワークを持っています。しかしながら、いままで挙げた11路線とそこからたどれる路線群とは孤立しているようです。 東京近郊区間大回り Wiki*を参照したところ、浅草線から直通している路線群から改札を通らずに他の地下鉄線に戻ってくることはできなさそうです。
地下鉄線ではありませんが、東京駅などで在来線から乗り換える際にも改札がある新幹線は、他路線と同一ホームでの（改札を通らない）乗り換えは不可能なのでしょうか？ 新幹線と在来線を同一ホームで乗り換えられるよう工事中の新潟駅でも、ホーム上で改札を通らなければならない構造になるようです。参考
しかし、手段は存在しました。東北新幹線から直通する山形新幹線は、普通列車と同じ線路を共用しているのがポイントです。 東北本線で福島へ行き、山形線に乗り換えます。福島4番線に到着するような列車を選ぶ必要があります。 山形線で赤湯へ行くと、同じホームで同じ方向の山形新幹線の列車に乗り換えられます。あとは新庄で折り返して東北新幹線の東京駅に行けます。東京駅でさらに乗り継げば、東北新幹線の仙台方面や、北海道新幹線、上越新幹線、北陸新幹線にも乗り継げることになります。
東海道新幹線方面は、山陽新幹線・九州新幹線を含めてもこのような抜け道はなさそうです。
東京の地下鉄路線同士を、同一ホーム上の乗り換えだけでどこまでつなげられるかという思い付きを検証してみました。
結果として、銀座線を起点としたとき、「銀座線・丸ノ内線・半蔵門線・新宿線」は地下鉄内で乗り換え可能、東急線を介することで「南北線・三田線・副都心線・有楽町線・日比谷線」に乗り換えられました。 東武線とJR線を直通する特急列車を用いることで、「千代田線・東西線」へもなんとか乗り換えが可能でした。一方、浅草線と大江戸線は、それぞれ孤立していることがわかりました。
普通の乗り換え検索とは違う、たいして役に立たない一発ネタにお付き合いありがとうございました。
手法編からの続きです。
まず、学習データの準備です。パーティを10,000個用意して、別の100個のパーティとバトルさせることにより勝率を求めました。
各特徴量を用いてパーティの勝率へ線形回帰します。
単純な最小二乗法でも学習は可能でしたが、「多重共線性」という問題があるため重みの要素が1,000以上の大きな値になってしまい、分析が困難でした。
そのため、リッジ回帰という手法を用いることで完全ではないにせよ分析可能な結果を得ることができました。
リッジ回帰の実装はscikit-learnライブラリを用いました。
9,000個のデータで学習し、残りの1,000個で評価しました。
まず、使用した特徴量ごとの回帰精度を示します。以前の記事で示したように、Pはポケモンの種類、Mは技の種類です。PMはポケモンとその技の組み合わせを示しています。
| P | PP | M | MM | PM | 決定係数R2 |
|---|---|---|---|---|---|
| Y | 0.388 | ||||
| Y | 0.312 | ||||
| Y | Y | 0.691 | |||
| Y | Y | 0.388 | |||
| Y | Y | 0.383 | |||
| Y | Y | Y | 0.847 | ||
| Y | Y | Y | Y | Y | 0.874 |
決定係数R2は回帰の良さを表す指標で、もっとも良い場合で1、最も悪い場合で(回帰先の期待値を定数で出すモデルで)0となります。 ポケモンと技の組み合わせ情報がパーティの強さを予測するうえで有用であることがわかりました。 ポケモンの情報だけ、技の情報だけの場合より、両方の情報がある状況のほうが大きく精度が向上することがわかります。
そして、線形モデルの良い点は、学習で求められた重みから各特徴量次元の寄与度を測れる点です。
今回、特徴量
の要素はすべて0か1であり、勝敗({1, -1})に回帰しているため、対応する重みが正の大きな値であればパーティを強くする効果のある特徴、負の大きな値であればパーティを弱くする効果のある特徴であるとみなすことができます。
現在実装されているポケモンは9種類、技は20種類に制限されていることに注意してください。
実装したポケモン：ダグトリオ・フーディン・ゲンガー・ナッシー・スターミー・ルージュラ・ケンタロス・ラプラス・サンダース
実装した技：ふぶき・１０まんボルト・サイコキネシス・のしかかり・じこさいせい・リフレクター・でんじは・かげぶんしん・きりさく・いわなだれ・はかいこうせん・あくまのキッス・どくどく・ あなをほる・にどげり・かいりき・メガドレイン・あやしいひかり・ナイトヘッド・はねる
まずはP特徴のみで回帰したときの係数を、大きい順に並べて示します。
| 特徴の意味 | 係数 |
|---|---|
| ゲンガー | 0.251 |
| ナッシー | 0.137 |
| ケンタロス | 0.031 |
| スターミー | -0.012 |
| ラプラス | -0.042 |
| フーディン | -0.043 |
| サンダース | -0.053 |
| ダグトリオ | -0.126 |
| ルージュラ | -0.144 |
ゲンガーの係数が最大です。これは、ゲンガーがパーティに入っていると勝率が大きく高まるということを意味しています。ゲンガーはゴーストタイプで、20種類の技のうち5種類を無効化できるところが強い要因だと思われます。 ダグトリオは係数が低いです。この環境だと強力な技「じしん」が使えない点が厳しいものと思われます。ルージュラは「ふぶき」で凍らないというメリットがありますが、意外にも最下位となりました。
次にM特徴のみで回帰したときの係数を、大きい順に並べて示します。
| 特徴の意味 | 係数 |
|---|---|
| ふぶき | 0.111 |
| サイコキネシス | 0.101 |
| 10まんボルト | 0.095 |
| あくまのキッス | 0.069 |
| じこさいせい | 0.067 |
| きりさく | 0.062 |
| はかいこうせん | 0.039 |
| のしかかり | 0.037 |
| いわなだれ | 0.025 |
| どくどく | 0.023 |
| あやしいひかり | 0.022 |
| かげぶんしん | 0.018 |
| かいりき | 0.009 |
| メガドレイン | -0.003 |
| あなをほる | -0.010 |
| にどげり | -0.037 |
| ナイトヘッド | -0.084 |
| でんじは | -0.107 |
| リフレクター | -0.109 |
| はねる | -0.177 |
妥当な順位だといえるのではないでしょうか。こおりタイプ以外の相手を27%の確率で即死させるふぶきが最強です。何の効果もない「はねる」がちゃんと最下位になりました。 「でんじは」も使い方によっては強力ですが、行動選択がランダムなため複数回無駄に使ってしまうなどの事態が生じやすいと思われます。 この序列はあくまで「行動をランダムに選んだ場合」の技の良さを示すものであることに注意が必要です。
最後に、すべての特徴量(P, PP, M, MM, PM)を用いて回帰したときの係数を示します。
まずは値が大きいものから10個示します。
| 特徴の種類 | 特徴の意味 | 係数 |
|---|---|---|
| PM | フーディン&サイコキネシス | 0.156 |
| PM | ナッシー&サイコキネシス | 0.139 |
| PM | ケンタロス&きりさく | 0.134 |
| PM | サンダース&10まんボルト | 0.128 |
| PM | スターミー&サイコキネシス | 0.123 |
| PM | ケンタロス&はかいこうせん | 0.119 |
| PM | ゲンガー&サイコキネシス | 0.111 |
| P | ゲンガー | 0.107 |
| PM | ゲンガー&10まんボルト | 0.105 |
| PM | ゲンガー&ふぶき | 0.105 |
ポケモンとタイプが一致する技の係数が非常に高いことがわかります。ポケモン単独、技単独では測れないポケモンと技の相性のよさを定量化することができていると考えられます。
次に、値が小さいものから10個示します(一部省略)。
| 特徴の種類 | 特徴の意味 | 係数 |
|---|---|---|
| PM | ナッシー&はねる | -0.156 |
| PM | (はねる関係省略) | |
| PM | ケンタロス&ナイトヘッド | -0.097 |
| PM | ナッシー&でんじは | -0.096 |
| PM | (でんじは関係省略) | |
| PM | (ナイトヘッド関係省略) | |
| PM | ゲンガー&リフレクター | -0.088 |
| MM | でんじは&あくまのキッス | -0.084 |
| P | ルージュラ | -0.065 |
| PM | (リフレクター関係省略) | |
| PM | フーディン&にどげり | -0.054 |
| PM | ルージュラ&あなをほる | -0.053 |
| P | ダグトリオ | -0.053 |
| PM | (にどげり関係省略) | |
| PM | ケンタロス&メガドレイン | -0.049 |
まず、はねる等の弱い技とポケモンの組み合わせが目立ちます。次に、「でんじは&あくまのキッス」という技と技の組み合わせが登場しました。 どちらも相手を状態異常にする技ですが、状態異常は複数種類掛けることができないため、この2つの技を両方覚えるのは良くないということが係数に表れています。 また、「フーディン&にどげり」や「ケンタロス&メガドレイン」のように、ポケモンの「こうげき」「とくしゅ」の能力値の大小関係と技が合っていない場合の係数が低いことがわかります。
以上で分析したように、2技関係特徴量により、ポケモンプレイヤーの直観に沿う形でパーティの強さを定量的に予測できることがわかりました。 この技術を用いることで、ランダムにパーティを組み替えるよりも効率的に強いパーティを探索できるようになることが期待できます。
今後はまずポケモン・技の種類を増加させる実装を行ったうえで、今回提案した手法を取り入れながら強いパーティの構築技術を模索していきたいと考えています。
数日前の記事にて研究の構想を発表しました。まだご覧でない方は先にリンク先をご覧ください。
今後はブログで研究の進捗を掲載しつつ、1年に1～2回程度まとめ記事を作れたらよいなと考えています。
以前発表した手法では、パーティの構築とそのパーティを使った行動の学習の2つの最適化を交互に行うことが重要でした。 行動の学習は（深層）強化学習を用いているのに対し、パーティの構築は単純な山登り法でした。 その手法の概略は、
というものでした。強化学習がそれなりにコストのかかる（1パーティにつき数分）処理なのに、学習対象のパーティがランダムというのは効率が良くありません。 ある程度有望なパーティに対してのみ強化学習を行ったほうが良いのではないでしょうか。 ここで、パーティを実際に対戦させなくても、強さがある程度予測できるのではないかという仮説を立てました。 例えば、「サイコキネシスを覚えたフーディン」がいるパーティと、「はねるを覚えたコイキング」がいるパーティなら、前者のほうが明らかに強そうです。 そこで、パーティ構成を入力とし、対戦シミュレーションをせずに勝率を予測する関数が作れるかどうかについて検討しました。
ここでは、パーティ構成を入力、勝率を出力とするような関数を機械学習で求めることにします。 今回は強化学習は用いずに、バトル中の行動選択はランダムとします。また、対戦相手はランダムに構築された100種類のパーティとします。 この条件下で、勝率の予測をできるだけ正確に行うことが課題となります。
この問題は教師あり学習で解くことができます。ランダムなパーティを生成して、実際にバトルを行った勝率を正解データとします。 パーティの勝率を、バトルなしに求める関数のパラメータを学習することが目的です。
ここで、勝率予測関数に入力する特徴量の設計が必要です。 ポケモンの種類・技の種類をシンプルに並べたベクトルを特徴量とし、深層学習で求めてしまうというのも1つの手です。 しかしこれだと、入出力関係がブラックボックスになってしまいあまり面白くありません。 今回は、特徴量を手動で設計し、線形モデルによって勝率を求めることとしました。
前述のように、今回は線形モデルでパーティの勝率を予測します。式で書けば、
となります。は勝率ですが、ここでは-1(全敗)～+1(全勝)の値域としました。
がパーティの構成を表す特徴量です。
は各特徴量に対する重みで、学習によって求めます。
はバイアスですが気にしなくて構いません。
特徴設計ですが、例えば次のような要素が必要と考えられます。
このように、単独のポケモンや技の強さのほか、いくつかのポケモンや技の組み合わせがパーティの強さの指標になると予想できます。
今回は、次のような特徴を考案しました。
P=Pokémon(ポケモン)、M=Move(技)を指しています。
例えば、PM特徴だと、=(ダグトリオ&ふぶき, ダグトリオ&10まんボルト, フーディン&ふぶき, フーディン&10まんボルト, ...)のように各要素が定義されます。
パーティ内にふぶきを覚えたダグトリオと10まんボルトを覚えたフーディンがいる場合、
=(1, 0, 0, 1, ...)という値になります。
現在実装されているポケモンは9種類、技は20種類なので9*20=180個の要素があり、そのうちいくつかが1になったベクトルとして表現されます。
実はこの考え方は、将棋AIで使われる「2駒関係」という特徴量のアナロジーになっています*1。 将棋では3駒関係が主流で、1億要素以上のベクトルで盤面を表現しています。
今回提案した特徴量を総称して「2技関係」と呼ぶことにします。将来的には、3つのポケモンや技の関係を考えることが可能です。ただしその分次元数が増加し、学習が難しくなるというのがデメリットです。 また、「ポケモンと、別のポケモンが覚えている技」という2要素の関係性を考えることも可能です。 金・銀バージョン以降だと「あまごい」や「まきびし」等、場に作用して後続のポケモンに影響を与える技があるため、特に有用な可能性があります。
実験結果は近日公開します。
(2017-12-30 続きを公開しました。)
*1:参考 金子 知適ら「駒の関係を利用した将棋の評価関数」 http://www.graco.c.u-tokyo.ac.jp/~kaneko/papers/gpw03.pdf
明日からコミケ（コミックマーケット）が始まりますね。 私は出展しないのですが、紙媒体で発行する雰囲気を味わうためだけに先日オンラインで公開した同人誌select766.hatenablog.comをコンビニで印刷してみました。 紙媒体の冊子を量産する際のノウハウが少しだけ得られました。
セブンイレブンのコピー機がインターネットにつながっており、ネットサービス ネットプリント で登録したPDFファイル等を印刷することができます。
ユーザ登録して原稿のアップロードまで10分ぐらいで簡単にできました。コピー機に入力する「予約番号」がメールで来ます。
予約番号をコピー機に入力し、印刷。
ホッチキスは別途必要です。コピー本らしい仕上がりになって満足です。
ただ、このやり方だとちょっとコストが高く、B5サイズ27ページ（紙は14枚）で540円かかりました。1ページあたり20円です。 会場で配布するものを製作するなら、データをUSBメモリで持参（ネット経由は単価が高くなる）し、B4サイズに小冊子形式で印刷して折ることで、1ページあたり5円まで下げられます。 ただし、紙を折り曲げて作った冊子をホッチキス止めする「中とじ用ステープラー」がないと不便です。Amazonで500円ぐらいで買えるようです。
セブンイレブン（というよりは印刷機供給元のゼロックス）は公式で同人誌印刷のやり方を解説しているようですね。機会があったら試してみたいと思います。 セブン‐イレブンのマルチコピー機で同人活動をもっと手軽に・もっと楽しく！
2017年も残すところあと1週間。皆様いかがお過ごしでしょうか。
クリスマスイブが暇だという方のため（？）に、ニッチな読み物を用意しました。
人工知能に「ポケモン」の戦略を考えさせたらどうなるか、というテーマで薄い本を書きましたので、興味のある方はぜひ手に取っていただければと思います。無料のPDFです。
次のリンクからどうぞ。 https://github.com/select766/pokeai/releases/download/book-201712/PokeAI-201712.pdf
発行所の「ヤマブキ計算所」ってのは深い意味はなくて、今回のためにつけた一人サークル名のようなものです。
