suzuki toyolab

(1)

卒業論文

将棋の駒組みにおける動的プログラ

ミング化

担当教員名豊泉洋

早稲田大学基幹理工学部応用数理学科

1w120282-1 鈴木拓実

提出日 2016 年 2 月 2 日

(2)

1 はじめに 3

2 DP の将棋への活用 3

2.1 DP の手法と立式

. . . . . . . . ³

2.2 DP と将棋の対応

. . . . . . . . ⁵

3 DP 化した式の実証 6

4 まとめ 8

(3)

1 はじめに

この論文では将棋の最終盤をDynamic Programming(^{動的プログラミング}^、以下_DPと表す）で定式化することを目的としていて、初期状態から囲いに組む手順について_DP化が可能であることが分かった。

現在将棋の研究は多岐にわたって存在している。棋譜分析から棋風を取り入れる、といった研究_[1]や、本将棋、詰将棋という実際の将棋に限定してもモンテカルロ木探索アルゴリズム_[2]、木を使った詰将棋問題の生成_[3]、必至問題の解のアルゴリズム作成といった先行研究_[4]などが既に存在する。しかし、将棋の_DP化をした先行研究は存在しなかった。そのため、_DP化することが容易と考えられる囲いの作成手順を_DP化することから行う。

2 DP の将棋への活用

2.1 DP の手法と立式

DPの手法はまず、最初に与えられた状況から向こうことのできる全ての次の状況を見ていく。それを繰り返すことで最後の状況まで見ることができる。そして、その最後の状況のうち最も高い価値を持つ者を見つける。すると最初に与えられた状態から進むべき道筋が見つかる、という手法である。つまり、図₁のように与えられた状況から最後の状況まで調べていき、その中で最も高い評価₍図₁の中では太枠の部分₎を見つける。これに至る道筋を逆にたどる₍図₂₎ことで最初の状況からの道筋が見つかる、というわけである。

また、_DPで使う用語として「段階」、「状態」、「終状態」、「決断」、「方針」、

「漸化式」、「次元の呪い」が挙げられる_[5]。「段階」とはプレイヤーが残している「決断」あるいは「動き」（将棋やチェスのように駒を動かすゲームに存在するものである駒をルールに従って別の位置に動かすことを表す）がいくつあるかの尺度を表す。「状態」とはゲーム上の駒やカードなどのプレイするために使う物の配置を表し、「決断」とはでゲーム上の「状態」を変化させる行動、つまりある「状態」での次の行動のことを言う。「方針」や「漸化式」は「状態」や「段階」に関連した価値や評価を表している。「次元の呪い」は次元が増えることによっておこる計算量の指数的な増加のことで最適化した計算を考えるときに生じやすい問題のことを指す（ただし今回はあまり影響しない）。また、_DPで解法の存在の有無を考える場合、「終状態」と呼ばれる目標とする「状態」へある「状態」から向かえるかどうかを考える。向かう方法が存在する場合は評価を₁、存在しない場合は評価を₀または_-1にすると定義されている_[5]。そのため、解法の有無を探索する式は以下のように

(4)

・・・

最初に与えられた状況

1つ先の状況

・・・・・・

最後の状況

・・・

図_{1: DP}の考え方

・・・

最初に与えられた状況

1つ先の状況

・・・・・・

最後の状況

・・・

図_{2: DP}の考え方₂

表すことができる。

_f_{(p) = max}

m∈M(p){f (T (p, m)} (1)





 (

「終状態」になる方法が存在する) ⇒ f (p) = 1 (

「終状態」になる方法が存在しない) ⇒ f (p) = 0 ⁽²⁾ ここで、_pはある「段階」においての「状態」、_M(p)は「決断」の選択肢１つ１つを元とする集合、_mは集合_M(p)のうちから選んだ₁つの「決断」、 T(p,m)^{は「状態」}p^{から「決断」}mによって変わった次の「段階」の「状態」、 f(p)^{は「状態」}p^{の価値を表している}[5]^。

次に、_DPの解が存在する場合について解に至る最善の方法を考える。「動き」の定義がされていれば、その「動き」の回数を最小にすることが最善の方法の一つとして挙げられる。この時₍₁₎では「動き」の回数を値にできないので以下の式が必要である。

g(p) = 1 + min

m∈M(p){g(T (p, m))} (3) ここでの_g(p)は最善の方法を選んだ時の_pからの「動き」の回数を表していてその他の記号_p、_m、_M(p)、_Tは₍₁₎の対応と同じである。この₂式をもとにして将棋との対応を考えていく。

(5)

香桂銀金玉金銀桂香 ^一

飛角 ^二

歩歩歩歩歩歩歩歩歩

三

四

五

六

歩歩歩歩歩歩歩歩歩七

角飛八

香桂銀金玉金銀桂香九

図 _3: 初期図

六

角銀飛銀八

香桂金玉金桂香九

図_4: 初心者囲い

2.2 DP と将棋の対応

まずは将棋の中で_2.1で使った用語を対応させる。「状態」は将棋では局面

（盤上でのすべての駒の配置）と対応する。ほかにも「段階」は残りの手数と、

「決断」は「動き」と同じ意味になるが１手（ある駒をルール上で可能なところへ動かすことのできるところへ動かすこと）と、「方針」や「漸化式」は

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

「状態」を初期配置₍図₃₎、最後の「状態」を囲いの完成形₍図₄₎として考える。図₃から図₄までを₍₁₎、₍₃₎の式で表すことができることを示す。なお、図₄より先の図では相手方の形と囲いは関係しないので省略する。まず₍₁₎の式で使われている記号を将棋で表すと、「状態」_pは与えられた局面、_M(p)は与えられた局面_pで指すことのできる手の集合、_mは_M(p)から選んだ₁手、_T(p,m)は与えられた局面_pで選んだ₁手_mによる₁手先の局面、_f(p)は囲いが完成する場合は₁、囲いが完成しない場合は₀を返す関数となる。

また、₍₃₎の式では_p,M(p),m,Tは₍₁₎と同じで_f(p)は囲いを完成するのにかかる最短手数を表す。

ここで将棋では動きの関係上同じ局面が登場することがある。かかった手数が違うときに同じ局面になった場合は場合は_2.1に書いてある「動きの回数を最小にすること」にそぐわないので₍₃₎の中では候補に含めないとする。ただし、手順が違うもののかかった手数が同じときに同じ局面になった時は₍₃₎ 上でも問題ないのでそれぞれを₁つとして数える。今回₍₁₎、₍₃₎を実証をするための囲いとしてここでは「初心者囲い」₍図₄₎と呼ばれる形を使う。

(6)

六六

歩歩歩歩歩歩歩歩歩七歩歩歩歩歩歩歩歩歩七

角銀飛八角飛銀八

香桂金玉金銀桂香九香桂銀金玉金桂香九

六六

角銀飛銀八角銀飛銀八

香桂金玉金桂香九香桂金玉金桂香九

六

銀飛銀八

香桂角金玉金桂香九

図_5: 初心者囲い₁手前の候補局面

3 DP 化した式の実証

将棋の開始状態から囲いの完成までを₍₁₎、₍₃₎で表すことが可能かどうかを図₍₄₎を使って確かめる。

まず₍₁₎について_2.2で書いたように初期状態は図₃、最終状態は図₄としている。この形は図₃から飛車を中央に持ってきた後で両方の銀を中央に向かうように動かせば完成するため図₃は_f(p)=1となり、初期状態を_f(p)で表すことができる。

次に₍₃₎について考える。上で示した方法だと₃手使うことになるので₍₃₎ で_f(p)=3となる局面の中に図₃と同じ局面があれば表すことができていると言える。このことを証明するために_f(p)=0から戻って示していく。 f(p)=0^は図4を表しているので、まずは_f(p)=1の局面を考える。これは次の局面で囲いが完成する局面を考えるので図₅の₅通りが存在する。

次に図₅のそれぞれの局面について₂手前を考える。次に₁の状況になる局面は_2.1で書いたように同じ局面になるものは除外して考える₍右側の銀が 4^八→3^{九に動く場合を除く})^ので図6^の10通り存在する。この作業を図₅ の他の₄通り通りについて行うと₂では₆通り、₃では₅通り、₄では₄通

(7)

六六

銀飛八角飛八

香桂角金玉金銀桂香九香桂銀金玉金銀桂香九

六六

角銀飛銀八角銀飛八

香桂金玉金桂香九香桂金玉金銀桂香九

六六

角銀飛八角銀飛八

香桂金玉金銀桂香九香桂金玉金銀桂香九

六六

角銀飛八角銀飛玉八

香桂金玉金銀桂香九香桂金金銀桂香九

六六

角銀飛金八角銀飛銀八

香桂金玉銀桂香九香桂金玉金桂香九

図_{6: 1}を選んだ時の初心者囲い₂手前の候補局面

り、₅では₂通りの合計₂₇通り存在する。

そして、図₆について同様にして₃手前を考える。まずは失敗例として図 6^の1^{を考える。次に}1^{の状況になる局面は図}7^の6^{通りである。しかし、} この中に図₃と一致するものは存在しないのでその先の手を考える必要がある。次に成功例として図₆の₂を考える。次に図₆の₂の状況になる局面は図₈、図₉の₁₁通り存在する。ここで₅は図₃と同じなので図₃は_f(p)で表すことが可能であることが言える。そして、図₅、図₆には図₃となるものは存在しなかったので_f(p)=3であることが分かり、同じことを図₅、図₆のすべての局面について行うと、_f(p)=3となる手順は

1,^▲6^八銀→▲5^八飛→▲4^八銀 2,^▲5^八飛→▲6^八銀→▲4^八銀 3,^▲5^{八飛→▲４八銀→▲}6^八銀の₃通りのみであることが分かる。

(8)

六六

銀飛八銀飛八

香桂角金玉金銀桂香九香桂角金玉金銀桂香九

六六

銀飛八銀飛八

香桂角金玉金銀桂香九香桂角金玉金銀桂香九

六六

銀飛玉八銀飛金八

香桂角金金銀桂香九香桂角金玉銀桂香九

図_{7: 2}手前で₂を選んだ時の初心者囲い₃手前の候補局面

4 まとめ

この論文によって将棋の序盤の駒組みの手順は_DP化して最短の手数を求めることができることが分かった。本来は将棋の最終状態である「詰み」から考えていくつもりで詰みを見つける詰将棋の_DP化を目標にしていた。しかし、最終局面が₁通りでないことや手数の概念を取り入れて考えなければならず上手くいかなかった。そこである局面を与えられてその局面から詰みまでたどり着けるかどうかを判定する_DPをまず作成して、与えられた局面から最短の詰みを見つける_DPの作成、将棋の終盤の速度計算の_DPの作成を目標にするつもりである。

参考文献

[1] ^大森^翔太朗^金子^知適将棋における棋風を学習するための棋譜分析の取り組み(2015)-Game programming workshop

[2] ^横山^大作ベイジアンアプローチに基づくモンテカルロ木探索アルゴリズムの将棋への適用(2013)-Game programming workshop

[3] ^石飛^{太一、飯田}弘之新たな知見を用いた詰問題創作への取り組み (2015)-Game programming workshop

[4] ^長井^歩難解な必至問題を解くアルゴリズムとその実装(2011)-Game programming workshop

(9)

六六

角飛八角飛八

香桂銀金玉金銀桂香九香桂銀金玉金銀桂香九

六六

角飛八角飛八

六六

角飛八角飛八

図_{8: 2}手前で₁を選んだ時の初心者囲い₃手前の候補局面１

六六

角金飛八角玉飛八

香桂銀玉金銀桂香九香桂銀金金銀桂香九

六六

角飛金八角飛玉八

香桂銀金玉銀桂香九香桂銀金金銀桂香九

六

角飛銀八

香桂銀金玉金桂香九

図_{9: 2}手前で₁を選んだ時の初心者囲い₃手前の候補局面２

(10)

[5] David K. Smith Dynamic programming and board games: A survey(2007)

suzuki toyolab

卒業論文

将棋の駒組みにおける動的プログラ

ミング化

担当教員名 豊泉 洋

早稲田大学 基幹理工学部 応用数理学科

1w120282-1 鈴木 拓実

提出日 2016 年 2 月 2 日

目 次

1 はじめに 3

2 DP の将棋への活用 3

2.1 DP の手法と立式

. . . . . . . . 3

2.2 DP と将棋の対応

. . . . . . . . 5

3 DP 化した式の実証 6

4 まとめ 8

1 はじめに

2 DP の将棋への活用

2.1 DP の手法と立式

・・・

・ ・ ・ ・ ・ ・

・ ・ ・

・・・

・ ・ ・ ・ ・ ・

・ ・ ・

2.2 DP と将棋の対応

3 DP 化した式の実証

4 まとめ

参考文献

担当教員名豊泉洋

早稲田大学基幹理工学部応用数理学科

1w120282-1 鈴木拓実

目次

. . . . . . . . ³

. . . . . . . . ⁵

・・・・・・

・・・

・・・・・・

・・・