読者です 読者をやめる 読者になる 読者になる

コンピュータ将棋流の時間攻めと電王戦の攻防

何を隠そう、私が最初に覚えた将棋の小技は時間攻めです。素人将棋では時間なんてそもそもカウントしないことも多いですが、プロ棋士(に限らずある程度将棋を指す人)の対局では持ち時間を意識した水面下の戦いは切っても切れない存在です。

終盤の圧倒的な読みの精度と、残り時間が何秒だろうと決して慌てない鉄壁の精神を持つコンピュータ同士の戦いでは時間攻めは意識されることのほうが少ないものかもしれません。が、将棋電王トーナメント本戦の計4時間という長丁場は、この手の戦に慣れていない開発者の精神には十分すぎるダメージを与えてくれました。それこそ今でも稀に夢に出るぐらい。

さて、コンピュータが慌てふためいてくれない関係で、コンピュータ将棋の時間制御は長らく似たようなルーチン(stockfishの受け売り)が使われ続けているのですが、果たしてこれは正しいのでしょうか。

結論から言うと、stockfishの時間制御は数学的にみてもかなり精密に作られていることが解りました。同時に、コンピュータと人間の時間の捉え方の違いや、それがもたらすドラマの存在にも気付くことができました。本稿ではコンピュータがいかに時間を捉えているかと、人間との違いについて、解説していきます。

 

・stockfishベースの時間制御

stockfishはざっくり言って以下のような思考で持ち時間を制御しています。

1.終局までの1手の平均時間を見積もる(20手目で残り時間50分、120手目ぐらいで決着がつくと予想するなら1手1分と言った要領)

2.最大思考時間を決める(近似的には平均時間の5-7倍)

3.局面を読み進める

4.同時に、読みを1手深くする毎に最適手が変化する確率を見積もる

5.消費時間(にある一定の数をかけたもの)が4で求めた確率を上回ったら読みを中断する

この中で特に優れているのが5の部分です。消費時間を増やす毎に、読みを打ち切る条件つけを厳しくすることがミソです。将棋(やチェス)は深く読めば読むほど、手が固まりやすくなると同時に読むべき局面が増えてしまうため、過去の自分の読みを信じて、煮詰まったと思ったら普段ならもう少し読む局面も放置して先に進めようという発想です。

なお、細かい導出はどう頑張っても簡単に書けなかった(もともと理系大学生が3-4年ぐらいで習うことで、その半数が首を傾げたまま卒業するような内容)ので、本稿末尾のオマケとします。

 

・コンピュータ流の時間攻めと人間の逆襲

 深く読めば読むほど、昔の自分を信じて読みを打ち切りやすくなるという仕様上、コンピュータの消費時間は人間に比べると平坦になりがちです。特に持ち時間が長いとその傾向は顕著となります。例えば、昨年末の竜王戦第7局では渡辺竜王、丸山九段の消費時間和は30手目までが1時間30分、40手目までで4時間30分、50手目までで6時間となっています。

これに対し、電王戦で山崎八段と戦ったponanzaは30手目で1時間26分、60手目で3時間10分、90手目で4時間30分と極めて平坦な時間の使い方をしています(まあ、ponanzaがstockfishベースの時間管理をしてる保証はないし、手によっては消費時間がばらつきはしてるのですが)。

人間はコンピュータに比べると頭の回転速度にゆらぎが多く、また、最善手が変わった回数を数えるなどの行為を苦手とはしていますが、コンピュータ流の指し方として、試して見る価値はあると思います。人間の感情的な部分さえ無視できれば、stockfishの戦略は人間でも成り立つはずです。

 

しかし一方で、コンピュータが人間に明確に劣る点もあります。それは、試合の終わる速度を読む力です。相掛かりや振り飛車など指し手の可逆性が高く(玉から上がるか金から上がるかetc)、同時に長期戦になりやすい戦形は、本来序盤は時間を節約していくべきなのですが、コンピュータは往々にして、序盤の玉を囲う順序を考えたりして時間を浪費しがちです。統計的なデータは揃えていませんが、この記事を書いてる横でもQhapaqが相掛かりの中盤戦で時間を切らし始め、1秒将棋による逆転合戦をエンジョイしてる真っ最中です。かといって、序盤はそんなに考えるなよと下手に時間を調整すると、横歩や角換わりの急戦によく考えずに突っ込んで壮大な爆死を遂げたりもします。

コンピュータの時間管理が影で仕事をした例としては、電王戦finalでのapery vs 斎藤六段の試合も挙げられます。aperyは序盤から時間を割と均一に使うというコンピュータ的にとても正しい戦略をとっていたのですが、急戦になってしまい早くから形勢を損ねることになってしまいました。コンピュータ的には「相手がこの局面で使える時間は俺と似たようなものだし、俺は悪くないと思ってるのだから大丈夫」と目論んでいたのですが、ほんの数手、物凄く深く読むべき瞬間をコンピュータは理解できなかったのです。斎藤六段はそこを理解し勝利をモノにしたのは人間の為す芸術と言えると思います。

 

・おまけ:汎関数微分を用いた最適な持ち時間配分の導出

持ち時間が一定の将棋では、ある手を長く考えると、別の手は早く指す必要があります。限られた時間の中で勝率を最適化するには、局面ごとにどれぐらい考えるかを決めねばなりません。

 時間を無駄にしている = 本来読むべき局面でない局面に時間を使っている = 無駄に読んだ局面と読むべき局面とでは同じ時間を費やしても得られる利得が後者のほうが大きい という思考実験をすれば、「無駄のない時間配分では、どの局面についても時間対効果が同じになっているのだろう」という予想を立てることができます。

汎関数微分をつかうと上記予想が正しいことが証明できます。数式で言えば、Y手目の局面について、X秒考えて正しい手がさせる確率がF(X,Y)であるとしたとき、正しい手がさせる確率の期待値を最大化させるにはF(X,Y)をXで微分した値がYによらず一定になるようにすればよいわけです。

 さて、前回の記事の検証によると、コンピュータが正しい手が指せる確率は、深さが浅い時は手の深さに線形になっているようです。N手読むのにかかる時間が2のN乗に比例する(最近のソフトは激しい枝狩で精々2手ぐらいしか枝を分けてないとどっかで読んだ)とすれば、時間を投資することで得られる利得は近似的には今まで消費した時間に反比例する(2^N-1 = 1+2+...2^N-1)ことになります。

これに気づいた時、私は「やった、これはtimemanの革命やで」と喜び勇んだわけですが、実際にstockfish(やそれを元にしたソフト)のソースコードを見ると、読みを打ち切る条件が手が変わる確率が消費時間の定数倍を下回った時になっていたという。