コンピューター将棋の構造　－　検索エンジン　「浅読みくん」

…という訳で「合法手生成モジュール」と「評価関数」を使って検索エンジン、その名も「浅読みくん」を構築してみたいと思います。「浅読みくん」はその名の示す通り３手先しか読めません。

唐突ですが、人間は「三手の読み」をどの様に行うのでしょう？将棋へたっぴの我としては…

①自分にとって都合の良さそうな手を考え、局面を進める
②相手が指しそうな手を考え、局面を進める
③自分にとって都合の良さそうな手を考え、局面を進める

…こうやって想像の中で３手進めて一番良さそうな結果の候補手を選びます。人間は極めて自然に「見込みのない手」をかなりの確率で最初から切り捨てて「実現しそうな手」を繋げて読みを入れていきます。これは５手読みだろうと１０手読みであろうと変わりはありません。重要なポイントは人間は先へ、先へと読みを入れます。正確な読みはいかにして予想の道のりを外さないか…という事になります。

「浅読みくん」の「三手の読み」は以下の方法で行われます。（注・実際のプログラム実行順序は少々異なりますが概念・結果は同じなので悪しからず。）ちょいと文章で説明するとややこしいのですが、図面を見ながら追ってください。

①　開始局面から一手進めた全局面を生成
②　上から一つ選んで一手進めた全局面を生成…これで二手先の局面が出現します。
③　上から一つ選んでまた一手進めた全局面を生成…これで三手先の局面が出現します。
④　ステップ③で生じた全局面より自分に一番都合の良い（勝っていると判断される）局面を選びます…自分の着手なのだから自分に一番有利な結果を選ぶのは当然。（不利な状況なら一番マシな局面を選びます）…局面の優位度に応じ点をつけ（「評価関数」の出番です）、最高点を一手前、すなわち「二手先の局面」に報告します。

⑤ 「二手先の局面」（相手が指した直後の局面）では「三手先の局面」（３０～２００）から戻ってくる評価点の中から相手にとっては最高・最良（自分にとっては最低・最悪）の点数を選び「二手先の局面」にその数字を報告します。

⑥ 「一手先の局面」（自分が指した直後の局面）では「二手先の局面」（３０～２００）から戻ってくる評価点の中から自分にとっては最高・最良（相手にとっては最低・最悪）の点数を選び…これが候補手の最終評価値になります。

⑦ 候補手中、一番最終評価値が高い手を選び「次の手」として推薦します。（同点の場合はランダムに選びます）

…といろいろ書きましたが重要なのは


① 検索エンジンは○○手先の局面を生成し、
② 評価関数は○○手先の局面を査定する時のみに使用。
③ 最後には○○手先の末端からトーナメント式に評価値の高い手が（相手の手番では評価値の低い手が）上に上り候補手の最終評価値になります。

もっと短くまとめるなら「○○手先の局面を生成し、一番評価値の高い局面へと繋がる候補手を選ぶ」…という事です。

チカレタ…ので更なる解説は（続）。

‹ コンピューター将棋の構造　－　検索エンジン　「浅読みくん」 ② コンピューター将棋の構造　－　合法手生成 　－　追記 ›
投稿者： 紫外線 投稿日時： 日, 07/12/2009 - 13:36 categories [ ]

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。

面白い

投稿者： みなかみ 投稿日時： 火, 07/14/2009 - 12:56

　楽しみに読んでいます。

紫外線　対　浅読みくん　解説

投稿者： webMaster 投稿日時： 火, 07/14/2009 - 01:00

①△２六歩　▲３四歩
お～っと、浅読みくんなんと初手に角道を開けてきた～。（現在定跡は入っていません）

角道を開けると７七の歩が取れるので「三手読み」には自然な手…ですが７七の歩を角で取っても簡単に取り返される事（角を失い大赤字）はまだ視野に入っていません。

②△２五歩　▲４四角
なんじゃこれは？浅はかだのう。

角道を開けた後には「７七の歩を角で取っても簡単に取り返される」のが見えますのでさすがに取りません。評価を上げることができない（何も取れない）のでランダムに手を選びました。

③△２四歩　▲２四歩
ふむ、「取れる駒は取る」…は分かるようです。

上記コメントそのままです。

④△２四飛　▲２二銀
２一の桂を取られないように防御…ってところ？

すぐ見える駒損は回避です…候補手の内これがランダムで出てきました。

⑤△２三歩打　▲３三銀
お～っと銀取りを防ぎ、小癪にも我の飛車を攻撃してきた～！！！！

駒損は回避…プラス取れるものは取ろうとする…ですね。

⑥△２八飛　▲２六歩打
なに～～～～～～～？？？お父さんはそんな手筋を教えた覚えはありません！！

想定外なのは当然。ランダムです。

紫様v.s.浅読みくんは・・・

投稿者： wasabinosuke 投稿日時： 月, 07/13/2009 - 13:51

創造主もちょっと驚くような展開という感じですね。

コンピューター将棋シリーズは、文系でコンピューター言語がまったくわからない私にはちょっと難しい部分もありますが、今後も楽しみにしています。
続きをまたお願いします！

紫外線　対　浅読みくん

投稿者： webMaster 投稿日時： 月, 07/13/2009 - 13:03

「３手読みの鬼」浅読みくんと対局テストの記録です。評価関数は「駒割りに応じて点数をつけるだけ」（自分の駒が多いほど高得点）…です。

先手：紫外線
後手：浅読みくん

初期盤面です

  9   8   7   6   5   4   3   2   1 
 -KY -KE -GI -KI -OH -KI -GI -KE -KY 1
 ... -HI ... ... ... ... ... -KA ... 2
 -FU -FU -FU -FU -FU -FU -FU -FU -FU 3
 ... ... ... ... ... ... ... ... ... 4
 ... ... ... ... ... ... ... ... ... 5
 ... ... ... ... ... ... ... ... ... 6
 +FU +FU +FU +FU +FU +FU +FU +FU +FU 7
 ... +KA ... ... ... ... ... +HI ... 8
 +KY +KE +GI +KI +OH +KI +GI +KE +KY 9

△２六歩　▲３四歩
お～っと、浅読みくんなんと初手に角道を開けてきた～。（現在定跡は入っていません）

2726
[P2][FU (3,3) => (3,4) ...]
  9   8   7   6   5   4   3   2   1 
 -KY -KE -GI -KI -OH -KI -GI -KE -KY 1
 ... -HI ... ... ... ... ... -KA ... 2
 -FU -FU -FU -FU -FU -FU ... -FU -FU 3
 ... ... ... ... ... ... -FU ... ... 4
 ... ... ... ... ... ... ... ... ... 5
 ... ... ... ... ... ... ... +FU ... 6
 +FU +FU +FU +FU +FU +FU +FU ... +FU 7
 ... +KA ... ... ... ... ... +HI ... 8
 +KY +KE +GI +KI +OH +KI +GI +KE +KY 9

[P1]{FU: 0, KY: 0, KE: 0, GI: 0, KI: 0, HI: 0, KA: 0, OH: 0}
[P2]{FU: 0, KY: 0, KE: 0, GI: 0, KI: 0, HI: 0, KA: 0, OH: 0}

△２五歩　▲４四角
なんじゃこれは？浅はかだのう。

2625
[P2][KA (2,2) => (4,4) ...]
  9   8   7   6   5   4   3   2   1 
 -KY -KE -GI -KI -OH -KI -GI -KE -KY 1
 ... -HI ... ... ... ... ... ... ... 2
 -FU -FU -FU -FU -FU -FU ... -FU -FU 3
 ... ... ... ... ... -KA -FU ... ... 4
 ... ... ... ... ... ... ... +FU ... 5
 ... ... ... ... ... ... ... ... ... 6
 +FU +FU +FU +FU +FU +FU +FU ... +FU 7
 ... +KA ... ... ... ... ... +HI ... 8
 +KY +KE +GI +KI +OH +KI +GI +KE +KY 9

[P1]{FU: 0, KY: 0, KE: 0, GI: 0, KI: 0, HI: 0, KA: 0, OH: 0}
[P2]{FU: 0, KY: 0, KE: 0, GI: 0, KI: 0, HI: 0, KA: 0, OH: 0}

△２四歩　▲２四歩
ふむ、「取れる駒は取る」…は分かるようです。

2524
[P2][FU (2,3) x (2,4) FU]
  9   8   7   6   5   4   3   2   1 
 -KY -KE -GI -KI -OH -KI -GI -KE -KY 1
 ... -HI ... ... ... ... ... ... ... 2
 -FU -FU -FU -FU -FU -FU ... ... -FU 3
 ... ... ... ... ... -KA -FU -FU ... 4
 ... ... ... ... ... ... ... ... ... 5
 ... ... ... ... ... ... ... ... ... 6
 +FU +FU +FU +FU +FU +FU +FU ... +FU 7
 ... +KA ... ... ... ... ... +HI ... 8
 +KY +KE +GI +KI +OH +KI +GI +KE +KY 9

[P1]{FU: 0, KY: 0, KE: 0, GI: 0, KI: 0, HI: 0, KA: 0, OH: 0}
[P2]{FU: 1, KY: 0, KE: 0, GI: 0, KI: 0, HI: 0, KA: 0, OH: 0}

△２四飛　▲２二銀
２一の桂を取られないように防御…ってところ？

2824
[P2][GI (3,1) => (2,2) ...]
  9   8   7   6   5   4   3   2   1 
 -KY -KE -GI -KI -OH -KI ... -KE -KY 1
 ... -HI ... ... ... ... ... -GI ... 2
 -FU -FU -FU -FU -FU -FU ... ... -FU 3
 ... ... ... ... ... -KA -FU +HI ... 4
 ... ... ... ... ... ... ... ... ... 5
 ... ... ... ... ... ... ... ... ... 6
 +FU +FU +FU +FU +FU +FU +FU ... +FU 7
 ... +KA ... ... ... ... ... ... ... 8
 +KY +KE +GI +KI +OH +KI +GI +KE +KY 9

[P1]{FU: 1, KY: 0, KE: 0, GI: 0, KI: 0, HI: 0, KA: 0, OH: 0}
[P2]{FU: 1, KY: 0, KE: 0, GI: 0, KI: 0, HI: 0, KA: 0, OH: 0}

△２三歩打　▲３三銀
お～っと銀取りを防ぎ、小癪にも我の飛車を攻撃してきた～！！！！

FU23
[P2][GI (2,2) => (3,3) ...]
  9   8   7   6   5   4   3   2   1 
 -KY -KE -GI -KI -OH -KI ... -KE -KY 1
 ... -HI ... ... ... ... ... ... ... 2
 -FU -FU -FU -FU -FU -FU -GI +FU -FU 3
 ... ... ... ... ... -KA -FU +HI ... 4
 ... ... ... ... ... ... ... ... ... 5
 ... ... ... ... ... ... ... ... ... 6
 +FU +FU +FU +FU +FU +FU +FU ... +FU 7
 ... +KA ... ... ... ... ... ... ... 8
 +KY +KE +GI +KI +OH +KI +GI +KE +KY 9

[P1]{FU: 0, KY: 0, KE: 0, GI: 0, KI: 0, HI: 0, KA: 0, OH: 0}
[P2]{FU: 1, KY: 0, KE: 0, GI: 0, KI: 0, HI: 0, KA: 0, OH: 0}

△２八飛　▲２六歩打
なに～～～～～～～？？？お父さんはそんな手筋を教えた覚えはありません！！

2428
[P2][FU => (2,6) ...]
  9   8   7   6   5   4   3   2   1 
 -KY -KE -GI -KI -OH -KI ... -KE -KY 1
 ... -HI ... ... ... ... ... ... ... 2
 -FU -FU -FU -FU -FU -FU -GI +FU -FU 3
 ... ... ... ... ... -KA -FU ... ... 4
 ... ... ... ... ... ... ... ... ... 5
 ... ... ... ... ... ... ... -FU ... 6
 +FU +FU +FU +FU +FU +FU +FU ... +FU 7
 ... +KA ... ... ... ... ... +HI ... 8
 +KY +KE +GI +KI +OH +KI +GI +KE +KY 9

[P1]{FU: 0, KY: 0, KE: 0, GI: 0, KI: 0, HI: 0, KA: 0, OH: 0}
[P2]{FU: 0, KY: 0, KE: 0, GI: 0, KI: 0, HI: 0, KA: 0, OH: 0}

＊＊＊　テスト終了　＊＊＊

いやはや、びっくりしました。

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。