4.6 ゲームの手の探索
詰め将棋を例にしてゲームの手の探索の超並列処理について述べる。将棋の手は局面と切り離しては意味がないので、手とはその一手を打った結果の局面であると定義する。従って、手を記述する際には周りの駒の配置も記述しなければならない。しかし、これは非常に繁雑になるので、最初の局面のみ示し、局面の変化分、即ち、打った手を記述することにより結果の局面を表すものとする。更に、先手と後手を一組にして[2三金2一玉]と表して一局面とする。局面の推移は[2三金2一玉]→[2二歩3一玉]と表し、[2三金2一玉]は[2二歩3一玉]であると読み、命題と考える。命題の内容に立ち入らない「AならB」という命題計算と考えるのは適当でない。
将棋の局面はどちらかが一手打てば変わるのに、上記のような考え方をする理由は、関数とその近似における差分法の考え方を取り入れたのである。関数f(x)を局面と考え、x=x0における初期値f(x0)から出発してx1=x0+h, x2=x1+h,・・・と辿り、最終目的値f(xn)に到達する。このとき、区分点毎に方向が変わるから、滑らかにf(x)を追尾するためには少なくとも第２階差まで考慮した追尾が必要である。これが第一局面と第二局面を対象と述語として一組にし、２局面先読みを単位とする理由である。又、将棋はx, yの二人で行い、互いに自分に有利な目的値へ導くゲームであるから２変数関数f(x, y)と考えることができる。故に、先手と後手を合わせて一手とする。
局面の推移を命題と考えるので多段論法や推論が使えるが、詰め将棋の場合は出発対象(局面)だけ与えられ、結論の述語(局面)が与えられないので4.5節の命題と同じ推論方法は使えない。もう一つの問題は命題の真偽を計算するに必要な命題集合が明示されていないことである。従って、命題集合を明示することから始めなければならない。一般には、ある手を一本道に辿り、それが駄目なら分岐点に戻って別の手を辿る縦方向の探索を行うが、ポリプロセッサでは一局面進行する毎に生ずる全ての分岐手について並行的に探索する。従って、局面の進行順に、第１局面、第２局面、・・・と分け、各局面に生ずる分岐手を命題で記述する。このとき、一つの対象に複数の述語があるときはそれらの述語を並べて表記し、対象の異なる命題は対象毎に区別する。
図5.20に例題の出発局面を示す。これを[ＳＳ]と表して第１局面を記述すると、
| 第１局面 | [ＳＳ]→[2三金2一玉][2三金3一玉][3三金3一玉][3三金2一玉] [3三金1三玉][3三金1二玉] |
の6個の命題がある。実際には[1三金同香]等の述語もあり、コンピュータの処理では検討を要するが、殆ど意味のない手であるので説明の簡単化のため省略する。
同一の対象に対する述語を先手の同じものでグループに分けると、グループの選択権は先手にあり、グループ内の述語の選択権は後手にある。次の局面は、これらの述語を対象とし、その分岐手を述語とする命題で記述する。以後の局面も同様であり、それらの述語の選択権も第1局面に同じである。局面が進行し、玉の逃げ路がないか、合が利かないとき[2三金?玉]のように述語「詰み」を表す。歩打ち詰みや王手が掛からない場合、及び、包囲網を玉が脱出したとき[？？]で述語「失敗」を表す。「詰み」の述語が現れたとき後手はグループ内の他の述語を選んで詰みを避けるが、他の述語がないときは、グループの選択権はないので他の対象を選択する必要があり、その対象を述語とする１局面前で選択する。「失敗」の述語が現れたとき、先手はそのグループ内の述語の選択権がないので他のグループを選んで失敗を回避するが、他のグループがないときは他の対象を選ぶ必要があり、その対象を述語とする１局面前で選択する。従って、下記の述語の選択規則が生ずる。これにより後手はできるだけ遅い詰みを捜し、先手はできるだけ早い詰みを捜すことになり、両者に最良の結果が得られる。| ［選択権による述語の選択規則］ | |
| ① | 述語が「詰み」のとき、「詰み」の述語を含むグループに他の述語があれば、「詰み」の述語は削除する。 |
| ② | 述語が「失敗」のとき、同じ対象に対する述語グループが他にあれば「失敗」の述語を含むグループは削除する。 |
| ③ | 「詰み」又は「失敗」を回避する他の述語がないとき、その対象を述語とする１局面前に戻り、当該述語を「詰み」又は「失敗」と読み替えて①②③を繰り返す。 |
| ④ | 第１局面まで戻っても、選択権のある他の述語がなければ「詰み」又は「失敗」の確定である。 |
命題集合を局面毎に書き出す処理は多段論法を各段毎に全ての命題について並行して実行しているのであり、詰み又は失敗の述語が現れたとき、それが求める結論であるか否かを逆戻りして確認する処理が推論である。推論の結果が真ならその逆の手順が解である。従って、述語の選択規則は推論規則ということができる。
図5.20を出発局面として各局面に生ずる命題を表5.2に列挙する。但し、各命題の対象は１局面前の述語と同じであるので表記を省略し、述語のみ表記して対象との関係を実線で示す。これにより、命題の関係は探索木の形式で表される。網掛けと反転文字で示した部分は途中で削除される命題であり、→[？？]の表記は失敗の判定の仕方によりその局面が変わり得ることを示す。従って、失敗の命題は削除してないが、各局面における命題の数が増えるだけで解の探索に影響はない。
の網掛けで示す。ａの詰みは第１局面に戻ると先手2三金のグループに他の述語があるので削除される。後手は2一玉を選び、先手は第３局面で歩打ち詰みは3二金により削除できるが「詰み」がないので第１局面で2三金は打たない。この手は「失敗」が確定していないので未だ削除できないが、保留して他の「詰み」を検討する。ｂの詰みは第２局面に他のグループがあるが後手に選択権はないので第１局面に戻ると先手3三金のグループには他の述語があるので削除される。ｃ,ｄの詰みもｂと同様であり、これらの第１局面の述語が削除されることによりその分岐手は全て削除される。ｅ,ｆの詰みは第２局面で先手3四金のグループに他の述語があるので共に削除される。ｇの詰みも同様に第２局面以降は削除される。残りの述語を対象とする第４局面の述語を書き出すとｈとｉの詰みが現れる。ｈは第３局面で3三飛成のグループに他の述語があるので削除される。ｉは第２局面で4二飛成のグループの他の述語は削除されているので第１局面に戻り、3三金のグループには他の述語があるので反転文字で示した述語は削除される。
残りの述語を対象とする第５局面を書き出すとｊ,ｋの詰みが現れる。第４局面には2二歩のグループに他の述語はなく、第３局面、第２局面、第１局面では既に同一先手のグループの他の述語は削除されているので後手はこれ以外の手を選択することができない。先手は他に選択肢はあるがそれらは第５局面迄に詰みが現れないから選択しない。故に、ｊ,ｋの詰みが求める解である。
ポリプロセッサでは１個のプロセッサが１個の述語を担当してこの処理を行う。第１局面には６個の述語があるから７個のプロセッサを、先頭のプロセッサに２個のプロセッサを接続し、更に、それぞれに２個のプロセッサを接続した２分木に構成すればよい。この２分木の根のプロセッサは出発局面(対象)プロセッサと第１局面(述語)プロセッサ間のデータ送受信及び述語グループの選択、削除の管理をする。そのボート0は出発局面を担当するプロセッサに入出力ポート3を設けて接続する。出発局面は第１局面の述語の対象であり、プロセッサは１個でよいが、ポート1と2は２分木を構成するポートであるので、対象とその述語の２分木はポート3により接続する。対象のプロセッサは出発局面より第１局面の述語を算出してポート3へ出力し、最後に出発局面をポート3へ出力する。ポート3に接続する２分木プロセッサは図5.19の文字列の文字を記憶するのと同様の方法により、１個の述語を内部状態に、出発局面のコピーを局所RAMに格納して局所RAMの局面を第１局面に変更する。これらのプロセッサはポート3に２分木プロセッサが接続され、第１局面より第２局面の述語を算出してポート3に出力し、最後に局所RAMの第１局面をポート3に出力する。以下同様にして２分木プロセッサのポート3に次の局面の２分木を接続して３分木ポリプロセッサが構成される。
述語が「詰み」のプロセッサはその２分木の根のプロセッサに削除の確認を求め、根のプロセッサは文字の検索と同様の方法により先手が同じ他の述語を検索し、それが有れば削除を許可し、無ければポート0に「詰み」を出力する。ポート3に「詰み」を受けた１局面前のプロセッサは自分の述語を「詰み」と読み替えて、その２分木の根のプロセッサに削除の確認を求める。この様にして、出発局面のプロセッサが「詰み」をポー ト3に受けたとき確定を送る。削除確認を求めたプロセッサはその述語をポート0に出力し、ポート3に受けた述語をポート0に転送すると詰みの手順が出力される。述語を１つの文字とすれば詰みの手順は文字列に相当し、図5.18のポリプロセッサに格納できる。同様に、定石と言われる手順も述語の列として格納される。
詰みの手順の探索に図5.18のポリプロセッサを用いることもできる。このとき、入出力ポート4と5はポート0,1,2と同様に全てのデータを送受できなければならない。ａ,ｂ,ｃ,・・・層の２分木はそれぞれ第１,２,３,・・・局面を担当する。プロセッサａは出発局面より第１局面の述語を算出してポート1へ出力し、最後に出発局面を出力する。ａ層の２分木プロセッサはそれぞれ述語の１個を内部状態とし、出発局面を受け取って各自の述語に対応する第１局面を局所RAMに構成する。次に、各自の第１局面に対応する第２局面の述語を算出してポート5へ出力し、最後に局所RAMの第１局面を出力する。第２局面はｂ層の２分木に構成されるが、根側の６つのプロセッサはポート4に受ける最初の述語を内部状態とし、続いて送られてくる分岐手の述語はポインタを付けて外周の空いているプロセッサに送り、ポインタによるソフト的な２分木を構成する。従って、この２分木を伝播する述語等のデータはポインタを調べて同一の部分木に属すことを確認の上で処理する。65535個から１個の述語を検索する時間は16個の述語の比較時間であるので、この様な構成でも処理時間の増加は問題にならない。第３局面以降も同様にしてｃ層以降の２分木に構成される。プロセッサａは詰みを回避できないことを知ったとき、それを表す記号を各層の２分木に伝播させる。削除の確認を求めたプロセッサは述語をポート0へ出力し、プロセッサａ,ｂ,ｃ, ・・・は解の手順を得る。
先に述べた３分木を用いる方法は、解の探索と得られた解を記憶するポリプロセッサは別であり、演算装置とメモリの関係にある。後の方法は両者が一体であり、得られた解は探索２分木の局所RAMに文字列を格納するのと同様の方法で格納される。詰め将棋の手順は記憶の必要はないが、定石と言われる手順は図5.18の２分木に格納しておいて必要に応じてそれを用いることができる。
対局においては、序盤はこれら定石から始めて相手が定石にない手を打った場合はその分岐局面と定石との優劣を判断して進め、中盤は取得駒の損得、相手王の守り崩し、包囲網、自王の守り等、様々な条件により局面を進め、終盤は詰め将棋である。しかし、いわゆる詰め将棋とは異なり、攻め手を緩めて相手王の包囲網を補強したり、自王の詰みを先延ばしする守りを打ったりが可能である。それが出来なくなれば投了である。