はじめに

明けましておめでとうございます。あさっち¹と申します。
大晦日に年越しそばを食べながらアルゴリズムの性能評価するためにCPUぶん回してました(笑)

これを機にQiitaを始めて時々専門的なことを綴っていこうと思ってます。適宜GitHubにもpushしていきますので。

なお専門知識をお持ちの方々、内容薄っぺらいなどの怒号・罵声お待ちしております。

導入

ある友達と立体四目並べで勝負した結果ボコボコにやられたんですよね。~~初めてだった、なんて言い訳はしません。~~
それに加えて大学でゲームAIを作るという実験があり、同期が立体四目並べを解くアルゴリズムを実装していたのもあります。

サンプルのソースコードは、以下の東大の伊庭先生のサイトから引用させていただきました²
http://www.iba.t.u-tokyo.ac.jp/software/gameHP/index.html

ただコンピュータと立体四目並べで対戦するだけなら上のサイトでC言語ソースコードがあがってるので、
・難易度選択、先手/後手の選択をコマンドライン引数からではなくシェルスクリプトの実行により分かりやすく可視化
・コンピュータによる推奨手を表示
を主軸に少しコードをいじりました。

なお、色々テストプレイ等してわかったんですが、私ボードゲーム弱すぎることが判明したんですよね…。お恥ずかしい限りです、精進します。

アルゴリズム

詳細は省略します。今回はUCT法を用いた実装とし、性能の評価としてはMinimax法との対戦による勝率、パラメータは以下の通りとします。

UCT法

評価値としては以下で定義されるUCB値
UCB = $A + c\sqrt{B}$
ただし
$A$ : 注目nodeでの勝利数 / 注目nodeに割いたplayout数
$B$ : 2$\log$(全playout数) / 注目nodeに割いたplayout数

第1項$A$はある分岐nodeからのplayoutによる純粋な勝率を表します。一方で第2項は簡単にいうと注目nodeに割いたplayout数がどれほど妥当かどうかを意味します。
この第2項のパラメータ$c$を以下の性能評価の項で変数として動かします。

固定するパラメータは
・総playout数 : 70000
・nodeを展開するplayout数の閾値 : 50
としました。

Minimax法

盤面のそれぞれのマスを以下のように重み付けし、(自分のスコア)-(相手のスコア)を評価値とします。なお、node生成数を抑える$\alpha$-$\beta$法をベースとします。
なお一番上が4段目となります。

minimax.c

int eval_board[4][16] =
  {
    {
      50, -10, -10,  50,
      -10,  10,  10, -10,
      -10,  10,  10, -10,
      50, -10, -10,  50,
    },
    {
      -10,  10,  10, -10,
      10,  30,  30,  10,
      10,  30,  30,  10,
      -10,   0,   0, -10,
    },
    {
      -10,  10,  10, -10,
      10,  30,  30,  10,
      10,  30,  30,  10,
      -10,  10,  10, -10,
    },
    {
      50, -10, -10,  50,
      -10,  10,  10, -10,
      -10,  10,  10, -10,
      50, -10, -10,  50,
    },
  };

その他のパラメータは以下で固定します。
・$\alpha$ = -200000
・$\beta$ = 200000
・探索は5手先まで

性能評価

その1(cの最適化)

先述のUCTのパラメータ$c$を0.1から1.5まで0.1刻みで動かした時のMinimax法との勝率をプロットしたものが以下の図となります。横軸が$c$の値、縦軸がUCT法の勝率です。
なお、ばらつきがあるので各50~250回の対戦です。

もっとも良かったのは$c$ = 0.7で勝率86%(215/250)でした。

その2(先手/後手の有利性)

その1で求めた$c$ = 0.7を固定した状態で、UCT法 vs UCT法を実行します。同じ条件のもとでコンピュータ同士を対決させたらどちらが有利なのか、というのを検証します。

700戦させたところ先手が364勝336敗でやや有利かな？といったところでしょうか？

余談ですが、将棋だとソフトPonanza同士の対決でも先手有利というデータが出てますね(2015年現在)
https://twitter.com/issei_y/status/599185896710148096

ソースコード

~~設計図共有サイト~~GitHubに掲載してあります。
Max OSやLinuxで動かすには、端末を開いていただき

$ git clone https://github.com/taiyaki8926/Tic-tac-toe
$ cd Tic-tac-toe
$ ./tic-tac-toe.sh

としてもらえれば動くと思います。

(2019-12-20 追記)
Windows環境で動くか確認しておりませんでしたが、この度Bash on Windowsでも動作確認がとれましたので以下に記します。

以下の記事に従ってbashを導入して下さい。

Win10のBash on Windows をインストールする

bashを導入した後は必要なモジュールを引っ張ってきます。

# 上の記事にも書いてある通り各種更新を行う
$ sudo apt update
$ sudo apt upgrade

# gitコマンドのインストール(おそらく不要のはず)
$ sudo apt-get install git

# makeコマンドのインストール
$ sudo apt install make

# gccコンパイラのインストール
$ sudo apt-get install gcc

# 実行
$ git clone https://github.com/taiyaki8926/Tic-tac-toe
$ cd Tic-tac-toe
$ ./tic-tac-toe.sh

課題

やっぱりCUI見にくいので、パイプライン化してmatplotlibマルチスレッド化、GUIの補強みたいなことができればなお良しです(理想はJavaScript記述だけど自分の力ではちょっと厳しいかな…)。

簡単に追加できそうなのはログの記録/表示と1手前に戻すUndo実装。あと、easyを選択した時にはeasyレベルのコンピュータ推奨手しか出せないことも問題点ですね…

Twitter : @taiyaki8926 ↩
ソースコード自体は厳密には2,3年前の学生が作ったものです。 ↩

立体四目並べのアルゴリズム実装と性能評価