条件付き確率PIPEによる将棋の評価関数の生成

(1)

1 .

駒位置と効き関係に注目した詰み評価関数の自動生成

輪誠f 横山

大

作f

_近

山隆↑ コンビュータゲームプレイヤにおいて精度の高い評価闘数の作成は、探索アルゴリズムの選択とともに電要な要素のひとつである。精度の商い僻価開放の作成のためにはその特徴を良〈表す評価要素の選択が不可欠である。本研究では詰将棋を対象として駒位置と効き関係の単純な特徴寝業から評価要素を自動生成することを目的として研究を行った。評価としては、生成した訴価要素について単屑パーセプトロンを用いて学習させる ζ とを行った。結果として.数千~数十万個程度の評価要素を生成し、 76%程度の正解率で読み・.f訴を判別できる評価関数を作成することができた.

Automatic c

o

n

s

t

r

u

c

t

i

o

n

o

f

e

s

t

i

m

a

t

i

o

n

o

f

mates

based on p

o

s

i

t

i

o

n

s

and e

f

e

c

t

s

o

f

p

i

e

c

e

s

MAKOTO MIWA.t DAISAKU YOKOYAMAt

and TAKASHI CHIKAYAMAt

Constructing 肝aluati岨 functions wi七h high 配C町'acyisone of thecri色icalfactors like the

I!election of thef;回t I!earch algorithminωmpu'色町耳回ne playe隠・ The 田，lectionof theu揖ful

eva1uationfeat岡田泊 e圃entialωω田struct 別aluation “nctionswith highaccur副司Y・ Inthis

pap町，we generateev叫uationfeatures for evaluation functionsintsume-shogi problem au-・ ωm剖ic叫ly. We m

i

!

d

e thefeatur国会omsimplefeat町民 poslti佃a 皿d effi劃お of piec回・As 間関ùuation ，明 coDStructed 例aluationfunctions by using thesingle-l却官 perceptron 組d

the generatede四luation featur国. As獄perimental r田ults，evaluation function using gener-ｭ

前edev町alhundred thous岨d 明叫四，tionfeaturesw踊 abletoc1踊si里yp個itionsabout 76% of 国curacy. はじめにとは限らない。コンピz ータゲームプレイヤにおいて静的評価関数 (以降、評価関数)はその緩る舞いを決める重要な要素のひとつである。評価関数とは局面の有利・不利の判定を行うためのものであり、多くのゲームプレイヤプログラムではその評価する対象の特徴を表す評価要素の重み付き線形和で表されている。現在、将棋などの比較的難しいゲームにおいては、重み付けなどについて部分的に自動化されているものはあるものの、そのほとん Eは入手で作られている.評価関数を人手で作る際にはそのゲームに閲する深い知識が必要とされ、重要な評価要素の見港としの回避、足りない纂棄の発見のために多くの時間老費やす必要がある。選択した要素に重み付けを行うことについても同様に多くの時簡を費やす必要がある。また、人手で作る方法はアドホックな方法であり、忌適に近い評価関数が得られるこのような評価関数作成の問題を解決する一つのアブローチとして評価関数の自動生成がある。評価関数の自動生成は、オセロなどの比較的簡単な問題においては多く研究がなされており有用な結果カ鳴られている@その一方で、それより難しいといわれるチェス・将棋・囲碁な E のゲームについては研究が少なく決定的な手法も見つかっていない。本舗では将棋の部分問題である詰将棋について、ある局而を与えた時、その局而が需むか詰まないかの程度を返すような評価関数の評価要素の自動生成を目的として研究を行った。詰将棋を対象としたのは、話み・不詰が明纏であり、手法の評価対象として適切であると考えたためである。本研究では次の手順で詰将棋の評価関数を作成した。まず、局面の駒位置と効き関係を真偽値の特徴要素として抽出した.次に、その特徴農薬の論理積を取ったもののうち、訓練局面の中に頻出であり、また詰み・不詰の選別に有用なものを選別し、評価要素とした.母後にパーセプトロン老用いて重み付けをすることで、評価関数を作成した。結果と f 東京大学大学院新領域.J成科学術笥科

Gr ... ill"te SchooJofFronti町 Sci皿C輔， Uni明開Ity OI

(2)

しては、約 76%の正解率で詰み・不結を判定できる評価関数を作成することができた。本論文では以降、 2 章で関連研究を紹介し、 3 章で本研究の手法、 4 寧で実験結果について説明し、 5 章でまとめと今後の課題を述べる。 2. 関連研究本章では関連研究として 2.1 で評価関数の自動生成に関する研究について紹介し、 2.2 で本研究で用いた頻出パターン抽出手法について述べる.

2 .

1

評価関数の自動生成評価関数の自動生成は、コンピュータゲームプレイヤの自動生成につながるとともあり、人工知能の大きな目穣の 1 つである。しかし、その困難さから評価関数の自動生成に隠する研究は非常に少ない。機械学習を用いた評価関数の生成に関する研究は、評価要素を人手で作成し、その重み付けを自動化するというものがほとんどである問。評価関数の自動生成は単純な評価要素(以降特徴要素)を元に評価鴎教を構築する.その研究は評価関数の作成の方法から主に 2 つに分けることができる。 1 つは評価重要素の生成を先に行い、抽出した評価重要素に重み付けを行う ζ とで評価関数を表現する方法である。この方法では、評価関数は評価要素の線形和で表される.とのような事慣には、盟関τ官7) ・ ELF21₎•

GLEM

3) .金子らの手法14)，15) な Eが挙げられる。もう 1 つは特徴要素を元に多層ニューラルネットワークなどを用いて直接的に評価関数を表現する方法である .ζ の方法では、評価回数は特徴要素の非線形結合で表される.このような研究には、強化学習を用いた TD-GammonI8_{) や進化的アルゴリズムを用}

いた Fogel による Tic

Checker旬、百e Dia凶.bu随d Ch錨s Projectl3) な E が挙げられる. Eちらの方法が良いと一概に言うことはできないが、前者の方法を用いる利点としては後者の方誌に比べて・少ない資源で高次の評価要素を作成できること・評価関数の分析が容易であること・評価関数の高速化が容易であることなどが挙げられる.一方で後者の方法の利点としては表現能力が高い ζ とが挙げられ、より正確な評価闘数を実現できる可能性がある。

2 .

1 .

1 GLEM

GLEM3_{)，4) とは、 G但.era1ized}

L

i

n

e

a

r

E

v

a

l

u

a

t

i

o

n

Mode1の略であり、 M.Buro カ鴨察した汎用の評価関数自動生成手法である o GLEM は彼が開発した 1997 年に人間のチャンピオンを倒した最強のコンピュータオセロプレイヤの 1 つであるLogistell02_{) に実際に用} いられている。この手法は現在最も強いコンピュータオセロプレイヤの l つであるといわれている Herak les19_{) など多くのコンピュータオセロプレイヤで使わ} れ、非常に良い結果を残している。 GLEM は次のように評価関数を生成する。まず、その評価関数のもととなる特徴要素 (a伽nic

J

e

a

t

u

T

e

s

)

を抽出する.これは、入手で行われ、候補としては他の特徴要素の組み合わせによって表現できない真偽値で表現された要素が挙げられる。次にアプリオリ法1) に似た方法で、特復要素の頻出な組み合わせを抽出し評価要素 (confi抑Tation) とする。最後に展小ニ乗法で重み付けを行う. GLEM はその特徴として、入手で抽出した pattern を用いる ζ とで、ある特定の形にあった特徴要素の組み合わせのみを対象としている.これにより頻州要素の生成を容易にし、 GLEM はその高速な評価要素へのアクセスが可能となる. Buro は 1 ，700 万の訓練局面、 51 の pattern を用いて、 GLEM の手法に基づき、 4 手ずつの 13 段階に分けてLogistello の評価関数を作成した.実験環境は

CPU

A

t

h

l

o

n

XP

1

8

0 0+

(1，666MHz)を用いている。結果として約 150 万の評価要素が得ら才1、評価要素の重み付けに 6 時間かかり、 1 秒に 140 万局面を評価できる高速な評価関数が得られている。 2.2 額出パターン抽出手法頻出パターンの抽出アルゴリズム肱 POS，we

1>-

log

, 化合物，ゲノムなど多〈の応用があり、データマイニングの分野においてこと数年で飛置的に進歩している. 以前はアプリオリ法"が主概であったが、現在良い結果を出しているアルゴリズムの多くは、 2000 年に提案された FP-g問W曲川アルゴリズムにおける FP-tree というデータ構造を基にしている.類出パターンとは、トランザクションがあるアイテム集合の部分集合として表現される場合に、その n 備のトランザクションの内に α 個{忌小サポートと呼ばれる)以上出現する集合のことをいう.績附パターンは、あるトランザクションの部分集合であるので、トランザクシヨンの含まれるアイテム集会の節分集合として表現される. このような頻出パターンを抽出するアルゴリズムで特に高速であるといわれているものには、 FP-8開店h叫や LCM (Lin回~

t

i

m

e

c1儲ed

i

t

e

m

s

e

t

M

i

n

e

r

)

16).1η な出噂げられる. このように高速に抽出する ζ とはできるものの、特にその最小サポートを小さくしたとき、とのような

(3)

-49-頻出パターンは非常に大量になる。それを軽減することのできる方法の l っとして頻出飽和パターンのみを抽出する手法が提案されている。頻山飽和パターンとは、そのパターンが含まれるトランザクシヨンの集合が等しいパターンについてその傾大元のみを抽出する手法である。このような手法として FPclose9) や LCM が提案されている。 FPclωe は FP-growth 同緩に FP-tree を構築し、 FP-tree から抽出したパターンを CFI

(

C

l

o

s

e

d

F

r

e

q

u

e

n

t

It四五set) ・tree という構造に鋪入し、頻出飽和パターンを高速に抽出するアルゴリズムであり、 IEEE ICDM'03 併殺のプログラミングコンテスト FIMI'03 において優勝している。また、 LCM は prefix 保存飽和拡彊という手法を用いることで、解保存用メモリを持たずに重複なく頻出パターンを抽出することを可能にしており、 IEEE

ICDM'

Q4 併設のプログラミングコンテスト FIMI'04 において優勝している。 3. 局面からの評価要素の抽出本研究は詰み・不詰の訓練局面から目的とする詰み・不詰の程度を返す評価関数の評価要素を生成することを目的としている。本研究において、この詰将棋を対象としたのは、・入手で摘出した特徴についてそれなりの高い精度で学習できており 22) 学習対象となりうる問題であることがわかっていること・詰将棋が詰み・不諮という明確な値を持った問題であり目的としている評価関数の評価要素の評価が比較的容易であることの理由カ略げられ、本す法の対象として適切であると考えたためである。また、評価が容易であることのほかにも、精度の高い評価関数そ作成することができれば、諮探索の制御などへの応用が可能であるという知見も叫において得られており、そのよラな評価関数の作成を目的とする ζ とは価値があると考えられる。また、本研究では詰将棋を対象としているが、本手法は、勝ち・負けを基にした方法を用いることで実際の本将棋にも適用可能であると考えらえる。ただし、現在の環境で本将棋を学習の対象とするのは難しく、今のところ本将棋は本手法を評価するには適切な対象ではないと考えられる。実際、本将棋について現在の入手で作成した評価関数と同等の精度の評価関数を機械学習によって作るということができている研究を見つけることはできなかった。本章では、以降、本手法において評価要素を生成する手法について説明する。本手法は次の 3 つの過程か

(

1 一，香，後手) (2 一，桂，後手) (8 九，桂，先手) (9 九香，先手) ( 1 ー，後手)→( 1 二，空)

(

1 ー，後手)→( 1 三，後手) (9 九先手)→ (9 七，先手) (9 九，先手)→(9 八，空) 図 1 初期館副の特徴袈~ (歩 1 ，歩，先手) (歩 2 ，歩，先手) (飛 1 ，飛，後手) 図 2 持ち崩の特徴農家らなる。 ( 1 ) 局面の駒位置と効き関係を特徴要素として抽出する。

(

2 )

頻出飽和パターン{特徴要素を組み合わせ)を抽出する。

(

3 )

頻出飽和パターンから諮み・不諾の判定に有用なものを選択するととで評価要素を生成する。以降この 3 つについて説明を行弘 3.1 局面の駒位置と効き関係の抽出詰将棋の評価要素を作成するためには、その評価関数への入力を表現するために、詰将棋の局面の状態を表現する集合が必要である。それぞれが局面の特徴の一端を表す単純な要素(特徴重要素)のセットとして、本研究では局面の駒位置と効き関係について抽出を行い、諮将棋に関する情報とした。局面の効き関係を用いたのは、 3.2 に示すように今回は議題積のみを対象としていることから駒位置によってのみでは表現できない効き関係が存在するためである。駒位置は(位置，駒の種類，手番)の形で、また効き関係については(位置，手番)→(位置，手番)の形でそれぞれ表現した。図 1 に初期銭面の特徴要家老示す。持ち駒については図 2 のように駒位置の位置に盤外の駒用のマスを設けた。また、効き関係については効き対象の手番に空マスをいれることで、空マスについての情報も考慮に入れるととにした。

(4)

とれにより局面は 37，33~ の真偽値の重要素によって表現することができ、乙の 37，336 の要素を特徴要素とした。 3.2 頒出飽和パターンの抽出本研究では 3.1 で説明した特徴要素の単純な槍理積で評価要素を表現する。評価要素を得る方法には、 Z聞I叩η な Eのように詰将棋のルールを与えてそれを展開して得る方法と、 GLEM3_{】のように特徴要素を組み合わせるととで得} る方法カ湾えられる。前者については、抽象度の高い情報を与えることが可能であり、また特徴要素がそのルールを表現できるものでなくてはならず特徴要素に関して見落としがないという動員があるが、そのJv ルの記述は困難である。後者については、その特徴要素の選訳には多くの可能性があり、特徴要素の選択を誤ると詰将棋の評価関数に必要な要素を全ては表現できないという問題もあるが、その特徴要素の抽向は比梯熔易である。本事院では後者のような特徴要素を組み合わせる h法で評価要素を抽出する ζ とにした。とこで、上記の 4 万程度の特徴要素の全ての治理績を取ると、組み合わせ爆発が起ζ ってしまう。例えば、要素 3 つの全ての論理積を記値するのに必要な記憧容量は単純に考えると 200TByte 以上~n'‘J になるため、通常のコンピュータの容量では全ての論理績を試せるのは要素数 2 までである。との制限では表現力の高い評価要素カ鴇られなくなってしまう。このため本研究では、 ζ の組み合わせ爆発を防ぐために大量の棋譜に頻出する論理積のみを抽出した。めったに出現しないが詰みであるととを確定できるような要素があればそのような要素を見逃しているととも考えられるがそのような襲棄を特定することは困難である.また、棋譜にめったに出現しないような特徴については学習において証拠が少ない ζ とになり、重み付けにおいて過学習の原固となりやすいため出演頼度で要素の教を削減する ζ とはいずれにせよ必要である. ζ の論理積の抽出は、その特徴襲索が真になっているラベルのセットで局面を表現するととで、頻出パターンの抽問問題と考えることができる。頻附パターンの抽出にはデータマイニングの分野で注目されている 2.2 に示した頻出飽和パターン抽出手法を用いた。頻出飽和パターンは頻出パターンに比べて教が少なく、抽出されるパターンにおける冗長性を減らす ζ とができる。 3.3 にポす指槙や多くの学習アルゴリズム 1t9x9x14x2 偶上の町 +38x2(持ち駒i)+9x9X2x 9X8x3(鋤き) 柑悶踊Ca x In 37336 x 3[bit) には、評価謀議それぞれが独立であるという仮定があり、 ζ の多くの従属なパターンの削除はその仮定を満たさない評価要素の削減につながる。 ζ のため、学習をより効果的に行う乙とができると考えられる。本研究では頻出飽和パターン抽出手法の一つである LCM を用いた. 3.3 評価要禦の選択頻出飽和パターンは非常に多い。そのため実際の評価関数に用いるにはその学習が困嫁である上に、評価にかかる時聞も多〈なってしまうことが考えられる。そとで、との大量のパターンから重要であるパターンのみを選別する ζ とを考えた。 ζ の選別の基準としては、ベイズ学習に基づいた確率の推定値刷、カイ 2 乗テスト、相互情報量的な Eカ噌えられる。事研究ではこのうち比較的計算コストの小さい確率の推定値とカイ 2 乗テストを用いるととにした。・ベイズ学習に義づいた確率の推定値確率の推定値とは局面にあるパターンが出現した時のその局面における詰みの確率の推定鎮 ζ とである.証鎚の数が多ければ、あるパターンが出現した時の詰みの確率の推定値 p は、そのパターンが含まれる訓練局面数 n、そのうち詰みである局面数 k について、

k

P=

(1) として、掻尤推定できる。しかし、実際には 2.2 に示した額出パターンの最小サポートはそれほど大きくなb、。このため本研究ではベイズ学習の手法を用いて確率の推定値を次のように求める。まず、パターンの確率を確率変数 6 として、パターンの確率を求める問題をとの S の期待値を求める問題と考える ζ とにする。ことで、雷撤局面について、対象とするパターンを含む局面が n 局面あり、そのうちの k 局面が詰みであったとする.ζ のような事象を A とすると、ベイズの定患に基づき、事象 A が起とったという条件のもとでの 8 の事後確率密度除、伊伊μ問

P

(

8 I

A

)

= 斗コ己ココ

P(A)

=P(8)P(AIの

か(8)P(AI仰

(

2 )

で与えられる。ことで、事象 A をベルヌーイ試行と考えることができるので、その糠率は 2 項分布により次のように与えられる。

P

(

A

I

8 )

=

nC/c8"'(1 ー θ)"-/C

(

3 )

(5)

-51-これを代入して、 P(OIA)

= ρ P(O)nCA:t'i"(l

-

o)n-k J~' P(θ)nCk9k(1 -9)n-

/

r

.

d

9 P

(9)9k

(

1 _

9)"-k 1 -_ '.-:'-.. ''-

-,

(4)

f

n

'

P(9)9"(I-9)•

"d9

カ呼専られる。ここで、事前確率密度 P(めをどうするかという問題がある。ととでは、対象とするパターンに関して、事前知識カt全くないものと考えて、事前確率密度はー織分布とする。これは、 P(9)

=

1 (

5 )

とするということである。これにより、が (1

-0

)

"

-

1

P

(

9 I

A

)

=

-::i 10' 併(1

-

9)n-"

d

9

一 eが("+1恥)ト-1(ο1- o)<n叫+勾「イ(k糾+1吟)-→仙 a 副、

一 10

19 似仰(伶

k

叫叩-の(叫

2 勾}ト-仰)-→ld9

となる@この確半分布は、ベータ分布であり、期待値は次のようになる。 11:

+1

E(9) = 一一 (η π+2 この結果から、あるパターンが出現した時の詰みの磁率の推定値 p は、そのパターンが含まれる訓練局面数 n、そのうち諮みである局面数 k について、 1 1:

+1

p=E(9)= 一一一 (8) π+2 で表される。この結果を見ればわかるとおり、.計算コストは非常に小さいものである。この値について、結みまたは不訪の確率が高いもの、すなわち磁率の大きいもの・小さいものを選訳すれば、有用な情報として用いることができると考えられる. -カイ 2 乗テストカイ 2 乗テストとは、クラスのラペJレとパターンの聞に相関があるか否かを調べる統計的な尺度である.カイ 2 乗テストは、独立性の指様となるカイ 2 乗統計量を用いる。 n 局面の訓練局面において、クラス 4、パターン t について、 k.o.Ji: r クラス 4 に属するもののうち t を含まない局面数」、 kil を「クラス t に属するもののうち t を含む局面数J とし、クラスを 0，1 とすると、カイ 2 乗統計量 χ2 は、次のように表される。

x

2

=

_n

₍

_k

_u

_k

_o

_-

_k_l₀_k_o

_I

₎

₂

x

(

k

u

+

k叫-1X

(

k

O

l

+

koo)ー 1

x

(

k

u

+

k

(

I1

)

-

1 x

(

k

l

0 +

k

o

)

-

l

(

9 )

カイ 2 乗統計量は、パターン t について観測値から推定した場合の理論値と実際の値のずれを表す。カイ 2 乗統計量が小さいほど独立性が高く、カイ 2 乗統計量が大きいほど強立性が低い。ここで選別したいものはラベルを推定できるものであり、ラベルとの独立性が低いもの、つまりカイ 2 乗統計置が大きいものを選訳すれば、有用な情報として用いることができると考えられる g 本研究ではこのようにして選択したパターンを論理積で表現したものを評価褒素とした。ただし、このようにして選択した評価要素のみでは、全ての局留を網癒することはできないため特徴要素をパターンに残すととで対処した。 3.4 評価要素の重み付けによる得価関数の生成評価要素の重み付けは、その評価要素の数が比較的多いため、学習が容易な単層パーセプトロンを用いて学習を行った。 4. 評価 4.1 実験方法実酸はIntel X回n

3 .

0

6 GHz d

u

a

l

・メモリ 2GB(以

降 X伺In)、 AMDOpteron 840(1.4GHz)x4 ・メモリ

4GB(以降 op回'on) の 2 台のマシン上で行った。実装には C++言語を用いた。評価対象としては、訓練局面 80，000 局面・テスト局面 9，7伺局面を用いた。これらの局面は、将棋倶楽節 24 のレーティング 2，200 以上の棋譜 9， 144 局について

(

1 )

それぞれについて終局までの最後の 10 局面を取り出す.

(

2 )

取り出した局面それぞれについて浅〈探索し、探索中に出てきたノードをランダムに 1 つずつ取り出す. ζ とで抽出を行ったものである。抽出した局面数が得られるであろう局面数よりも少ないのは、読めない棋譜や同じ局而を排除したためである。また、ラベル付けに関しては、 PDS で 5，000，000 ノード探索するうちに詰みであると判定された局面を詰み、ぞれ以外を不詰としてラベル付けした。 4.2 実験結果抽出した頻出飽和パターンの教を図 3 に、 4.1 に示した X回B において抽出にかかった時聞を図 4 に示した。結果として短小サポートが 2%のときに 38， 173， 197 の頻出飽和パターンが得られている。頻出パターンを全て抽出した場合には、 319，528，422 ものパターンが得られており、飽和パターンのみを抽出することで頻出

(6)

同.f#JJ.踊 r t ・. 同皿機IWJ トー今一一一一一一一←一一一ー寸.-ー一一ーーーー一一ー-

M田IWJt-一一一一一一一一一一一一一念ー苓一一一一-i 叩 M田IWJt-一一一一一一一一一一一一一念ー苓一一一一-i

叫醐ト一一一一一一一一一一一一一一一一一一←一--+ー

‘

岨曲トー一一一一一一一ー一一一一一←一一ー一一一 '国トー一~一一一ーーー一一一一一一一一司← 凶ト F 一ー一一戸ーーー一ー一司一一子句会合}ムーーー一一ーョ I !.,- ‘ー」一一一一」一一{ゐー】ー一一---ー--" o.s o.s 0-1 o.a o.s a・， Zぬ車"。ωr-

•

咽.000.000 ト一一一一一一一一一一一一一一一一

T- ト一一一一一一ーで

.，'創羽田トー一一吋ーーーーーー可「一一司-_...-一一ー一一一一一

日「-ーナー

ω00 トー一ー一一一一+ーーーー---一一一一一ー一一-E冊 ; 一一一一←一一一一一一一一一時トー一一一一一←一一一一一一一~一一一----一一 1 L一一一』一一一品一一一ーι一一_... ー---。， 0 同 20 28 .'"サポート骨d 図 s 最小サポートに対する頻出飽和パターンの数図 7 確率の推定値に基づいた選訳 4曲。師縦割~ r t棚脚「勺一一一一一一一一一一一一一 e曲園。: ・一一一一ー一一一一-IIUIIIO ト一一一~・一一一一一一一帥曲ト一一一一一一ー一一一一一一一ーーー一一」一、 '国トー一一ー一一一ー一ーー一一ー一一一一ー一一一一ーーー司 100 斜陽磁調 81淘 ...凶カイ&陸圃 “ S 醸償国笛 '0.000r ，.0伺卜一一一一一一吋一一一一一一一一一一一一ー一一一

言 '00

f

一一---1一一一一一一

o s 咽 15 却 28 忌串守ポートE唱図 4 忌小サポートに対する頻出飽和パターン輸出にかかった時間が頻出でないことがわかる。固からわかるとおり 23 の特徴重要素の積で表されるような長いパターンを得ることができている。この長いパターンの例を図 6 に示した。矢印は効きを、灰色のマスは駒がないことが効きによりわかったマスである. 次にこの量小サポート 2%の頻出飽和パターンについて、評価要素の選択を行った。 3.3 に示したベイズ学習に基づいた確率の推定値、カイ 2 乗テストそれぞれについて選択を行った結果を図 7-8 に示した.確率については、諮みの積率が 0.5 以下の磁率のものは不諮の確率について、ぞれ以外のものは詰みの確率について、それぞれの確率の下隈を超えるものを抽出するようにした.カイ 2 乗テストについては、カイ 2 乗分布表の値を外れたものが多かったため、カイ 2 乗統計量そのものの値について、その値よりも大きいものを選訳するようにした。選択には 4.1 に示したOpter，岨において約 14 時聞かかった. 長後にこのようにして抽附した評価要素を特徴量として、単属パーセプトロンで学習させた.学習係数 0.001 ・学習回数 1 ，000 固として学習させた結果老図 9 ・ 10 に示す。図 9 ・園 10 に示したように最も良いもので 76.62%の正解率が得られた。いずれについても、評価援策が多いものについて正解率が下がっているが、これは学習係数・学習回数を固定して比較しているために過学習が起きていることが考えられる。また、この結果は入手で匁}に示された評価要素を選別園 8 カイ 2 乗テストに基づいた選択岨醐副凪 t ・-. 1個以同値... ・・. ._-自由トーチー~・-唯一一一ーー一一ーー・ーーー

!-f-

剛M皿ト→でーーー-..---一一ー__--.-_ø.ーー一-_.-叫醐闇 H I.IJOO

I

r

•

.一一則 l←一一一一一一一一一ぷ一一し一一一~_________._.______.__~_..--..l o 師陣園調，申-;，骨量a 園 E 頻出飽和パターンの長園 6 録骨、観品飽和パターンの倒パターンの 88%程度を削減できており、飽和パターンの摘出はパターンの削減に大いに員献していることがわかる.この最小サポート 2%の頻出飽和パターンの長さごとの分布を図 5 に示す。鎖出パターンについてもその長さごとの分布老示した.点線は全パターンを摘出した場合の数を示しており、ほとんどのパターン

(7)

-53-••

国ー砲事の推定値に皇毒づいたE平価要業を用いた学習

三一一…一一

t r

u

園 10 カイ 2 索テストに基づいた抑制i要索を用いた学習し、重み付けした評価関数よりも 5%程度惑い。とれは、抽出した特徴援索が学習局面数についてスパースであること、頻出する組み合わせの下憶の設定が大きすぎたことが原因であると考えられる。 5. おわりに本研究では、 3 章で示したように、局面の駒位置と効き関係を表す単純な真偽値の特徴要素を元に諮むか詰まないかの程度を返す評価関数を作成した。具体的には、特徴要素について訓練局面から頻出飽和パターンを抽出し、用意した確率またはカイ 2 乗の指額において有用なものを選択し、それを評価要素とし、単層パーセプトロンで学習することで評価調教を構築した。結果として 4 章で示したように 4，000 万弱の願出飽和パターン、数千から数十万の評価要素が得られ、最も良いもので 76%程度の正解率が得られた。今後の課題としては、 1 つは特徴要素の組み合わせの選択をより洗練させるとと 'b~挙げられる。 ζ れには、選奴の精度を上げることと計算量を減らすことの 2 つの対処が必要である。選択の精度を上げるには、重要な要素の選叙に現在栂械学習で提案されている他の特徴選択手法10) を用いる ζ とが考えらえる。これらの手法には今闘の方法に比べると計算コストがかかるものの、精度の高い選択ができているもの桝註する。また、計算量を減らすにはビーム探索法や遺伝的アルゴリズムなどの近似アルゴリズムを用いるととが考えられる。特徴要素を減らして履小サポートを小さくするな Eの方法もあるが、この対処では特徴要素の数が詰将棋よりも多くなってしまうような問題に応用できず、根本的な解決にはなっていない。また、表現能力を上げるために和や否定を用いるととも考えられるため、このような計算量を減らす手法は必要である。また、もう 1 つの課題として、実際の評価調数として用いるための高速化カ噂げられる。とのためには、 GLEM における pattem カ育有用であると考えられる。 pattern を向動生成する方法は今のととろ提案されていないが、特徴要素のクラスタリングなどを行うととで可能ではないかと考えている。この pattern を用いることで失われる組み合わせも存在するが、特徴要素の組み合わせの計算量を削減できることも考えられる。また、最小サポートをより小さくする ζ とも可能となり、今回見逃した有用な要素を発見できる可能性がある。参考文献

1 )

Agr.aw叫， R.， lmieli叫i， T. 岨.d SW8.I凶， A.N.:

M

i

n

i

n

g

A鎚ociation R'叫.es betw田n

S

e

t

s

o

f

I旬ms

i

n

L釘ge D戯畠加昌也，

P

r

o

c

e

虔

n

g

s

01 幼e

1

9

9 ACM

SIGMOD

Inter混d初nal C，叩ife陀nce

on Management

0

1 Data (Buneman

,

P

.

and

J

a

.

ｭ

jo品， S.(叫.))， WiωM碍ton，

D.C.

,

p

.

2

0

7 -

2

1

6 (

1

9

3 )

.

2 )

Buro

,

M

.

:

LOGIS四LLO. av泌lable a'七 http://www.ω.叫b酎a.回/ mburo/log.h凶.

3 )

Buro

,

M

.

:

Fr

om S

i

m

p

l

e

F1伺品町四旬Sophis

t

i

c

a

t

e

d

E'叫四tion

Fùn

ctioDS

,

Proceed

i

n

g

s

0

1 t

h

e

F

i

r

s

t

I

n

t

e

m

a

t

i

o

n

a

l

C

o

n

f

e

r

e

n

c

e

on

Compω

e

r

s

and Games

(CG・98) (v田 d回 Herik，

H. J

.

回d Iida， H.(他))，

V

o

l

.

1558

,

Ts曲uba， J叩回，

Springer-Verlag

,

p

.

1 26-

1

4

5

(1倒的.

4 )

Buro

,

M

.

:

Im

p

r

o

v

i

n

g

He帥tic Mini・M町 se町'ch

by

S

u

p

e

r

v

i

s

e

d

Lear凶ng，

A

r

t

i

f

i

c

i

a

l

I

n

ｭ

tell:旬開ce，

Vo

l

.

134 ,

N

o

.

1・2， pp.85ー卯 (20但).

S

p

e

c

i

a

l

I

s

ue on

Ga.rn凶， Compu加畠血d

Art

i

ｭ

f

i

c

i

a

l

1凶elli~迎。e.

5 )

ChalI回以前i，

S

.

:

MI伽飢，g

t

h

e

Web:

Disω開r

i

n

g

K

n

o

w

l

e

d

g

e

from

HW加ertezt

Data

,

Morg:岨 I{aufm姐且Pub

(

2

0

2 )

.

6 )

Chellapilla

,

K.回d F1暗~，

D

.

B

.

:

Evolvi時阻 E却ert Check1悶 Playing

P

r

o

g

r

a

.

r

n

Wiぬou色 Us

ingHum岨 E却ertise，

lEEE

7 h

&

n

s

a

c

t

i

o

n

s

on

E叩lutionary Computat初n，

VoL 5

,

N

o

.

4 ,

p

.

4

2

2 -4

2

8

(却01).

ηFawce抗.

T

.

E

.

:

Feat包re

D

i

s

c

o

v

e

r

y

for 丹吋・

l

e

m

S

o

l

'lJi

ng Systems

,

PhD τ'hesis，

D

e

p

a

r

t

ｭ

m佃t ofCompu総r Sci回僧， Uni明翠叫世yofM舗 sachuset旬，Amb館前，

M A

(

1

9

3 )

.

(8)

8 )

Fogel

,

D

.

B.:臨時 Evolutionary

P

r

o

g

r

a

m

ｭ

ming t

o

C

o

n

s

t

r

u

c

t

N

e

u

r

a

l

Networks もhat

a

r

e

c

a

p

a

b

l

e

o

f

pla;戸時 Tic-Tac-Toe，

P

r

o

c

e

d

i

n

g

s

0

1 t

h

e

IEEE In

teTn

a

t

i

o

n

a

l

Confer官nce

on N

e

u

r

a

l

Networks ρCNN-9!J)， S阻Francis∞，

pp.875-8

7

9 (

1

9

3 )

.

9 )

Gr油ne， G. 血d

Zhu

,

J

.

:

EfficientIy 田ing prefix・trees

i

n

mining 仕equent

itemsets

,

l

n

P

r

o

c

e

d

i

n

g

s

of 幼e

IEEE ICDM Workshop

on

F't宅quent

l

t

e

m

s

e

t

Minin9

lmplementatio間 (20凶).

1

0 )

lsabelleGuyon

,

A

.

E

.

:

An

I

n

t

r

o

d

u

c

t

i

o

n

t

o

V.卸会

a

b

l

e

and

FI白色ure

Se

lection

, JMLR 防L !J，

p

.

1

5

7 -

1

8

2

(2∞3).

1

1 )

J.H岨， J.Pei，

Y

.

Y

.

:

Mining F

r

e

q

u

e

n

t

P

a

t

e

r

n

s

w

i

t

h

o

u

t

C

a

n

d

i

d

a

t

e

G佃ぽ副on，

SIGMOD Conｭ

l

e

r

e

n

c

e

~OOO，

p

.

1 -

1

2

(20佃).

1

2 )

rnkr幽， J.

F

:

Ma出ne

L

e

a

r

n

i

n

g

i

n

G間関:

A Survey

,

Machines t

h

a

t

Learη to

P

l

a

y

Games

(Fürnkr岨z， J. 回d

Kubat

,

M.(eds.))

,

Nova S

c

i

ｭ

e

n

c

e

Publishers

,

Huntington

,

NY

, chap色er2，

p

.

1

1 -

5

9 (

2

0

1 )

.

1

3 )

Seliger

,

R

.

:

THE

DISTRlBUτ官D

CHESS

PROJECT.

http://neural-ch闇.ne他国.com/.

1

4 )

T

.

K組dω，K. Y. 岨d

Kawai

,

S

.

:

Autom叫ic F伺，ture Construc色ion 岨d Optimiz鉱ion

f

o

r

G四.eralG創ne

Player

,

Th

e

6 t

h

Game

Pn穆Tam mi時 Workshop，

p

.

2 5-

3

2 (

2

0

1 )

.

1

5 )

T

.

K掴eko，

K.

Y. 岨d

Kawai

,

S

.

:

Au

t

o

ｭ

mated

Id四.tific必ion

o

f

P

a

t

e

r

n

s

i

n

E

v

a

l

u

a

t

i

o

n

F\m

ctions

,

Advanωs

i

n

Computer Games 10

何回 d四 E副k，

H

.

J.

,

lida

, H. 岨d

Heinz

,

E

.

A.(eds.)) ，阻四町 Acad田ic

P

u

b

l

i

s

h

e

r

s

.

p

.

27 9-

2

9

8

(2脳).

1

6 )

T

.

Uno

,

M. Kiyomi

,

H. A

.

:

LCM 咽 3.: Col・

l

a

b

o

r

a

t

i

o

n

o

f

Arra

y

,

Bitmap 血d Prefix 古田 for Frequ，四，t Itemse主拙凶ng， chi岨go，乱 (20田).

1

7 )

Talå油:e

Uno

,

M幽幽hi 阻yomi，

H

.

A

.

:

1一CM

ver

.

2 :

Eflìci.ez泊 F拙ning Alg国也ms

f

o

r

F

r

e

ｭ

qu叫/αωed/M副malIt個節句，

I

n

t

e

m

a

t

i

o

n

a

l

C

o

n

f

e

r

e

n

c

e

on Data Mining

,

F't可制nt Ite悶et

Mining

Implementatio回 ~004

(

2

0

4 )

.

1

8 )

'Ilωauro，

G

.

:

TD-

G

a.mm

on

,

A

Se1ι岡崎ing

Backg

a.mmOD

Pro

gram

,

Achi駒田 Master-Levei

Play

,

p

.

1 9-

23

(

1

9

3 )

.

1

9 )

'Il釧m創出， K.: 賢官曲1es. a;咽1ぬ，le

a

t

h色tp://www.herak1edourn刷出.def.

2

0 )

T:回目伽， Y. 岨d chika戸血a， T.: 勘臨時

ingReIi曲出量y

o

f

R叫鑓包DeciøionLists

u

s

ｭ

包gBa;拘必岨Le舘叫且g，

J

o

u

r

n

a

l

0

1

Na如ral

L

a

n

ｭ

卵句e Pro倒'ft可，

VoL 9

,

N

o

.

3

(2∞2).

i

n

Jap岨箇e.

2

1 )

Utgoff

,

P

.

E. 岨d 岳民up，

D

.

:

C佃紺uctive

F¥m

c

t

i

o

n

Appraximation,

P.ω，ture &加ction，

C

o

n

s

t

r

u

c

t

i

o

n

and S

e

l

e

c

t

i

o

n

:

A Data Mining

P

e

r

s

p

e

c

t

i

v

e

(Liu

, H. 曲d

Motoda

,

H.(eds.))

,

Th

e

K

l

u

w

e

r

I

n

t

e

r

n

a

t

i

o

n

a

l

S

e

r

i

e

s

i

n

Engin鶴子 ing 阻d

Computer Science,

V

o

l

.

453,

Kl

uwer

A叫emic Pub凶ers，

c

h

a

p

t

e

r

1

4 (

1

9

8 )

.

22) 三輸誠，横山大作，近山隆:SVM による将棋の諮みの予測とその応用，第 9 回ゲーム・プログラミングワークショップ，

条件付き確率PIPEによる将棋の評価関数の生成

1

.

駒位置と効き関係に注目した詰み評価関数の自動生成

大

近

Automatic c

o

n

s

t

r

u

c

t

i

o

n

o

f

e

s

t

i

m

a

t

i

o

n

o

f

mates

based on p

o

s

i

t

i

o

n

s

and e

f

f

e

c

t

s

o

f

p

i

e

c

e

s

MAKOTO MIWA.t DAISAKU YOKOYAMAt

and TAKASHI CHIKAYAMAt

i

!

d

2

.

1

GLEM

Toc

2

.

1

.

1

GLEM

L

i

n

e

a

r

E

_近