Microsoft Word - thesis2004_mori.doc

Size: px

Start display at page:

Download "Microsoft Word - thesis2004_mori.doc"

あおしかやぬま
5 years ago
Views:

1 将棋プログラムにおけるプランニングと評価平成 16 年度卒業論文山形大学工学部情報科学科グリムベルゲン研究室学生番号氏名森健太郎

2 概要コンピューターゲームには探索が必要不可欠である. しかし, その探索には水平線問題が付きまとう. そこで, 水平線の向こう側を見越した探索をすべく, 人間の考え方に近いプランニングを探索に適用した. その結果, 将棋のプログラムにおいて序盤の守りである囲いを組むことができた. これにより, 水平線の向こうを見越した探索が可能となった. i

3 目次 1 序論人工知能の歴史ゲームの歴史ゲームプログラミング本研究の目的研究の背景探索ゲーム木局面の評価 Minimax 探索探索の問題点将棋とプランニングプランニング水平線問題解決へのアプローチ研究内容探索とプランニング定跡とプラン矢倉囲い矢倉囲いのプランプランのボーナス値前提条件実験結果と考察ボーナス値の偏り実際に指した手矢倉囲いのプランと指し手船囲いのプランと指し手居飛車穴熊のプランと実際の指し手左美濃のプランと実際の指し手プラン全体の考察まとめと今後の課題参考文献 ii

4 1 序論本研究は人工知能の一分野であるゲームプログラミングについての研究である. では, そもそも人工知能とは一体何なのか. 人工知能の定義は, 広い意味ではコンピュータシステム等に知的な活動をさせることを総称して人工知能であり, もう少し狭い意味で取ると知識や推論等を用いて行う処理となる. 本研究の説明の前に, 人工知能の歴史を振り返って人工知能とはどういうものなのかを説明したいと思う. 1.1 人工知能の歴史 AI の研究はコンピュータの出現とほぼ同時期に開始された.1950 年代初頭の研究者が注目したのはゲームプログラミング, 具体的には西洋での主要なゲームであるチェスプログラムの開発であった年夏, アメリカニューハンプシャー州ダートマス大学で後にダートマス会議と呼ばれる会議があった. この会議で初めて AI という言葉が世に現れた. AI 研究の初期, すなわち 1970 年代までの主要なテーマは, ゲームパズルのプログラミング, プランニング, 定理証明が挙げられる. この頃は人間はある一般的な能力を持っており, これにより人間の知的な行動が引き起こされると考えられていた. そしてコンピュータを知的にするには, 状況に応じて動作する判断能力を与える必要があるとし, この能力は問題に依らない一般的なものであるという意識があった. したがってこの一般的能力こそが知能とされていた. しかし, この時代に対象としたのは比較的単純化された世界における問題であり, 現実の諸問題に適用できるかどうかの見通しは立ってい -1 -

5 なかった年,J.McCarthy と P.J.Hayes が人工知能にとって最大の問題であるフレーム問題を指摘した. これは今からしようとしていることに関係のあることがらだけを選び出すことが, 実は非常に難しいという問題である. 例えばロボットに輪投げをさせようとする. そうすると投げる輪の初速度や投擲角度, 輪の回転数などを考えなければならないが, さらに輪投げをする場所が屋外なら, 風の影響や気温, 湿度までも考慮しなければならないかもしれない. 人工知能は輪投げをする以前に, 様々な条件の内どれが関係のある条件なのかを調べるために無限の計算が必要になって止まってしまうのである. しかもこの問題は, 人間は普通遭遇しない ( 人間は考えなくてよいことは考えない為 ) のだが, 解決できない問題でもある年,E.A.Feigenbaum は講演を行い, 知識工学なる新しい研究分野を生み出した. 注目すべき点は, 知識工学が問題個別の知識の重要性を示したことである.1970 年頃までの AI 研究では, 問題に依存しない一般的能力 ( 知能 ) を追求していたが, 結果的には現実問題に対応できる成果は得られなかった. そこで問題の固有の知識を集め, それを基にした有用なシステム作りを知識工学は強調したのである.E.A.Feigenbaum の提言を機に, エキスパートシステムに代表される知識ベースシステムが AI 研究の大きな柱となってくる. 70 年代後半から知識表現への積極的な取り組みが始められ, 知識の表現, 利用, 獲得など, いわゆる知識情報処理が注目されてきた. さらにこれらの研究成果と相まって, 画像認識, 自然言語処理, 音声認識, エキスパートシステムなどの応用分野でも大きな前進が記された. 80 年代に入ると全世界的に AI 研究が活発化した. この傾向は大学などの研究機関のみならず産業界にも広がり, 社会をも巻き込むブームとなった. -2 -

6 しかし 90 年代半ばに入るとそれまでの AI ブームが下火を迎えた. 期待されたエキスパートシステムは部分的には成功を収めたものの, やはり様々な状況に対する適応性は低く, 結局, 知的システムと言っても, 頭の硬い, 融通の利かない知的さでしかなかった. いま,AI 研究は転換期を迎えている. 現実世界の動的環境に存在するエージェントを想定して, 知能そのものを問い直そうという動きがそれである. このように, 様々な分野で新しい概念やアイデアを取り入れながら AI 研究は今もその活躍の場を広げている [1]. 1.2 ゲームの歴史本研究に関連するゲームプログラミングの歴史について同様に見ていく. ゲームプログラミングの歴史はチェスプログラムの歴史と言っても過言ではない. なぜなら, 西洋ではチェスは人類の英知の象徴とされ, 強いチェスプログラムを開発することは, すなわち知的な振る舞いをするコンピュータの開発と考えられたからである. 機械によるゲームプレイングはプログラム可能なコンピュータが開発されるよりずっと古くから研究されていた.1769 年には W.von Kempelen が Turk というチェスプレイング自動機械を展示した [2]. これは実際には機械によるものではなく, 中に小柄な人間のチェスプレイヤーが隠れてプレイしていたもので, この頃から人々は機械にチェスをさせることを望んでいたことがわかる年に C.Babbage が機械によるゲームプレイング実現の可能性についてのまじめな議論を初めて行った. 最初の動くゲームプレイング機械は 1890 年頃スペインの技術者 L.T.Quevedo によって作られた. KRK というチェスの終盤の局面 ( 一方がキングとルークだけ, もう一方はキングだけ ) に特化した機 -3 -

7 械で, 機械がキングとルークの側, 人間がキングだけの側として戦う. この機械のプレイは正確で, いかなる局面からスタートしても ( 機械が先手を持てば ) 人間のキングを詰むことができた. しかしこのチェスの終盤の適切な戦略は十分に単純で, 人間にも記憶してアルゴリズム的に実行できるものだった年に最初のプログラム可能なコンピュータが開発されて以来, コンピュータチェスの様々なアイデアが考えられ, 研究された.C.E.Shannon が 1950 年に, 現代のゲームプレイングプログラムの基本となる原理を示した論文を発表し, 翌年の 1951 年,A.Turing がチェスの一局を完全にプレイする始めてのプログラムを書いた. しかしこのプログラムはコンピュータ上では一度も動かされずに終わった. 一局を通してはプレイできなかったものの,D.G.Prinz は詰めチェスを解くプログラムを書いて実際にコンピュータ上で走らせた. 初めて一局を通してプレイできるチェスプログラムが書かれたのは,1958 年, A.Bernstein によってだった. H.Simon は 1958 年に 10 年以内にコンピュータのプログラムが世界チャンピオンに勝つと予測したが,1967 年の MacHack6 は人間とまともにプレイできる程度の実力だった. 結局, チェスプログラムが世界チャンピオンに勝ったのは,1997 年,IBM 社の Deep Blue だった [3]. こうして C.E.Shannon がゲームプログラミングの基本原理を発表してから約半世紀後, 人間よりも強いコンピュータチェスプログラム開発は区切りがついたと言えよう. 今後はさらにチェスよりも選択肢が多く, 複雑とされる将棋や囲碁といった新たなゲームに研究の場を移している. また, チェス以外のゲームでは, バックギャモンにおいて G.Tesauro によって作られた TD-GAMMON が 1998 年に当時の世界チャンピオン M.Davis と対戦し, 僅差で敗れはしたが, 世界でもトップクラスの実力を認められている. -4 -

8 この TD-GAMMON は新たな機械学習法を備えており, ゲームプログラミングにおいてのみならず機械学習の分野においても成功例として挙げられる. このように, 人工知能のゲームプログラミング以外の分野の技術を用いて結果として成功を収めるといった例がある. 1.3 ゲームプログラミング強いゲームプログラムの実現は, 上記の様に人工知能の誕生以前から盛んに研究され続けている. それは, ゲームプログラミングの特徴として, ルールが明確である ( フレーム問題が起きない ), 勝ち負けがはっきりつくなど, 研究の題材として扱いやすい点が挙げられる. これらは他の人工知能の研究分野には見られない特徴である. よって,TD-GAMMON における機械学習のように, 他分野で研究された技術を試験的に実装するのに適している. ここで将棋というゲームについて説明したいと思う. 将棋は二人零和有限確定完全情報ゲームと呼ばれるゲームである. 零和とは二人の得点の合計が 0 になる, つまり相手にとっての損がそのまま自分にとっての得になるという特徴を示す. 有限とは, いつかは必ず終わることを示し, 確定とは偶然の要素に左右されないことを示す [4]. 完全情報は相手に自分の手を隠さないことを示す. これに分類されるゲームの特徴は, 理論上は完全な先読みが可能であり, 双方のプレーヤーが最善手を打てば, 必ず先手必勝か後手必勝か引き分けかが決まるという点である. 実際には完全な先読みを人間が行う事は困難であるため, ゲームとして成立する. そこでゲームプログラミングではこの種類のゲームを解く手段として探索という手法を用いる. 探索とは何か問題を解くに当たって, 有効な解析的な解法 -5 -

9 を用いることのできない, あるいは用いないときに, 実際に試行錯誤することによって解を得ようとする行動のことである. 具体的にはある局面から可能な全ての手を考え, その手を指した局面からまた一手というように, 全ての可能な手と局面を考えることを言う. この手法では, 将棋と同じ種類のゲームである三目並べならまだしも, チェスや将棋などの終局までの手数が多いゲームでは, 先読みする手数が増えれば予想される局面の数が指数関数的に増えていくため, 初期局面から終局まで読みきることは事実上不可能である. そこで探索は深さ, または時間によって打ち切られる. 前者は何手先まで読んだら ( 終局まで読みきっていなくても ) そこで終了し, 後者は決められた時間を経過したらそこで終了する方法である. しかしこれは終局まで読みきっていないため, あいまいさが生じる. このあいまいさの為に, 勝利という目標にとって合理的でない手を打つことになる. では人間のプロの棋士はどうであろうか. 探索の深さで言えばコンピュータの方が短い時間で深く読むことができる. 実際に, 終局まで読む詰め将棋ではプロ棋士でも読みきれないような問題も解くことができる. しかしプロ棋士は順を追って先読みするのではなく, 数手もしくは数十手先の局面を想定し, その局面に近づくように手を指していく. これは人工知能におけるプランニングという手法に良く似ている. 1.4 本研究の目的プランニングとは与えた目標を達成するために必要な行動の系列を生成するものであり, 上記のように将棋のプロ棋士の考え方に近い手法であると考えられる. 本研究の目的は, これを用いて探索によって生じるあいまいさを抑える -6 -

10 ことである. -7 -

11 2 研究の背景 1 章ではゲームプログラミングの抱える問題点と本研究の目的を述べたが,2 章では問題となる探索や評価の方法, そしてその解決策として考えられ, 本研究の目的でもあるプランニングについて説明する. 2.1 探索探索とは, 何か問題を解くにあたって, 有効な解析的な解法を用いることができない場合, 試行を繰り返すことで解を得る行動のことを言う. まず解くべき問題を状態と状態変化に分ける. 将棋ならば, 盤面の駒の配置と指し手の持ち駒が状態であり, 交互に駒を動かすことが状態変化に当たる. 最初に与えられる状態を初期状態といい, 目的とする状態は最終状態と呼ばれる. 初期状態から最終状態に至る, 状態及び状態変化の並びが解となるゲーム木一般的に, 探索を行う場合, 局面や駒の動きを表現する為にゲーム木を用いる. ゲーム木とは, 現在の局面から派生する局面の展開を木の形で表したものである. ゲーム木において, 一つ一つの展開される局面をノード ( 節点 ) と呼び, そこから派生する駒の動きを枝と呼ぶ. ゲーム木の頂点のノードを根と呼ぶ. あるノードから派生したノードを子と呼び, 元のノードを親と呼ぶ. それ以上派生していないノード, つまり子を持たないノードを葉と呼ぶ. 終局となるノードでは, 図 2.1 の様に勝ち, 負け, 引き分けを決めることができる. -8 -

12 引分け引分け引分け負け負け勝ち勝ち勝ち勝ち根葉葉葉葉葉葉葉葉葉終局図 2.1: ゲーム木の例このゲーム木を用いて探索を行う場合, 木構造を全て表すことができれば全ての局面を展開できたことになり, ゲームの勝ち負けがはっきりとわかる. しかし実際にはごく単純なゲームを除いてはノードの数や, 探索にかかる時間も膨大になる為, 不可能である. その為, 実際のゲームでは探索に制限時間を設け, 制限時間内で探索できる最大の深さまで探索した後, 局面の形勢を判断する評価関数を用いて最大の深さのノードを評価する方法が用いられる局面の評価ここで, ゲームプログラミングにおいて探索と並び重要とされる評価関数について説明する. 評価関数とは, ある局面の有利さを数値として表すものである. なぜこの評価関数が必要不可欠かと言えば, 図 2.1 のように終局までゲ -9 -

13 ーム木が展開でき, 勝敗が明確になる場合は探索によって解が得られる. しかし実際には, 与えられた時間内に初期局面から終局まで読みきることは ( 三目並べのような簡単なゲームを除いて ) 不可能であるため, 途中で打ち切る必要がある. ここで, その局面が自分にとってどのくらい有利か, どれだけ勝利に近いかを判断する為に評価関数が必要になるのである. 例えば将棋では, 駒それぞれの価値や, 駒の位置, 王将の危険度などを判断し, それを数値化することでコンピュータはその局面が自分側にとって有利かどうかを判断する Minimax 探索 Minimax 法というのは, 自分側は自分の利益が最大になるように行動し, 相手側は自分側の利益が最小になるように行動する, という仮定の下で探索を行う手法である. この場合, 相手は完璧なプレイヤーであると仮定している. このような仮定の下で自分の手を選択すれば, もし相手がこちらの利益を最小にするような手を打ってこなかった場合, つまりこちらの読みが外れた場合, 予想よりも得をすることになる. Minimax 法の 3 手探索の例を図 2.2 に示す

14 7 A 7 2 B C D E F G H I J K L M N O P 図 2.2:Minimax 法の 3 手探索の例 Minimax 法の手順を書くと次のようになる. 1 葉 ( 一番下のノード ) の評価値を評価関数によって求める. 2 子の評価値が全て定まっているようなノードにおいて自分の番であれば子の中から最大のものを選び, ノードの評価値とする. 相手の番であれば子の中から最小のものを選び, ノードの評価値とする. 3 根のスコアが求まるまで2のステップを繰り返す. 図 2.2 で探索する順を説明する. まず, 初期局面であるノード A からノード B,C を展開する図

15 A B C 図 2.3:B,C までの展開同様にノード B からノード D,E を, ノード D からノード H,I,J を展開する図 2.4. A B C D E H I J 図 2.4:H,I,J までの展開この探索は 3 手探索の為, ノード H,I,J は葉となる. そこでここで評価関数を用いて葉の評価を出す図

16 A B C D E H I J 図 2.5: 葉の評価ノード D は自分の手番なのでノード H,I,J の内, 最も高い評価値を選ぶので, ノード D の評価値は 7 となる図 2.6. A B C 7 D E H I J 図 2.6: ノード D の評価値の決定

17 ノード E でも同様にすると図 2.7 のようになる. A B C 7 9 D E H I J K L 図 2.7: ノード E の評価値の決定ノード B は相手番なので評価値は最小のものを選ぶ. ここではノード D の 7 を選ぶ図 2.8. A 7 B C 7 9 D E H I J K L 図 2.8: ノード B の評価値の決定

18 ノード C から展開されるノードでも同様にすると図 2.9 の様になる. A 7 B 2 C D E F G H I J K L M N O P 図 2.9: ノード C の評価値の決定最後にノード A に高い方 ( このときはノード B) の評価値を選び,3 手探索終了となる図自分の番 7 A 相手の番 7 2 B C D E F G 自分の番 H I J K L M N O P 図 2.10: 3 手探索終了

19 2.2 探索の問題点様々な探索法や探索の効率を上げる方法は存在するが, そのどれもがやはり開始から終局まで読みきることはできない. そこで探索を途中で打ち切る必要があり, 以下の問題が生じる. 例えば n 手先まで探索したとする. するとコンピュータには n 手先までの展開が全てわかっていることになる. しかしこれは逆に言えば n+1 手より先は全くわかっていないということになる図これは重大な問題である.n 手先では有利に見えても, 実はその先に落し穴が待ちうけていた, などということにもなりうる. 逆に, 不利なようで実は有利な手を見落としてしまうということも起こりうる. 自分の番 7 A 相手の番 7 2 B C D E F G??? 図 2.11: 探索の問題例えば将棋では, 自分の歩で相手の銀を取れる局面で探索を打ち切った場合, 駒の価値を重要視してその手を選ぶかもしれない. しかしその先を探索すれば, 逆に自分の飛車を相手の歩で取られる局面があるかもしれないのだ. 探索を打ち切った時点では有利と思われた手が, その少し先で不利に転じる可能性があ

20 る. これをゲーム木の末端を水平線に例えて水平線問題と言う. この問題に対し, 対応策として静止探索がある. これは駒の取り合いや強制手筋 ( 相手がそれに対応せざるを得ない手 ) が存在する局面では探索を続け, 駒の取り合いや強制手筋が存在しない静かな局面, つまり駒の損得による評価があまり変化しない局面になるまで深く探索を行うものである. しかしこの方法では水平線問題を根本的に解決したとは言えない. 確かに探索を行い n 手先まで読み, さらに n+1 手先の相手の反撃の一手まで読めるだろう. だがさらにそこから数手先の反撃に対する守りや, 終局までの様子は依然わからないままなのである. そこで, 水平線の向こう側を見越した道標が必要と考えられる. 2.3 将棋とプランニング将棋のプロ棋士は頭の中で一手一手順を追って手を進めるよりも, おおよその駒の配置を思い浮かべ, そこまでの手順を辿って考える. これはプランニングの手続きによく似ているプランニングプランニングは探索とは異なり, 初期状態, ゴール状態, 可能な行為を与えることで, ゴール状態までの行為の列 ( プラン ) を生成する. 探索は闇雲に試行錯誤型であるのに対し, プランニングは目標を持って手を進めるのである水平線問題解決へのアプローチ探索には必ず水平線問題が発生する. これに対し, 水平線の向こうに存在する目標局面をゴール状態としてプランニングに与え, 探索と着手に方向性を持

21 たせる. 将棋に例えれば, 将棋には王将の周りの囲い方, さらにそれらを有効に崩す戦法など, 様々な定跡が存在する. 定跡は先人の経験と研究による, 現時点で最善と思われる手順の指し手である. ここで矢倉囲いという囲いを組みたいとする図矢倉囲いは先手後手合わせて最短でも 25 手必要になる. 将棋は 1 局面に対し可能な着手は平均 80 手あるとされる [5]. ということは,25 手探索ではノード調べる必要がある. 仮にチェスの DeepBlue の様に秒間 2 億ノード探索できる将棋マシンがあったとして,25 手探索をさせた場合, 日かかる. これではゲームとして成り立たない. そこでプランニングにより矢倉囲いを与え, そこまでの指し手を生成させる. この指し手を探索に組み合わせることで, 探索としては矢倉囲いが完成した局面まで深く探索はできないが, 探索と指し手には矢倉囲いへの方向性を持たすことができる. 次章で実際の方法について説明する. 図 2.12: 矢倉囲い

22 3 研究内容 2 章では探索の問題点とその解決策を提案したが,3 章では解決案としてのプランニングを探索にどのように関係させるか, また具体的にどのようなプランを実行させるか例を挙げて説明する. 3.1 探索とプランニング 2 章でも説明した通り, 図 3.1 の探索ではコンピュータはノード B への手を指す. 7 A 7 2 B C 水平線 D E F G 9 X 図 3.1: 水平線問題しかし, ノード B より低い評価値のノード C が, 未探索だが評価値が高いノード X に到達するとわかっていれば, ノード C への手を指す方が将来的に有利になる. この探索にプランニングを用いた様子が図 3.2 である

23 7 A +α 7 2 B C D E F G 9 X 図 3.2: プランニングによる評価値へのボーナスノード X を目標状態とすると, 自分側はノード C への手を指さなければならない. 図 3.2 ではαの値が 6 以上ならノード C への手を指す図 3.3. この様に, プランニングでノード C への手をプランとして生成し, ノード C 以下のノード全ての評価値にボーナス値 6 を与える. 8 A B C D E F G 15 X 図 3.3: ボーナスによる評価値の変更

24 以上の様に, 生成されたプランにある手が探索の中に存在する時, そのノード以下の評価値をボーナス値によって底上げしてやることで, 探索の限界である水平線の向こうを見越した着手が可能となる. 3.2 定跡とプラン将棋には定跡がある. それは現時点で最善手と考えられるものであると 2 章で述べた. そこで, その定跡からある囲いまでの手順をリスト化して, プランニングによって生成されるプランとして使用することが望ましいと考える. しかし, 定跡は相手も定跡通り指す上では役に立つが, 自分か相手どちらかが定跡から外れれば, そこからは探索による読み合いの勝負になる為, あくまで目的は定跡通りに手を進めることではなく, 囲いが完成する局面に到達することと考える. 以下に例として矢倉囲いを説明する矢倉囲い矢倉囲い自体について説明する図 3.4. 図 3.4: 矢倉囲い相手の状況によって, 一番端の歩が上がっていたり, 角が移動していたりす

25 るが, 図 3.4 のような駒組が矢倉囲いである. この囲いは 7 八の金を守っている駒が王だけなので, 横からの攻撃にはそれほど強くないが, 上部からの攻撃には強いという特徴がある矢倉囲いのプラン矢倉囲いのプランは具体的には以下のようになる. 7 六歩 6 六歩 6 八銀 7 八金 5 八金 7 七銀 6 七金右 6 九王 5 六歩 7 九角 6 八角 7 九王 8 八王状況によって順序は変わるが, どういった動きになるか, 局面と並べて考える. 図 3.5 初期局面図では囲いに関係しない駒は省く. 図 3.5: 初期局面図八金まで 17 六歩 26 六歩 36 八銀 47 八金 55 八金図 3.6:5 八金まで

26 図九角まで 1 7 七銀 2 6 九玉 3 5 六歩 4 7 九角図 3.7:7 九角まで図八角まで 1 6 七金 2 6 八角図 3.8:6 八角まで図八玉まで 1 7 九玉 2 8 八玉図 3.9:8 八角まで 3.3 プランのボーナス値上で説明したそれぞれの手について, ボーナス値を定める. このボーナス値は, 1 囲いを組む 2 手数を損しない 3 王を危険にさらさない

27 4 飛車などの大駒を取られてしまう場合はプランを後回しにするの 4 つの条件を満たす値が望ましいと考えられる. 1は最低条件であるが, 例外もある. 相手が急戦をしかけたときや, 相手の攻め方と設定した囲いとの相性によっては無理に囲わない方がよい場合もある. 2 について, 図 3.10 では 7 九角図 3.10: 手損の例の前に 7 九玉を指した為に 2 手損になる. 3について, 同じく矢倉囲いを目指した場合だが, 図 3.11 のように囲いの途中で玉の守りが薄くなる場面が出図 3.11: 手順の失敗例ても芳しくない. 4について, 図 3.12 ではあと 3 手で矢倉囲いが完成するが, その前に飛車が取られてしまう. こういった局面では, プランよりも先に相手の駒を取る必要がある. 図 3.12: 駒損の例つまり, 囲いに行ける状況ならプランニングによって囲いを目指し, 駒の取り合いのような急な展開が予想されるときはプランよりそちらを優先するボーナス値を設定する

28 3.4 前提条件前節でプランのボーナス値の条件を挙げたが, 図 3.10 や図 3.11 のような状態で, ボーナス値のみで手順を細かく指定することは難しい. そこで, プラン中のある手を指す前に必ず指していなければならない手を指定し, その手を指して初めて指せる, という条件を設ける. これを前提条件と呼ぶことにする. 4 章でプランのボーナス値と実際にプログラムが指した手を検証する

29 4 実験結果と考察 3 章で説明したように, 定跡を参考にしながら囲いまでのプラン作成を目的として研究を進めてきたが,3 章で述べた矢倉囲いだけではなく, 他にも船囲い, 左美濃, 居飛車穴熊の 4 つの居飛車の囲いを作成した. ここで居飛車の囲いに限定した理由として, 相居飛車戦の定跡は多く, 相振り飛車戦の定跡は比較的少ないことから, 参考とする定跡が多い方が研究を進める上で都合がいいと考えたことを挙げる. 4.1 ボーナス値の偏りプラン中の手それぞれにボーナス値を与えるわけだが, そのボーナス値には偏りがある. 主に手順が先の手は値が高く, 手順が後になるほど値が低くなる. これは値に偏りを与えたプランと, 値を全く均等に与えたプランを比較した時, 偏りを与えたプランはその値が大きい手から順に指したためである表 4.1. 値に偏りのあるプラン値が均等のプランプランの手順指した手ボーナス値指した手ボーナス値 1 7 六歩 7 六歩六歩八金 5 八金八金八玉 6 八玉六歩八玉 7 八玉八玉六歩 5 六歩八玉六歩 9 六歩六歩 200 表 4.1: ボーナス値の偏りによる手順の違い ( プランは船囲い ) 表のプランは船囲いのプランである. ボーナスの総和はどちらも同じである

30 船囲いは手数が少なく, 初手での探索で読みきることが可能である. 値に偏りがあるプランと均等のプランどちらもプランの最後まで探索することが可能で, 比較対象として適しているためここで例として挙げる. なお, このプランにはどちらも 6 八玉の前に 5 八金を指すという前提条件を用いている. 表を見ると, 値が均等であるプランの指し手はプラン通りの順では指していないが, 偏りのあるプランの指し手は実際のプラン通り指している. これから, ボーナス値の大きい手から優先的に指していくことがわかった. 以上のことから, プランの手順は手のボーナス値の大きい順囲い到達の失敗, または手損が発生する場合, 前提条件を用いるとしてプランを作成した

31 4.2 実際に指した手プランのボーナス値, および前提条件について述べたが, 以下に4つの囲いとそのボーナス値, 前提条件を結果として記載する. さらに実際に指した手について1~4の条件を満たすことを検証する. 1 囲いを組む 2 手数を損しない 3 王を危険にさらさない 4 飛車などの大駒を取られてしまう場合はプランを後回しにする矢倉囲いのプランと指し手図 4.1: 矢倉囲い矢倉囲いの特徴は,3 章でも述べたが 7 八の金を守っている駒が王だけなので, 横からの攻撃にはそれほど強くないが, 上部からの攻撃には強いという特徴がある. 表 4.2 にプランの手とボーナス値, そして実際の指した手を示す

32 プランの手順前提条件ボーナス値実際の手順六歩六歩六歩八金八銀八銀八金七銀八金六歩七銀六歩九玉八金六歩九玉七金右 6 九玉七金九角 5 六歩 90 4 八銀八角 7 九角 80 7 九角九玉 6 八角 70 6 八角八玉 7 九玉 70 7 九玉八玉 13 表 4.2: 矢倉囲いのプランと実際に指した手プランの手順と実際に指した手順の誤差は 1~3 手であった. これは, プランによるボーナス値は指した局面以下に与えられ, 手順が変わってもボーナス値の総和は変わらないためと考えられる. プランのボーナス値を設定する上での条件 1は囲いを組んだことからクリアしている.2については前提条件によってクリアしている.3の条件についても,6 七金を指す前に 6 九玉を指すという前提条件でクリアしている.4 については, 実験で使用したプログラムの駒の価値がそれぞれ歩は 100 点, 香車と桂馬が 300 点で, それ以外の駒は 450 点以上と設定されているため, プランのボーナス値と比べても駒損以上のボーナスは与えないと考えられる

33 4.2.2 船囲いのプランと指し手図 4.2: 船囲い船囲いの特徴は, 玉の上部からは弱いが, 手数がかからず, 横からは強いことが挙げられる. さらにこの船囲いから矢倉囲い, 左美濃, 穴熊に発展することもできる. 以下にプランの手とボーナス値, そして実際の指した手を示す表 4.3. プランの手順前提条件ボーナス値実際の手順六歩六歩八金右八金八玉 5 八金右八玉八玉八玉六歩六歩六歩六歩 6 表 4.3: 船囲いのプランと実際に指した手表を見ると, プランと実際の指した手順は一致している. よって条件 1~4 も満たしている

34 4.2.3 居飛車穴熊のプランと実際の指し手図 4.3: 居飛車穴熊居飛車穴熊の特徴は, 必要な手数が多くなるが, 玉が自陣の端に閉じこもり相手の攻め駒から遠くなることで, 守りが堅くなることである. 以下にプランの手とボーナス値, そして実際の指した手を示す表 4.4. プランの手順前提条件ボーナス値実際の手順六歩六歩六歩八金八金右八玉八玉八玉八玉七角七角 6 八玉六歩八玉八玉八香 8 八玉八香九玉九玉八銀 9 九玉八銀九金八金八金 9 九玉八金八金九金 11 表 4.4: 居飛車穴熊のプランと実際に指した手表を見ると,6 六歩が遅れた点と最後の金の順序が入れ替わった点を除けばほぼプラン通りの手順の指し手だった. また,6,8,10 手目のボーナス値はその

35 直前の手より高いが, 前提条件により探索に渡さないようにしている. これにより 1~4 の条件を満たした左美濃のプランと実際の指し手図 4.4: 左美濃囲い左美濃の特徴は玉の上部が船囲いより相手陣に近く薄いが, 反面横や下部からの攻めには船囲い以上に強い点が挙げられる. 以下にプランの手とボーナス値, そして実際の指した手を示す表 4.5. プランの手順前提条件ボーナス値実際の手順八金八玉八玉六歩八玉八玉六歩八金七玉六歩八銀 8 七玉七玉六歩 8 七玉六歩六歩八銀 6 表 4.5: 左美濃のプランと実際に指した手 ( 対振り飛車 ) 左美濃は居飛車の囲いだが, 相居飛車戦になると全く囲わなかった. 表の手順は相手が振り飛車の時の手順である

36 4.3 プラン全体の考察プラン実行中に指した手は全てプランの中の手だったが, 手順はプラン通りであったのは船囲いだけであった. これはプランによるボーナス値は指した局面以下に与えられ, 手順が変わってもボーナス値の総和は変わらない為と考えられる. また, 穴熊のような比較的手数のかかるプランは手順通りに着手させることが困難である. これはプランの手数が多いほどボーナス値の偏りが相対的に小さくなるためだと考えられる. 手数の多いプランは前半部, 後半部のように段階的に探索に影響させることができればより容易に囲いまでの着手を方向づけることが可能だと考えられる

37 5 まとめと今後の課題今回の実験はプランニングによって囲いを組むことを目標とした. また, この時次の1~4を満たしていることを条件とした. 1 囲いを組む 2 手数を損しない 3 王を危険にさらさない 4 飛車などの大駒を取られてしまう場合はプランを後回しにする結果として条件を満たし, 囲いを組むことは成功した. 囲いを組むことには成功したが, プランと実際の指し手の手順には誤差があった. 今回は囲いのプランであるため, 手順については相手側を考える必要性が薄かったが, 今後必要と思われる攻めのプランでは相手の応手によって成否が大きく異なると考えられる. そのため, ボーナス値の差以外で明確に手順を定める方法が必要と考えられる. また, 今の段階では一つのプランを実行し始めると, そのプランが終了するまでずっとボーナス値を与え続けてしまうので, 失敗が確定した場合の強制終了と, その状態からの再プランニングが課題として考えられる

38 参考文献 [1] 馬場口登, 山田誠二 : 人工知能の基礎, 昭晃堂, (1999). [2] 人工知能学会, [3] J. Schaeffer: A Gamut of Games,AI Magazine,vol.22,no.3,pp.29-45, (2001). [4] WikiPedia, [5] 松原仁著, 将棋とコンピュータ, 共立出版,(1994)

Microsoft PowerPoint - ゲーム理論2018.pptx

Microsoft PowerPoint - ゲーム理論2018.pptx 89 90 ゲーム理論 ( 第回ゲーム木探索 I) 九州大学大学院システム情報科学研究院情報学部門横尾真 E-mail: yokoo@inf.kyushu-u.ac.jp http://agent.inf.kyushu-u.ac.jp/~yokoo/ ゲーム木探索行動の選択が一回だけではなく交互に繰り返し生じる前の番に相手の選んだ手は分かる 9 9 例題二人で交代に, から順にまでの数を言う.