将棋とコンピュータ（松原 仁 著）

概要

松原先生によるコンピュータ将棋の（1994年時点での）最新動向をまとめたもの^[1] … Continue readingです。モンテカルロ法、Bonanzaメソッド、ディープラーニングなどが登場する前なので少し古い内容ですが、それでも紹介されている内容はコンピュータ将棋に限らずAI全般で今なお重要な概念ばかりだと思います。

将棋とコンピュータ (情報フロンテイアシリーズ)

以下、本書を読んだ時のメモになります。

構成

1. 将棋の数学的性質

ゲーム理論の立場から将棋の必勝法についての説明。「二人零和有限確定完全情報ゲームならば必勝法が存在する」という有名な定理の前提条件（二人、零和、有限、確定、完全情報）について具体例を挙げながら説明していてて分かりやすいです。

2. ゲームのプログラムの仕組み

• ゲーム木、静的評価関数を用いた探索。基本的に探索深さを増やすほど強くなることが経験的に知られていますが、理論的には必ずしもそうではないケースもあります。
• MinMax法：人間の思考をモデル化。ただし、相手が自分と同じ評価関数を用いることと最善手（評価関数で最も良くなる手）を打つと仮定。
• αβ法：MinMax法と同じ結果を保証しつつ探索を効率化した方法。評価関数が高い順に指し手が並んでいると非常に効率良く（同じ探索コストでMinMax法と比べ約2倍の深さ）を探索できます。

3. プログラムを強くするための工夫

• 定石データベース、終盤データベース
  • チェスやオセロなど終盤のパターンが限られているゲームで有効
• 静的評価関数の効率化
  • 差分計算、簡略計算（ある値より大きいか小さいかだけを判定）、同一局面の表引き
• 静的評価関数の学習
  • 1950年代にサミュエルがチェッカーで試すなど古くから研究されているアプローチ
• キラーヒューリスティック
  • 相手をとがめる手（評価値が良くなる手）を似た局面でも試す
• 反復深化法
  • αβ法は節点が評価関数の高い順に並んでいるか否かが探索効率に大きな影響を与えます。深さを反復的に増やし、前回反復の結果を使って良さそうな手から読むことで効率的な探索を実現しました。チェスプログラム強化に最も有効だった手法の1つといわれています。
• 選択的深化
  • ゲーム木の一部だけを深く読む。チェスや将棋では駒の取り合いが終わるまで読み進める静止探索（quiescence search）や兄弟節点より極端に評価値が高い場合に探索を延長する非凡拡張（singular extension）なども選択的深化の1つですね。
• 時間配分の工夫
  • チェスでは手数が増えると持ち時間が増え平均M分/手使える。配分戦略としてはM/2時点で評価値、最善手から探索継続かを判断。継続の場合はM時点で再度判断。評価値が段々下がっている時などは延長して考えるといった戦略が知られている（係数は進行度等で調整する）。切れ負けルールの場合の決定版は今のところない。他には相手の考慮時間を使うなどがあります。

4. 将棋以外のゲームのプログラム

本書では1994年時点での状況が説明されていますが、大きな進歩があったゲームについては下線付きで追記しています。

•  チェッカー
  • サミュエルの学習メカニズムで強化したプログラムが有名（一時はもう研究の余地がないとさえ考えられていました）。その後シェーファーのChinookが世界チャンピオン ティンズレーと死闘を繰り広げました。
  • その後、ティンズレーに勝利。さらにチェッカーは双方最善を尽くせば引き分けになることを解明されています。
• バックギャモン
  • 知識ベースのプログラムが世界チャンピオンに勝利。一時下火になったがニューラルネットワークで学習したプログラムが世界チャンピオン並みに強くなるなど研究は続いているようです。
• 五目並べ
  • アリスが五目並べが黒必勝であることを証明。
  • 連珠も自由打ちであれば黒必勝であることが解明されています
• オセロ
  • Logistelloが登場し世界レベルに肉薄
  • その後、世界チャンピオンに勝利しています。
• チェス
  • シャノンが初めてプログラム化を検討し、MinMax法、評価関数の概念を提示。マッカーシーなど蒼々たる研究者がプログラムを作るも当時はHW性能が低く知識主導でなかなか強くならなかったようです。
  • CHESS.X.Yが探索主導型で大幅に性能向上し人間の上級者レベルに到達。トンプソン（Unixの開発者）がチェス専用マシンを作るなどHW改良、SW改良の両輪が回り超一流レベルにまで進化を遂げます。
  • Deep Thoughtがカスパロフに挑戦し負け（2戦2敗）たものの世界チャンピオンの背中が見えてきています。
  • その後、Deep Thoughtの後継Deep Blueがカスパロフに勝利したのは有名な話ですね。
• 囲碁
  • 場合の数が多く、また評価関数の設計が難しくゲームプログラム研究において究極の目標。
  • その後2016年にモンテカルロ法やDeep learningを応用したAlpha Goがイ・セドルに勝ってビッグニュースになりました。
  • さらに2017年にAlpha Goがカケツに完勝し、コンピュータVS人間の戦いはひとまず終止符が打たれました。

5. コンピュータ将棋

将棋の難しさ

類似のゲームであるチェスと比べ「盤面が広い」「駒の種類、総数が多い」「成る駒の種類が多い」「持ち駒を再利用できる」ため可能な指し手が多く探索の分岐因子が大きく難しいとされています。形勢判断も「駒の損得」「駒の効率」「王の堅さ」「手番」「進行度」など複数要素を考慮する必要があると言われており良い評価関数を作るのが難しいです。

コンピュータ将棋の歴史

1984年に登場した「森田将棋」は3手以上の詰みを読み他のプログラムとは比較にならないほど強かった。その後、「柿木将棋」「永世名人」「YSS」「極」が登場し5強時代に突入。

プログラムの中身

序盤は定石データベースを利用。中盤は探索で指し手を決定。前向き枝狩りで残す手は20～30程度が一般的。手筋や格言に相当するものをルールベースで実装。優勢な場合は千日手を回避するようにする。入玉模様を考慮した評価関数を作っているプログラムは少ないとのこと。

6. 詰め将棋とコンピュータ

初期の詰め将棋解図プログラムとしては野下氏、伊藤氏のものが有名です。野下氏は反復深化、伊藤氏は最良優先をベースにしているそうです。超短編（9手詰以下）であればプロ以上の実力。解図だけではなく余詰チェックにも使われています。

将棋とコンピュータ (情報フロンテイアシリーズ)