東海大学紀要情報通信学部
東海大学紀要情報通信学部
vol.7,No2,2014,pp.9-16

論文

Vol.x, Nox, 20xx, pp.xxx-xxx

論文

NSL による Blokus Duo Multi Game AI システムの実装
玉城 良*1 ,清水 尚彦*2

Implementation of Multi Game AI system of Blokus Duo on FPGA with NSL
by
1
*2 *2
*1*andTamaki, Naohiko
NaohikoShimizu
SHIMIZU
RyoRyoTAMAKI(receivedon Sep.22,
onJanuary
Jan.13, 2015)(Received:
September
22,20142014&&accepted
Accepted:
13, 2015)
Abstract
is athatgame
two players
move onpieceson aofboard
1414.
In thegameplayers
BlokusDuo,researchers
have
Blokus Blokus
Duo is aDuo
game
twothatplayers
move pieces
a board
14 ×of14.
In thegamefor fortwotwoplayers
BlokusDuo,researchershavestudiedstudieda GameAI fromtheInpast
years.theIn general,game AI isby
structuredusing
ansearchgame tree
search of algorithm.
is thea GameAI from
the past
years.
general,game AItheis structured
using an by
game
tree
of algorithm.
There is theThere
one ofissue ofissue of gametree searchof algorithm
is a complicatedprocedureof gametree. Inthis
order
to improve
this issue,
weAI
designedgameonetreeofsearchalgorithm
is a complicatedprocedureof game tree.
In orderto improveissue,
we designeda Gamesystem aon an
pruning.byThis
systemis designed
by using
NSL(Next
Game
AI system
FPGAofbyanusing
tree searchof an α−βFPGA
by using
game ontreeansearch
α − game
β pruning.
This system
is designed
using
NSL(Next
Synthesis
Language),
andSynthesis
it can design
Language), procedure.
and it can design
the complicatedprocedure. Fora high-speed,
we implemented
a parallelized
calculationof the calculationGamethe complicated
For a high-speed,
we implemented
a parallelized
a calculationof the Game
AI. As a result,an average
Asprocessa result,ofanthe
averagecalculation
the processof thethreemoves game tree search have been 8.24 seconds.
time AI.
of thethree moves
gametime
treeofsearch
have been
8.24
seconds.
Keywords:
NSL(Next
Synthesis
Language),
BlokusDuo,Alpha-Beta
Pruning
Keywords:
FPGA,FPGA,NSL(Next
Synthesis
Language),
BlokusDuo,Alpha-Beta
Pruning
NSL(Next
Synthesis
Language),
キーワード: FPGA,
NSL(Next
Synthesis
Language),
ブロックスデュオ,α−β法
ブロックスデュオ,
α−β法
キーワード
: FPGA,関連する研究として，以下のように，Blokus Duo Game AI の実装の報告が挙げられる． いずれも，FPGA(Field Programmable
Gate Array) 上にシステムを実装している．

1. はじめにチェスや囲碁，将棋などの人工知能分野の中の Game AI の研• Sugimoto らは，高位合成 Cyber Work Bench を使用し，高速な Blokus Duo Solver を実装している 3) ．
• Liu C らは，モンテカルロ法による，play-out4) を行って最善手を算出している 5) .
• Jiu Cheng Cai らは，高位合成を利用して，複雑な評価関数を多く用意することで，探索空間を狭めても強い Game
AI を実現している 6) ．
• Kojima らは α − β 探索をする二つの CPU コアを載せたGame AI を設計している 7) ．

究は古くから研究されており，1997 年には IBM の Deep Blue1)と呼ばれるチェス専用のスーパーコンピュータが当時のチェス
世界チャンピオンと対戦し，勝利している． コンピュータチェ
スの研究を経て囲碁・将棋などのゲームが研究され，その中でも近年では，Blokus Duo と呼ぶゲームが盛んに研究されている
5)6)7)． Blokus Duo は 14×14 のサイズの盤面上で行う二人零和

有限確定完全情報ゲームである． このゲームは盤面の組み合わせが有限であるため，完全な先読みが可能である． このような二人零和有限確定完全情報ゲームの AI は，ゲーム木と呼ぶデータ構造を探索し，終局まで先読みをして自分が勝利するような高位合成言語やソフトウェアを用いて Game AI を設計する利点

指手を選択し，ゲームを導くことによって，完全に勝利するこ

は，ソフトウェアレベルで逐次的にアルゴリズムを記述することとができる． Blokus Duo におけるゲーム木の複雑さは 1070 かで設計が容易になることや，複雑なアルゴリズムを実装しやすいと試算されている ． ゲーム木の複雑さとは，1 試合のという点である． しかし，ソフトウェアレベルでの実現のみだ

内の探索しなければならない局面の数を指す． 近年のゲームシと，Game AI の計算性能は上がりづらいため，クロックを意識

ステムでは 1 秒間に 100 万局面以上 (10 ) を読むことが可能にした設計による，高速化が必要となる.

なってきている．しかし，上述のゲームシステムで完全な先読みを行うためには，限りなく計算時間を要するため，この課題に対

我 々 の 手 法 で は ，動 作 記 述 言 語 NSL(Next Synthesys
Language)9) を用いたゲーム木探索の実現と，クロックを意識しする研究が行われている．

た並列探索による高速化を実現する． ゲーム木探索では，再帰

ら 10

80

2)

6

*1

情報通信学研究科

的処理により，木の探索が行われるため，ソフトウェアによる情報通信学専攻 (修士課程)

実現が一般的であるが，我々は独自のハードウェアスタックを

School of Information
and Telecommunication
Engineering,
Graduate
School of Information
and Telecommunication
Course of Information
Telecommunication
Engineering,Engineering,
Course ofand
Information
and Telecommunication
MasterEngineering,
Master's Program*2 情報通信学部 組込みソフトウェア工学科 (教授)
School of Information and Telecommunication Engineering,
Department of Embedded Technology, Professor

用意することでゲーム木探索を実現する． ハードウェアによるゲーム木探索アルゴリズムの実現の利点は，ハードウェアが基本
的に並列での動作となるため，処理の要所に並列的な要素を加えられる点である． NSL は特徴として，Verilog HDL や VHDLなどのレジスタ主体の設計と異なり，動作を主体した抽象的な-1−9−

NSL による Blokus Duo Multi Game AI システムの実装

NSL による Blokus Duo Multi Game AI システムの実装
記述が出来る． 抽象的な記述は，複雑なアルゴリズムの設計を能な指手の候補が無くなった時点で親ノードに戻り (Depth-1)，

助けている．

Depth=1 の状態で配置可能な指手の候補が無くなった場合，探索

本研究の目的は，動作記述による Game AI の実現と，それにを終了する．

よる高速化の手法の確立を目的としている． 高速化を行うこと

Depth
0

は，Game AI の計算性能を上げ，探索空間が広くなることによって，いずれ Game AI がゲーム木を完全に解くために貢献するた

Root Node1めである．
本論文では，2 章で，探索法について紹介し，3 章で，Blokus

2

Duo に，基本の方針としての Blokus Duo に関するデータ・手続
き・評価関数について述べる． 4 章では，ゲーム木探索を実現す

3

る上で，必要になるデータやモジュールについて解説する． 5 章

Leaf Node= Player Nodeでは，実際のゲーム木探索の設計について，制御方法やモジュー
ル構成，システムの構成を解説する． 6 章では，実装した結果と= Opponent NodeFig.1 Game Tree Search

Game AI の計算性能について述べ，最後にまとめを述べる．
本 実 装 の Blokus Duo Game AI は ICFPT(The International

2.2 minmax 法

Conference on Field-Programmable Technology) のルール 8) にある局面が自分にとって有利であるかを評価することで，ゲー則った仕様となっている． ICFPT では Game AI を FPGA 上にムを有利に進める minmax 法と呼ぶ手法がある． minmax 法で実装しお互い交互に指手を出し合いながら対戦する． ルールにはゲーム木を辿っていき，評価を行ったノードで，先読みを打ち至っては付録で述べている． インターフェースには RS232C シ

きる．相手の指手を評価する時は，相手にとって不利な盤面になリアル通信を採用した． 実装方法に関しては，CPU や IP コア

るかを評価する (最小評価)，また自分の指手を評価する時は，自(Altera の Nios II プロセッサ，Xilinx の MicroBlaze MCS 等)，専

分にとって有利な盤面かを評価する (最大評価)． 先読みの数が用ハードウェアなど自由に実装してよい． 一方，使用デバイス

多ければ多いほど，自分にとってゲームを有利に進めることがでは制限されており，100MHz 前後の動作周波数の FPGA を載せきる．

た Board が指定されている．
実装ツールとして，動作記述言語 NSL, 動作合成に nsl2vl, シ

2.3

ミュレーションに gtkwave, vvp, iverilog, 論理合成には Quartus

α−β 法

α − β 法とはゲーム理論における探索アルゴリズムのひとつ
で，minmax 法の最大最小評価を基本とした探索をする． α − βII 13.0，動作テストとして Blokus Duo GUI10) を用いた．

法の最大の特徴としては，同じような計算結果になる部分のノードを枝刈りすること (部分木の枝刈り) によって，処理数が削

2. 探索手法

減され，結果的に計算速度が高速になることである． 加えて，

minmax 法と近似した探索結果が得られるため，非常に有用である． Blokus Duo に α − β 法を適用した場合，最大で探索すべき局面を平方根まで下げられ，1080 の平方根，1040 まで探索量を二人零和有限確定完全情報ゲーム (以下二人ゲームとする) において，ゲーム木の複雑さの問題が挙げられている． 問題に対して，二人ゲームの Game AI は一定の深さまでの探索，すなわ削減できる 2) ．

ち，先読みした局面において，盤面の評価計算によって，各プレイヤーの有利・不利を判断して，自分に有利にゲームを進めていく． 探索の打ち切りと盤面の評価は，実用的な計算速度と Game

3. 設計の方針

AI の対戦の強さを求めることができる．
本研究では，ゲーム木の探索手法として，minmax 法を基本と設計の方針として，ハードウェアにおけるゲーム木探索の実した α − β 法のアルゴリズムをハードウェアとして設計してい

現，ゲーム木探索の高速化の順で設計を実施する． Blokus Duo

述べる．

盤面やピースのデータと，それらのデータを操作する手続き，評く． ここでは，ゲーム木探索と minmax 法，α − β 法について

2.1

におけるゲーム木探索を実現するためには，ゲームの基本となる価関数が必要となる． 本章では，ゲームを構成するための基本

ゲーム木探索的なデータや手続き，評価関数について述べる．

ゲーム木探索は Fig.1 のように相手プレイヤー (Opponent)の指手を含んだ盤面を Root Node(Depth=0) として探索してい3.1

く． Root Node = Opponent Node であり，Opponent Node の子

ゲームのためのデータ

Blokus Duo では 14 × 14 マスの盤面上で，21 種類の重複しなノードは必ず Player Node となり，Player Node の親子のノード

い形の異なる 1〜5 個の正方形を連結したピースを，お互い交互

は Opponent Node となるように，交互に局面を探索していく．

に出し合って対戦を行う． Blokus Duo の Game AI を構成するノードが Leaf Node(Depth=3) となったとき，局面の評価を行い，ためには，基本的に以下に列挙するようなデータが必要となる．

親のノード (Opponent Node) に戻る． 木の末端 (Leaf Node) か• Board Memory:盤面

ら親ノード (Opponent Node) に戻ったとき，次局面の子ノード• Piece:ピース• PieceAvailable Memory:各ピースの使用状態(Player Node) に枝分かれする． あるノードにおいて，配置可-2− 10 −玉城良・清水尚彦玉城 良・清水 尚彦• Move(PieceNum,Rotate,X,Y):指手 (ピース番号，回転状態，

0
0
0
0
0

X 座標，Y 座標)• PlayerNum:プレイヤー番号 (1 or 2)
Board Memory はお互いに交互に出し合った Piece を保持するために用いる． Blokus Duo の盤面は 14 × 14 サイズをとってい

0
0
1
0
0

0
0
1
1
0

0
0
0
1
0

0
0
0
0
0

PieceNum=8
Rotate=0(a) Piece be norotate

るが，盤外を Game AI に認識させるために，16 × 16 のサイズのメモリを Board Memory として用意する． 16 × 16 サイズにした

結果，Y の 0〜15 の値に対して 4bit の左シフト演算をすること

0
0
0
0
0

0
0
0
1
0

0
0
1
1
0

0
0
1
0
0

0
0
0
0
0

PieceNum=8
Rotate=1(b) Piece be reversed

Fig.3 Example for rotate the pieces

で，Board Memory への参照が容易になった． Board Memory への値の参照は Fig.2 上に示されるように，左上からアクセスして

PieceAvailable を 21bit のメモリで用意し，各 bit で 0 を未使

いく． Board Memory は一次元配列として用意しており，NSL

用，1 を使用済みとする． PieceAvalable の 21bit はピースの種類

記述で値を格納する際は，の数 (21 種類) を用意したため，1 つのピースの使用状態を 1bit

(1)で判断している． 指手をサーチする処理の初めに，このデータのように行う． Board の内部データは各データが 4bit のビット間を削減することが出来る． PieceAvailable の値を変更するとBoard[(y << 4) + x] := DAT A;

を読むことで，enable か disable を判断し，指手サーチの処理時幅をとり，Fig.2 下のように，盤外を 3, 空きマスを 0, プレイヤー

きは，NSL 記述で，以下のような排他的論理和を用いて，反転1 を 1, プレイヤー 2 を 2 として扱う．
0

1

2

3

4

5

6

7

8

9

したいビットを PieceNum を用いて参照する．

⊕
Avail[player−1] := Avail[player−1](0b1 << P ieceN um);
NSL による Blokus Duo Multi Game AI シス(2)

10 11 12 13 14 15

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31........
........
........

........
........
........
........
........
........
........
........

........
........
........
........

........

32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239

5)

240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255

Board Memory Map for Blokus Duo

3
3
3
3

6)

3 3 3 3 3 3 3 3 3 3 3 3 3 3 30 0 0 0 0 0 0 0 0 0 0 0 0 0 3
0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
1
0
0
0
0
0
0
0
0

3
3
3
3
3
3
3
3
3
3
3
3 3 3 3 3

0
0
0
1
1
1
0
0
0
0
0
0
0

0
0
0
0
1
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
2

0
0
0
0
0
0
2
2
0 2
0 0
0 0
0 0
0 0

0
0
0
0
0
0
0
2
0
0
0
0
0

3 3 3 3 3 3 3

0 = empty 1 = Player 1 2 = Player 2

0
0
0
0
0
0
0
0
0
0
0
0
0

3
3

0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0

3

= Wall

3
3
3
3
3
3
3
3
3
3
3
3 3 3 3

Fig.2 Index map of the board memory for Blokus Duo

7)

8)
9)

10)

erato.ist.hokudai.ac.jp/docs/summer2012/compgo plan pub.pdf,
20143.2
年9月
19 日アクセス.
Game
AI の基本的な手続き
Liu, C. (2013) ”Implementation of a highly scalable blokus duo
ゲームを正しく進めるために，基本的な手続きを設計する．
solver on FPGA”, Field-Programmable Technology (FPT), 2013 In以下に列挙する基本的な手続きは，動作の追跡のために NSL のternational Conference on, pp.482-485, IEEE.
構文要素である手続き (Procedure) 記述により設計する． 手続き
Jiu Cheng Cai; Ruolong Lian ; Mengyao Wang ; Canis, A. ; Jongsok
Choi記述は状態遷移やパイプライン，順序回路を用いた制御を提供す; Fort, B. ; Hart, E. ; Miao, E. ; Yanyan Zhang ; Calagar, N. ;9)る構文である
Brown,
S. ; Anderson,．
J (2013) ”From C to Blokus Duo with LegUp
high-level
Selectsynthesis”,
Move: Field-Programmable Technology (FPT), 2013
International
Conference on,
pp.486-489,
IEEE. Move は x 座標，y 座標，
カウンタによりMoveを生成する．
Kojima(2013)”An
implementationof
BlokusDuoのplayer
ピース番号，回転状態から成り立つ．
Move
Value onrange とし
FPGA”, Field-Programmable Technology (FPT), 2013 Internationalて，PieceNum(0〜20),Rotate(0〜7),X(0〜14),Y(0〜14) をとる．
Conference on , pp.506-509, IEEE.
Check Move:ICFPT (2013) ”Rules of Blokus Duo”, http://lut.eee.u生成した Move が配置可能かチェックする．
ryukyu.ac.jp/dc13/rules.html
2014-09-18 accessed.
Add
Node:
オーバートーン株式会社(2012) 「NSL リファレンスマニュアル」,
http://www.overtone.co.jp/binaries/documents/reference
配置可能な Move を Piece として Board Memory に追加する．
/NSLピース使用状況を更新する．
Language Reference ver1.4.pdf 2014 年 9 月 18 日アクセス.
青山 卓也, 玉城 良, 廣瀬 翔太, 清水 尚彦 (2013) 「NSL による
Evaluation:
Blokus Duo のハードウェアシステム・GUI 実装」, 第 39 回パルテ
ゲーム木の末端 (Leaf Node) の Board Memory を評価する．
ノン研究会, Vol.39, pp.43-46, パルテノン研究会.
ノードが Leaf Node の時以外は，評価を行わない．

Remove Node:
配置した Piece を削除する
付録 . Board Memory の状態を親ノードに戻す． ピース使用状況を前のノード状態に戻す．

Blokus DuoGameのルール
AI は上記の各手続きを中心に動作する． ゲーム木探索

Blokusにおいて，Duo では 14×14マスの盤面上で，お互い交互に
21 種
14x14 盤面で21 種類のピースと 8 種類の回転状態を
Piece は Board Memory に指手を保持する際の実際のピースで
α − β 法によって枝考慮し，3 手先を 2 プレイヤが読む場合，類の形の異なるピースをひとつずつ置いていく．
最終的にお互ある． 25bit の Fig.3(a) のような無回転状態のピースデータを刈りがされないとき，探索すべきノードは最大で約 378003 とな
いがピースを盤面上に置けなくなった時点の，残ったピースの21 種類用意し，PieceNum(0〜20) と Rotate(0〜7) を入力するとる．そのため，非常に多い頻度で手続きが動作するため，各手続
総面積が少ない方が勝利となる．
また，ルール上の制約として，
パターンテーブルによって，Fig.3(b) のように回転状態を適応しきにかかるクロック数を限りなく少なくする必要がある．
新しくピースを置く時は，Fig.13 左のように角を一つ以上自分のた Piece が生成される． 25bit のうち，0 は空きマス，1 を Piece
Fig.13 右のように自分のピースとピースと接しなければならず，
3.3 評価関数として扱い，ピースアドレスが 1 を指すとき，各プレイヤーの数辺で接してはならない．相手のピースに対しては，マスが被らな二人ゲームでは，ゲーム木が非常に大きいため，全ての組み合
字を Board に書き込む．
ければ自由に接してよい．
わせを完全に探索することはできない． 二人ゲームの Game AI
2 2 2
2 2 1
− 11 −
1 1 1
1

-3-

2 2 2
2 2 1
1 1 1
1

NSL による Blokus Duo Multi Game AI システムの実装

NSL による Blokus Duo Multi Game AI システムの実装
は，木を一定の深さまで探索したら，局面に対して，勝ち負けでの内部では X(0〜14), Y(0〜14), PieceNum(0〜20), Rotate(0〜7)なく有利不利を計算するような静的評価を行う． 評価値はプレの順にカウントする． Rotate のカウントが終了した時点で，イヤーの局面が有利であれば大きい値，不利であれば小さい値にCounter は出力信号 fin を High にする． 出力信号 fin が High ななる．

らば，ノードを親ノードに移す．

我々は有利不利の判断をする評価関数として，Fig.4 に示すよStack Memory:

うな，勢力範囲計算を採用した． 勢力範囲計算では，評価計算のノードを子ノードに移す場合，Add Node 手続きによる処理

ために Board Memory と同じサイズの Evaluation Memory を用(Board に Piece を追加する) を行う． また，親ノードに移す場

意する． 勢力範囲は Piece を 2bit 左シフトした値を Influence と合，追加した指手の情報を保持しておかなければならない． ノー

して Evaluation Memory に書き込むことで実現する． Influence

ドを親ノードに移す処理のために，Fig.6 に示す Stack Memoryの範囲は付録で述べている Blokus Duo の制約に則って，Cornerを用意する． Stack Memory は (Depth + 1) × 4 のサイズをとを中心として，上下左右に 2 つ，全斜め方向に 1 つとる．評価値

り，Move(X, Y, PieceNum, Rotate) を格納していく． スタックポ

は Influence の個数の合計を計算する．

インタには Depth を使用し，Depth を始点とした相対アドレスを用いて Move を格納する． 親ノードに移る場合，Delete Node 手

Evaluation Board Memory
44
4 4 4 4 4
4 4
4 4
4 4
1
4 4
4 4
4
1 1 1
4
4 4
1
4
1 1
4 4
4
1 1
4 4
4
4 4
1 = Piece= Corner

続きを行う． そのとき，Stack Memory から削除したい Move を取り出す． 取り出した Move の PieceNum と Rotate から Pieceを生成し，Board に Piece を empty(=0) として入力し，Depth を
デクリメントすることで，削除手続き，及び親ノードへの移動が完了する．
Module:Player
fin
Depth

4 = Influence

Module:Counter
Counter[1]x Multi Game AI システムの実装
NSL による Blokus DuoyFig.4 Influence on the Evaluation Memory

Counter[2]PieceNumerato.ist.hokudai.ac.jp/docs/summer2012/compgo plan pub.pdf,
RotateCounter[3]2014 年 9 月 19 日アクセス.
5) Liu, C. (2013) ”Implementation of a highly scalable blokus duo
solver on FPGA”, Field-Programmable Technology (FPT), 2013 In4. ゲーム木探索設計
Fig.5 Multiple Counter Modules
ternational Conference on, pp.482-485, IEEE.
6) Jiu Cheng Cai; Ruolong Lian ; Mengyao Wang ; Canis, A. ; Jongsok
ある局面に対して，何手か先読みをすることでゲーム木を作; Fort, B. ; Hart, E. ; Miao, E. ; Yanyan Zhang ; Calagar, N. ;はゲーム木の末端で局面を評価成することが出来る． Game AIChoi
BA
Brown, S. ; Anderson, J (2013) ”From C to Blokus
Duo with LegUp
Depth
BA+ 1
BA+ 2
BA+ 3
し，指手の良し悪しを判断する． ゲーム木探索は評価した値を(Based Address) BA+ 0
high-level synthesis”, Field-Programmable Technology (FPT), 2013
用いて，ルートノード (元となる局面) に対して，最善手を決めInternational Conference on, pp.486-489, IEEE. 0 (0 << 2)
0x00
XY
PieceNum Rotate
AI にお of Blokus Duo player on
るアルゴリズムである． 本章では，ハードウェア
7) Kojima (2013) ”An Game
implementation− β 法の設計について述べる．
けるゲーム木の設計，および α FPGA”,
Field-Programmable Technology (FPT), 2013 International(1 << 2)
Conference
on , pp.506-509, IEEE.
X
Y
PieceNum Rotate
1
0x04
4.1 ゲーム木探索の設計
8) ICFPT (2013) ”Rules of Blokus Duo”, http://lut.eee.uハードウェア動作によるゲーム木探索には 3 章で述べた手
ryukyu.ac.jp/dc13/rules.html 2014-09-18 accessed.
(2 << 2)続きとゲームのためのデータ，加えて，ゲーム木探索のための
9) オーバートーン株式会社 (2012) 「NSL リファレンスマニュアル」, 0x08X
Y
PieceNum Rotate
2
Depth,
データが必要になる． ゲーム木探索のためのデータとは
http://www.overtone.co.jp/binaries/documents/reference
Language Reference ver1.4.pdf 2014 年 9 月 18 日アクセス.
これらのデータはハードウェア
Counter, StackMemory を指す．/NSL
Fig.6 Stack Memory for Bloku Duo10) 青山 卓也, 玉城 良, 廣瀬 翔太, 清水 尚彦 (2013) 「NSL によるによるゲーム木探索で重要な役割を果たす．
Blokus Duo のハードウェアシステム・GUI 実装」, 第 39 回パルテ
Depth:
ノン研究会, Vol.39, pp.43-46, パルテノン研究会.
Depth はゲーム木探索内でのノードの深さ状態を表す． Depth
4.2 α − β 法の設計
をインクリメントすることでノードを子ノードに移すことを表
minmax 法は一定の深さまで，すべての指手を探索するため先し，デクリメントで親ノードに移すことを表す．

付録

読み数が増える度に探索空間が指数的に増大する． そのようなCounter:問題を克服するために，α − β 法では，評価値が近似している
Blokus モジュールを用い，
Duo のルール
探索の範囲
Move(指手) の生成には Counter
ノードの枝を刈る． ノードの枝刈りには α カットと β カットをFig.5 のように，14x14 盤面の3手
Duo では 14×14マスの盤面上で，お互い交互に21 種β より大きい場合，最善手として β と Moveは Counter の状態で決まる．Blokus
用いる． 評価値が類の形の異なるピースをひとつずつ置いていく．
最終的にお互出力として PieceNum,Rotate,x,y
先を 2 プレイヤが読む場合には，を更新し，ノードを親の親に移す．
親の親にノードを移した後，を持つ，3 つのカウンタを用意し，入力したDepth の値に応じたいがピースを盤面上に置けなくなった時点の，残ったピースの次局面の子ノードに枝分かれをする． これは β による枝刈りで総面積が少ない方が勝利となる．
また，ルール上の制約として，
Counter が起動する． すなわち
Counter[Depth] となる. Counter
ある． β カットのみを用いて探索することを NegaMax 探索と新しくピースを置く時は，Fig.13 左のように角を一つ以上自分のピースと接しなければならず，Fig.13 右のように自分のピースと-4-辺で接してはならない．相手のピースに対しては，マスが被らなければ自由に接してよい．

− 12 −

玉城良・清水尚彦玉城 良・清水 尚彦
呼ぶ． NegaMax 探索ではお互いに最大の評価値のみを求めるた

START

FINISH

Add
opponent Move

Send Move

め，β 値を越える評価値が算出されるまで探索をし続ける． こ
こで，最大探索を打ちきるために，α カットを導入する． もし，
評価値が α より小さい場合，枝刈りを行う． α は β の更新された値を受け継ぐ． したがって α は β にとっての最小値となり，(EvaluatedV alue < α)∨(β < EvaluatedV alue)(3)

Select Moveが成り立ったとき，枝刈りを行う． また，最善手の更新，及びCheck Move

ハードウェア Game AI の設計[enable]ゲーム木探索は各手続きと必要なデータによって状態を遷移

Add Node

する． NSL の手続き記述 Procedure 構文は状態遷移によるフロー制御機能を提供する．

Evaluation

めのデータと手続きによるゲーム木探索の状態遷移を示してお[Depth == Leaf]

り，手続き内の具体的な処理は，図中では省略する．
状態遷移によるゲーム木探索の制御{Depth--}{Pop}[EV < alpha || beta < EV]{Pruing=1}

Delete Node

ここで，状態遷移によるゲーム木探索について述べる． Opponent Move が入力された時，ゲーム木探索を開始するために，相手の指手を Board Memory に追加 (Root Node の作成) する．
Opponent Move から Select Move へ遷移する時，Depth をインクリメントする (子ノードに移す)． Select Move では Piece の生成を行い, 枝刈り状態 Pruing と Counter モジュールの fin 信号を遷移条件とする． Select Move の遷移条件がすべて Low の場
合，Check Move へ遷移する． Check Move では Piece のチェックを行い，Board Memory へ配置可能 (enable) なら Add Node, 配
置不可能 (disable) なら Select Move へ遷移する． Add Node では Board Memory に Piece を書き込み，Depth をスタックポイン
タとして指手を Push する． Evaluation では，Depth == Leafの場合，評価値計算を行い，Delete Node へ遷移する． また，
Depth < Leaf の場合，Depth をインクリメントして，SelectMove へ遷移する．
枝刈り操作は Select Move の遷移条件を用いる． Select Moveの遷移条件の Pruing, Counter[2].fin, Counter[3].fin が High の場
合，Pruing を Low にして，Delete Node に遷移する． Delete
Node では EvaluationValue と alpha,beta が条件を満たした時，
Pruing を High に，Depth をデクリメント，Pop を行い，SelectMove へ遷移する． 深さ 1 のカウンタ (Counter[1]) の出力信号
fin が High ならば，Send Move へ遷移する． Send Move では評
価値や alpha, beta, カウンタなどを初期化し, 最後に上位モジュー
ルに Move を出力しゲーム木探索を終了する．

5.2[Depth < Leaf]{Depth++}{Push}

我々は Fig.7 に示した状態遷移を制御して α − β 法を適応したGame AI を設計した． Fig.7 の状態遷移図は，ゲーム木探索のた

EV : Evaluation Value

Fig.7 State transitin diagram of Game AI

最善手の Move を追加するための Board Memory のバックアッ
プとして使用する．
それぞれの手続きは上記のローカルメモリを用いて計算を行う． Evaluation モジュールは 3 章で述べた EvaluationMemory
をローカルメモリとして用意している．
Module : Player
Write

Write

Backup
Board
MemoryAdd opponent move
Select move

Read
Write
Write

Read

Board
MemoryWrite

Get value

5.1[Pruing||
Counter[2].fin ||Counter[3].fin]{Pruing=0}[disable]

最大値の更新は評価値が β より大きいときのみ行う．

5.

[Counter[1].fin]{Depth++}Evaluate the board of
the current

Module:Evaluation

Check move
Add node

Add

Send
move

Read
Add

Push
Pop

Evaluation

Move

Available
MemoryStackMemoryRemove node
Generate a Piece data

Module:CounterFig.8 Block diagram of Player module

ゲーム木探索モジュールの構成

ゲーム木探索を行うモジュールの構成を Fig.8 に示す． モジ

5.3

ュール内部ではそれぞれローカルメモリ (Board Memory, Backup

システム設計

我々は α − β 法に基づいた探索を行う Game AI を Player モ

Board Memory, Available Memory, Stack Memory) を用意する．
それぞれのローカルメモリは 3, 4 章で述べた通りである． また，新たに加えた Backup Board Memory は Add opponent move 手
続きを行う時に Root Node の盤面状態を保持しておき，最後にジュールとして設計した． Player モジュールをコアとして組み込んだ Game AI システムを，ブロック図として Fig.9 に示す．
本システムは RS232C シリアル通信をインターフェースとして-5− 13 −NSL による Blokus Duo Multi Game AI システムの実装

NSL による Blokus Duo Multi Game AI システムの実装
搭載しており，シリアル通信を経由して他プレイヤーとの対戦を

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3

行う． 今回，他プレイヤーと対戦するための host システムとして，Blokus Duo GUI を使用した． Blokus Duo GUI は，PC 上で動作するソフトウェアプログラムである． Blokus Duo GUI は，

Blokus Duo の対戦用インターフェース機能だけでなく，指手を選ぶ時間を計測する機能を持っており，Game AI システムのテストだけでなく，計算速度測定にも用いた． 動作速度測定は，シリアル通信の送受信に要する時間も含める． また，シリアル通
信の通信速度は 115, 200[bps] である．

Not Accelerated Single Game AI システム
計算速度テストの結果，Fig.9 に示した Single Game AI システ
ムの計算速度は，先読み回数 (=3) の時，1 試合における平均計
算時間は 502[s] となった．
Txd

Rxd

RS232C

Encoder

Hex

Send
Buffer

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3

3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3

3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3

: ReadHex

Fig.10 Read from Board Memory

ASCII

Decoder

3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3

(a) Read from Board Memory (b) Read from Board Memory
with unloop
with loop

Cyclone IV E: EP4CE115F29C7
ASCII

3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3

Counter Evaluation

Move

PlayerReceive
BufferMulti Game AI システム

我々は，計算時間をさらに短縮するために Fig.11 に示すようOpponent
Moveに，Game AI の並列化を行った． 今回，3 つの GameAI を FPGA上に搭載することで，GameAI の並列処理化を実現した. Multi
Game AI システムでは各 Player モジュールで探索範囲を分担しており，今回はゲーム木を 3 分割し，並列に探索した． Multi
Game AI システムでの指手の選択は最終的に Compare に評価値

Fig.9 Block diagram of Single Game AI on FPGA

Accelerated Single Game AI システム
我々は，先読み回数 (=3) の時の，計算時間を実用的な速度にを送り，それぞれ値を比較し更新していくことで指手を選択す
る． Compare は評価値を各 Player モジュールの算出した評価値するために，Game AI システムの高速化を行った． 初めに，処を比較し，最大，もしくは最小となる評価を求め，その評価に対理のボトルネックとなったのが，Evaluation モジュールである．

応した指手を更新する． 各 Player モジュールはそれぞれ，最後

Evaluation モジュールはローカルな EvaluationMemory を用意しており，Fig.10(a) のように，局面の評価のために Player モジュー
ルの Board Memory から盤面データを 256 クロックかけて読みに選択した指手がお互いに異なるため，Compare 処理が終了した時，最善手となる指手を各 Player モジュールの Board Memoryに書き込むことが必要である．

出しを行っている． 加えて，評価中に EvaluationMemory を走Multi Game AI システムを実装した結果，先読み回数 (=3) の時，平均計算時間を約 8.24[s] に短縮した．

査する処理で 256 クロックかけており，Evaluation の処理には
約 520 クロック必要となる． Evaluation は局面の数だけ処理を行うため，クロック数の削減は高速化処理のために必要である．

Txd

我々は Evaluation のクロック数の削減のために，Fig.10(b) のように，Board Memory を読み出すための入力端子を 16 本用意

Rxd

ASCII

RS232C

した． Board Memory の読み出し用入力端子を 16 本用意した

Cyclone IV E: EP4CE115F29C7
Encoder

Hex

ASCII

結果，Evaluatoin にかかるクロック数は約 280 クロックに削減

Decoder

した．

Counter Evaluation

Hex

また，Add Node の時の，Board Memory への書き込みに Piece

Send
Bufferのサイズ分ループしていたため，毎回 25 クロックかけて書き込

Player_0

Move

みを行っていた． 書き込み処理に対しても，書き込み用端子をCompare25 本用意し，ループを展開したことによって，25 クロックから
1 クロックにクロック数を削減した． 信号線を増やしたことによるループの展開を行った結果，先読み回数 (=3) の時の，1 試

Receive
BufferEV &Move

Player_1
Player_2

Opponent
Move

Module :Player

合における平均計算時間が，Not Accelerated Single Game AI シ

EV : Evaluation Value

ステムのときは 502[s] だが，今回は 36.13[s] となり 13 倍の速度向上となった．

Fig.11 Block diagram of Multi Game AI on FPGA

-6− 14 −玉城良・清水尚彦玉城 良・清水 尚彦
550

Table
1 Result of Implementation
Table.1

500
450

Average time [S]DeviceAccelerated
Single Game AI
Multi
Game AI

Cyclone IV E
EP4CE115
Total logic elements
Dedicated logic registers
Total logic elements
Dedicated logic registers

21,291/114,480(19%)
4,246/114,480(4%)
96,411/114,480(85%)
7,426/114,480(6%)

400
350
300
250
200
150
100
50

6. 実装結果と性能
6.1

0

実装結果

(a)Not Accelerated
Single Game AI System(b)Accelerated
Single Game AI System(c)Multi
Game AI System

Fig.12 Average calculation speed of the systems

我 々 は 動 作 合 成 言 語 NSL を 用 い て ，Altera Cyclone IV E

EP4CE115F29C7 上に Game AI システムを実装した． 論理合
成には Quartus II version 13.0 を用いた． Game AI システムは50MHz で動作する． 複数の Game AI をコアとして組み込んだMulti Game AI システムと，単一の Game AI をコアとした Single

7. おわりにGame AI システムを論理合成した結果を，Table.1 にデバイスのリソース使用率として示す． LE(logic elements) は Cyclone シ

我々は Blokus Duo における Game AI システムの実装について述べた． Game AI の探索アルゴリズムとして，α − β 法を用い，ゲーム木探索を行った． ゲーム木探索のアルゴリズムは動

リーズにおける，組み合わせ回路や順序回路などを構成する論理リソースの最小単位である． Single Game AI システムの実装

作合成言語 NSL の手続き記述によって，容易に実現できたこと

結果として合計 21,291 の TLE(Total logic elements) を使用した．

を確認した． 動作時間測定の結果，Game AI システムを高速化

また，Multi Game AI システムでは Single の約 4 倍となる合計するためには，ひとつのノードに対する処理時間を短縮することが，ゲーム木探索の処理性能を上げることを示した． さらに，

96,411 TLE を使用した． TLE の結果から，Player モジュールはGame AI の計算性能の向上のために，複数の Game AI を並列で動作させる Multi Game AI システムを実装した． Multi Game AI
システムは並列動作によって，3 手読みを平均計算時間 8.24[s]システムの中で多くのリソースを使用することを示す．加えて，Counter モジュールと Evaluation モジュールは Player モジュー
ルの下位モジュールになっており，Player モジュールと同じ数という実用的な速度になった．

の Counter と Evaluation モジュールを用意した． この下位モ

6 章で述べた通り，Multi Game AI システムは多くのリソース

ジュールと Player モジュールの構成は，更なるリソース使用率を使用した． リソース使用の増大はシステムの不具合となる問の増加の原因になっている． 本手法では，計算速度の高速化に向

題の他，本システムの計算性能を越えるハードウェアを設計する

けて，より多くの Game AI を FPGA に搭載するために，リソーためにも，アーキテクチャの再構成が必須である．

スの使用率を抑えるべきである．リソース使用率を抑えるため

また，評価関数の精度や，ゲーム AI の強さについては議論しに，Player モジュールの構成を見直す必要がある． 加えて，実ていない．本稿の結果から，適用可能性のある，Negascout や反装したシステムは並列計算のために単純に Player モジュールを

復深化深さ優先探索などの複雑なゲーム木探索アルゴリズムを複数用意したが，複数用意しなくてもよい処理を選定し，Game適用し，計算性能や，ゲーム AI の強さを比較し検討することで，AI 内部の構成を見直す必要がある．
6.2

ゲーム AI の実装技術において，今後の発展に期待できる．

システム性能実装したシステムの平均計算時間を Fig.12 に示す． Fig.12 の各システムは，それぞれ先読み (=3) まで探索する． Fig.12(a) の高速化しない通常の Single Game AI システムの平均計算時間は参考文献

502[s] となっている． Fig.12(b) の Accelerated Game AI システ
ムの平均計算時間は 36.13[s] となり，(a) のシステムを大幅に高(2007)「 新 た な 科 学 技 術 の 発 見 の た め の エ
IBM Blue Gene」, http://www06.ibm.com/jp/press/20070516001.html 2014 年 9 月 18 日 ア1) IBM

速化する結果となった． この結果は，ひとつのノードに対するン ジ ン と な っ た

処理を短縮したことによって，処理全体の性能が上がったことをクセス．

示す． Fig.12(c) の並列でゲーム木を探索する Multi Game AI シ2) 小谷 善行編 (2010) 「ゲーム計算メカニズム」 コロナ社.
3) Sugimoto, N. ; Miyajima, T. ; Kuhara, T. ; Katuta, Y.more authors,(2013) ”Artificial intelligence of Blokus Duo on FPGA using Cyber
Work Bench ”, Field-Programmable Technology (FPT), 2013 International Conference on, pp.498-501, IEEE.
4) 美 添 一 樹 (2012) 「 モ ン テ カ ル ロ 木 探 索 お よ び
コ ン ピ ュ ー タ 囲 碁 の 進 歩 に つ い て 」, http://www-

ステムの平均計算時間は 8.24[s] となり，ほぼ人間の思考速度と同等の応答性能になったため，実際に対戦ができるレベルまで，

Game AI を高速化することができた．

-7− 15 −NSL による Blokus Duo Multi Game AI システムの実装

NSL による Blokus Duo Multi Game AI システムの実装

5)

6)

7)

8)
9)

10)

erato.ist.hokudai.ac.jp/docs/summer2012/compgo plan pub.pdf,
2014 年 9 月 19 日アクセス.
Liu, C. (2013) ”Implementation of a highly scalable blokus duo
solver on FPGA”, Field-Programmable Technology (FPT), 2013 International Conference on, pp.482-485, IEEE.
Jiu Cheng Cai; Ruolong Lian ; Mengyao Wang ; Canis, A. ; Jongsok
Choi ; Fort, B. ; Hart, E. ; Miao, E. ; Yanyan Zhang ; Calagar, N. ;Brown, S. ; Anderson, J (2013) ”From C to Blokus Duo with LegUp
high-level synthesis”, Field-Programmable Technology (FPT), 2013
International Conference on, pp.486-489, IEEE.
Kojima (2013) ”An implementation of Blokus Duo player on
FPGA”, Field-Programmable Technology (FPT), 2013 International
Conference on , pp.506-509, IEEE.
ICFPT (2013) ”Rules of Blokus Duo”, http://lut.eee.uryukyu.ac.jp/dc13/rules.html 2014-09-18 accessed.
オーバートーン株式会社 (2012) 「NSL リファレンスマニュアル」,
http://www.overtone.co.jp/binaries/documents/reference/NSL Language Reference ver1.4.pdf 2014 年 9 月 18 日アクセス.
青山 卓也, 玉城 良, 廣瀬 翔太, 清水 尚彦 (2013) 「NSL による
Blokus Duo のハードウェアシステム・GUI 実装」, 第 39 回パルテノン研究会, Vol.39, pp.43-46, パルテノン研究会.

付録

付録
Blokus Duo のルール

Blokus Duo では 14×14 マスの盤面上で，お互い交互に 21 種
類の形の異なるピースをひとつずつ置いていく． 最終的にお互
いがピースを盤面上に置けなくなった時点の，残ったピースの
総面積が少ない方が勝利となる． また，ルール上の制約として，
新しくピースを置く時は，Fig.13 左のように角を一つ以上自分のピースと接しなければならず，Fig.13 右のように自分のピースと辺で接してはならない．相手のピースに対しては，マスが被らなければ自由に接してよい．
2 2 2
2 2 1
1 1 1
1
1 1
1 1

2 2 2
2 2 1
1 1 1
1
1 1
1 1

Newly placed tile
must have at least one
corner to corner contact
1= Player1

Newly placed tile
must not haveedge to edge contact
2= Player2

Fig.13 Corner to Corner Contact-8− 16 −