新時代のクラスタシステム ~MultiponderとPreponder~

第29回世界コンピュータ将棋選手権に参加された皆様、感染してくださった皆様、改めてお礼申し上げます。Qhapaq di molto(QDM)は5位入賞という結果を残すことが出来ました。

 

本大会でQDMはPreponderを使ったクラスタシステムを構築しました。Preponderは前年度優勝ソフトであるHefeweizenが採用したMultiponderを発展させたシステムです。本稿ではQDMの躍進の屋台骨となったPreponderについて解説していきます。

 

ソースコードは此方からどうぞ

github.com

 

【システムの概要】

【Ponder】

コンピュータ将棋におけるPonderとは相手の手番中に先の展開を予想しておくことを意味します。人間の将棋でも予想外の手に慌てふためいたり、逆に自分の手を相手に読まれた結果、とっておきの一手が即指しで返されてしまったりすることがあると思いますが、コンピュータ将棋でも同様のことが起こります。

従来の将棋ソフトの多くは自分の指し手を決める際に相手の返しの手を一つ予想しておき(予想手)、相手の手番中に予想手を指された後の局面を検討します。予想手が当たれば相手の思考時間を自分の持ち時間に加えられるし、外れればその読みは破棄します。予想手の一致率はソフトの相性にもよりますが5割強程度と考えられています。

f:id:qhapaq:20190507190246p:plain

Ponderのイメージ図

 

【Multiponder】

一方、Multiponderでは予想手を複数用意し、それぞれの予想手について先の展開を読みます。予想手を5〜6程度用意すればほぼ全ての局面で相手の手を当てることが出来ます。複数の計算ノードを用意し、それぞれに局面を割り振ることで、実効的な持ち時間を3割程度増やすことが出来ます。

f:id:qhapaq:20190507190205p:plain

Multiponderのイメージ図

【Preponder】

PreponderではMultiponderに加え自分の手番中に2手先の展開を読ませることで実効的な持ち時間をさらに増やすことができます。2手先を読む都合上、Multiponder程の的中率は出ませんが、当たると時間を大幅に稼ぐことが出来ます。Preponderが外れた(自分の手が予想手と一致しなかった)場合はPreponderはMultiponderと等価になります。

 

f:id:qhapaq:20190507190145p:plain

Preponderのイメージ図

【実験結果】

Qhapaqの自己対局でPonder、Multiponder、Preponderを比べた所、PreponderはPonderだけの時に比べ実効的な持ち時間が5割増し程度になることが解りました。大会当日でもPreponderによって序盤から長考をした結果、有利な戦型持っていけたケースが多かったと考えています。

f:id:qhapaq:20190507190112p:plain

Ponder, Multiponder, Preponderの比較