CODE VS for STUDENT で作ったAI、「MazAI」の紹介

CODE VS for STUDENTの決勝用AI提出が完了しました！

残念ながら、予選通過したバージョンからいい感じの改良ができず、実質的にはわずかなバグ修正だけで終わってしまいました。
予選通過したときの記事にも貼ったAIの動画がこれです↓
youtu.be

提出したAIの内容を紹介したいと思います。
名前は「MazAI」です。
決勝AIは名前が「MazAI-Z」になっています。マザイゼットです。

提出したAIの概要

敵の盤面は見ずに、一人ゲームとして処理した。

評価関数

すべての列に1～9のブロックを落とし、最大スコアの連鎖を記録。
スコア = 連鎖数 * 1000 + log_10(連鎖スコア) * 1000
また、一定数以上の連鎖をしたノードには送ったオジャマ数*1000点を加算する。

このスコアに以下の値に係数をかけたものを足す。

予告オジャマ数
フィールドのオジャマ数合計
フィールドの色ブロック数合計
和が10になる特定の配置の数(5種類)

f:id:piroz95:20161206230025p:plain

各列の高さ(10列)
各列の高さの差の絶対値(9列)
最大連鎖
最大連鎖の消費ブロック数 / 連鎖数
最大連鎖の発火点の高さ

合計30次元

係数は機械学習を使って決めた。
詳しくは後述する。

探索

送れるオジャマの数が200を越えたら即発火する。
ビームスタックサーチ(chokudaiサーチ)を用いた。
ハッシュ(zobrist hash)による重複消去を実装した。
最初の発火までは深さ13・時間2500ms。
発火後は、深さ10・時間1500ms。
発火したノード(お邪魔を一定以上送ったノード)はそれ以上展開せず、ビームとは別に保存する。
発火ノードが存在しない時はビームサーチの結果を普通に使う。
発火ノードが存在するとき、そのいずれかに向かう。
発火ノードのうち、スコアと発火ターンで見て下位互換になっているものは候補から消しておく。
また、送るオジャマの数が200を超える発火ノードは最も早いものだけ残す。
向かうノードはノードのスコア/1.11^ターン数が最も高いものを採用した。

評価関数の係数の自動調整

「将棋機械学習」でググったら出てきた
近年のコンピュータ将棋の急速な伸びの理由は？ | やねうら王公式サイト
に影響を受けてやってみました。
（けどよく分からなかったので助けてほしいです。）

$X$ を盤面とする。
$X$ の特徴値ベクトルを小文字で $x$ と表すことにする。
特徴値を計算する関数を $\phi$ とすれば $x=\phi(X)$ とも書ける。

ベースの評価関数の評価値を $f(X)$ ,パラメータベクトルを $w$ とする。
機械学習付き評価関数の評価値 $f'(X)$ を次のようにする。
$f'(X) = f(X) + w^T x$
( $w^T x$ は $w$ と $x$ の内積)

このとき、浅い探索の評価値を深い探索をしたときの評価値に近づけるということを考える。
$X$ からベースの評価関数の値を用いて $i$ 手読んだ結果の最良の盤面を $X_i$ と表す。
$s,d$ を $s < d$ を満たす定数として、 $w$ を調整して次の式を最小化したい。
$\{f(X_d) - f'(X_s)\}^2$
つまり次式の最小化になる。
$\{f(X_d) - f(X_s) - w^T x_s\}^2$

ここまで1つの盤面 $X$ について考えたが、実際は複数の教師データについていい感じになるようにする。
盤面 $X$ に対して教師データを $(x_s,f(X_d) - f(X_s))$ とする。
$N$ 個の教師データを $\{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\dots,(x^{(N)},y^{(N)})\}$ と表すと、
$w$ に対する目的関数 $L(w)$ は
$L(w) = \frac{1}{N} \sum_i^{N} (y^{(i)} - w^T x^{(i)})^2$
で表されて、これを最小化する。

これは微分可能な連続最適化の問題になり、勾配降下法を使うことができるが、勾配の計算が重いので代わりに確率的勾配降下法(SGD)を用いる。
SGDの学習率の更新にはAdaGradを使った。

あとは、特徴量に正規化をかけたりL2正則化を入れた。

$s,d$ は、最終的には $s=0,d=5$ とした。
教師データは実際の対戦における自陣の盤面を使用した。

機械学習失敗話

正直、よく分からずに使っている部分があってパラメータおみくじみたいになった。
正規化を入れないとヤバかった気がする。(追記：正規化がバグってた)
改良したAIの対戦から教師データを取ったらなぜか弱くなったことがあった。
教師データの数を増やしたら弱くなったことがあった。
特徴量は2000次元くらいのものも試したが最終的に30次元の方が強かった。
- 30次元の特徴量は色々な特徴量をぶちこんだ所から係数が大きいものを人力チョイスした。
ここを書いていて不安になって機械学習なしバージョンと戦わせ始めたら連敗した
- 追記：2-3くらいの割合で負けた

追記：
takaptさんにtwitterでリプを頂いてやり取りしていたら、正規化する時に分散の計算をバグらせていたことが分かりました。
takaptさんありがとうございました。
$\sigma^2 = E(X^2) - E(X)^2$ を計算するところを1箇所 $N$ で割り忘れていて[\sigma^2 = N E(X^2) - E(X)^2]を計算していました。
このバグった正規化の結果から何を学習していたのかは謎です。
次元数を減らして強くなったというのは、特徴量の計算時間が減って探索ノード数が増えたという可能性があります。
悲しい・・・

週末に決勝

チームラボ本社で決勝😇
live.nicovideo.jp

2ヶ月くらいの間どういうことを試していたかの記事はまた別に書きます。