ねね将棋miniを開発しました

第28回世界コンピュータ将棋選手権まで1か月を切りました。開発者の皆様いかがお過ごしでしょうか。

開発がうまくいかないので現実逃避として、将棋におけるディープラーニング評価関数の雰囲気を知ってもらうため、「ねね将棋mini」というアプリを開発しました。 アプリとはいっても、インストールは不要でWebブラウザ上で動作します。こちらからご覧ください。https://select766.github.io/neneshogi_mini/ 1MB程度のロードが発生しますが、最新のWebブラウザが載っていればスマホでも動作します。

概要

ディープラーニングを使うと、局面を受け取って次の適切な指し手を予測するDNNモデル(ディープニューラルネットワーク)を学習することができます。 DNNの表現力は大きく、先の展開を探索しなくても既存の将棋AIの指し手を40%程度の確率で当てることができます。 そこで、ねね将棋のために学習したDNNで(探索なしに)指し手を選択し、自己対局するアプリが「ねね将棋mini」です。 ディープラーニングの棋風といえるほどのものがあるかはわかりませんが、探索がないのにうまい感じに寄せたりするのは見ていて面白いですよ。

この記事では、ねね将棋miniを構成する技術要素を解説します。

主な要素は次の通りです。

  • DNN
    • 指し手を決定するコアとなるモデル(評価関数)です。
    • やねうらおさん提供の棋譜をもとに教師あり学習しています。
  • DNNのランタイムフレームワーク
    • ねね将棋miniでは、生成済みの棋譜をダウンロードするのではなく、Webブラウザ上でDNNを実行し、1手ずつ指し手を生成しています。
    • Webブラウザ上でDNNを実行するためのフレームワークWebDNNを活用しています。
  • 将棋盤の表現
    • 駒の利きなどを含めた将棋盤の表現をWebブラウザ上で行うためにShogi.jsを活用しています。
    • 王手のチェックがなく、そのままでは合法手生成に使えなかったためforkして機能を足しました。
    • 王手放置、打ち歩詰めを考慮した合法手生成機能を実装しました。
  • DNNの入力生成
    • DNNの入力は3次元のテンソル形式で行います。これは86×9×9のテンソルになっており、駒の配置の情報を加工して入力する必要があります。
    • 1次元のフラットなベクトル上で操作するのがわかりにくかったので、ndarrayというライブラリで抽象化しました。

DNN

局面(盤上の駒配置、持ち駒、王手かどうか等)を入力とし、各指し手の確率を出力するモデルです。構造としてはConvolutional Neural Networkです。

以下の棋譜を利用させていただきました。 depth10で作った110億局面の教師データ、期間限定で公開します

ねね将棋miniでは複雑さの違う2種類のモデルを提供していて、"small1"では35%、"large1"では40%程度の確率で学習元の棋譜の指し手を当てられる(その指し手の確率が最大となる)ようです。 "small1"だと圧縮した状態で1MBを切るサイズとなっています。

DNNのランタイムフレームワーク

ねね将棋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;
        }
    }
}

全体をつなげてUIをくっつける

将棋盤と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

条件を定式化します。微妙なケースは今回存在しませんでした。

  • 同一ホーム乗換とは、駅にてある電車から降りた後、そのホームに接するいずれかの線路に入ってきた電車に乗り換えることを指します。同じ線路を走る後続列車でもかまいません。
    • 改札を通ったり高さの違う場所を通ることはできません。
    • 終着駅のくし形ホーム(Eの字)の扱いは微妙です。
  • 定期列車であれば、本数の少ない直通列車を利用してもかまいません。
  • 乗車券の発売要件は気にしません。物理的に実行可能*2なら、終点または途中駅での折り返し乗車も可です。

調べ方ですが、路線図を見ながら接続駅の構内図を検索し、ある路線と別の路線が乗り換え可能かを調べていきます。2018年3月時点の情報に基づきます。駅名から、駅の構内図等へのリンクを張っています。

それでは出発です。

PASMOエリアの路線図 を見ながらだとわかりやすいです。

銀座線→丸ノ内線半蔵門線

特段意味はないのですが、日本初の地下鉄の起点である銀座線浅草駅を出発点に選びました。

銀座線は他社との直通がありません。しかしいきなり詰み、ではありません。地下鉄としては珍しく、同一ホーム上で別路線との乗り換えが可能です。 赤坂見附丸ノ内線表参道半蔵門線と同一ホームで乗り換えられます。

丸ノ内線も同様に他路線との直通がなく、ここで行き止まりです。なお、赤坂見附から支線の方南町へは直通列車がありませんが、中野坂上で乗り換え可能です。

半蔵門線東急田園都市線東急大井町線東急目黒線南北線三田線

半蔵門線は渋谷から東急田園都市線と直通しており、ここから多数の路線につながります。

東急田園都市線二子玉川東急大井町線と乗り換えが可能、東急大井町線大岡山東急目黒線と乗り換えが可能です。 東急目黒線は目黒にて南北線三田線と直通しています。

銀座線浅草からここまでを図にすると、次のようになります。

f:id:select766:20180305214239p:plain
銀座線~東急線南北線

②では、同一路線の反対方向の線路に移るために適当な駅(中央林間等)で折り返します。

南北線はさらに埼玉高速鉄道線に直通していますが、そこまでで行き止まりです。三田線も同様に行き止まりです。

東急目黒線東急東横線副都心線有楽町線

東急目黒線田園調布にて東急東横線と乗り換えが可能、東急東横線副都心線と直通しています。

副都心線小竹向原和光市有楽町線と線路を共用しており、有楽町線へもつながります。 副都心線からは東武東上線西武池袋線への直通列車があり、西武のほぼすべての路線(孤立している西武多摩川線を除く)に乗り換えが可能でした。気が向いたら郊外私鉄同士のつながりも可視化したいところです。

東急東横線日比谷線

東急東横線中目黒にて日比谷線と乗り換えが可能です。以前は直通がありましたが、今は乗り換えが必要になっています。

半蔵門線新宿線

半蔵門線新宿線九段下で乗り換えが可能です。一応半蔵門線新宿線は別会社なので、2013年までは壁で仕切られていました。参考

新宿線からの直通で、京王線へも乗り換えが可能です。

ここからが難しい

ここまで、東急線の助けだけで多くの路線に同一ホームで乗り換えられることがわかりました。地下鉄13路線のうち、9路線を制覇できました。

残っているのは、東西線・千代田線・浅草線大江戸線です。東西線・千代田線は、ともにJRの路線に直通しています。JRの広大なネットワークにどこか「穴」があれば、これらの路線に乗り換えられそうです。

半蔵門線東武伊勢崎線東武日光線→特急スペーシア→JR湘南新宿ライン

今までに到達した路線から、JRに抜けるルートはないのでしょうか?1件だけ見つけました。東武とJRを直通する特急スペーシアの利用です。

半蔵門線東武伊勢崎線スカイツリーライン)に直通しています。途中で東武日光線東武日光行きの電車に乗り換えることが可能で、楡木(にれぎ)等で折り返すことにより栃木の浅草方面ホームに到達できます。ここでJR新宿行きの特急スペーシアに乗車でき、栗橋駅でJR線に入り、JR湘南新宿ラインの経路を通って大宮駅に到達します。

なお、栗橋駅はこの直通列車に乗る以外では東武とJRで改札が分離されており、またこの列車ではSuica/PASMOが利用できないという特殊仕様になっています。

別解として、福島県まで北上する必要がありますが東武日光線東武鬼怒川線野岩鉄道会津鉄道→JR只見線→JR磐越西線JR東北本線という経路も可能かもしれません。

さて、無理やりながらJR線に入ることができました。

JR湘南新宿ライン→JR上野東京ライン常磐快速線常磐線各駅停車→千代田線

スペーシアきぬがわ号はJR湘南新宿ラインの経路で大宮に到着するので、3番線か4番線に到着するものと考えられます。ここでJR上野東京ラインに乗り換え、新橋へ行きます。 新橋で逆方向の上野東京ライン(常磐線直通)に乗り換えられます。

常磐線複々線で、上野東京ラインから常磐線に直通する列車は快速線、一方で千代田線からの直通列車は各駅停車線を走行します。 最後のポイントは、松戸の3・4番線で常磐快速線から常磐線各駅停車に乗り換える点です。ほかの駅では快速と各駅停車のホームが別になっており乗り換えられません。

常磐線各駅停車から千代田線への直通列車に乗れば、千代田線に入ることができます。10路線目もなんとかなりました。

JR湘南新宿ライン→特急成田エクスプレス中央快速線→中央線各駅停車→東西線

東西線はJR中央・総武線各駅停車と直通しており、千代田線と同じように考えれば乗り換えられます。しかし中央線系統は意外にも他のJR路線との独立性が高く、容易には入れません。

数少ない直通列車を使う以外では解が見つかりませんでした。その一例を紹介します。

まず、スペーシアきぬがわ号を浦和で降り、同じ方向の湘南新宿ライン(大船方面)に乗り渋谷に行きます。 次に逆方向の特急成田エクスプレス中央快速線直通、高尾行き)に乗り換え、吉祥寺で逆方向(東京方面)の中央線快速電車に乗り換えます。 御茶ノ水で中央線各駅停車に同じホームで乗り換えられます。錦糸町など適当な駅で西方向に折り返し、中野を通り過ぎて高円寺などで東西線直通列車に乗り換えます。

これでどうにか東西線に入ることができました。地下鉄13路線のうち11路線制覇です。

中央線各駅停車に入る方法はいくつか別解があります。

ですがどれも1日数本しかない列車が必要となり、どうも不完全燃焼でした。

浅草線大江戸線は孤立

大江戸線は郊外への直通もなく、完全に孤立しています。

浅草線は、両端で京急線・京成線に直通しており、広いネットワークを持っています。しかしながら、いままで挙げた11路線とそこからたどれる路線群とは孤立しているようです。 東京近郊区間大回り Wiki*を参照したところ、浅草線から直通している路線群から改札を通らずに他の地下鉄線に戻ってくることはできなさそうです。

新幹線

地下鉄線ではありませんが、東京駅などで在来線から乗り換える際にも改札がある新幹線は、他路線と同一ホームでの(改札を通らない)乗り換えは不可能なのでしょうか? 新幹線と在来線を同一ホームで乗り換えられるよう工事中の新潟駅でも、ホーム上で改札を通らなければならない構造になるようです。参考

しかし、手段は存在しました。東北新幹線から直通する山形新幹線は、普通列車と同じ線路を共用しているのがポイントです。 東北本線福島へ行き、山形線に乗り換えます。福島4番線に到着するような列車を選ぶ必要があります。 山形線赤湯へ行くと、同じホームで同じ方向の山形新幹線の列車に乗り換えられます。あとは新庄で折り返して東北新幹線の東京駅に行けます。東京駅でさらに乗り継げば、東北新幹線の仙台方面や、北海道新幹線上越新幹線北陸新幹線にも乗り継げることになります。

東海道新幹線方面は、山陽新幹線九州新幹線を含めてもこのような抜け道はなさそうです。

まとめ

東京の地下鉄路線同士を、同一ホーム上の乗り換えだけでどこまでつなげられるかという思い付きを検証してみました。

結果として、銀座線を起点としたとき、「銀座線・丸ノ内線半蔵門線新宿線」は地下鉄内で乗り換え可能、東急線を介することで「南北線三田線副都心線有楽町線日比谷線」に乗り換えられました。 東武線とJR線を直通する特急列車を用いることで、「千代田線・東西線」へもなんとか乗り換えが可能でした。一方、浅草線大江戸線は、それぞれ孤立していることがわかりました。

東西線への乗り換えはもう少しエレガントな方法がほしいところでした。

普通の乗り換え検索とは違う、たいして役に立たない一発ネタにお付き合いありがとうございました。

*1:電車とホームの隙間を乗り越えられるのかは知りませんが。

*2:銀座線渋谷駅のように、乗降ホームが完全に分離されている場合は不可

ポケモン×人工知能 2技関係によるパーティ強さの予測(実験編)

手法編からの続きです。

実験

まず、学習データの準備です。パーティを10,000個用意して、別の100個のパーティとバトルさせることにより勝率を求めました。

各特徴量を用いてパーティの勝率へ線形回帰します。 単純な最小二乗法でも学習は可能でしたが、「多重共線性」という問題があるため重み \boldsymbol{w}の要素が1,000以上の大きな値になってしまい、分析が困難でした。 そのため、リッジ回帰という手法を用いることで完全ではないにせよ分析可能な結果を得ることができました。

リッジ回帰の実装はscikit-learnライブラリを用いました。

http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.RidgeCV.html#sklearn.linear_model.RidgeCV

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となります。 ポケモンと技の組み合わせ情報がパーティの強さを予測するうえで有用であることがわかりました。 ポケモンの情報だけ、技の情報だけの場合より、両方の情報がある状況のほうが大きく精度が向上することがわかります。

そして、線形モデルの良い点は、学習で求められた重み \boldsymbol{w}から各特徴量次元の寄与度を測れる点です。 今回、特徴量 \boldsymbol{x}の要素はすべて0か1であり、勝敗({1, -1})に回帰しているため、対応する重みが正の大きな値であればパーティを強くする効果のある特徴、負の大きな値であればパーティを弱くする効果のある特徴であるとみなすことができます。

現在実装されているポケモンは9種類、技は20種類に制限されていることに注意してください。

実装したポケモンダグトリオフーディン・ゲンガー・ナッシー・スターミー・ルージュラケンタロスラプラス・サンダース

実装した技:ふぶき・10まんボルト・サイコキネシス・のしかかり・じこさいせい・リフレクター・でんじは・かげぶんしん・きりさく・いわなだれはかいこうせん・あくまのキッス・どくどく・ あなをほる・にどげり・かいりき・メガドレイン・あやしいひかり・ナイトヘッド・はねる

まずは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技関係特徴量により、ポケモンプレイヤーの直観に沿う形でパーティの強さを定量的に予測できることがわかりました。 この技術を用いることで、ランダムにパーティを組み替えるよりも効率的に強いパーティを探索できるようになることが期待できます。

今後はまずポケモン・技の種類を増加させる実装を行ったうえで、今回提案した手法を取り入れながら強いパーティの構築技術を模索していきたいと考えています。

ポケモン×人工知能 2技関係によるパーティ強さの予測(手法編)

PokéAI(ポケモン×人工知能)ネタです。

数日前の記事にて研究の構想を発表しました。まだご覧でない方は先にリンク先をご覧ください。

select766.hatenablog.com

今後はブログで研究の進捗を掲載しつつ、1年に1~2回程度まとめ記事を作れたらよいなと考えています。

最適化手法の問題点

以前発表した手法では、パーティの構築とそのパーティを使った行動の学習の2つの最適化を交互に行うことが重要でした。 行動の学習は(深層)強化学習を用いているのに対し、パーティの構築は単純な山登り法でした。 その手法の概略は、

  1. ベースとなるパーティを用意する。(最初はランダム)
  2. パーティ内のポケモン・技をランダムに変えたものを多数用意する。
  3. 各パーティの行動選択方法を学習し、勝率が最大のパーティを選択する。
  4. 2に戻る。

というものでした。強化学習がそれなりにコストのかかる(1パーティにつき数分)処理なのに、学習対象のパーティがランダムというのは効率が良くありません。 ある程度有望なパーティに対してのみ強化学習を行ったほうが良いのではないでしょうか。 ここで、パーティを実際に対戦させなくても、強さがある程度予測できるのではないかという仮説を立てました。 例えば、「サイコキネシスを覚えたフーディン」がいるパーティと、「はねるを覚えたコイキング」がいるパーティなら、前者のほうが明らかに強そうです。 そこで、パーティ構成を入力とし、対戦シミュレーションをせずに勝率を予測する関数が作れるかどうかについて検討しました。

問題の定義

ここでは、パーティ構成を入力、勝率を出力とするような関数を機械学習で求めることにします。 今回は強化学習は用いずに、バトル中の行動選択はランダムとします。また、対戦相手はランダムに構築された100種類のパーティとします。 この条件下で、勝率の予測をできるだけ正確に行うことが課題となります。

この問題は教師あり学習で解くことができます。ランダムなパーティを生成して、実際にバトルを行った勝率を正解データとします。 パーティの勝率を、バトルなしに求める関数のパラメータを学習することが目的です。

ここで、勝率予測関数に入力する特徴量の設計が必要です。 ポケモンの種類・技の種類をシンプルに並べたベクトルを特徴量とし、深層学習で求めてしまうというのも1つの手です。 しかしこれだと、入出力関係がブラックボックスになってしまいあまり面白くありません。 今回は、特徴量を手動で設計し、線形モデルによって勝率を求めることとしました。

特徴量の設計

前述のように、今回は線形モデルでパーティの勝率を予測します。式で書けば、

{ \displaystyle
y = \boldsymbol{w}^T  \boldsymbol{x} + b
}

となります。 yは勝率ですが、ここでは-1(全敗)~+1(全勝)の値域としました。 \boldsymbol{x}がパーティの構成を表す特徴量です。 \boldsymbol{w}は各特徴量に対する重みで、学習によって求めます。 bはバイアスですが気にしなくて構いません。

特徴設計ですが、例えば次のような要素が必要と考えられます。

このように、単独のポケモンや技の強さのほか、いくつかのポケモンや技の組み合わせがパーティの強さの指標になると予想できます。

今回は、次のような特徴を考案しました。

P=Pokémon(ポケモン)、M=Move(技)を指しています。 例えば、PM特徴だと、 \boldsymbol{x}=(ダグトリオ&ふぶき, ダグトリオ&10まんボルト, フーディン&ふぶき, フーディン&10まんボルト, ...)のように各要素が定義されます。 パーティ内にふぶきを覚えたダグトリオ10まんボルトを覚えたフーディンがいる場合、 \boldsymbol{x}=(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分ぐらいで簡単にできました。コピー機に入力する「予約番号」がメールで来ます。

予約番号をコピー機に入力し、印刷。

f:id:select766:20171228143035j:plain

ホッチキスは別途必要です。コピー本らしい仕上がりになって満足です。

ただ、このやり方だとちょっとコストが高く、B5サイズ27ページ(紙は14枚)で540円かかりました。1ページあたり20円です。 会場で配布するものを製作するなら、データをUSBメモリで持参(ネット経由は単価が高くなる)し、B4サイズに小冊子形式で印刷して折ることで、1ページあたり5円まで下げられます。 ただし、紙を折り曲げて作った冊子をホッチキス止めする「中とじ用ステープラー」がないと不便です。Amazonで500円ぐらいで買えるようです。

セブンイレブン(というよりは印刷機供給元のゼロックス)は公式で同人誌印刷のやり方を解説しているようですね。機会があったら試してみたいと思います。 セブン‐イレブンのマルチコピー機で同人活動をもっと手軽に・もっと楽しく!

PokèAI ~人工知能の考えた最強のポケモン対戦戦略~

2017年も残すところあと1週間。皆様いかがお過ごしでしょうか。

クリスマスイブが暇だという方のため(?)に、ニッチな読み物を用意しました。

人工知能に「ポケモン」の戦略を考えさせたらどうなるか、というテーマで薄い本を書きましたので、興味のある方はぜひ手に取っていただければと思います。無料のPDFです。

次のリンクからどうぞ。 https://github.com/select766/pokeai/releases/download/book-201712/PokeAI-201712.pdf

発行所の「ヤマブキ計算所」ってのは深い意味はなくて、今回のためにつけた一人サークル名のようなものです。

第5回将棋電王トーナメント総括(本番編)

2017年11月11日から12日にかけて、ドワンゴ日本将棋連盟主催の「第5回将棋電王トーナメント」に「ねね将棋」というソフトで出場しました。この記事では、東京・六本木の「ニコファーレ」で行われた本番の感想などを述べます。

ソフト開発に関しては、以前書いた記事をご覧ください。

select766.hatenablog.com

戦績としましては、ねね将棋は、予選で3勝5敗となりました。予選落ちです。

前日準備

大会前日(金曜日)から会場にはマシンが用意されており、将棋ソフトのセットアップが可能でした。参加は任意ですが、時間が取れたのでこの日に会場でセットアップを行いました。

依存ソフトウェア問題

C++製のソフトだと、実行バイナリと評価関数ファイルを設置するだけで終わることが多いかと思います。ねね将棋はPython製で依存するライブラリが多いため、会場でセットアップするための事前準備が必要でした。会場でのネット環境が不明だったため、ライブラリをオフラインでインストールできるようにあらかじめダウンロードしてUSBメモリに入れて持っていきました。最近のソフトはインストーラがネット接続を前提としている場合が多く面倒でした。

結果的には会場のマシンからかなり高速なネット接続が可能で、そこまで準備することは必須ではありませんでした。本番対局中だけネット接続を切断するという運用がなされていました。

依存ソフトウェアの種類が多いため30分ほどはかかりましたが、事前準備をしっかりしていたため、会場でのセットアップと動作確認はすんなり進みました。Linux利用勢はここでOSの入れ替えが必要なので大変そうでした。

予選(11/11)

9:00ごろ会場入りしました。テスト対局を経て本番に臨む準備が整いました。ソフトのトラブル対応を見越してか時間には結構余裕が取ってありました。ほかの開発者と交流していればそんなに暇という感じではありませんでした。

会場はこんな感じです。

f:id:select766:20171214081828j:plain

第1局 vs Ponanza

初戦は誰と対局になるか事前に知らされておらず、いきなり対局が始まるという状況でした。

開始直後の表示がこちら。

f:id:select766:20171214081703p:plain

お、おう。

Ponanzaに勝てるわけがないので、ある意味プレッシャーは減りました。バグでおかしな挙動をしたり30手で詰まされたりしなければOKという意識です。

Ponanzaは山本さんではなく、今回新たに参加された大渡さんが改良および本番の操作をされていました。従来通りの高速な探索部と深層学習を組み合わせて強化されたそうです。極限までチューニング済みの探索部に、鈍足な深層学習を組み合わせるのは難しい仕事だっただろうと想像します。

対局は、Ponanzaが1手ごとに着実に評価値を上げていきねね将棋の負けとなりました。偶然にもPonanza引退の大会で対戦できたことを光栄に思います。選手権だとシードがあるので強いソフトと弱小ソフトと当たることはそもそもなく、貴重な機会でした。

第2局 vs Novice

各局の対戦相手は、それまでの勝ち数が同じになるように組まれます。ここでは1敗同士の対戦になりました。

Novice戦。Noviceは探索部の高速化を重視されているそうです。

35~45手目でねね将棋の指し手が迷走し、一気に敗勢となり2連敗となりました。

第3局 vs 十六式いろは改

ここまでねね将棋は2連敗。1勝はしたいという目標を掲げていたので、焦ってきました。

十六式いろは改戦。十六式いろは改が先手で、いきなり定跡(やねうら王の標準定跡を使用しています)を外されたためねね将棋が2手目を即指しせず、バグったかと焦りました。

十六式いろは改は、相手が動かした駒の周囲にある自分の駒を動かすというルーチン(!?)で動いているそうです。ねね将棋が8五歩と飛車先を伸ばすと、8六歩と応じてくる独特すぎる棋風でした。

飛車先をそのまま突破し、20手で詰みに至りました。ねね将棋の初勝利です。

f:id:select766:20171214081743j:plain

開発者の方が楽しそうにお話しされていて、対局の勝ち負けだけではなく楽しむことも大事だと改めて思いました。

第4局 vs TMOQ

TMOQ(「とくだいもっきゅ」と読むようです)戦。

この間にニコ生に出演。阿部先生に(ソフト名の元ネタの)ねねっちネタを拾えてもらえて満足。

対局のほうは悪手で一気に形勢が悪くなり、そのまま負けました。

第5局 vs Girigiri

Girigiri戦。

Girigiri側が飛車を活用できず、ねね将棋が徐々に評価値を上げる初の展開でした。

Girigiriは数手先の負けを見切ると投了ではなく反則負けをするというちょっと変わった仕様らしく、58手目でGirigiriの反則負け。棋譜解析では4手で詰む局面でした。

第6局 vs CGP

CGP戦。

CGPはしっかり読みを実装されているらしく、順調に評価値を稼がれてねね将棋の負けとなりました。

評価関数がなんであれ、探索部がしっかり実装されているソフトは強敵です。

第7局 vs にこあ将棋

にこあ将棋戦。

にこあ将棋が先手で、初手5八玉。またいきなり定跡を外れる展開でした。

早々ににこあ将棋が角を捨ててしまい、一気にねね将棋が駒を成る展開となりました。ねね将棋3勝目。

第8局 vs なのは

なのは戦。

24手目まで定跡が続く対局でした。

50手目で事件が起きました。ねね将棋がクラッシュし、時間切れ負けとなりました。

ログを見たところ、読み筋が千日手になった場合に置換表の参照部分がおかしくなることがあるようです。開発中には起きなかったバグで、痛恨の敗戦となりました。棋譜解析によれば互角の局面で、最後まで指したいところでした。

伝統あるなのはとの対局で、強さ以前のソフトの品質についてもっとよく考えなければいけないと学びました。

決勝トーナメント(11/12)

翌日の決勝トーナメントはニコ生で観戦していました。優勝者決定の前には会場に行こうかと思っていたのですが、体調が思わしくなく断念。

自分は野田さんの「平成将棋合戦ぽんぽこ」を応援していました。ぽんぽこ vs Ponanza、ぽんぽこ vs shotgunの戦いは特に緊張して見ていました。自分の将棋の棋力は低いですが、西尾先生の解説を聞きながら上位陣の巧妙な手筋に感服していました。

ぽんぽこ優勝、おめでとうございます。

今後に向けて

すでに述べた通り、ねね将棋は予選で3勝5敗となりました。2か月ほどのソフト開発でここまで達成できたことは満足しています。しかしやはり対局で負けると悔しいとも感じました。次はもっと勝ちたい、という気持ちを感じたので、2018年5月に開催されるであろう世界コンピュータ将棋選手権でぜひリベンジしたいと考えています。

深層学習を用いた将棋ソフトの開発技術はまだまだ成熟していません。設定すべきパラメータ、学習のさせ方等に大幅な改善の余地があるでしょう。また、長い手数の詰みを見つけるという点では従来の軽量な評価関数を用いた深い探索はなくならないでしょう。これらの融合というのも大きなテーマになると思います。

最後に、大会主催のドワンゴ様、日本将棋連盟様、大会で対局・交流させていただいた開発者の皆様、そのほかコンピュータ将棋を応援してくださる皆様に深く感謝申し上げます。