この記事は Retty inc. Advent Calendar 13日目の記事です．
昨日はRyosukeMurai氏(@RyosukeMurai)のRettyでよく使うベイジアンフィルター（ベジタリアンフィルターではない）でした．

こんにちは！ Retty inc.のsakataです．これでRetty Advent calendar三本目(サンプルコードで使われているものは除く)のKotlin記事になります．そろそろRetty社内にKotlin激推し勢力がいることにうすうす気づき始めたでしょうか．みなさんKotlinは書いていますか？かわいいですよね．¹

巷ではDeepLearningが流行っていますね．Rettyでも徐々に製品に活用されつつあります．DeepLearningではライブラリの関係でPythonやC++が採用されることが多い気がしますが，KotlinはかわいいのでAIも簡単にかけてしまいます．そこでこの記事ではKotlinを使ってボードゲームAIを書いていきます．(ただしDeepLearningではない)

題材を決める

まず，AIが解決する問題を決めなければなりません．下の条件を満たすと(締切的に)良さそうです．

実装がかんたんである
盤面の良し悪しを数値化しやすい
総当りで解くのは厳しい程度にゲームの進行パターンがある

ということで今回はリバーシ(オセロ)でやっていこうと思います．一応今回と同じ仕組みでチェスでも将棋でも囲碁でもオリジナルのボードゲームでもいけます．

ゲームを実装する

gradleプロジェクトを作り，kotlinでコマンドラインアプリケーションを作っていきます．Kotlinはかわいいのでコマンドラインアプリケーションを作るのもかんたんです．

build.gradle(抜粋)

apply plugin: 'kotlin'
apply plugin: 'application'

mainClassName = "io.github.yusaka39.reversi.commandline.main.MainKt"

dependencies {
    compile "org.jetbrains.kotlin:kotlin-stdlib:$kotlin_version"
    compile project(':game')
}

run {
    standardInput = System.in
}

一部抜粋です．大体いつも通りですね．いつAndroidアプリにしようとか思っても良いようにゲームの処理のみを担当するサブモジュールgameを作っておきます．

ゲームの実装

後々色々なタイプのプレイヤー(人が入力するプレイヤー，今回実装するAI，ネットワーク越しに操作できるプレイヤー等)を実装したり各種アウトプットインターフェースに対応する可能性を考慮してゲームからの情報の表示とプレイヤーはインターフェースを定義してAbstractFactoryパターンで組み替えれるようにしておきます．gameモジュールに上記インターフェースとゲームの処理をゴリゴリ実装していき，ルートモジュールにそれらを使ってCUIリバーシを実装していきます．

Pluggableにする

せっかくモジュールを切ったので，外で実装されたgameモジュールに含まれるインターフェースの実装を実行時に組み込んでいろいろな実装のプレイヤーで勝負できると楽しいですね．ということでかんたんなプラグインの仕組みを作ります．引数に渡されたpathからjarを探してAbstractPlayerFactoryのサブクラスを探します．

Main.kt(抜粋)

private fun getPlayerFactoryClasses(args: Array<out String>):
        List<Class<out AbstractPlayerFactory>> {
    val urls = args.getOrNull(0)?.let {
        File(it).listFiles { f, name -> name.matches(Regex(""".*\.jar$""")) }
                .filterNotNull()
                .map { it.toURI().toURL() }
    } ?: emptyList()

    return ClassPath.from(URLClassLoader.newInstance(urls.toTypedArray())).topLevelClasses
            .map { try { it.load() } catch (e: NoClassDefFoundError) { null } }
            .filter {
                it?.let {
                    it != AbstractPlayerFactory::class.java &&
                            AbstractPlayerFactory::class.java.isAssignableFrom(it)
                } ?: false
            }
            .map { it as Class<out AbstractPlayerFactory> }
}

今回はクラスパスを漁るのにguiceを利用しました．
あとはよしなにインプットからPlayerFactoryを選べるようにします．

Randomに打つPlayerで遊んでみる

動作確認のためRandomに打つPlayer(以後Rand君)を実装してみます．有効な打ち手から一つをランダムで選びます．

動かしてみる

ここまで来ると一応遊ぶことができます．

$ ./gradlew distTar
$ cd build/distributions/
$ tar -xf reversi-1.0-SNAPSHOT.tar
$ ./reversi-1.0-SNAPSHOT/bin/reversi

動きました

試しにRand君同士で何回か戦わせてみます．

$ for i in $(seq 0 200); do ./reversi-1.0-SNAPSHOT/bin/reversi << EOF | grep 'WIN' >> log; done   
1
1
EOF
$ sort log | uniq -c
  91 CPU[BLACK] WIN
 105 CPU[WHITE] WIN

引き分けはカウントされてません．単純なボードゲームだと先手が有利なことが多い気がしますがリバーシはそうでもないようです．試行回数増やすと結果変わってくるかもしれませんが．

AIを実装する

ここまで来るとAIを実装することができます．今回AIが自分の手を選ぶときに使うアルゴリズムにはalpha-beta法を利用します．

min-max法

alpha-beta法の土台になるアルゴリズムです．ゲームの展開の分岐を木構造で表したものの中から自分に有利な展開を選択するのに使います．

先を読んだ上で、ある局面がどの程度有利であるかを評価するには、以下の考え方を用いればよい。
1. 読みたい局面が相手の番であれば、その局面の次に出現するすべての局面のうち最も悪い（不利な）、つまり相手にとって最も有利な(評価値が最小)手を相手は打ってくるはずである。そこで、次に出現するすべての局面の評価値の最小値を局面の評価値にすればよい。
2.読みたい局面が自分の番であれば、その局面の次に出現するすべての局面のうち最も良い評価(評価値が最大)の手を打つことができる。そこで、次に出現するすべての局面の評価値の最大値を局面の評価値にすればよい。

wikipedia から引用

alpha-beta法

min-max法の探索に枝刈りの仕組みを入れたものです．このウェブページにわかりやすい図解があります．

min-maxの説明からわかるように，今回作成するAIの強さは盤面を評価する関数の良し悪しとゲーム木の何手先を終端ノードとして盤面を評価するか(i.e. 何手先まで読むか)で決まります．枝刈りが効率的だと読める手の数が増えたり探索が高速になったりします．

実装

新しくgradleプロジェクトを作り，libsディレクトリを作って先程作った本体のdistのlibからgameモジュールのjarをコピーしてきます．思うがままに実装します．

AlphaBetaPlayer.kt

    override fun handleTurn(board: Board, validMoves: List<Grid>): Grid {
        val threadPool = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors())
        val treeToScore = ConcurrentHashMap<Node, Int>()
        validMoves.forEach {
            threadPool.execute {
                val tree = Node(this.side, it, board.clone().apply {
                    this.put(this@AlphaBetaPlayer.side, it)
                })
                treeToScore[tree] = evaluateScore(tree)
            }
        }
        threadPool.shutdown()
        threadPool.awaitTermination(1, TimeUnit.MINUTES)
        return treeToScore.maxBy { it.value }!!.key.move
    }

今回はこんな感じで実装しました．evaluteScore()の中でalpha-beta法を使って木を評価しています．評価関数はとりあえず

自分の石の数 - 相手の石の数

として5手先まで読むようにしました．最近はシングルコアCPUを殆ど見ないので最初の分岐を基準に並列で探索しています．一分間待って終わらなければその時点で一番評価の高い手を返します．~~Interruptする仕組みを書くのが面倒だったので~~残ったタスクは時の流れに身をまかせます．(一分超えることも殆ど無いし)

Rand君と戦わせてみる

AIが入ったプロジェクトをビルドしてできたjarを適当なところに突っ込みます．今回はdistTarを解凍した中にplayersディレクトリを作って配置しました．

$ ./bin/reversi $(pwd)/players/

無事jarファイルが読み込まれました！

勝てました！何回か戦わせてみます．

$ for i in $(seq 0 20); do ./bin/reversi $(pwd)/players << EOF | grep 'WIN' >> log; done
0
2
EOF
$ sort log | uniq -c
  17 ALPHA_BETA[BLACK] WIN
   4 CPU[WHITE] WIN

思ってたより良い結果が出ました．

改善例

評価関数を改善する

今回は単純に石の数の差を評価値として使いましたが，リバーシの石には価値の差があります．例えば自分が取ってる角やそれに隣接した辺にある自分の石は敵の石になることがないので価値が高いといえます．あるいは，リバーシにおいては次のターンに相手が置ける場所を減らしていくのは有効な戦法ですので相手のそれも評価関数に組み込めるでしょう．例えば次のようなものが考えられます．

\boldsymbol{x} := [自分の石の数, 相手の石の数, 相手が置ける手の数...] \\
\boldsymbol{w} := [それぞれのパラメータにかかるウェイト...] \\
score = \sum_{i=0}^{パラメータの数}\boldsymbol{w}_i\boldsymbol{x}_i

評価関数を調整する

上の例をそのまま使います．この場合，評価関数の良し悪しはウェイトの値で決まります．例えば自分に有利なパラメータに負のウェイトをかけると全力で負けるAIになってしまいます．でもウェイトを一つ一つ調整しては強いかどうか確かめる，なんてことはしたくありません．そこで遺伝的アルゴリズムを使って調整してみるのはどうでしょう．なんかよくわからないけど大きな可能性を感じるので好きです．ウェイトを遺伝子としてたくさんのプレイヤーを生成してバトル・ロワイヤルさせましょう．勝率の高いものを次の世代に生き残らせます．きっとそのうち強い組み合わせのウェイトが生まれるはずです．~~ホントはここまでやろうと思ったけど時間が足りなかった．~~

そもそも別の手段で手を選ぶ

DeepLearningとかどうでしょう．きっと強くなります．

成果物

おもむろにAIを実装したくなった人のために役に立つかもしれないので今回の記事のために作ったものをMITライセンスで公開しておきます．

reversi本体 github
alpha-betaなAIPlayer github

Kotlinの魅力はたくさんあるのですが話すと長くなるし他にたくさん記事があるのでこの記事ではKotlinの魅力を"かわいい"で全て通します ↩

超実用的でラブリーなKotlinで古典的AI