25 Study on Effectiveness of Monte Calro Tree Search for Single-Player Games

平成

25

年度

修士学位論文

一人ゲームの解探索におけるモンテカルロ

木探索手法の有効性に関する研究

Study on Effectiveness of Monte Calro Tree Search

for Single-Player Games

1165065

那須 律政

指導教員

松崎 公紀

2014

年

2

月

28

日

高知工科大学大学院 工学研究科 基盤工学専攻

情報システム工学コース

要 旨

一人ゲームの解探索におけるモンテカルロ

木探索手法の有効性に関する研究

那須 律政

現在，二人ゲームにおいてモンテカルロ木探索が注目されている．モンテカルロ木探索の 特長は，ゲーム固有の評価関数を必要としないことである．この特長によって囲碁のプレイ ヤプログラムの棋力を向上させたことで知られ，以降二人ゲームにおいて活発に研究されて いる．一方でパズルなどの一人ゲームに適用した研究例は非常に少ない．パズルの中には， 探索規模が大きいため全探索ができない問題が存在する．そのような問題を解くためには何 らかの効率のよい探索手法が必要となる．そこで，本研究では探索問題に対するモンテカル ロ木探索手法の有効性の検証を行った．数独の問題生成とナップサック問題について取り上 げ，モンテカルロ木探索の適用を行い，実験によって有効性の検証を行った．比較対象のア ルゴリズムは，遺伝的アルゴリズムとした．結果として，モンテカルロ木探索は探索開始直 後において，ある程度の精度の近似解を得られることと，近似解の精度が一定以上上昇しづ らいことがわかった．またその原因として，最適解を持たないノードに対してプレイアウト が集中していることがわかった． キーワード モンテカルロ木探索, 遺伝的アルゴリズム,数独, ナップザック問題

Abstract

Study on Effectiveness of Monte Calro Tree Search

for Single-Player Games

Norimasa NASU

Currently, Monte-carlo tree search has been actively studied for two-person games. Monte-carlo tree search took much attention after the first application to the igo player. However, there are few studies on monte-carlo tree search applied to one-person games. For some one-player games we cannot perform complete-search due to their very broad search space. An efficient search algorithm is needed to solve those problems with broach search space. In this study, we apply the monte-carlo tree search to one player games and verified the effectiveness. We use two problems for experiments: the knapsack problem and generation of Sudoku problems. The performance of monte-carlo tree search is compared with that of the genetic algorithm. The experiment results show the following facts. Firstly, the monte-carlo tree search gives a rather good solution immediately after the start. Secondly, the accuracy of the solution is hard to rise. Thirdly, the reason is that many playouts are done on a node that does not give an optimal solution.

目次

第1章 はじめに 1 1.1 研究の背景 . . . 1 1.2 関連研究 . . . 2 1.3 本論文の構成 . . . 2 第2章 数独 3 2.1 数独のルール . . . 3 2.2 数独の解探索 . . . 3 2.2.1 手動解法による数独の解探索 . . . 4 2.2.2 SATソルバによる解探索 . . . 5 2.3 数独問題盤面の生成 . . . 6 第3章 ナップサック問題 8 第4章 モンテカルロ法とモンテカルロ木探索 9 4.1 モンテカルロ木探索 . . . 9 4.2 モンテカルロ木探索のアルゴリズム . . . 10 4.3 数独問題盤面生成への適用 . . . 11 4.4 ナップサック問題への適用 . . . 13 第5章 遺伝的アルゴリズム 15 5.1 遺伝的アルゴリズムの処理の流れ . . . 15 5.1.1 個体の選択方法 . . . 17 5.1.2 交叉 . . . 18

目次 5.1.4 エリート戦略 . . . 20 5.2 数独問題盤面生成への適用 . . . 20 5.2.1 数独盤面の染色体表現 . . . 20 5.2.2 関数の設定. . . 20 5.3 ナップサック問題への適用 . . . 22 5.3.1 ナップサックの染色体表現 . . . 22 5.3.2 関数の設定. . . 22 第6章 実験 24 6.1 数独の問題生成 . . . 24 6.2 ナップサック問題の解探索 . . . 26 6.3 検証. . . 30 第7章 まとめ 31 謝辞 32 参考文献 33

図目次

2.1 数独における問題の一例 . . . 4 2.2 図2.1の問題の解盤面 . . . 4 2.3 SATを用いた解探索アルゴリズム . . . 5 2.4 数独の問題盤面生成 . . . 6 4.1 モンテカルロ木探索アルゴリズム . . . 10 4.2 数独問題生成に対するプレイアウトのアルゴリズム . . . 12 4.3 ナップサック問題に対するプレイアウトのアルゴリズム . . . 13 5.1 遺伝的アルゴリズム . . . 16 5.2 次世代個体の生成 . . . 16 5.3 トーナメント選択の例 . . . 18 5.4 一点交叉の例 . . . 18 5.5 3点交叉の例 . . . 19 5.6 一様交叉の例 . . . 19 5.7 盤面のマスへの番号付け . . . 21 5.8 親盤面の例1 . . . 21 5.9 親盤面の例2 . . . 21 5.10 子盤面の例1 . . . 22 5.11 子盤面の例2 . . . 22 5.12 子盤面の例3 . . . 22 6.1 n = 17の問題生成における評価値の推移 . . . 25 6.2 n = 18の問題生成における評価値の推移 . . . 26

図目次

6.4 n = 250の問題に対する評価値の推移 . . . 28 6.5 n = 300の問題に対する評価値の推移 . . . 29

表目次

3.1 品物リストの一例 . . . 8

6.1 数独盤面の生成実験結果 . . . 25

6.2 得られた近似解 . . . 27

第

1

章

はじめに

1.1

研究の背景

コンピュータサイエンスの一分野として，ゲーム研究が行なわれている．例えば，対戦 ゲームを対象とした研究としては，機械学習や探索アルゴリズムによる強いプレイヤプログ ラムの作成がある．これらの分野は人工知能に関連する分野であり，ゲームを対象とした研 究から人工知能に対する新たな知見を得ることを目的として研究されている．また，パズル の研究については，探索やパターン解析といったアルゴリズムの評価の為に研究されること もある．ゲームを対象として，既存の手法を改良したり新たな手法を開発し，コンピュータ サイエンスの広い分野に貢献することがゲーム研究の意義である． 特に近年，二人ゲームに関する研究が活発に行なわれている．その中でモンテカルロ木探 索[2]が注目されている．モンテカルロ木探索は，乱数によるシミュレーションを行い近似 解を求めるモンテカルロ法とゲーム木探索を組み合わせた手法である．モンテカルロ木探索 の特長は，評価関数が不要であることと，探索空間が膨大なゲームでも適用可能であるこ とである．この特長により，コンピュータ囲碁において勝率を劇的に向上させた[14]．その 後，対戦ゲームにおいて注目され，囲碁や将棋といった二人ゲームを対象として多くの研究 が行われている[11] [14]． 一方で，パズルを含む一人ゲームへのモンテカルロ木探索手法の適用例は非常に少ない． 一人ゲームをコンピュータに解かせる場合，多くの場合において何らかの探索を必要とす る．適用する探索アルゴリズムの性能は，得られる解の善し悪しに影響する．モンテカルロ 木探索を一人ゲームに適用しその性質を調査することで，一般的な探索問題に対してモンテ

1.2 関連研究 カルロ木探索がどのような性質を持つのかを調査する． 本研究の目的は，パズルを含む一人ゲームにおけるモンテカルロ木探索の有効性を検証す ることである．問題として，数独の問題生成とナップサック問題を取り上げる．それぞれの 問題に対してモンテカルロ木探索による解探索プログラムを作成し，近似解の精度と実行時 間から性能を調査した．アルゴリズムの比較対象として，最適化問題の近似解探索によく用 いられる手法である遺伝的アルゴリズムによる解探索プログラムを用いる．

1.2

関連研究

モンテカルロ木探索は，二人対戦ゲームにおいて多くの研究が行なわれている．将棋に対 するモンテカルロ木探索の適用を目的として，従来用いられていた学習方策とモンテカルロ 木探索を組み合わせる方法が関らによって提案されている[11]．また，プレイヤに隠された 情報があるゲーム (不完全情報ゲーム) を対象として，隠された情報の推定がプレイアウト に与える影響を調査した研究が報告されている[13]． 一人ゲームに対するモンテカルロ木探索の適用例としては，Samegameに適用する研究 がSchaddらやTakesらによって行なわれている[7] [8]．

1.3

本論文の構成

本論文の構成は以下のとおりである．第2章，第3章では，本研究で対象とする数独と ナップサック問題についてそれぞれ説明する．第4章では，モンテカルロ木探索の概要につ いて説明し，数独の問題生成とナップサック問題に対してどのように適用したかを示す．同 じく第5章では，遺伝的アルゴリズムの概要と，それぞれの問題についてどのように適用し たかを示す．第6章では，第4章と第5章で述べた方法を数独の問題生成とナップサック問 題に適用し実験を行う．また，実験結果について考察を行う．最後に，第7章で本研究のま とめを行う．

第

2

章

数独

2.1

数独のルール

数独[10]とは，ペンシルパズルの一つで，マス目で区切られた正方形の盤面に数字を書き 込んでいくパズルである．問題として，図2.1のような盤面が与えられる．盤面は3×3ご とに太線で区切られており，この区切られた領域をブロックという．また，盤面にはあらか じめ数字が配置されており，この数字をヒントという． 与えられた盤面に対して，以下の規則にしたがって1∼9の数字を入れていく． 規則1 1つのマスには1つの数字が入る 規則2 すべての横列と縦列において，1つの列には1∼9の数字が1つずつ入る 規則3 すべてのブロックにおいて，1つのブロックには1∼9の数字が1つずつ入る この規則にしたがって，すべてのマスに数字を入れることができれば完成となる．図 2.1の 問題の解は，図2.2となる．図2.2のように，すべてのマスに数字がはいった盤面を解盤面 という．

2.2

数独の解探索

数独を人間が解く場合，解法と呼ばれる手法を用いて解く．解法は，第2.1節で示した数 独のルールから導かれる規則性を用いて，各マスに入る候補を絞り込んでいく．空マスにお いて，数独のルールもしくはその他の解法により取り得ないと判定された数を除いた，解の 候補となる数字を候補数字と呼ぶ．

2.2 数独の解探索 図2.1 数独における問題の一例 図2.2 図2.1の問題の解盤面 本節では，人間が数独を解くときに用いる解法について説明する．また，コンピュータに 数独を解かせる方法の1つであるSATソルバを用いた方法についても説明する．

2.2.1

手動解法による数独の解探索

本論文中にて用いる解法を以下に示す． Cell-Unique あるマス x について，x が持つ候補数字が aの1つだけであるとする．こ のとき，x の数字を a に確定する． Line-Unique／Block-Unique ある横列，縦列またはブロックについて，数字 a が入 り得るマスが x の1つだけであるとする．このとき，x の数字を a に確定する． k-Naked ある横列，縦列，ブロックについて，k 個のマス x1, x2, . . . , xk が持つ候補数 字が k 個の数 a1, a2, . . . , ak からなる集合の部分集合のみからなるとする．このとき， その横列，縦列，ブロックの x1, x2, . . . , xk 以外のマスの候補数字から，a1, a2, . . . , ak を消す． k-Hidden ある横列，縦列，ブロックについて，k 個の数 a1, a2, . . . , ak のいずれかを 候補数字として持つマスが x1, x2, . . . , xk の k マスのみであるとする．このとき， x1, x2, . . . , xk の候補数字から，a1, a2, . . . , ak 以外の候補数字を消す．

2.2 数独の解探索 solve(board) { cnf <- CNFOfBaseRule cnf <- append(cnf, toCNF(board)) if (satisfiable(cnf)) { answer = findAnswer(cnf) cnf2 <- append(cnf, negate(answer)) if (satisfiable(cnf2)) { return multiple } else { return unique } } else { return noAnswer } } 図2.3 SATを用いた解探索アルゴリズム 本研究では，上に示した手動解法を実行するソルバプログラムを作成し，数独の問題盤面 の評価に用いた．

2.2.2

SAT

ソルバによる解探索

SATソルバは，連言標準形（CNF）で与えられた命題論理式（以下CNF式と呼ぶ）の充 足可能性を判定するためのプログラムである [5]．第2.1章で示した数独のルールと盤面に 配置されたヒントをCNF式として表すことにより，SATソルバで解くことができる． まず，数独のルールを表現するCNF式に，盤面に配置されたヒントを表現するCNF式 を追加する．数独のルールを表現するCNF式には，文献[5]でextended encodingと呼ば れる手法を利用した．これは，各マス，横列，縦列，ブロックに数字が高々1つ，また，少 なくとも1つあることを表現したものである．次に作成したCNF式をSATソルバに渡す． CNF式が充足可能でないときには解なし（no_answer）である．CNF式が充足可能である ときには，1通りの変数割り当てを求め，それを否定したものをCNF式に追加する．この ようにして作った新しいCNF式をSATソルバに渡し，それが充足可能であるときには複 数解（multiple），充足不可能であるときには唯一解（unique）とする．

2.3 数独問題盤面の生成

makeBoard() {

loop until boardのヒント数が$n$個 { board’ <- setHint(board) if(solve(board)が複数解){ board <- board’ } else if(solve(board)が唯一解){ return board; } } } 図2.4 数独の問題盤面生成

2.3

数独問題盤面の生成

数独の問題を作成する場合，以下のような制約がある． 制約1 1つの問題に対して解はただ1つでなければならない 制約2 仮置きによる試行錯誤を必須としてはいけない 仮置きによる試行錯誤とは，“あるマスにある数字が入ると仮定して解き進める”ことを指 す．仮置きを用いれば，盤面の全探索が可能になるため理論上すべての問題を解くことがで きる．しかし，“盤面から規則性を見つけ出し解を求める”というパズル性が失われること や，探索空間が膨大であるため，人間には解くことが困難であるという問題がある．そのた め，人間が解く数独の問題を生成する場合，仮置きが必須な問題は避けられることが多い． 本研究では制約1のみを遵守し，制約2は考えないこととする． 白紙の盤面を初期盤面，ヒントを1つ配置することを1手とし，唯一解に定まる問題盤面 の生成が最終目的とすれば数独の問題生成は探索パズルに置き換えることができる． 数独の問題は，図2.4の方法で逐次的に生成することができる． setHintでは，いずれか1つの空きマスを選択し，選択した空きマスにランダムな数字 を1つ配置する．solve関数は，第 2.2.2節で定義したSATソルバを用いる．solve関数 によって現在の盤面の解の数を探索し，

2.3 数独問題盤面の生成 複数解（multiple）だった場合，さらにヒントを置く．解なし（no_answer）だった場 合，配置したヒントを削除する．唯一解（unique）だった場合，その時点での盤面を問題盤 面として得ることができる． 問題盤面を生成するだけであれば，以上の方法で容易に問題盤面を生成することが可能で ある．一方で，探索空間が膨大かつ唯一解に定まる盤面が少ないこと，盤面から抽出できる 特徴がなく評価関数の設計が困難であることから，ヒント数の少ない問題を生成することは 容易ではない．本研究では，モンテカルロ木探索と遺伝的アルゴリズムを数独の問題盤面生 成に適用して，ヒント数の少ない問題盤面を生成させることを試みる．

第

3

章

ナップサック問題

ナップサック問題[3]は，組み合わせ最適化問題に分類される問題の1つである．本研究 で用いるナップサック問題は，複数0-1ナップサック問題と呼ばれる問題である[6]．m個 のナップサックとn個の品物のリストが与えられる．ナップサックiは容量Ciを持ち，品 物j は重さ wj と価値vj を持つ．品物は分割することができず，1つの品物は高々1つの ナップサックに入れることができる．重量の合計がナップサックの容量を超えないように， かつ価値の合計が最大になる品物の組み合わせを探索するという問題である． 例題を次に示す．ナップサック数m = 2 個のナップサックがあり，それぞれの容量は C0 = 10, C1 = 15である．品物は表3で与えられるものとする．すべてのナップサックに ついて，ナップサックkiの重量の総和がCi 以下になり価値の総和が最大になる組み合わせ は，k0 ={0, 1, 4}，k1 ={2, 3, 5, 6}となり，価値は82となる． 表3.1 品物リストの一例 番号j 0 1 2 3 4 5 6 7 8 9 重量w 5 4 3 4 5 2 3 1 4 3

第

4

章

モンテカルロ法とモンテカルロ木

探索

4.1

モンテカルロ木探索

モンテカルロ木探索[2]は，乱数を用いたシミュレーションを行うことで近似解を得る手 法であるモンテカルロ法とゲーム木探索を組み合わせた手法である．モンテカルロ木探索の 特長は，評価関数が不要であることと，探索空間が膨大なゲームでも適用可能であることで ある．モンテカルロ木探索では，ある一つの盤面からゲームの終局まで，乱数による仮想的 なプレイを行う．これをプレイアウトという． モンテカルロ木探索の重要な点は2点ある．1つは，プレイアウトを行う候補手を選択す る際に，すべての合法手に対して均等にプレイアウトを行うのではなく，それまでのプレイ アウトで得られた評価値をもとに，有望である可能性の高い手に多くのプレイアウトを割り 当てる点である．もう1つは，ある候補手のプレイアウト回数がある閾値を超えた時に，そ の手を展開してもう1手探索し，プレイアウトの開始点を1つ深くする点である．この2点 によって，評価の高い手に対する探索を深くし，評価の低い手に対する探索を少なくするこ とができる． 本章のこれ以降では，モンテカルロ木探索の概要と，各問題に対してどのように適用した かを説明する．

4.2 モンテカルロ木探索のアルゴリズム MCT(root) { loop until 終了条件 { leaf <- select_downwards(root) leaf.n <- leaf.n + 1 if (expand_cond(leaf)) { leaf <- expand(leaf).first_child } board = playout(leaf.board) update_upwards(leaf, getvalue(board)) } return select_best_child(root) } 図4.1 モンテカルロ木探索アルゴリズム

4.2

モンテカルロ木探索のアルゴリズム

図4.1 にモンテカルロ木探索の擬似コードを示す．モンテカルロ木探索では，終了条件 （探索時間もしくは探索回数）に到達するまでプレイアウトを繰り返し，最終的に評価値の 最も良い候補手を選択する．繰り返しされる処理は，大きく次の4つからなる． 1. それまでのプレイアウト回数と評価値をもとに，根ノードから葉ノードまで降りる （select_downwards）． 2. 葉ノードのプレイアウト回数を増やし，閾値を超えた（expand_cond）際にはそのノー ドを展開する（expand）． 3. 選択された葉ノードから，乱数によるプレイアウトを行う（playout）． 4. プレイアウトの結果の盤面から評価値を計算し（evaluate），葉ノードから根ノードま で値を更新する（update_upwards）． 図 4.1において関数として記述した，プレイアウトの対象とする子ノードの選択方法 select_downwards，ノード展開の閾値 expand_cond と展開方法 expand，プレイアウ ト方法 playout，終局盤面の評価値 evaluate およびノードの持つ評価値の更新方法 update_upwards をそれぞれ定めることによりモンテカルロ木探索を行うことができる．

4.3 数独問題盤面生成への適用

以下では，コンピュータ囲碁などで広く用いられている UCT アルゴリズム[4] で用い られている子ノードの選択方法について述べる．UCT では，子ノードの選択に UCB1 （Upper Confidence Bound）アルゴリズム [1] を用いる．これは，多腕バンディット問題 （Multi-armed bandit problem）[12]において，計算量が小さく高い報酬が得られる戦略で ある．Xj は j 番目の候補の評価値の期待値，nj は j 番目の候補のプレイアウト回数，n は全体のプレイアウト回数，c は問題ごとに定める定数とする． ucbj = Xj + c √ 2 log n nj (4.1)

UCB1アルゴリズムでは，式4.1によって各候補のUCB1値を計算し，UCB1値が最大と なる候補を選択する．このUCB1アルゴリズムを用いることで，有望な候補に多くのプレ イアウトを行うことと，評価値が偶然低い場合に対する救済という2つの性質によりプレイ アウト対象が決定される．

モンテカルロ木探索を1人ゲームの解探索に適用するためには，図4.1における子ノード の選択方法 select_downwards，子ノードの展開条件 expand_condと展開方法 expand， プレイアウト方法playoutと結果の評価方法 evaluate，ノードが持つ評価値の更新方法 update_upwardsを，問題に合わせて定める必要がある．本研究では，子ノードの選択方法 についてはUCB1を用いることとした．

4.3

数独問題盤面生成への適用

モンテカルロ木探索を数独の問題生成に適用するために，第4.2節で示した各関数を定 める． ■ノード展開条件と展開方法 葉ノードの展開の基準として，プレイアウトがある一定回数 行われた際に葉ノードを展開することとした．

4.3 数独問題盤面生成への適用

playout(board) {

loop until board.hint == $n$ { hint <- selectHint(board) board’ <- addHint(board, hint) if (solve(board’) == noAnswer) {

board <- deleteCand(board, hint) } else { board <- board’ } } return board } 図4.2 数独問題生成に対するプレイアウトのアルゴリズム ■プレイアウト方法 生成するヒント数がnのときのプレイアウトの概略を図4.3に示す． プレイアウトにおける1ステップの計算は，配置するヒントを選択（selectHint）し，そ のヒントを配置した盤面が解を持つかどうかの判定（solve）をした後，解がない場合には そのヒントを候補数字から消す（deleteCand），もしくは，解が存在する場合にはそのヒン トを盤面に加える（addHint）のいずれかを行う．この1ステップの計算を，問題盤面に配 置されたヒント数がnになるまで繰り返す．関数solve がすべての盤面について，解なし， 唯一解，複数解のうちのどれであるかを正確に判定できるとき，この playout 関数は解を 持つ盤面を受け取り唯一解を持つ盤面を返す．関数 solve については第2.2.2節で示した SATソルバを用いる．プレイアウトが終了すると，ヒント数nの問題盤面が1つ得られる． ■終局盤面の評価方法 プレイアウトによって得られた盤面に対して，なんらかの評価値を 与える必要がある．第2.2.1節で示した手動解法を用いて，問題を解探索が可能なところま で解かせる操作を行う．どの解法も適用できなくなったところで解探索を打ち切り，残って いる空きマスの候補数字の総数をカウントし，候補数字が少ないほど高評価とした．盤面サ イズがn×n，残っている候補数字の数がcとしたとき，盤面評価値vは次の式で得られる． v = n3− c (4.2)

4.4 ナップサック問題への適用 playout(items, knapsack) { loop (infinity) { items’ <- getItemList(items) if (items’ == empty) { break loop } item <- selectItem(items’) knapsack_id <- selectKnapsack(knapsack)

knapsack <- addItem(knapsack, knapsack_id, item) } return bag.value } 図4.3 ナップサック問題に対するプレイアウトのアルゴリズム ■ノードの持つ値の更新方法 ノードの値は，プレイアウトごとに更新する．その際，プレ イアウト対象となる葉ノードの選択するまでにたどったノードを逆順にたどり，その経路上 のノードの値を更新する．

4.4

ナップサック問題への適用

モンテカルロ木探索をナップサック問題に適用するために，4.2節で示した各関数を定 める． ■子ノードの選択方法 子ノードの選択方法は，UCB1を用いた． ■ノード展開条件と展開方法 数独の場合と同じく，プレイアウトがある一定回数行われた 際に葉ノードを展開することとした．この回数は，木全体で同じ回数とした． ■プレイアウト方法・盤面の評価 まず，どのナップサックにも入っておらず，かついず れかのナップサックの空き容量を超えない重さをもつ品物をリストアップ（getItemList) し，リストアップされた中から品物を1つ選択する(selectItem)．次に，どのナップサッ クに入れるかを選択 (selectKnapsack) し，選択した品物を入れる (addItem) ．これを， ナップサックに入る品物が無くなるまで繰り返す．品物が無くなったら，ナップサックに入 れた品物の価値の総和を評価値として出力する．

4.4 ナップサック問題への適用

■ノードの持つ値の更新方法 数独と同じく，プレイアウトごとに対象となる葉ノードの選 択するまでにたどったノードを逆順にたどり，その経路上のノードの値を更新する．

第

5

章

遺伝的アルゴリズム

遺伝的アルゴリズム[9]は，生物の集団が遺伝によって進化する過程を模倣したアルゴリ ズムである．ある問題に対する解候補を個体が持つ染色体に見立て，遺伝子の複製と交叉， 突然変異を繰り返すことにより，最適解またはそれに近い近似解を得る．

5.1

遺伝的アルゴリズムの処理の流れ

遺伝的アルゴリズムでは，1つの解候補を1つの個体として表現する．各個体がもつ，問 題の解にあたるデータ列を染色体といい，染色体がもつデータを遺伝子という．染色体の各 遺伝子が取りうる値は，解の表現方法によって定められる．これを対立遺伝子という．ま た，各個体が持つ染色体がどれだけ最適解に近いかを表現する評価値を持つ．これを適応度 という．遺伝的アルゴリズムを与えられた問題の解探索に適用するためには，問題の解を染 色体で表現する必要がある． 図5.1 に遺伝的アルゴリズムの擬似コードを示す．1世代ごとの操作は，大きく次の3つ からなる． 1. 現世代の各個体について，個体がもつ解の適応度を計算する（evaluate）． 2. 現世代の個体集団を親として，評価値と乱数を用いて次世代の個体集団を生成する （generate_next）． 3. 次世代の個体集団を，現世代の個体集団として置き換える． これらの操作を，世代上限まで繰り返し，最終的に得られた個体集団のうち，最も適応度が

5.1 遺伝的アルゴリズムの処理の流れ Genetic_Algorithm(first) { now <- first loop until 最終世代に到達 { evaluate(now) next = generate_next(now) now <- next } return max(now) } 図5.1 遺伝的アルゴリズム generate_next(population) { next <- null

loop until nextの個体数が一定数になる

parent1, parent2 <- select_parent(popuration) if(交叉確率){

child1, child2 <- crossover(parent1, parent2) if(突然変異確率){

child1, child2 <- mutation(child1, child2) } next.add(child1, child2) } else { next.add(parent1, parent2) } } return next } 図5.2 次世代個体の生成 高かった個体を解として出力する． 次世代の個体生成について，擬似コードを図5.2 に示す．まず，現世代の個体集団から各 個体がもつ適応度をもとに，乱数を用いて親となる個体を2つ選択する（select_parent）． 次に，選択した 2 つの親について，一定の確率で交叉を行い，2 つの子個体を生成する （crossover）．交叉を行わない場合には，選択した 2つの親個体がそのまま2つの子個体 となる．交叉が行われた場合，生成された2つの子個体について，一定の確率で突然変異を 行う．突然変異では，子個体がもつ遺伝子をランダムに変化させる（mutation）．最後に， 2つの子個体を次世代の個体集合に加える．交叉判定と突然変異判定については，確率を設 定し乱数によって判定する．親の選択方法については，完全にランダムに選択するのではな

5.1 遺伝的アルゴリズムの処理の流れ 度の高い個体，またはそれから生成された個体が次世代に残りやすくなる．世代交代を繰り 返すことで，平均的に適応度の高い個体集団が作られていく．最終世代まで繰り返し，その 集団の中で最も適応度が高い個体が持つ解を近似解として得ることができる． 遺伝的アルゴリズムをある問題の解探索に適用するためには，図 5.1 における適応度 の計算 evaluate，図 5.2における親個体の選択方法 select_parent，子個体の交叉方法 crossover，突然変異の方法 mutationを問題に合わせて定める必要がある．

5.1.1

個体の選択方法

次世代の個体集団の生成をおこなうために，現世代の個体から親を選択する必要がある． 親となる個体の選択は，乱数を用いて行う．このとき，すべての個体から等確率に選択を行 うのではなく，適応度に応じて選択確率を決定し，適応度の高い個体が，適応度の低い個体 よりも選択されやすくする．これにより，次世代に適応度の高い個体，またその特徴を受け 継いだ個体が生成される確率が上がり，次世代の個体集団の平均適応度が高くなりやすく なる． 一般的に用いられる個体選択方法には次のようなものがある[9] ■ルーレット選択 ルーレット選択は，各個体の適応度の比に応じて選択確率を決定する方 法である．個体iの適応度がfiとしたとき，N 個の個体集団から個体iが選ばれる確率pi は，次の式で与えられる． pi = fi ∑N j=1fj (5.1) ∑N j=1fj は個体集合に含まれるすべての個体の評価値の総和を表し，fiは，任意の個体の評 価値を表す． ■トーナメント選択 トーナメント選択は，ある一定数の個体をランダムに抽選し，その中 で最も適応度の高い個体を選択する方法である．図5.3に具体例をあげる．まず，ランダム に一定数の個体を抽選する．このとき抽選する個体数をトーナメントサイズという．図 5.3 の例では，トーナメントサイズは3となる．そして，抽選した個体から，もっとも適応度の

5.1 遺伝的アルゴリズムの処理の流れ 図5.3 トーナメント選択の例 図5.4 一点交叉の例 高い個体が選択される．

5.1.2

交叉

交叉は，生物が生殖によって次世代に遺伝子を受け継ぐ過程を，操作としてモデル化した ものである．交叉の際には，2つの親個体が選択され，その2つの親個体がもつ遺伝子の特 徴を受け継いだ新たな子個体が生成される．交叉の方法については，与えられた問題に応じ て設計する．一般的に用いられる交叉方法には次のようなものがある[9]． ■一点交叉 一点交叉は，遺伝子をランダムに決めた一点で区切り，そこで遺伝子を交叉さ せる方法である．染色体の長さがmのとき，遺伝子に0からm− 1の番号が割り振られて いるとする．0からm− 1の範囲で乱数によって交叉点を決定し，交叉点以降の遺伝子を親 同士で交換する． 具体例を図5.4 に示す．図5.4は，染色体の遺伝子数が7，交叉点3の例である． ■n点交叉 n点交叉は，遺伝子の区切りをランダムにn箇所決め，区切り点ごとに交互に

5.1 遺伝的アルゴリズムの処理の流れ 図5.5 3点交叉の例 図5.6 一様交叉の例 いるとする．0からm− 1の範囲で乱数によって交叉点を決定する．最初の交叉点以降の遺 伝子は親同士で交換し，次の交叉点以降は親のものをそのまま受け継ぐ．これを遺伝子の終 わりまで繰り返す． 3点交叉の具体例を図5.5 に示す．図5.5の例は，染色体の遺伝子数が7，交叉点が1, 2, 4の例である． ■一様交叉 一様交叉は，乱数を用いて遺伝子1つごとに交叉するかしないかを決める方法 である．具体例を図5.6 に示す．図5.6の例は，染色体の遺伝子数7の例である．

5.1.3

突然変異

突然変異は，交叉によって生成された子がもつ染色体の一部を，親個体と関係のない値に 変更する操作である．遺伝的アルゴリズムの問題点として，解が局所的な最適解で安定し， 世代交代による適応度の上昇が止まることが挙げられる．突然変異は，一定の確率で子とな る個体の染色体をランダムに変化させ，その個体を次世代に組み込むことで局所的最適解か らの脱出を図るねらいがある．

5.2 数独問題盤面生成への適用

5.1.4

エリート戦略

遺伝的アルゴリズムでは，現世代から次世代に引き継ぐ個体を乱数によって決定する．そ のため，適応度の高い個体が現世代にある場合でも，それがそのままの形で次世代に残らな い可能性がある．それを防ぐために，交叉による次世代の個体生成を行う前に，現世代の個 体集合から適応度が高い順に，いくつかを次世代の個体集合にそのまま複製する方法が用い られることがある．これをエリート戦略という．

5.2

数独問題盤面生成への適用

5.2.1

数独盤面の染色体表現

遺伝的アルゴリズムを数独の問題生成に適用するためには，数独の盤面を個体として扱え るようにする必要があるそこで，本研究で対象とする9×9数独の盤面について，染色体の 形による表現に変換する． 9×9数独の盤面は，図2.1のように縦9マス，横9マスの81マスで与えられる．盤面 のマスに図5.7のように番号を振り，マス番号をインデックス値とした長さ81のリストに 置き換える．ヒントが配置されているマスはその数字を遺伝子とし，空きマスについては 0 を遺伝子とする．したがって，9×9数独における対立遺伝子は0∼9 の10個の数字のう ちいずれか1つとなる．図2.1を染色体で表現すると，[000000000 000030804 700009000 000006020 014000300 000000000 200000096 000000070 008140000] となる．

5.2.2

関数の設定

遺伝的アルゴリズムを数独の問題に適用するために，5.1節で示した各関数を定める． ■適応度の計算 第2.2.1節で示した手動解法を用いて，問題を解探索が可能なところまで 解かせる操作を行う．どの解法も適用できなくなったところで解探索を打ち切り，残ってい

5.2 数独問題盤面生成への適用 図5.7 盤面のマスへの番号付け 図5.8 親盤面の例1 図5.9 親盤面の例2 ■親個体の選択方法 親個体の選択方法については，上で述べた適応度をもとに，ルーレッ ト選択を用いた． ■交叉 数独の盤面を交叉によって生成するにあたり，親盤面のヒント数と子盤面のヒント 数を同じ数に統一する必要がある．5.1.2で述べた一般的な交叉の方法では，染色体内の遺 伝子の内容は考慮していない．一般的な交叉方法によって生成した子盤面のヒント数は，親 盤面のヒント数と異なる場合がある． 以下に2点交叉の例を示す．親盤面が図5.8と図5.9であるとする．図5.8と5.9の盤面 はともにヒント数17である．染色体の交叉点を23, 41とし，その間の遺伝子を入れ替える と，子盤面として図5.10と図5.11が得られる．しかし，図5.10のヒント数が18，図5.11 のヒント数が16となり，親盤面とヒント数が異なる．そのため，一般的な手法ではなく数 独の盤面に合わせた交叉方法を定義する必要がある． 本研究では，盤面のヒント数をnとしたときの交叉方法を，次のように定めた．親盤面の ヒント数をnとする．まず，交叉点cを，乱数によって0以上 n以下の値に決定する．親

5.3 ナップサック問題への適用 図5.10 子盤面の例1 図5.11 子盤面の例2 図5.12 子盤面の例3 盤面1の盤面について，先頭からc個のヒントを子盤面にコピーする．親盤面2の盤面につ いて，末尾からn− c個のヒントを子盤面にコピーする．図5.8と図5.9を親盤面としたと き，交叉点が7のときの子盤面は図5.12となる． ■突然変異 突然変異は，すでに配置されているヒントから1つをランダムに選択し盤面か ら消し，盤面の空きマスをランダムに1つ選択して，ランダムな数字を1つ配置するとした．

5.3

ナップサック問題への適用

5.3.1

ナップサックの染色体表現

遺伝的アルゴリズムをナップサック問題に適用するためには，ナップサックの状態を個体 として扱えるようにする必要がある．ナップサックを染色体表現に変換する． 本研究で扱う問題は，複数0-1ナップサック問題であるため，1つの品物はいずれか1つ のナップサックに入る，またはいずれのナップサックにも入っていない状態をとる．m個の ナップサックについて，ナップサック番号を0からm− 1 とし，ナップサックに入ってい ない場合を-1とすると，品物のリストと同じ長さのリストでナップサックを表現できる． 第3章で示した例題において価値が最大となる組み合わせを染色体に変換すると，[0 0 1 1 0 1 1 −1 −1 −1]となる．

5.3.2

関数の設定

5.3 ナップサック問題への適用 ■適応度の計算 個体の適応度は，すべてのナップサックに入れた品物の価値の総和とし た．ただし，いずれかのナップサックについて品物の重量の総和がナップサックの要領を超 えた場合，適応度を0とした． ■親個体の選択方法 親個体の選択方法にはルーレット選択を用いた． ■交叉 交叉方法には，5.1.2節で述べた交叉方法のうち，一様交叉を用いた．各遺伝子の 交叉率は50%とした． ■突然変異 突然変異は，いずれか1つの品物をランダムに選択し，いずれかのナップサッ クにランダムに入れなおす，もしくはナップサックから出し未取得の状態にするとした．

第

6

章

実験

第4章，第5章で述べた方法を用いて，数独の問題生成およびナップサック問題に適用 し，実験を行った．実験は次の環境上で行った．

OS： ubuntu 12.04

CPU： Intel Core i5-2500 @ 3.30GHz

メモリ： 8GB Java： 1.6.0 26-b03 また，実験結果の図表中では，モンテカルロ木探索をMCT，遺伝的アルゴリズムをGA と表記する．

6.1

数独の問題生成

数独の問題生成について，モンテカルロ木探索と遺伝的アルゴリズムを適用し，ヒント数 の少ない盤面の生成実験を行った．生成する盤面のサイズは9×9とし，ヒント数n = 17, 18, 19, 20の唯一解をもつ盤面の生成を試みた． モンテカルロ木探索のパラメータは，次のように設定した． C 値： 1.0 展開閾値： 30

6.1 数独の問題生成 表6.1 数独盤面の生成実験結果 ヒント数n MCT GA 17 554 631 18 550 664 19 599 729 20 675 729 図6.1 n = 17の問題生成における評価値の推移 世代サイズ： 30 交叉率： 100% 突然変異率： 30% エリート数： 1 選択方法： ルーレット選択 実験結果を表6.1に示す．また，n = 17，18における評価値の推移を図 6.1，図6.2に 示す． モンテカルロ木探索による問題生成プログラムでは，少数ヒント盤面の生成はできなかっ

6.2 ナップサック問題の解探索 図6.2 n = 18の問題生成における評価値の推移 た．一方で，遺伝的アルゴリズムによる問題生成プログラムではヒント数 n = 19, 20の問 題生成に成功した．また，評価値の推移を見ると，n = 17のときモンテカルロ木探索の評 価値は35678ミリ秒時点で554となり，それ以降上昇していない．n = 18の場合において も，33411ミリ秒の時点で550となりそれ以降上昇していない．一方，遺伝的アルゴリズム はヒント数17または18のどちらの場合においても断続的に評価値が上昇した．

6.2

ナップサック問題の解探索

ナップサック問題について，モンテカルロ木探索と遺伝的アルゴリズムを適用し解探索を 行った．品物数をnとしたときのナップサック問題形式は次の通りである． ナップサック数m ： 3 ナップサック容量C： C0 = 4n, C1 = 5n, C2 = 6n 品物j の重量 ： ₁₀n∼n 品物j の価値 ： n₅∼2n

6.2 ナップサック問題の解探索 表6.2 得られた近似解 品物数n MCT GA 最適解 50 2635(-14) 2649(0) 2649 100 6316(-17) 6323(-10) 6333 150 12972(-131) 13029(-74) 13103 200 16748(-749) 17328(-169) 17497 250 22853(-905) 23511(-247) 23758 300 28149(-1585) 28575(-1159) 29734 C 値 ： 1.0 展開閾値： 100 また遺伝的アルゴリズムのパラメータは，次のように設定した． 世代サイズ： 30 交叉率： 50% 突然変異率： 30% エリート数： 1 選択方法： ルーレット選択 以上の条件で，品物数nが50, 100, 150, 200, 250, 300の場合について，それぞれ解探索 を行った．終了条件は探索開始から600秒(=10分)経過とした．モンテカルロ木探索によ る近似解は，終了までに行われたプレイアウト結果のうち，評価値が最も高かったものとし た．遺伝的アルゴリズムによる近似解は，終了時の個体集団のなかで最も適応度が高かった ものとした． 各nに対する実験結果を表6.2に示す．括弧内の数字は，得られた近似解と最適解の差 である．また，nが200, 250, 300の時の評価値の推移について，図6.3，図6.4，図6.5に 示す．

6.2 ナップサック問題の解探索 図6.3 n = 200の問題に対する評価値の推移 表6.2から解るとおり，モンテカルロ木探索によって得られた近似解は，遺伝的アルゴリ ズムによって得られたものよりも低かった． 評価値の推移をみると，モンテカルロ木探索のプレイアウトによる探索では早い段階で近 似解を発見していることがわかる．モンテカルロ木探索が表6.2に示した近似解を得た時間

6.2 ナップサック問題の解探索 図6.5 n = 300の問題に対する評価値の推移 表6.3 MCTで得られた近似解と同時点でのGAの近似解 品物数n 実行時間(ミリ秒) MCTによる近似解 GAによる近似解(MCTとの差) 50 729 2635 2608(-27) 100 2406 6316 6065(-251) 150 11419 12972 12471(-501) 200 17059 16748 16576(-172) 250 30359 22853 21353(-1500) 300 55757 28149 26325(-1824) と，その時点での遺伝的アルゴリズムによる近似解について表6.2に示す．すべてのnにお いて，モンテカルロ木探索が近似解を得た段階では遺伝的アルゴリズムによる近似解よりも 高い評価値を得た．しかし，それ以降実験終了までプレイアウトによる近似解の更新が無い ため，最終的に遺伝的アルゴリズムが高い評価値を得た．

6.3 検証

6.3

検証

実験結果から，モンテカルロ木探索による解探索では，探索序盤においてある程度高い評 価値の解を得たことと，その後の探索で近似解の値が更新されていないことがわかった．原 因の調査のために，nが200，250，300の場合における表6.2の時点でのモンテカルロ木か ら，プレイアウト回数の多い葉ノードを調べた．その結果，少数のノードに対して大半のプ レイアウトが集中していることがわかった．また，プレイアウトが集中していたノードから 全探索を行ったところ，最適解が存在していないことがわかった．プレイアウトするノード の選択方法として用いているUCB1においては，プレイアウト回数の少ないノードに対し ては，期待値が低くてもプレイアウトを行うことがあるが，プレイアウト回数が増加しても 期待値が低い場合，そのノードからのプレイアウトが行なわれなくなる．期待値が高いが最 適解が存在しないノードに対して，プレイアウトが集中していることから，局所的最適解に 陥っていることが解った．遺伝的アルゴリズムでは，突然変異によって局所的最適解からの 脱出を行う仕組みが存在する．単純なモンテカルロ木探索では一度展開したノードは変化し ない．そのため UCB1を用いたノード選択では，一度期待値が高いが最適解が存在しない ノードが展開され，プレイアウトが集中し始めると脱出が難しいという問題があることがわ かった．

第

7

章

まとめ

本研究では，モンテカルロ木探索が探索問題においてどの程度有効であるかを検証するこ とを目的として，数独の問題盤面生成とナップサック問題を対象として，モンテカルロ木探 索によって探索を行うプログラムを実装した．また，比較対象として遺伝的アルゴリズムを とりあげ，同じく数独の問題盤面生成とナップサック問題に対して解探索を行なうプログラ ムを実装し，2つのプログラムについて比較実験を行った．実験の結果から，探索サイズが 大きい探索問題に対して遺伝的アルゴリズムと比較して短時間である程度の近似解を得るこ とができたが，それ以上にプレイアウトを行っても近似解の精度が上がらないことがわかっ た．その原因として，期待値が高いが最適解が見つからないノードに対してプレイアウトが 集中しており，局所的最適解に陥っていることがわかった． 改良点としては，プレイアウトを行うノード選択の方法が挙げられる．ノード選択方法に ついては，現状ではUCB1を用いているが，期待値が高いが最適解が存在しないノードが 存在する場合にそのノードにプレイアウトが集中する問題がある．この問題を解決すること で，局所的最適解からの脱出を図る．局所的最適解に陥る問題を解決し，モンテカルロ木探 索手法によって最適解を得ることが今後の課題である．

謝辞

本研究の遂行ならびに本研究に関して多大なるご助力をいただきました高知工科大学情報 学群松崎公紀准教授に，心からお礼を申し上げます．また，本論文の副査をお引き受けいた だいた坂本明雄教授，吉田真一准教授に，心からお礼を申し上げます．最後に，4年間を共 に過ごした松崎研究室修士2年の皆様，そして6年間という長い大学生活を支えてくれた家 族に対して，心からお礼を申し上げます．本当に今までありがとうございました．

参考文献

[1] P. Auer, N. Cesa-Bianchi, and P. Fischer: Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, Vol. 47, No. 2–3, pp. 235–256, 2002.

[2] C. Browne, E. Powley, D. Whitehouse, S. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, S. Colton: A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on computional intelligence and AI in games, Vol. 4, No. 1, 2012.

[3] H. Kellerer, U. Pferschy and D. Pisinger, Knapsack Problems, Springer, Berlin, 2004.

[4] L. Kocsis, C. Szepesv´ari: Bandit Based Monte-Carlo Planning, 17th European Conference on Machine Learning (ECML 2006), Lecture Notes in Computer Science 4212, pp. 282-293 (2006).

[5] I. Lynce, J. Ouaknine: Sudoku as a SAT problem. In Proceedings of 9th Interna-tional Symposium on Artificial Intelligence and Mathematics, 2006.

[6] S. Martello, P. Toth: Knapsack problems : algorithms and computer implementa-tions, Wiley, Chichester, pp. 157–182, 1990.

[7] M. P. D. Schadd, M. H. M. Winands, M. J. W. Tak, J. W. H. M. Uiterwijk: Single-player Monte-Carlo tree search for SameGame. Journal Knowledge-Based Systems, Vol. 34, pp. 3–11, Elsevier, 2011.

[8] F. W. Takes and W. A. Kosters: Solving SameGame and its Chessboard Variant. In Proceedings of the 21st Benelux Conference on Artificial Intelligence (BNAIC), pp. 249–256, 2009.

[9] 北野 宏明: 遺伝的アルゴリズム1, 産業図書, 1993.

参考文献

通巻563号, 一般社団法人情報処理学会, 2012.

[11] 関 栄二, 三輪 誠, 鶴岡 慶雅, 近山 隆: シミュレーション・バランシングを用いたモン テカルロ将棋の方策学習, pp. 2533–2543,情報処理学会論文誌, Vol.53, No.11, 2012. [12] 但馬康宏, 小谷善行: k-armed バンデット問題のゲームへの適用における試行回数

について. 情報処理学会研究報告, AL, アルゴリズム研究会報告, Vol. 2008, No. 49, pp.65–70, 2008.

[13] 西野 順二, 西野 哲朗: 大貧民における相手手札推定. 多人数不完全情報ゲームのモンテ カルロ木探索における推定の効果, Vol. 2011-MPS-86, No. 31, pp. 1–4, 2011.

[14] 美添 一樹: モンテカルロ木探索：コンピュータ囲碁に革命を起こした新手法,情報処理, Vol. 49, No. 6, pp. 686–693, 2008.