実現確率探索のゲーム全般への応用
-L
i
n
e
s
o
f
Action
を題材にして-橋本剛 1 長嶋津久作田誠 2，
Jos
Uiterwijk
3
，飯田弘之 2，4
1 静岡大学工学部
2 静岡大学情報学部
3
Department o
f
Computer Science
,
U
n
i
v
e
r
s
i
t
e
i
t
Maastricht
4 科学技術振興事業団さきがけ研究 21 r機能と構成」領域
E
-
m
a
i
l
;
{h儲imoto，
cs8066
,
sakuta}@cs.inf.shizuoka.ac.jp
,
[email protected]
,
iid伽a@cωs. inf.shizuoka.a舵c.j必p
概要
4-2
鶴岡は実現確率探索を考案し，プログラム「激指」に実装して 2002 年世界コンピュータ将棋選手権を見事 に制した.実現確率探索は局面の実現確率を闇値として探索することで，より「有りそう J な手の場合はど んどん深く読み， r無さそう J な手の場合はほとんど読まない.これまで前向き枝刈りと探索延長によって 行ってきたことをシステマティックに非常に簡単なアルゴリズムで行う優れた探索法であるといえる.とこ ろが，激指の手法ではプロの棋譜から指し手の確率を計算しており，参考となる棋譜が十分に寄在しない多 くのグ}ムではこの手法は通用しない.本稿ではコンピユ}タの自動学習により指し手の確率を自動で計 算し，実現確率探索をあらゆるゲームに応用させる手法， ARPS (自動実現確率探索)を提案する.実験には連結型の二人ゲーム Lines
o
f
A
c
t
i
o
n
(LOA) を遺び 13 種類の分類を与えて A貯S を実装し分類の確率を計算した.一般的な反復深化探索との対戦結果は， ARPS が反復深化に比べてより深くよりより絞り込ん だ読みで大きく勝ち越しその優位性を示した.
A
p
p
l
i
c
a
t
i
o
n
o
f
R
e
a
l
i
z
a
t
i
o
n
P
r
o
b
a
b
i
l
i
t
y
S
e
a
r
c
h
f
o
r
Any Games
-a
c
a
s
e
s
t
u
d
y
u
s
i
n
g
L
i
n
e
s
o
f
A
c
t
i
o
n
Tsuyoshi Hashimoto 1
,
J
l
!
n
N
agωhima
2
，
Makoto Sakuta2
,
Jos Uiterwijk
3
and Hiroyuki
Ii
da
2,
41
Faculty o
f
Engineering
,
2F
a
c
u
l
t
y
o
f
Information
,
Shizuoka U
n
i
v
e
r
s
i
t
y
3Department o
f
Computer Science
,
U
n
i
v
e
r
s
i
t
e
i
t
Maastricht
4
"Information and Systems"
,
PRESTO
,
Japan S
c
i
e
n
c
e
and Technology Corporation
abstract
Re
cently
, Rβalization-Probability
S
e
a
r
c
h
w剖 proposeda
n
d
i
m
p
l
e
m
e
n
t
e
d
i
n
t
h
e
s
h
o
g
i
p
r
o
g
r
a
m
GEKｭ ISASHI,
w
h
i
c
h
won t
h
e
W
o
r
l
d
Computer S
h
o
g
i
C
h
a
m
p
i
o
n
s
h
i
p
i
n
2002.1も searchesd
e
e
p
e
r
after
“
prob
a-b
l
e
"
m
o
v
e
s
a
n
d
s
h
a
l
l
o
w
e
r
a仇er “improbable"m
o
v
e
s
.
I
t
c
a
n
e
f
f
i
c
i
e
n
t
l
y
p
e
r
f
o
r
m
a
s
e
l
e
c
t
i
v
e
s
e
a
r
c
h
s
i
m
i
l
a
r
t
o
f
o
r
w
a
r
d
p
r
u
n
i
n
g
a
n
d
s
e
a
r
c
h
extensions
,
w
h
i
l
e
u
s
i
n
g
a
c
o
n
s
i
d
e
r
a
b
l
y
s
i
m
p
l
e
r
a
l
g
o
r
i
t
h
m
i
n
a
sysもematicw
a
y
.
However
,
s
i
n
c
e
t
h
e
method i
n
G
EKISASHI calculat伺 move同categoryp
r
o
b
a
b
i
l
i
t
i
e
s
f
r
o
m
m肌ygam飽b
y
p
r
o
f
e
s
s
i
o
n
a
l
players
,
i
t
c
a
n
n
o
t
be 田吋 for gamω 七ha七 lackt
h
e
a
v
a
i
l
a
b
i
l
i
t
y
o
f
a
s
u
f
f
i
c
i
e
n
t
q
u
a
n
t
i
t
y
o
f
game r
e
c
o
r
d
s
.
T
h
i
s
p
a
p
e
r
propo自es àted凶.quec
a
l
l
e
d
A凶omaticRe
a
l
i
z
a
t
i
o
n
-
P
r
o
b
a
b
i
l
i
t
y
S
e
a
r
c
h
(ARPS)
,
w
h
i
c
h
c
a
n
b
e
a
p
p
l
i
e
d
t
o
a
n
y
g
a
m
e
.
We
h
a
v
e
s
e
l
e
c
t
e
d
L
i
n
e
s
o
f
A
c
t
i
o
n
(LOA)
,
which 泊 ac
o
n
n
e
c
t
i
o
n
-b
a
s
e
d
tw
o
-
p
l
a
y
e
r
game a
n
d
i
s
co回ideredv
e
r
y
d
i
f
f
e
r
e
n
t
f
r
o
m
c
h
e
s
s
-
l
i
k
e
g
a
m
e
s
.
ARPS h
a
s
b
e
e
n
i
m
p
l
e
m
e
n
t
e
d
a
n
d
e
x
a
m
i
n
e
d
i
n
a
LOA p
r
o
g
r
a
m
.
The r
e
s
u
l
t
s
o
f
o
u
r
e
x
p
e
r
i
m
e
n
t
s
h
a
v
e
shown t
h
a
t
ARPS i
s
superior 七onorm
a
.
l
iもeratived
e
e
p
e
n
i
n
g
i
n
s
t
r
e
n
g
t
h
a
n
d
p
e
r
f
o
r
m
s
na町owera
n
d
d
e
e
p
e
r
se乱rch田.-81-1
はじめに
将棋では合法手が非常に多いため，これまでは各プ ログラマーが独自にさまざまな前向き枝刈りや探索 てきたことが非常に簡単なアルゴリズムでシステマ ティックに行うことができるのである.他のゲームでの問題点
延長の手法を用いていた.だがそのやり líはプログ
3
ラマーの手作業に依得する事が多いのが現状で，複 「激指J が 2002 年世界コンピュータ将棋選手権 を制したことから，実現確率探索は将棋に関しては 明らかに優れた手法であるといえるし，他の多くの ゲームでも非常に有効に働くと予想される.ところ が，ここで一つ重要な問題点がある.将棋のように プロ棋士が大勢いて優れた棋譜が大量にあるゲ}ム では問題がないが， LOA のように多くのゲ}ムでは 手本となるべき棋譜は残念ながらほとんど侮在しな い.そのため，この優れた手法を他のゲームに応用す るには指し手の確率を計算する新たな手法が必要に なる.そこで，我々はコンピユ}タの自動学習によっ て指し手の確率を計算させあらゆるゲ}ムに実現確 率探索を応用する lí法を提案する. 雑でわかりにくいものになりやすいという大きな欠 点がある.これに対して，鶴岡はプロの棋譜から抽出 した指し手の確率を元に局面の実現施率という値を 計算しこれを闇値に用いる実現確率探索を考案し，と の手法を実装したプログラム『激指J で 2002 年世界 コンピュータ将棋選手権を見事に制した.このよう に実現躍率探索が優秀なアルゴリズムである事は疑 いがないが，この手法を将棋以外のゲームで使う場 合に一つ重大な問題がある.激指の手法ではプロの 棋譜から指し手の確率を計算しており，将棋のよう にすでに強いプレイヤーがいて棋譜が十分にある場 合は問題がないが，参考となる棋譜が十分に存在し ない多くのゲ}ムではこの手法は通用しない.本稿 ではこの実現確率探索を将棋のように強いお手本があるゲームだけでなく，あらゆるゲームに対応させ 4
自動実現確率探索 (ARPS)
る lí法を提案し，連結型の二人ゲ}ムで将棋種とは かなり性質の違うLineso
f
A
c
t
i
o
n
(LOA) を用いて その優秀性を明らかにしていく.2
実現確率探索とは
鶴岡 [1] の提案した実現確率探索について説明す る.まず指し手を人為的に分類し， (主手，得する駒 取り，両取り等)この各指し手をプロ棋士の棋譜 ([1] では羽生の棋譜 600 局)を元に統計を取り，指し手 の確率を以下のように計算する. r指し手の確率= 指し手を選んだ数/指し手が存在した数」探索ではこ の指し手の確率を元に局面の実現確率を以下のよう に計算する. (局面の実現確率)=
(直前の局面の実現確率) x (指し手の確率) 実現確率探索では闇値として深さの代わりにこの局 面の実現確率を用い，それ以外の点は普通の深さ打 ち切りによる探索アルゴリズムと何ら代わりはない. だが(局面の実現確率)を閥値として探索すること で，より「有りそう J な手の場合はどんどん深く読 み， r無さそう」な手の場合はほとんど読まない，と いうこれまで前向き枝刈りと探索延長によって行つ コンピュータの自動学習によって指し手の確率を 計算させる新しい実現確率探索の手法，自動実現確 率探索 (Automatic R朗lization-P
r
o
b
a
b
i
l
i
t
y
Search,
または ARPS) をここに提案する.確率を自動で計 算するので，鶴岡の提案した実現確率探索と違いプ ロ棋士などの優れた棋譜が存在しないグームにも応 用できる.話は簡単で，まず指し手の分類を行い，こ れと実現確率探索のアルゴリズム ([1] または [2] 参 照)を実装する.ここで，各指し手種類の確率は同じ イ直にしておく. 次にコンビュータに自動対戦をさせ，探索を行うた びにJレート局面で「指し手が寄在した数」と「指し 手を選んだ数J をカウントする.一定数対局をした ら，ここで得た値を元に各指し手の確率を計算する. この値を元に実現雄率探索を行いまた「指し手が存 在した数」と「指し手を遺んだ数J をカウントし，こ れを繰り返していく.ここで注意しないといけない のは，指し手種類の確率が 0 だとその手は絶対に遺 ばれないので，初期値として「指し手が存在した数j と「指し手を選んだ数J に 0 でない数を入れておか ないといけない.各分類の確率が安定するまでこの 手目買を十分繰り返すことによって各指し手分類の確 率を得る.値を得られれば，その値を利用して実現確-82-率探索を行える. 駒の動き }jの例を図 3 に示す. f4 の白駒を使って説 明する. f4 の左上と右下には 2つ駒があり 2 マス動 けるので， d6 と h2 に動ける.同様に d4 にも動ける
5
LOA への応用
が，h6 は自分の駒があり行けない.上下占向には駒が
4 つあるが，上も下も 4 マス以内に敵の駒があるため 本手法の効果を調べるため，連結型の二人ゲームで 動けない.左右庁向では駒が 3 個あるので，c4 と黒駒 将棋種とはかなり性質の違う LinesofAction (LOA) を取って移動することができる.右~は 3 マス進む を題材とし，我々の LOA プログラム (T-T) (うるう と盤外になるので動けない. る)へ実現，確率探索を実装した. LOA を選んだ理由 は，数年前から Computer Olympiad [3J の競技種目 になっており性能を試しやすいという事，オセロの ように一定の手数で必ず終わることがなく将棋のよ うに終局条件が満たされるまで続くゲ}ムであり実 現確率探索の効果が期待される，といった点である. まずは LOA のルールを紹介する.5
.
1
LOA のルール LOA は 8x8 の盤を使い黒と自の二人のプレーヤー で行う二人零和完全情報ゲームである.以下 Mark Wina.nds のページ[4J;を元に LOA のル-;レを示す. 1.初期配置は図 l のように呆は盤の上辺と下辺に それぞれ 6 個，白は盤の右辺と左辺にそれぞれ 6 個並べる. 2. 鼎番からスタートし，黒白交互に一手ずつ指す 3. プレイヤーは必ずどれか一つ駒を動かさないと いけない.動かす駒は動く }j向のライン上にあ るすべての駒の数と同じ数だけマスを動かない といけない. 4. 味庄の駒は飛び越えることができる. 5. 敵の駒は飛び越えられないが，敵の駒のあるマ スに動けるときはその駒を取ることができる. 6. ゲームの目的は盤上の自分の駒をすべてつなげ ることである.つなぎ点は縦横斜めのいずれか の庁向でもよく，先につなげたほうが勝ちとな る.図 2 は県の駒がすべてつながっており，呆の 勝ちである. 7. どちらかのプレイヤーの駒が一つになったら勝 ちである. 8. 合法手がない場合は負け 9. 同時に両プレイヤーの駒がつながった場合は引き 分け. (2002 年度より Computer Olympiad で採 用されたルーノレ.それ以前は手番側の勝ちだった) 10. 同一局面 3 回で引き分け -83 一 図 1: LOA 初期局面 図 2: 終了局面例図 3: 駒の動き点例
とエリアによって分ける) ，直前に動いた駒を取る手
5
.
2
LOA プログラム (T-T) (うるうる)
(CHOKUTORI1 ，CHOKUTORI2and3) の計 13 種
実験に使う我々の LOA プログラム (T-T) につい 類に分類した
て説明する. 自動対戦を 100 回行うことで各分類の「指し手が5
.
2
.
1
評価関数 容在した数J と「指し手を選んだ数j をカウントし確 率を計算した.なお，一つの局面で同じ分類の指し手 が複数寄在する場合は「指し手が寄在した数J を 1 と 評価関数はまず自分の駒すべての重心を計算し，重 して計算した.図 4 に計算した確率の値を示す.ここ 心に近い駒ほど高い点数を与えている.重心から 3 で直前に動いた駒を取る手は C-TORI と書いている.マス以上離れているとマイナスの評価値を与えてお 中央 (AREA l)で駒を取る手 (C-TORI_l，TORL1)
り，重心から遣い駒はない々がいいと判断させてい が特に高い確率になっている.他に AREA1 に行く るそれ以外では完全に勝ちまたは負けのときだけ 手は比較的高い. その評価をしている.
5
.
2
.
2
終盤(結み)探索 通常の探索をはじめる前に勝ちと負けだけを調べ る終盤探索を行っている.これは将棋の詰み探索に 相当するが，王手という概念はないのですべての指し 手を候補として探索を行う.探索には PDS [5] を用 い，一定のノード数を超えたら探索を打ち切る.LOA
の終盤探索について詳しくは [6] を参照されたい.5
.
3
LOA の指し手分類 ARPS の実装にあたって問題になるのが分類の仕庁 であるが，ここでは盤を図 6 のように 3 つのエリアに 分け，各エリア聞での移動をそれぞれ分類し (lT01-3T03) ，他には敵の駒を取る手 (TORI1，TORI2and36
実験
(T-T) に自動対戦により得た確率を用いる実現確 率探索 (R品lization-ProbabilitySearch
, RP) と，単 純な深さ打ち切りの反復深化(IterativeD
e
e
p
e
n
i
n
g
search ， ID) の二つを実装し毎回ハッシュに 10 万ノー ド登録されたら読みを打ち切るという条件で先後入 れ替えで 50 回づっ対戦を行った. 結果は RP 先手で RP の 43 勝 7 敗， RP 後手で RP の 32 勝 18 敗といずれも RP が大きく勝ち越し，本 手法が単純な深さ打ち切りの反復深化に比べて優秀 であることが示せた.次にある局面での RP と ID そ れぞれの探索ノード数を図 5 に示す. [1] と同様に実 現確率探索の特徴的な分布になっており，ID より効 率的に探索を行っているのがわかる.-
8
4
-35
30
r-.2
5
渓歪
20
..Q~
15
2
0.10
5
0
〆々がしごググググ〆，
priF
決?と
Fφ:
〆
Ó'J
、、 図 4: 各指し手分類の確率 [:ep
t
h
s
o
f
s
e
a
r
c
h
n
o
d
e
s
6000∞
0 5000∞
oむ
00
∞
O
L•
230
∞∞
0~
2000000
3 ε 1000∞
o0
0123456789101112131415
d
e
p
t
h
|工ロ|
図 5: 探索ノード数の比較 F 3 0 07
まとめ
実現確率探索はこれまで前向き枝刈りと探索延長 によって行ってきたことをシステマティックに非常に 簡単なアルゴリズムで行う優れた探索法であるとい えるが，激指の手法ではプロの棋掛から指し手の確 E与を計算しており，参考となる棋輔が十分に仔在しな い多くのゲームではこの手法は通用しない‘我々は コンピュータの自動学習により指し手の離率を自動 で計算し，実現確率探索をあらゆるグームに応用さ せる手法自動実現確率探索 (ARPS) を提案した.実 験には連結型の二人ゲーム Lineso
f
A
c
t
i
o
n
(LOA)
を選ぴ， 13 種類の分類を与えて ARPS を実装し分類 の確率を計算した.一般的な反復深化探索との対戦 結果は， ARPS が反復深化に比べてより深くよりよ り絞り込んだ読みで大きく勝ち越しその優位性を示 した.8
Fu
ture work
本手法はプログラムに探索を行わせ自身が選んだ 指し手によって指し手確率を計算するため，答えが はっきり出やすいゲームではまったく問題がないが， そうでない場合は非常に評価関数に依存する.まずは LOA のゲームの性質を詳細に調べより優れた評価関 数を作成し， ARPS の効率をさらに高め Computer Olympiad で優勝できるプログラムを作成したい. また，評価関数の学習に関してはこれまでに多く研 究されているので，評価関数も学習させながら本手 法を用いるとより効果的であると，思われる.今後は LOA だけでなく AMAZONS など他のグ}ムにも実 装し，評価関数も学習させより本手法の効果をあげ てみたい.また，分類を自動で行えるシステムを考案 しより一般化した形で本手法を展開し，優れたゲー ムアルゴリズムの自動作成という左向へ研究を進め ていきたい.参考文献
[1] 鶴岡慶雄，横山大作，丸山孝志，近山隆.局面 の実現確率に基づくグーム木探索アルゴリズム.Th
e6
t
h
Gαme Programming Workshop,
pp.17-24， 2∞1.
[
2
]
~敢指開発チーム. 将棋プログラム「激指j のf式 -v-.
h
t
t
p
:
/
/
w
w
w
.
l
o
g
o
s
.
t
.
u
-
t
o
k
y
o
.
a
c
.
j
p
;
-
g
e
k
i
s
a
s
h
i
/
[
3
]
7
t
h
Computer
Olympiad
Homepage
,
h
t
t
p
:
/
/
w
w
w
.
c
s
.
u
n
i
m
a
a
s
.
n
l
/
o
l
y
m
p
i
a
d
2
0
0
2
/
[
4
]
The Rules
,
M
a
r
k
'
s
LOA Homepage
,
http://www.cs.unimaas.nl/m.win組ds/
