ローカルルールを用いた地の確率的評価法の研究

(1)

1-2

ローカルルールを用いた地の確鞠句評価法の研究

永吉宏之等々力賢鈴木篤之東京大学大朝完工学系研究科システム量子工学専攻 na四倒.vma且α.lu-tokvo.ac.in 概要本研究では、数理的な解析をもとに、 4 近傍を考慮したローカノレルーノレを作戒し、それを用いること

により、局面上の各地点の取り得る状態の確率を出力する評価関数の計算法を提案する。本評価法の妥

当性を検証するためプロの棋譜を用いることで鞘面を行ったの棋譜上の対局途中の局面においての本手法による地の確率制面を、棋譜上の終局面の状態と比較するにより統計的に解析を行った。その結果、死活の影響が少ない場合において良好な結果カ均等られた。

Re鵠arch ofProbab出BtiC 時国防'ry

Es

t

i

m

a

t

i

o

n

us:泊g Local R叫創

日n方u恒 N唱ay'値比Ma縄問官凶oriki， A鈎uyukiS四uki. D句artm阻.t of Quan如皿 E噌且鴎ringand 匂胸間鎚ence，

&主∞，lofE噌n回ring， TheU国四国tyof'lè向。 Abs回ct

h 出ispap町 wepro戸鴎 aprobab:出血回討回y 醐ma出，nme也00

u

s

i

n

g

l

o

c

a

l

r

u

1 e

s

i

n

oonsidera也n

a

f

4

nei位同泊gar回 ofthe 匂曙et paint. τ'his me也.00 国2 回出脱出e probabil均 d 姐也阿nt 凶ng black(whiω 総出ωq 明也民k

t

h

e

a

c

u

r

a

c

y

a

f

o

u

r

me也od，鴨田eprofe組閣al 伊m館組dαmpal'e

t

b

e

o

u

t

p

u

t

a

f

o

u

r

proba凶怠也副mation 泊也.emi剖le

o

f

t

h

e

game

wi也 result

a

f

the 伊me. 鴨 ob凶ngood n叫土8wh阻 lifeand 血a血 isnot 泊宜.uen出l

1. はじめに情報処理の分野で研究されてきたゲームには、チェス、将樵囲碁などがあるが、その中でも囲碁が最も難しいとされてきた。その主相理由は分岐因子が大きい、評価が難しいなどであり、それらを解決するために様々な研究がされているが、他のゲームに比べると強いプログラムは出来ていなし、実際にコンピュータ囲碁プログラムを作成する場合、プログラムの強さと密接な関係、のある重要な要素が場っかある。正確な死活判定、効率的なゲーム木探索、精度のよい評価関数等である。その中でも精度のよい評価関数の僧或は、駒の損得が支軍助なチェスヰ帯棋と異なり、複数の重要な要素カ球難に絡み合うために、非常に困難である。従来、囲碁の評価関数としては、主として石の影響をポテンシャルとして表現する影響力関数

に基弘、て構成されたものカ準用されてきた回。

それらの評価関数は人間の感覚に合致するようにパラメータがチューニングされているため、評価の数郡句な根拠を得るのは難し川

一方で終盤における数理的な解析の研究凶が

盛んに行われている。特に回廊で構成され止簡単な寄せは、完全に解くことが出来ている。そこで本研究では、数理的制持析による評価関数封筒岳するために、回廊、 T 字輔、+母唱に対する簡単t，dt鞠?をもとに、 4 近傍を考慮したローカ/レルー/レを作成し、それらを連立方程式として解くことにより、局面上の各地点の地になる確率を求める評価法を提案することを目的とする。 2. 対局終了局面における喝事囲碁の対局カ幣了した局面において、局面上の各点の状態を、右の状態より黒石、白石、空きの 3 状 n B

(2)

態、地の状態より黒地白地中立の 3 状態、 3X 3=9 種頼の状態に分類することが出来る。この中で、黒石かつ黒肱白石かっ白地は存在しないので、実際は 7 種類の状態が可能である。この 7 種類の状態l丈どのような組み合わせでも隣接可能なわけではな川、隣接可能なのは、・黒地に所属するものどうし .白地に所属するものどうし .中立に所属するものどうし・黒地に所属するものと中立黒石精き黒石〉 .白地に所属するものと中立白石倍き白羽である。対局終了時にこのバ戸ルを適用すると、石の死活珂綻していれは空き地劇場椀Vょのれ白地なのか、中立(ダメ、セキなど〉なのかを隣接地点の状態により決定することが出来る。局面が対局終了昨でなb 暢合において、局面上の各地採の状態は、 7種類の状態の湯合状態になっていると考えることが出来る。例えば死活のはっきりしない黒石の場合は、中立黒石t活き黒石7 と白地黒石OEに黒石?の混合状態であると考えることが出来る。言b 喰えると混合状態の各戒分の割合と広石の死穏や地になる確率から構成されていると考えることが出来る。対局終了時における隣接可能ルールを応用することにより、混合状態の各成分の審拾を推定することカ珂憶ではないかと考えられる。そこで対局終了時における隣接可能ルールの拡張としてローカルルールを考えることにする。このローカルルールを満たすような混合状態を求めることにより地の確咽拘評働t可能であろう。 3. ローカルルールの構成本布槍では局面上の空き地点の状蜘こ対する 4近傍のローカルルーノレを用い、それによって構成された連立方程式を解くことにより地の確咽均評価を行うことを考える。本謀、石の現知ま重要制脊報ではあるが、現在、石の涜沼こ対するローカルJトJ\.郁与えられていないため、ここで仕すべての石は活きていると仮定する。局面上の空き地点を位置により、中央、辺、隅の 3 種類に分類し、それ窃応対して隣債する地点の状態からさらに分類を行も\それぞれに対してローカルルールを構築する。各ローカル Jレーノレl胡象地点の隣横伏態を含掛斬可能な形状 (回風 T 字路、+等喝なのに対する解析結果を参考にして構輔討ーる。 -空きが中央に属している場合 *空きが黒石、白石の両方に隣接している場合

客船

図 1 鳳石、白石倒寛加こ虜捜している場合この場合は空き地点が黒地になる確率と白地になる確鼎ま 0 となるの *空きが黒石のみに隣接してし、る場合この場合は白地になる確噛ま 0 となる。黒地になる確率は隣接している黒石の数によって求め方が異なるの柿隣接する黒石の数が 4 の場合

-

'

1 .

図 2 隣接する黒石￠場初t4 C7;場合図 2 中の X が黒地になる磁揮は 100% となる。柑隣按する黒石の数が 3 の場合空き地点が黒地になる確率は閉じた巨廊に対する解析を元に推定することができる。空き地点が黒地になる確率を h、隣接空き地点が黒地になる確率を Pn とすると九 =0.5凡 +0.5 ，，.、合M が成り立ち、この関係式をローカノレルー/レとする。

(3)

R = O R = i

2 1 _ 3

P

,=':"

P

v

=

'

:

'

" 2 .

.

4 九 =1

P

x

=1

図 3 閉じたE聞こ対する解街

~=1 九 =1

図4 除、たE副司付る'.

-11-"隣按する黒石の教が 2 の場合空き地点が黒地になる確率』玄、聞いた回廊に対する解析を元に推定することができる.この場合、正確な関係お湘雑な多項均こなるため、ローカルルールは 2 次近似丈で構成する. 空き地点が黒地になる確率をぬ隣接空き地点が黒地になる確率の平糊車を P，. とすると

P

x

=

0 .

0

6

3

4

9

2 P

f

t

2 +

0.686508え +0.25ω

が求まり、これをローカルルーJレとする. 帥隣接する黒石の数が 1 の場合空き地点が黒地になる碓網ま、 T寺帯型に対する解析を元に推定することができる.自制服臓にローカJレJいーJレを 2 次近似式。欄賦する. 空き地点が黒地になる確串を h 隣接空き地点が黒地になる確率の平均値を凡とすると

P

x

=

0 .

1

8

7

1

8 p

"

2

+

0 .

6

8

6

2

8

2 p

"

+

0.125ω

が求まり、これをローカルルーJレとする. 九 =0 九 =1

P

x

=1

図 5 1苧割強Bご対する飾瞬

(4)

*空きカ鴇石とも白石とも隣接していない場合空き地，~が黒地になる確率』ネサ停帯型に対する解析を元に推~することができる。前例と同様にローカfレルールを 2 次近似式で構除する。空き地保が黒地になる磁率を h、隣接空き地点が黒地になる確率の平瑚直を凡とすると

P

x

=

0 .

3

4

6

3

2 0p

"

2

+

0 .

5

9

1 l

8

0 p

"

+

0.0625ω

が求まり、これをローカIvlいづレとするの

p

,

=0

P

v

=土

^

1

6 PIz--ｭ

" 256

九 =1

P

x

=1

図6 刊雫姐に対する解析 -空きが辺に属している場合隣接する 3 点に黒石と白石の存在により分類を行い、それそ仇のケースに対してローカルルーJレを構築する。 *空きが黒石、白石の両方に隣接している場合この場合、空き地点カ鴇地になる確率と白地になる確率はともに 0 となるn *空きが黒石のみに隣接してし、る場合空き地点が白地になる確率は 0 となる。黒地になる確率を求めるために隣接している黒石￠教でさらに分類を行うの柑隣皆する黒石の数が 3 の場合空き地点が黒地になる確率は 100%となる。軸隣接する黒石の数が 2 の場合この場合lま、空きが中央に属し隣皆する黒石の数が 3 の場合と同様になる。ローかレノトー'JVIま剤。と閉じになる。帥隣接する黒石の数が 1 の場合この場合は、空きが中央に属し隣皆する黒石の数が 2 の場合と同様になる。ローカJレルールは式ω と閉じになる。 *空きが黒石、白石ともに隣接していなb 暢合空き地点が黒地になる確率は、 T字帯型に対する解析から推定することができる。ローカルルールは式抱)と同じになるの -空きの位置が隅に属している指合この場合、隣皆する 2点の状態から分類を行b\ それそ仇に対してローカルルーノレを構築する。 *空きが黒石、白石の両方に隣接している場合空き地点が黒地になる確率と白地になる確率はともに 0 となる。 *空きが黒石にのみ隣接している場合空き地点が白地になる確率は 0 となる。黒地になる確率を求めるために、隣接している黒石￠場了でさらに分類を行う。 "隣接している黒石の数が 2 の場合こι場合の黒地になる確率は 100%になる。柑隣接している黒石の数が 1 の場合この場創立、空きが中央に属し隣皆する黒石の数が 3 の場合と同様になる。ローかレルールは到。と同じになる。

(5)

-アグハマが多b 場合アグハマが多い場合は局面上に死に石が多く残っているため、本手法による確率桜評価値の精度は悪化している。特に確率的評価値の高い憤按で顕者である。 *空きが黒石とも白石とも隣接していない場合この場合の黒地になる確率は、聞いた巨廊に対する解析から推定することが出来る。ローカルルーノレは式"12)と同じになる。情成されたローカノレルーJレを局面上の空き地点に適用し、それらを連立方程式として解くことにより、地の確輔制面が鳴られる。 -・崎・・・t・・} ヂー9. 岨=・..，.・

.

ー.(・・? 。-，。 21"0 1'1. '.7 1 。町却 _s・・.. 833。官..

,

z。ー却 '・.00。 .“・ s・.. ...40 '2・・. -岨. 48.7 ...8。帥個 8101 _ea.・ ...8。 _s・・・

.,"

_fI8.・ ...7。 _"・・a _10・・ 7%. . 7・・10 t.・

.,.

_“

.8 ...t。 _10・・ 2・唱 .7.1 同・唱。。 140・国・ -・.。アゲハマ品移b 場合 J・

• .

・・・，

,

，・....

.

...、...

.

...、.

.

'

_•

ベ.'・・・・，，・J ・

•

aτ ・・・、，

,

，、，

,

，、'..

'

•

20 40ω80 地の砲.的解価値 (96) 表2 1 ∞ A 0・

m

碍

事 ω

.

$

2ω

霊 m

r

o

_o

4 ，本手法の統計傑麟値プロの槻普を用いて本手法の統計的な考察を行うのプロ棋譜中の局面に対して本手法を適府する。その結果得られた地の確率自情価を、対局終了時の地の状態と比較することにより、評価のE確さを鞘面することができる。たとえば、黒地になる確率が 50% の空き地点が 100個あった場合、それらに対指する対局終了時の状態が 50個程度黒地になっていれば評価は妥当であるということができる。本覗党では石の死活を考虚していないため、死活判定の影響が小さ b 、と思われるアゲハマの少なし棋譜と死活判定の影響が大きし、と，割オLるアゲハマの多ν惨詰普に対して統計官明朝子を行った。 -アグハマが少ない場合本手法による地の確朝瀞価値と棋譜から求めた栂憎句確率がほぼ直瀬状に分布し、よく一致している。石の死活の影響カ沙なし暢合には本手法の妥当性カ派されたといえるであろう。 1ω 5. 考察本手法は爽活の影響治沙なし場合、よい評価法ではあるが、幾つ村湾僻する陪題点がある。それらについての考察を行う。アゲハ吋移L 場合図 8 .・・~...(・・2 ヂー98 申書t・ .齢骨・・t・・3 。-，。 _2・.7'‘ '00II a・-。唱。 -20 2・唱 .7 3723 12. 倉。-.。市..，.，t 4880 24

,

1 ...。 11341 4838 31. I .0 ・・5。 @唱，. _s・・g 415.15 .。ー.。

'

0

4 '

_'8'・ 47.51 10-7。電 "4 1183 151.e 70-80 ，..。 '0唱 3 72.・ a。ー.。 8 .. ..。 T 唱 .8 同-'00 80。 708 83.3 -欠け目の判定アゲハ吋妙なb 喝合 o~ 表 1

,

••••

•.•••

••••••••••••••••

e

-.・・

•••

•

・・

••

パ・

•.••

••••••••••••••••

••

・

••

・

••

・

••

・

••

••..•••

、

•••

EE--、.目

-•

••••

• ••••

• . .

. .

.

、

•.

•

. . . , .

••••

•

∞ MWωωm -Z4 市咽包 Emg 一日占 .L 沼恒』

-13-1 ∞ 20 40ω80 地の砲率的解価値(%) 図 7 アゲハ吋沙なも鵠合

(6)

本研究ではローカルルールを 4 近傍の状態で構成しているため、 8 近傍に属する斜め位置の状態を考慮してし、な凡そのため欠け目の判定前難しくなっている。例えば図 9 は 4 近傍の状態が同じで 8 近傍の状態が異なるものである。図中の下 2 つは欠け目の形であるn この陪題点は斜め位置を考慮することにより解決可能だと，駅つれるn -隣皆する地点聞の相関例えば、隣按する黒石の数が 2 の場合において直融型と L 字型の区別をしていない点部損ずられる。 L 字型において斜め位置に石カ靖在するときは蘭線型と同じ扱いでよいのだが、石が存在しなb 暢合は異なる扱いをしなければならなb 、そ￠哩由として隣接する空き地点の確率が斜め位置の空きを過して相闘を持ってしまうからである。

- "

金十e

"'-1ω

・..~霊 H

・ωrlω

図 10 隣協働制奇士の憎刻島田つの問題点はローカ/レノトルを 4 近傍から 8 近傍4主張することにより、解決可棺であると恩われるn -黒地確皐と白地確率の同時考虚現在、黒地になる確率を求める場合に隣陵する空き地点の白地になる確率を考慮に入れていない。そのため明ら糾こ白地になる領核中に黒姻こなる可能 t封t生じている。この陪題点を解決するために、より詳細な解析を行い、黒地になる確率と白地になる確率を同時に用いたローカルルールを構成する必要がある。 -石の死活確率現在、石の死活を考慮してし、な川これは実用上の最大の陪題点であるn 石の苑ヨ舌を確率的に表現するには次の点を考慮できれば可能であると思われる。 *宥連が 2 眼を持つ確率石速が 2 眼を持勺曜割ま、本手法を適用することにより石連の周囲の地になる確率を求め、それを使用して求めることが可能であると考えている。 *石甜調悦劃師自率石直聞の連絡暗率ほ数酒句に求めること炉I能であろう。連絡確率を求めるためのローカ/レルーJレを構成し、それを用いることで求めることができると考えている。 -ローカルル-/レの近似本研究においてローカルルーJレを隣接空き地点の地になる確率の平均値の関数とし、実際の関係式を求めるf廿つりに 2 次針路1式を与えた。実際には正確な関係式をつくることが出来るのだが、槙維な多項式￠漣立方程式を解かなければならなくなるため実用的な意味を持たないと思Jオもる。ただし、さらに高精度な評価が可能になった場合、 2 次式より精度の酌活似式が必要になると思土れる。 6. まとめ数理的な解析による評価関数を作成するために、回廊、 T 字輔、寸停識に対する簡単t.t)1断をもとに、 4 近傍を考麗したローカルノレールを作戒し、それらを連立方程式として解くことにより、局面上の各地点の地になる確率を求める評価法を提案した。本手法をプロ棋譜上の局面こ適用したところ、死活の影響効沙ない場合に良好な結果治鴇ら払本手法の有刻生を示した。 .考文献 [叫斉鵡泰己、“コンピュータ囲碁研究'、人工知能学会誌 Val lO，

Vall0

,

No.6

,

1

9

5

1

凶 E.Ber凶amp、 D.Wolfe 著、吉)1 附歯肉L 小材雄 1台、石原孝一郎訳、“囲碁の算法ヨセの研智'、