やねうら王 PR 文書― スーパーテラショック定跡生成手法について ―やねうら王チーム要

旨

近年、Deep Learning 系の将棋ソフトはプロ棋士の研究にも取り入れられてきている。Deep
Learning 系の将棋ソフトは従来型の将棋ソフトに比べると序盤戦術に長けていると言える。本論
文手法は、その優れた序盤感覚のソフトで大規模な定跡を自動生成しようという試みである。

現在においては、もはや人間の棋譜は定跡生成には直接

第１章 従来の定跡生成手法は使えないと言っていいだろう。

第 1 節 人間の棋譜から第2節

floodgate の棋譜からコンピュータ将棋も 2010 年ごろまでは人間が定跡を棋譜の数で言うと floodgate(コンピューター将棋ソ手で入力していた。特にプロの棋譜は神聖視されており、フトの対局サーバー) 4の棋譜を用いるというのは魅力

プロの棋譜に出現した 32 手目までの手順をそのまま定的である。floodgate の棋譜の数は 50 万棋譜以上存在

1

跡としているソフトも多数存在した。GPS 将棋[2009-]

するし、その時代時代の最新のソフトが参加しているたなどもプロの棋譜の手順をそのまま定跡化しているよめ、floodgate の棋譜を用いればお手軽かつそれなりのうであった。

精度で生成できる。2015 年ごろまでわりと流行していた手法である。

しかしながら、プロの棋譜には 76 歩 34 歩 68 銀 88 角成(角のタダ取り)で投了というような棋譜も混じってfloodgate の棋譜から定跡を生成する場合、Bonanza

おり、プロの棋譜をそのまま定跡として採用していたの narrow book の考え方を踏襲し、定跡上の各局面では、

2

Bonanza[2005-] がこの手順を指すということで話題になるべく floodgate で採用された回数が多い指し手をなったこともある。

選択する。採用回数が多い指し手ほどその信頼性が高いと考えられるからである。Apery[2015]5や、やねうら王[2014]6の standard_book.db などに見られるようにこの

そこで、その棋譜の指し手が指された回数を集計し、指された回数が多かった指し手を指すことでこのよう方法で作成された定跡を搭載する将棋ソフトはわりとな悪手を指さないようにするような試みがあった。

多い。

Bonanza で言うと narrow book というエンジンオプショ
ンである。

しかし採用回数ベースで定跡を生成する場合、棋譜の数が少ないとその局面での採用確率が 100%であってもあるいはプロの棋譜に対して自作の将棋ソフトで 1

信用ならないという欠点がある。例えばその局面を含む

局面 0.1 秒や探索深さ 12 など短い時間(or 深さ)で思考

棋譜が 1 つしかない場合に、その棋譜の指し手を定跡とさせ、悪い評価値の指し手だけを取り除くというハイブ

して登録して良いのかという問題がある。

3

リッドな手法が取られることもあった。習甦 [2014]がそのようなアプローチを取っていた。

また弱いソフトの指し手が混じっている場合、それがどれほど信用できるのかという問題もある。ひどい例でプロの棋譜を用いる場合、インターネットで入手でき言うと、定跡を抜けた直後の局面で先手必敗(評価値

る棋譜の数が限られている(4 万局程度)というのがある-600)ということもあった。

し、トッププロより将棋ソフトの方が棋力が高くなった

1

4

Wikipedia 「GPS 将棋」:
https://ja.wikipedia.org/wiki/GPS%E5%B0%86%E6%A3%8B
2
Wikipedia「Bonanza」:
https://ja.wikipedia.org/wiki/Bonanza
3
Wikipedia「習甦」:
https://ja.wikipedia.org/wiki/%E7%BF%92%E7%94%A6

floodgate :http://wdoor.c.u-tokyo.ac.jp/shogi/floodgate.html
5
Wikipedia 「Apery」:
https://ja.wikipedia.org/wiki/Apery
6
Wikipedia 「やねうら王」:
https://ja.wikipedia.org/wiki/%E3%82%84%E3%81%AD%
E3%81%86%E3%82%89%E7%8E%8B

2

あと、floodgate での対局は、序盤での持ち時間を節約するために何らか定跡を用いて対局させることが多いようで、実際の勝率は低いのにわりと採用されている

第3節

序盤の指し手というのが存在していることが dlshogiの山岡の研究からわかっている。7

人間+ソフトのハイブリッド

ある程度の棋力を有する人間が、将棋ソフトを使いな
がら、将棋ソフトで上位にくる指し手の変化をすべて調

そこで、floodgate の棋譜を用いる場合、勝率ベース

べ、そしてその定跡の末端の局面から対局させて勝率をで指し手を選択するという方法も考えられる。その指し計測し、形勢が互角であっても勝率が悪い局面への指し手を指したあと、実際に勝っているのかという点を考慮

手は取り除くという、気の遠くなるような作業を経て作しようというわけである。この方法は、わりとうまく行られた定跡がある。

くのだが、強いソフトが採用している定跡を過度に信用してしまう問題がある。例えば、floodgate には初手 38

このような定跡としては suimon_fan 氏が公開されて銀に固定したソフトや、必ず振り飛車にする定跡を搭載

いる s-book_black8が優秀なことで有名だ。WCSC31 で優した将棋ソフトが参加していた。おそらくそのような序勝した elmo[2021]も手作業による定跡であり、いまだ

盤定跡を用いた時に、普通に指すのに比べてどれくらい上位ソフトの開発者でもこのような手作業での定跡生

レートが落ちるのかを見たい開発者がいたのであろう。

成を行っている開発者は少なくはない。

このような棋譜が混じっている場合、勝率ベースで定跡を生成する場合でも信用ならない指し手が紛れ込む可

第4節

能性はいくらでもある。

自己対局型自動生成

そこで出てきたのが定跡の自動生成という技術であfloodgate の棋譜に対しても自作の将棋ソフトで短いる。2015 年ぐらいから流行りだす。ただ、当時の将棋

時間で思考させ、明らかに悪い評価値の指し手は取り除

ソフトは序盤はわりと精度が低かったので、実際に序盤

くというハイブリッドな手法が取られることもあった。

で思考させて、良い評価値の枝を掘っていく(思考させ習甦の方法に倣い、やねうら王[2015]もそのような方法て定跡局面として登録していく)のは、わりと危なっかを用いたことがある。

しいところがあった。

しかし、floodgate の棋譜上に数回しか出現しなかっ

そこで、自己対局をして勝率の良いところを掘り進めた局面の指し手は信用ならないので、30 回以上出現していくという手法が用いられることが多かった。とりわ

た局面についてのみに絞って定跡化しようなどとする

けそのなかでも優秀だったのは shotgun 定跡9と呼ばれと、局面数はかなり減ってしまい、定跡として十分な局るもので、SDT5(第 5 回将棋電王トーナメント)で面数を確保できないという問題があった。

shotgun というソフトが採用し(shotgun は SDT5 準優勝)、
その後、WCSC28 で Hefeweizen がそれを受け継いだ。10

いずれにしても棋力にばらつきのある外部の棋譜に頼る以上、その信頼性を担保するのが難しく、データも
8

suimon_fan : https://twitter.com/mztn7_fan
芝世弐 , コンピュータ将棋における定跡生成法の一提案 :https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_uri&item_id=192055&file_id=1&file_no=1
10
芝世弐 , Hefeweizen WCSC28 PR 文書
https://www.apply.computer-shogi.org/wcsc28/appe
al/Hefeweizen/appeal.pdf

無限に用意できるわけではないので定跡の局面数にも9

自ずと限界があった。

7

山岡忠夫 「floodgate の序盤 3 手の統計」
https://tadaoyamaoka.hatenablog.com/entry/2021/1
1/06/010026

3

shotgun の方法は簡単に言ってしまえば異種ソフトを跡ツリー上の各局面からの PV(最善応手列)が得られる。

ローカル環境で対局させ、勝率ベースで定跡化するといそれをその各局面の最善手とした定跡 DB ファイルを別うもので、相手が既知の将棋ソフトの場合、わりと高い途出力する。これがテラショック化コマンドの概要であ確率でその定跡の指し手を指すようである。

る。

Hefeweizen の手法はほぼノーメンテナンスで定跡がこのテラショック化コマンドは、やねうら王[2019]

生成していけるということで、定跡自動生成系としてはで実装され、このテラショック化した定跡を用いてやね

わりと高い評価がなされているが、自己対局ベースなのうら王は WCSC29 で優勝した。

で生成にとても時間がかかることや既知のソフト以外のソフトだと定跡から外れやすいという欠点はあった。

ところが、その大会後に判明したことだが、Minimax
探索は末端の評価値が root(定跡の探索開始局面 = 初生成のためにとても時間がかかるのでは、定跡に登録

期局面)まで伝播してくるので、ノイズに極めて弱いとできる局面数が稼げないことになる。いくら精度が高くいう性質がある。従来の将棋ソフト(非 Deep Learning

優秀であっても相手より先に定跡が尽きてしまったの系の将棋ソフト)では、評価値にずいぶんノイズが乗っでは、大会では相手の方が多くの持ち時間を残したままているようで、テラショック化には向かないという意味

終盤に突入してしまい、結果、不利になってしまう。

があった。実際、やねうら王が WCSC29 で用いた定跡と前述の s-book_black とを対局させてみたところ、定跡

このように定跡 DB はその登録されている指し手の質、を抜けた局面でやねうら王の定跡側が不利な局面であ

精度はもちろんのこと、なるべく実戦で実現しやすい局った。

面が数多く登録されていることも重要である。
また、上の手法は、与えた棋譜ファイル上で Minimax
探索のようなことをやっていることになるわけだが、こ

第 5 節 Minimax 探索型(テラショック化)の時、与えた棋譜の指し手しか先後ともに指さないといどんな方法で定跡を生成するにせよ、
その定跡の leaf

う暗黙の仮定をしていることになる。これはじゃんけん

node(末端の局面)での評価値が得られているなら、定跡で言うとグーが封じられているようなもので、その状態のゲームツリー上で Minimax 探索を行えば、先後が定跡で(グー、チョキ、パーすべてを使える相手に)勝てるの上の指し手で最善を尽くした時に到達する leaf node がかという意味もある。

確定する。
テラショック化という発想自体はさほど悪くなかっ11

やねうら王では、これをテラショック化と呼んだ。 やたのだと思うのだが、以上のように明らかな欠点も抱え

ねうら王[2017]には与えた棋譜の局面で思考させ、定跡ており、従来型のソフトには荷が重いと言わざるを得な

DB 上の各局面に評価値をつけるコマンドをすでに用意かった。

していたので、このコマンドを用いて、まず floodgateの棋譜などを与え、各局面に評価値をつける。その後、

第6節

その定跡 DB をテラショック化することができれば、定第一章まとめfloodgate の棋譜から勝率の高かった指し手のみを選んで定跡化するのはさほど悪くないものの、floodgate

11

やねうら王ブログ 「テラショック定跡の生成手法」 :https://yaneuraou.yaneu.com/2019/04/19/tera-shock-book-generation/の棋譜に出現した指し手しか指せないという意味で、グーしか出せないジャンケンにも似ている。今後、将棋ソ

4

フトの序盤がシビアになってくるとそんな方法は通用しなくなってくるだろう。

結局、現時点で定跡の自動生成手法で成功しているのは shotgun 定跡ぐらいのものだが、実際にローカル対局を行うので費やすリソースのわりに掘れる(登録できる)定跡の局面数に自ずと限りがある。

テラショック化は悪いアイデアではなかったが、従来の将棋ソフトには評価値にムラがある(ノイズが乗っている)ので、意図通りには機能しない。また PV(最善応手列)の周りを重点的に掘りたいのに、事前に与えた棋譜の局面しか掘れず、テラショック化してからその定跡を用いて自己対局させて、その対局棋譜を与えて思考させて、またテラショック化する、というようないイテレーション(反復)でしか定跡を掘っていけないので思考
対象局面の選出に非常に手間と時間がかかる。

5

ので、「自分だけがグーの出せないじゃんけん」のよう

第 2 章 スーパーテラショックになってしまう。

定跡生成手法テラショック化した定跡を用いて、実際に対局させ、その対局棋譜上に現れた局面について再度思考させる
ようなイテレーション(反復)も考えられる。やねうら王

第 1 節 Deep Learning 系思考エンジンの[2019]ではそうやって定跡を生成していたのだが、テラショック化自体に時間が相当かかるし、ローカル対局に利用も時間を要する。この方法だとあまり PV まわりを掘り

従来型の非 Deep Learning 系の将棋ソフトの序盤には進められない。

評価値にムラがある(ノイズが乗りやすい)、不正確であ
そこで、定跡ツリー上で、αβ探索13を行い、PV(最善るという弱点があった。

応手列)を取得し、その leaf node(末端の局面)を展開
そこで定跡の生成には Deep Learning 系の将棋ソフト

する(思考対象とする)ような仕組みを用意することにを用いることにした。現在、ソースコードが公開されてした。

いる Deep Learning 系の将棋ソフトのなかで最強である
dlshogi12の互換エンジンとしてふかうら王という将棋

これをここでは「(次に思考すべき局面の)選出」と呼ソフトを開発した。

ぶことにする。選出された局面をふかうら王の思考エンジンを用いて思考していく。これをここでは「思考」と今回の定跡生成では、このふかうら王で 1 局面 1 秒程呼ぶことにする。つまり、「選出」と「思考」。今回の度思考させる。Deep Learning 系の将棋ソフト、特にふ定跡の自動生成はこの二つで成り立っている。

かうら王では、思考させた局面のすべての合法手に対する評価値が得られる。なので、この得られた評価値をそ

第3節の指し手で 1 手進めた局面での評価値であると仮定して、有望そうな局面のみを効率的に展開していくことが選出の高速化と思考との並列化

この「思考」中にも「選出」を行わなければ思考エンできる。

ジンに遊び時間が出来てしまうから、「選出」と「思考」
は並行して行える必要がある。また「選出」自体を高速

そのあと任意のタイミングで定跡 DB に対してテラシ化しないと、思考エンジンに遊び時間ができてしまう。

ョック化を行い、最終的な定跡 DB を得る。これがスーパーテラショック定跡生成手法の骨子である。

そのためには、
1) 思考エンジンが思考中にも次に有望そうな局面を何局面でも選出できること

第 2 節 思考対象局面の選出

2) 選出が思考より遥かに短い時間で完了すること

どの局面を思考対象として選ぶかという問題がある。

この二つが必須条件である。

外部から棋譜を与えてその局面を思考させるという方法もあるが、それだと与えた棋譜の局面しか思考しない

13

Wikipedia : Alpha beta pruning :https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_
pruning12

dlshogi GitHub :https://github.com/TadaoYamaoka/DeepLearningShogi

6最終的な局面数は 1500 万局面程度を想定している。1

上記のプログラムの局面 1 秒で間断なく思考しつづける時、1 日 86400 局面

foreach m in 全合法手:思考できるから、半年で 1500 万程度であるという想定の直後に、pos を m で進めた局面が思考中であるなら、である。

この指し手 m はないもの(非合法手)として扱えば、次に良い評価値を持つ leaf node が探せるはずである。基本

この 1500 万局面の定跡をメモリ上に読み込んでいる的な考えかたはそれだけなのだが、これを高速に行える

状態においても 1 回の選出が 1 秒未満で完了する必要が必要がある。

あると考え、今回はそれを目標に開発を行った。
やねうら王では、局面に対応する hash key として
Zobrist Hashing という技法を用いている。15

また、そこで今回、

やねうら王には、ある局面で指し手 m を指した局面に対1)のために ranged alpha beta search という技法を応する hash key を求める関数も用意されている。

開発した。
2)のために 高速化のための探索上の工夫を複数実施

これを用いれば実際には盤面を動かさずして、指し手した。

m を指したあとの局面の hash key が得られる。
この hashkey が思考中の局面集合のなかにあれば、ないものとして扱う。つまり、さきほどの部分は、次のようなコード

第 4 節 ranged alpha beta search

を書いてある。

まず、典型的な alpha beta 探索の疑似コードを示す。
これはゲーム木探索の教科書などに載っている。14
foreach m in 全合法手:// 探索中のノードの hash key 集合に m を指した局面の hash key が含まれるなら、m をないものとして扱う。
if searching_nodes.contains(pos.key_next(m)):
continue// pos : 局面// alpha : alpha beta 探索の alpha 値// beta : alpha beta 探索の beta 値
Value search(pos,alpha,beta):
foreach m in 全合法手:
if pos を m で進めた局面が定跡 DB 上にある:
pos.do_move(m) // m で 1 手進める
value = -search(pos,-beta,-alpha)pos.undo_move() // 1 手戻す
else:
value = pos の局面で m を指した時の評価値// 思考した時に全合法手に対応する評価値が得られている。
if alpha < value:
if beta <= value:
return value # beta-cut
alpha = value# update alphareturn alpharanged alpha beta search の基本的なコードは以上である。

この疑似コードの searching_nodes は実際のプログ
ラムでは C++の std::unordered_set を用いている。そのためこの集合に含むかどうかの判定は極めて短い時間で行われる。

hash key だとたまたま衝突してしまうと困るので、本来は局面を一意に識別できるものを使うべきである。
14

Wikipedia 「アルファ・ベータ法」:
https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%
E3%83%95%E3%82%A1%E3%83%BB%E3%83%99%E3%83%BC%E3%8
2%BF%E6%B3%95

15
Zobrist hashing :https://en.wikipedia.org/wiki/Zobrist_hashing7

そのようなものとしては SFEN 文字列16やそれを 256bit

尤も、元があまりに悪い評価値であれば 100 点を加点17に符号化した PackedSfen などがあるが、その変換コスしたところで評価値としては悪いままであるから、このトは馬鹿にならない。

leaf node が選出されることはない。このように、与えた棋譜であっても展開するに値しないならばそこ以上

やねうら王では、hash key を通常使う 64bit のみならは掘らないというのも自動的に上のコードでなされる

ず、128bit、256bit に変更する機能があるので、本手ので、有望な枝だけが延長される。このため大量の棋譜

法では、128bit の hash key を用いることにした。このを与えてもそのすべての局面について思考するわけで場合、天文学的な確率でしか hash 衝突は生じないので、はなく、優れた局面の「選出」性能を発揮する。

定跡生成の用途で用いるならば問題ないと言えるだろう。

第 6 節 千日手局面回避のテクニック
本手法では、千日手局面に到達した時のスコアは 0 として扱っている。通常の探索においては先手は、初期局

第 5 節 棋譜上の局面を掘る面においてプラスの評価値がついている。後手は(先手が初手で最善手を指した場合)自分の局面でマイナスの本提案手法の目的は、外部棋譜を用いず、自分の思考

評価値がついている。すなわち、ranged alpha beta

エンジンのみでノーメンテナンスで低コスト(少ない計

search では先手は千日手を回避しながらプラスの評価算量)で定跡を自動生成することにあるが、実際には、値の局面に辿り着きたいし、後手はマイナスの評価値を与えられた棋譜の局面を掘り進めたいこともある。

避けるため千日手を目指すような探索をしていることになる。

そのため、さきほどの ranged alpha beta search の疑似コードの以下の行

この手法を実装する上で難しい点として、千日手まわvalue = pos の局面で m を指した時の評価値

りの処理が挙げられる。そこまでの経路(手順)と同じ局の続きに以下のコードを追加する。

面に循環してしまう時、それをどのように取り扱うかという問題がある。

// kif_nodes:棋譜上に出現した局面の hash keyの集合
if kif_nodes.contains(pos.key_next(m)):
value += 100

局面の合流を取り扱わなければ千日手に関してあまり難しい問題は発生しないのだが(Deep Learning 系でMCTS を用いる将棋ソフトや囲碁のソフトはそうなっているものが多い)、定跡の生成で合流を取り扱わない場
合、将棋では特に角換わりで手待ちを繰り返して同じ局棋譜上に出現した局面であれば、leaf node の評価値に面に合流することが多く、そこで組み合わせ爆発を生じ加点している。これにより、ranged alpha beta searchてしまい、そこ以降の定跡を掘れなくなってしまう。

を行う時にこの leaf node は優遇される。
このため、定跡生成においては局面の合流を適切に取り扱う必要があるが、合流を取り扱うと千日手の問題が16

SFEN 文字列 「USI プロトコルとは」: http://shogidokoro.starfree.jp/usi.html
17
やねうら王では SFEN 文字列をハフマン符号化し、256bit にする機能が備わっている。これを PackedSfen
と呼ぶ。

出てくる。

8

そのため、今回、千日手局面を ranged alpha beta

β探索を行う現代の将棋・チェスのソフトで広く使われsearch で回避するための手法を開発した。次のようにている手法である。

行う。
PV node : PV(最善応手列)に関係する node に関する「思考」済みの局面が再び「選出」された時、それは探索。枝刈りはほとんどしない。

千日手手順でその局面に到達したものだと考えられる。

NonPV node : PV 以外の node に関する探索。枝刈り

これを banned nodes 集合と呼ぶ。PV が千日手である場

わりとする。

合、循環局面に至る指し手 m とその局面の hash key をペアで保持しておき、その組み合わせの指し手 m を非合すなわち、探索する時に PV node 用の探索モードと、法手として扱えば良いのである。

NonPV node 用の探索モードとの二つの探索モードがあると考えられる。PV はしっかり leaf node まで確認す

この状態で「選出」を行えば、自動的にその次に有望るが、NonPV node では枝刈りをできる限りする。PV(最な leaf node が得られるので、千日手局面が PV になり

善応手列)の読みが担保されていればまあいいだろうと続けて「思考」できないという状況は回避できる。

言う考えかたである。

これで「選出」時の千日手に関する問題は解決したの

例えば、ranged alpha beta search で指し手 m で１だが、テラショック化の時に千日手局面をどう解決する

手進めて再帰的に search 関数を呼び出すところ(次行)かと言う問題はある。これについては、第 9 節で詳しくは、
value = -search(pos,-beta,-alpha)述べる。

以下のように、最初にまず NonPV モードで探索をし、α値を更新しそうな時だけ真面目に PV モードとして探索しなおすというコードになる。
value = -search<NonPV>(pos,-beta,-alpha)if nodeType == PV && alpha < value:
value = -search<PV>(pos, -beta, -alpha)

第 7 節 PV and nonPV
ranged alpha beta search は、通常のαβ探索と同様に再帰的に行われるが、ある局面の探索結果を記憶しておき、二度目にその局面に訪問した時は前回の結果をまた、NonPV node では、前回その局面に訪問して探用いたい。

索した時の探索のスコア(best alpha)を記録しておき、それを用いて枝刈りを行う。

しかし、PV の leaf node は「選出」されたあと、「思考」が完了するまで無いものとして扱われるので、記憶

ただし、αβ探索では、探索窓として区間していた各局面での探索結果の値が不正なものとなっ(alpha,beta) の範囲に収まる値を探索している。探索てしまう。

結果がこの値の範囲内に収まれば、再度訪問した時に、その値をそのまま使えるが、そうでない場合はどうなる

そこで、PV と NonPV という考え方を導入する。これのだろうか？これについては次節で述べる。

は、チェスの Stockfish18というチェスのソフトなどα18Stockfish : https://stockfishchess.org/

9この時の最大を記録した value を search_value に保管

第 8 節 fail low/fail highし、bound upper(上界)とラベルをつけておく。

alpha beta 探索は、その局面で区間(alpha,beta)の間に収まる値のなかで最大のものを探す探索である。

次にこの node に訪問したとき、alpha がbeta 以上の値がひとつでも見つかれば、その局面の探

alpha >= search_value

索を即座に中断し、search 関数はその値を返す。このであれば、どの指し手 m でも alpha を上回らず fail状態は fail high と呼ばれ、そこで関数から抜ける枝刈

low が起きる見込みが高いので即座に関数から抜け出すりのことは beta cut と呼ばれる。

ことができる。(上界による枝刈り)

fail high が生じた時、この node のなかの指し手でまた、alpha < search_value < beta であるような

beta を超えるものが一つ以上あることはわかるが、こsearch_value の時は、search_value に bound_exact(正れを次回の探索の時に活かすにはどうすれば良いだろ

確にその範囲)のラベルをつけておく。

うか？
以上 3 つの枝刈りは NonPV でのみ行われる。そこで、これを解決するのが、bound lower(下界)という考え
19

方である。

その 3 つを合わせると以下のような枝刈りが search 関

fail high が生じた時の value(探索値)を数の先頭で行えることがわかる。

この局面の探索の値 search_value として保存しておく。
// すでに探索済みでかつ千日手が絡まないスコアが記録されまた、同時にこの値に関するラベルとして bound lower
であるとラベルをつけておく。

ている時の枝刈り。(NonPV 限定)
if nodeType == NonPV and search_value != VALUE_NONE:
if

実際は search_value 以上の値を記録する指し手 m がbound == BOUND_EXACT

あるかも知れないが、前回の訪問時にすべての指し手or (bound == BOUND_LOWER && search_value >= beta

を調べたわけではないので(beta cut したので)、そこor (bound == BOUND_UPPER && search_value <= alphareturn search_value

はわからない。ただ、少なくとも search_value の値を持つ指し手 m が 1 つは存在することは言えている。

再度訪問したときに、bound lower の値として
search_value が記録されていたとして、その時の探索

第 9 節 cyclic score

窓の beta がbeta <= search_value

循環スコア(cyclic score)とは千日手が絡んだ探索であるなら、beta cut して良いことになる。(下界にの値のことである。いかに NonPV node であっても循環よる枝刈り)

スコア(cyclic score)を信じない方が良いと思われる。

同様に、前回の探索で alpha を上回る指し手 m がなか

千日手は経路(そこまでの手順)に依存するので、経路ったとして、この場合 fail low と呼ばれる状態だが、が異なれば千日手にならないこともある。

19

英語では lower bound と呼ぶが、Stockfish などのソースコード上では BOUND_LOWER という定数ラベルが用いられているので、それに倣い、ここでは bound lowerと書く)

そこで、千日手を検出した場合、循環スコアにはcyclic フラグを立てて、子 node に cyclic フラグが立

10

っていれば、
その node の探索値 search_value は cyclic体が難しく、また、よほど工夫しないとメモリ空間的にscore であるとみなし、それを信用しない、とすることも現在の PC では厳しいので、今回の採用は見送る。

は出来る。
そこで本手法では、cyclic score に関してはきちん
ただ、こうしてしまうと組み合わせ爆発が起きるようと取り扱うことは諦め、NonPV では cyclic score であでテラショック化が現実的な時間で終わらなくなって

ろうと信用するような実装にしてある。

しまう。主な原因として次のような局面がある。

第 10 節 本手法の効果

60 手目付近で矢倉に組み上げて、先後ともに角を動かして手待ちを繰り返す。角の動かし場所は 5 箇所程度

本論文の手法で 80 万局面ほど思考し、テラショック

あり、先後で 5×5 の組み合わせがある。cyclic score

化を行ったスーパーテラショック定跡では、初手 76 歩だからと言って、前回の探索値が丸々使えないのでは、に対する 34 歩を明確に悪手(評価値-243)だと認定した。

こういう部分で組み合わせ爆発を容易に起こすようで22ある。
2 手目 34 歩はプロの将棋においても昔からよくある
df-pn による詰将棋にも似た問題があって、GHI 問題

オープニング(序盤)だが、本論文の手法は、この 2 手目という有名な問題がある。df-pn に出現する GHI 問題自の 34 歩を咎めるところまできている。実際、そのあと体は、千日手を検出した場合、そこまでの手順を hash

ソフト同士の対局によると先手勝率が 6 割程度であり、key 化したものを置換表に記憶しておくことで、GHI 問

このオープニングは現在プロの将棋でも減りつつある。

題自体は回避できる。20 21

23

しかし、テラショック化の時に GHI 問題の回避のため

また、第一章で紹介した s-book_black とスーパーテにそのように経路を保存しておいても上に書いたようラショック定跡とで対局させた場合、29 手目まで定跡にその経路自体が容易に組み合わせ爆発を起こすのでで進行し、スーパーテラショック定跡側の定跡が先に尽

無限に近い経路の数をその局面の探索結果の情報としきたが、その局面から最新の将棋ソフト(水匠 4)で対局て保持する必要が出てくる。

を引き継ぎ、思考時間を変えて 100 戦やってみたところ
55 勝 42 敗 3 引き分けであった。s_book_black は先手専これを回避するためには、千日手を検出した時、そこ

用定跡のため、スーパーテラショック定跡側は後手番でまでの経路で千日手に関与しない局面の hash key の集ある。後手番で勝ち越しているのでこれは十分な戦果で合(white list)と、千日手に関与する局面の hash key

あり、人間がソフトを活用し、長い時間と労力を掛けての集合(black list)とその時の探索の結果値をその局作り上げた定跡集を、外部棋譜を一切使わず、かつ、ノ面の情報として保存しておく必要がある。これは実装自ーメンテナンスな自動定跡生成により打ち破ったと言えるだろう。

Kishimoto, Akihiro and Martin Müller. “A
solution to the GHI problem for depth-first
proof-number search.” Inf. Sci. 175 (2005): 296-314.
20

22

やねうら王ブログ , スーパーテラショック定跡が76 歩に 34 歩を全否定 :https://yaneuraou.yaneu.com/2021/11/05/super-tera-shock-book/21

koumori-n , コウモリのちょーおんぱ 「詰将棋ソルバーにおける GHI 問題対策」
https://komorinfo.com/blog/and-or-tree-ghi-problem/23

山口 祐, ツイッター
https://twitter.com/ymg_aq/status/1456283886439
12908911

第 11 節 本手法のまとめ
現代にふさわしい定跡生成手法として、次のような手法の誕生が望まれていた。
・完全な自動生成(ノーメンテナンス)
・少ない計算資源で掘っていける・(floodgate の棋譜など)外部の棋譜を用いない
・(shotgun 定跡のように)対戦相手の思考エンジンを仮定しない・思考対象局面の選出が小さな計算コストで出来る・テラショック化のような定跡ツリー上で Minimax を行い、評価値の高い leaf node を目指す定跡が生成される

本論文で提案するスーパーテラショック定跡生成手
法では、これらの要求をすべて満たすことが出来た。

また、スーパーテラショック定跡生成手法は実際にやねうら王のソースコード上に実装し、公開もしている。
24

参考にしていただければ幸いである。

24

やねうら王 GitHub , makebook2021.cpp :https://github.com/yaneurao/YaneuraOu/blob/e620b
83d4ecb110120cf2abe4f4c806e0634c9b4/source/book/makebook2021.cpp

12