GPU を用いたコンピュータリバーシの高速化

GPU を用いたコンピュータリバーシの高速化
美濃研究室　T07KF007　奥祐二
グラムを作成する．
1　はじめに
5　minimax 法と αβ 法
現在，画像処理に使われている GPU の高い並
列計算処理を汎用計算処理に応用する研究・開
発がされている．
本研究では，αβ 法によるゲーム木探索を
GPU を用いて大規模並列化することで，探索の
高速化をする．そして最終的にはリバーシの完
全読みを達成する事を目的とする．
minimax 法とは，「自分にとっての最善手は
相手にとっての最悪手」という考えで，相手は
自分にとって最悪の手を打ってくると仮定して，
深さ優先探索（DFS）で自分の最善手を求めるア
ルゴリズムである．[3]
しかし，minimax 法は全ての手をしらみ潰し
に探索するため，ゲーム木の大きさによって探
索ノードが膨大な量になるという欠点がある．
そこで minimax 法における絶対に採用される
ことがない手を枝刈りして効率を改善した αβ
法がある．枝刈りの判定方法は，1 つ上のノー
ドの値を，相手の手番の場合は下限値（α）に，
自分の手番の場合は上限値（β）に設定し，こ
の値を越えた場合に枝刈りをする．αβ 法の枝
刈りの例を図 1 に示す．
例では，相手の手番の時に，α=-3 で，その
範囲に当てはまらない-8 という評価が得られた．
したがって，未探索の子ノードは枝刈りされる．
2　コンピュータリバーシとは
リバーシとは，2 人用のボードゲームで，
8×8 の升目を持つ盤面に，交互に石を置いてい
き，最終的に石の数が多い方が勝つゲームであ
る．コンピュータリバーシとは，リバーシにお
けるプレイヤーの思考をコンピュータにさせる
プログラムである．
3　ゲーム木探索の現状
ゲーム木探索アルゴリズムはゲーム木を使っ
て最善手の探索をするアルゴリズムである．
ゲーム木は木構造であり，局面の評価値をノー
ドで表し，エッジは打った手を表す．今までに
多くのゲーム木の逐次探索アルゴリズムや並列
探索アルゴリズムの研究がされている．その結
果として，1993 年には，6×6 マスのリバーシの
完全読みが達成された．[1]しかし，未だに標準
的な 8×8 マスのリバーシの完全読みは成されて
いない．理由としては，先読みする深さが増え
るほど，探索するノード数が膨大になるという
問題があるためである．
: 自分の手番
: 相手の手番
-3
-3
15
-8
-3
-8
-7
5
-7
図 1:深さ 2 の αβ 法
6　GPU を用いた実装
4　GPU
本研究では，ゲーム木探索の部分を GPU 上で
動作させる．図 2 に深さ２の場合の並列化を示
す．ゲーム木のルートノードから伸びるノード
を各スレッドに割り当てる．全スレッドの探索
が終了した時，GPU は各スレッドの最上位の
ノードの評価値を CPU に返す．そして，CPU は
その中で評価値の高い手を選ぶように実装した．
スレッドはストリーミング・マルチプロセッ
サ（SM）１つにつき１つのスレッドを動作させ
るため，各スレッドは独立となり，スレッド毎
に並列して αβ 探索をする．
今回使用した GPU は再帰呼び出しがサポート
GPU を画像処理では無く，他の一般的な用途
で利用することを GPGPU という．
GPGPU の特徴として大規模なマルチスレッド
がある．GPU はコンテキストスイッチが高速な
ため，たくさんのスレッドを動かすことで性能
を引き出す．したがって，GPGPU ではたくさん
のスレッドを動かすことで，大規模並列化を図
ることができる．
NVIDIA 社は GPU に対する GPGPU 開発環境の
CUDA[2]を提供している．本研究では，この
CUDA を使って GPU 上でゲーム木探索をするプロ
1
されていなかったため，αβ 法のバックトラッ
キングを実装した．
: 自分の手番
: 相手の手番
-8
-3
スレッド１
-8
実行時間 [ms]
-3
15
1000
-3
CPU
-7
17
スレッド２
-9
-7
100
10
GPU
実行時間
1
CPU
実行時間
0
スレッド 3
1
図 2:GPU を用いた αβ 法の並列化
4
7 10 13 16 19 22 25 28
コンピュータの打った手の番号
図 3:深さ 3 の αβ 法において
7　ゲーム木探索の高速化の実験
GPU と CPU での実行時間
7.1　実験方法
表 1:スレッド間の実行時間の分散
GPU を使って，深さ３のゲーム木探索を，深
さ 2 のゲーム木に分割して，スレッド 14 個で並
列探索する．コンピュータがこの探索方法をす
る時の，並列探索するスレッド全てが終わるま
での時間と，並列探索するスレッド１つ１つの
実行時間を，一連のゲームを通して，コン
ピュータの各手について計測をする．高速化の
比較のため，CPU も同様に実験を行う．
実験環境は以下の通りである．
OS : Ubuntu 9.10 (32bit)
CPU: Intel Core i7 (2.67GHz)
GPU: NVIDIA GeForce 9800 GT
(Compute Capability:1.1, SM 数:14)
比率
打った手
[C P U / G P U ] の 番 号
0 .4 9
9
0 .4 8
8
0 .4 7
29
0 .4 6
30
0 .4 1
17
0 .4 0
16
0 .3 6
12
0 .3 5
4
合計時間
[m s ]
1 0 1 6 .3 8
1 1 5 6 .6 8
7 .8 1
2 .1 4
6 2 6 .9 9
7 2 4 .0 4
5 5 8 .2 8
4 7 8 .0 0
探索した
スレッド数
14
13
3
1
13
14
10
9
分散
3 1 .2 4
9 9 .6 8
0 .0 3
0 .0 0
5 9 .3 6
3 6 .5 2
5 0 .3 1
7 6 .7 8
8　まとめと今後の課題
本研究は，GPU を用いてコンピュータリバー
シのゲーム木探索を並列化し，高速化ができた
かどうか実験した．
実験から，GPU を用いてゲーム木探索の並列
化を行ったが，本研究の手法では GPU を使って
ゲーム木探索の高速化はできなかった．
今後の課題として，マルチスレッドのスレッ
ド数を増やすこと，ゲーム木の分割方法がある．
そこで解決策としては，ゲーム木を葉ノードま
で並列化する方法が考えられる．葉ノード単位
でゲーム木を分割できれば GPU の性能を引き出
すことが可能となり，高速化する見込みがある
と考える．
7.2　結果と考察
並列探索するスレッド全てが終わるまでの
実行時間の結果を，実行時間を対数目盛にし
たグラフで図 3 に示す．スレッド１つ１つの実
行時間から得られた，スレッド間の探索にかか
る時間の標準偏差と，実際に探索を行ったス
レッドの数を表１に示す．表１は CPU の実行時
間と GPU の実行時間を比較して，その中で速い
順に並べて上位 8 個のみのデータを示す．
図３から，GPU は CPU と比べて約 10 倍遅かっ
た．表１から，GPU の高速化につながる以下の
特徴 3 つが得られた．
• 探索したスレッド数が多い
• スレッドの実行時間の分散が少ない
• 分割したゲーム木が極短時間で終わる
結果から，スレッドの探索時間が短くなるよ
うな負荷分散や，ゲーム木の分割方法の見直し，
マルチスレッドのスレッド数を増やす必要性が
あることがわかった．
9　参考文献
[1]Joel Feinstein:”Amenor wins world 6x6
Championships!”,http://www.maths.nottingham
.ac.uk/personal/jff/,1993
[2]青木尊之，額田彰:”はじめての CUDA プログラミ
ング”，工学社，2009
[3]Seal Software:”リバーシのアルゴリズム”，工
学社，2003
2
標準偏差
5 .5 9
9 .9 8
0 .1 7
0 .0 0
7 .7 0
6 .0 4
7 .0 9
8 .7 6