８年前に書いたコンピュータ将棋の基礎を解説した文書を見つけました。せっかくなので、少し手を入れて公開することにします。
柿木 義一
１．はじめに
読者としては、将棋についてはある程度知っていて、しかし、コンピュータについては、よく知らないということで考えたいと思います。
解説する内容は、将棋プログラムを作成する上での基礎的な理論で、現在確立されているものとします。
２．ゲーム木
将棋やチェス、囲碁、オセロ等のゲーム（ゲーム理論では、「２人零和確定完全情報ゲーム」と分類される）は、図１に示すような「ゲーム木」として表現することができます。ここで、●は先手番の局面を、○は後手番の局面を表します。それらから下に伸びている線（枝）が、その局面で可能な指し手です。最も上にある局面が現局面であり、下へ１手後、２手後と局面が進むことになります。
将棋等のゲームプログラムは、このゲーム木をつくって手を読みます（「探索」と呼びます）。
詰将棋の場合も、同様にゲーム木をつくって解くことができます。この場合、指し手は、攻め方であれば王手だけ、受け方であれば、王手を回避する手だけになります。
また、定跡書で、定跡の手を木として表現しているものがありますから、ゲーム木の考え方は、容易に受け入れられるでしょう。なお、将棋等のプログラムは、序盤のために定跡データを持っていますが、これには木構造がよく使われます。
● 現局面
／ ＼
○ ○ １手後
／｜＼ ｜＼
● ● ● ● ● ２手後
図１ ゲーム木
３．完全なゲーム木と勝敗
「完全なゲーム木」という言葉は、一般的ではないかも知れませんが、ルール上指せるすべての手を終局まで作ったものとします。将棋では不可能ですが、３×３の３目並べのような単純なゲームでは可能です。
図２は、完全なゲーム木の例です。木の一番下の局面（終端局面）は、終局のものです。終局時は、ゲームのルールによって、当然、勝敗が決まります。図では、先手からみたときの勝敗を示しています。
完全なゲーム木からは、双方が最善を尽くしたときの現局面の勝敗と現局面での最善の指し手を求めることができます。これは、末端の局面での勝敗を次の規則で以前の局面へ持ち上げることによって行います。
(1) 任意の局面で、可能な指し手の中で、それを指すとその手番の勝ちになる指し手があれば、その局面は勝ち、すべて負けならば負けとします。
これは、考えてみれば、当然の事です。この規則を下の終端局面から上の局面へくり返し適用することによって、全局面の勝敗が決まります。こうして、現局面の勝敗が求まります。また、現局面において、どの手を指せば勝ちになるかもわかります。
図２の例であれば、Ｂの手を指せば、後手がどのように指しても勝ちにできます。
ここまで説明した完全なゲーム木は、将棋には関係ないかと言うと、そうでもなくて、詰将棋を解く場合、手数を限定すれば、完全なゲーム木を探索することになります。この場合、「勝ち」「負け」は「詰み」「不詰み」となります。
勝
Ａ ● Ｂ 現局面
負 ／ ＼ 勝
○ ○ １手後
勝 ／｜＼ ｜＼
● ● ● ● ● ２手後
／｜ 負 勝 勝 勝
○ ○
勝 負
図２ 完全なゲーム木
４．ミニマックス法
今回は、完全なゲーム木をつくることができないときの方法を説明します。
将棋のように、ゲーム木を終局までつくることができない場合、人間が手を読むのと同様に、プログラムもある深さまで手を読み、その末端の局面の優劣を評価します。
優劣を評価する部分を「静的評価関数」、あるいは単に「評価関数」と呼びます。形勢を数値で表わさなければなりません。ここでは、評価値が＋で数値が大きい程先手が優勢、−であれば、後手が優勢だとします。
このような場合、次の規則をくり返し用い、末端の評価値を上へ持ち上げ、現局面での最善手を求めます。
(1) 先手番の局面では、そこから１手指した局面の評価値の中で最大のものを評価値とする。
(2) 後手番の局面では、そこから１手指した局面の評価値の中で最小のものを評価値とする。
図３は、ゲーム木とその評価の例です。末端の局面の数値は、評価関数で得たものとし、それ以前の局面の評価値は、末端の評価値を上で述べた方法で持ち上げたものです。このような処理の結果、現局面で指すべき手はＢであり、その評価値は７であることがわかります。
このように、評価値を求める方法を「ミニマックス法」と呼びます。これは、思考ゲームのプログラムの基本的な考えかたです。相手も最善を尽くすことを仮定する合理的なものです。はめ手は、相手が間違えたとき、自分が優勢になる手で、正しく対応されれば、不利となります。プログラムは、このような手は狙わないことになります。
7
Ａ ● Ｂ 現局面
-5 ／ ＼ 7
○ ○ １手後
15 ／｜＼ ｜＼
● ● ● ● ● ２手後
／｜ -5 5 7 8
○ ○
10 15
図３ ミニマックス法
５．縦型探索と横型探索
ゲーム木をプログラムで探索する方法は、大きく分けて、「縦型探索」と「横型探索」の二つがあります。これらの変形も多く存在しますが、今回は触れないことにします。
縦型探索は、図４に示す数字の順で木を探索していく方法です。このように、現局面から最初の枝を末端まで探索し、その後、次の枝へと移っていきます。なお、ゲーム木の表記は、習慣として、探索を左から右へ行うように示します。
一方、横型探索は、図５に数字で探索順を示すように、読みが浅い部分から探索を始め、順に深い部分へと移る方法です。
縦型探索と横型探索は、それぞれ特徴がありますが、プログラムが簡単に記述でき、また、メモリの使用量が少なくなる利点から、縦型探索が多く使用されます。
1
● 現局面
2 ／ ＼ 8
○ ○ １手後
3 ／｜＼ ｜＼
● ● ● ● ● ２手後
／｜ 6 7 9 10
○ ○
4 5
図４ 縦型探索の探索順序
1
● 現局面
2 ／ ＼ 3
○ ○ １手後
4 ／｜＼ ｜＼
● ● ● ● ● ２手後
／｜ 5 6 7 8
○ ○
9 10
図５ 横型探索の探索順序
６．αβ法
前述の縦型探索で、ミニマックス法を用いて、局面を評価していくとき、読む必要のない手があることがわかります。
図６は、ゲーム木の例です。ここで、大文字のＡＢＣは局面を、小文字のａｂｃは指し手を表わすこととします。また、数字は先手からみた局面の評価値です。
縦型探索では、この木をＡ→Ｂと、左から順に読んでいきます。Ｂの局面で、その先の評価を終えたとき、先手番なので、ミニマックス法の原理によって、最大の価値を求め、10の価値が得られます。次に、Ｃの局面で、ａの手を読んだとき15の価値が得られたとします。この時点で、Ｃの局面の価値は、ｂの価値に関係なく、最低15である保証が得られます。Ａの局面は、後手番なので、最少値を求めることになるので、この時点で、局面Ａの価値はＢの10と確定します。このように、ｂの指し手は読む必要がありません。
同様に、その後のＥの局面で、５の価値が確定したら、Ｄの局面の価値は５以下になり、Ｆ以降の局面は、調べる必要がありません。図６で、×は、読む必要がないことを表わしています。
結局、現局面の価値は、10であり、指すべき手は、ｃとなります。
このように、読む必要がないことを「枝刈り(prune)」または「カット（オフ）(cutoff)」と呼び、この探索法を「αβ法」と呼びます。αβ法は、ミニマックス法と同じ結果が得られ、しかも、読む手が少なくなるので、明らかにミニマックス法よりも優れています。これがゲーム木探索の基本的な方法であり、現在、最も多く使われています。
10
● 現局面（先手番）
ｃ／ ＼
10 ／ ＼
Ａ○ Ｄ○≦5 １手後（後手番）
／｜ ｜＼
10 ／ ｜ 5 ｜ ＼
Ｂ● Ｃ●≧15 Ｅ● Ｆ●× ２手後（先手番）
／｜ ａ｜＼ｂ ｜＼ ＼
／ ｜ ｜ ＼ ｜ ＼ ＼
○ ○ ○ ○ ○ ○ ○ ３手後（後手番）
10 5 15 × -5 5 ×
図６ αβ法による探索
1991/08/18 〜 1991/10/06 原著
|042/042 SDI00503 柿木 義一 【コンピュータ将棋の基礎】（１）
|(18) 91/08/18 22:54
|050/050 SDI00503 柿木 義一 【コンピュータ将棋の基礎】（２）
|(18) 91/08/25 20:33 042へのコメント
|072/072 SDI00503 柿木 義一 【コンピュータ将棋の基礎】（３）
|(18) 91/09/01 20:42 050へのコメント
|090/090 SDI00503 柿木 義一 【コンピュータ将棋の基礎】（４）
|(18) 91/09/23 08:06 072へのコメント
|096/096 SDI00503 柿木 義一 【コンピュータ将棋の基礎】（５）
|(18) 91/10/06 10:14 090へのコメント
1999/07/19 改定