将棋AIの開発者と話していて、置換表の仕組みの詳細を把握している人が少なそうだった。置換表は、将棋AI以外のゲームAIでも使える汎用的な技術である。この技術が誰も口伝しないままロストテクノロジーになってはいけないと思い、私が重い腰を上げ筆を執る次第である。

// 別のところに向けて書いてた記事なのでQ & A 方式になってて読みづらくて申し訳ない。

Q. この記事の対象者は？

A. ゲームAIに興味のあるすべての人(将棋AI固有の話ではないです)

Q. 置換表とはなんですか？

A. 探索した情報を保存しておくテーブルである。置換表(transposition tableの訳語)は、将棋AI界隈では、俗に「ハッシュテーブル」や「ハッシュ」とも呼ばれる。

Q. なぜ置換表が必要になるのですか？

A. 探索した情報を保存しておきたいからである。

Q. どんな情報を保存するのですか？

A. その局面におけるbestmove、static eval、search eval、depthなどを保存しておく。

Q. bestmoveとはなんですか？

A. 直訳すると「最善手」のことだが、無論、本当の意味で最善であるはずもなく、いまの探索状況において、その局面で最善と考えられる指し手という意味である。

Q. static evalとはなんですか？

A. static evalとは、評価関数(evaluation function)が返してきた値のことである。評価関数は局面(盤上の駒の配置+手駒+手番)を渡すと、形勢を評価して数値化したものを返してくれる(数学的な意味での)関数である。

Q. search evalとはなんですか？

A. 探索した時の評価値である。

Q. 探索とは？

A. やねうら王では探索の根幹にalpha-beta法(alpha-beta pruning)を採用している。

アルファ・ベータ法(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%82%BF%E6%B3%95

alpha-beta法は、英語で「alpha-beta pruning」と書くことからもわかるように、pruning(枝刈り)の手法の一種である。将棋AI界隈では、俗に「αβ探索」などとも呼ばれ、探索手法の一種であるかのように思われている節もあるが、ある条件を満たす時に安全に枝刈りできるという枝刈り手法であるというのが本当のところである。

alpha beta法で探索すると開始局面から指定のdepth(深さ)で探索した時のベストな評価値が返ってくる。これは先手と後手が最善を尽くした時にたどり着く末端の局面(leaf node)のstatic eval(評価関数を呼び出して返ってきた値)である。これをsearch evalと呼ぶ。

Q. depthとは？

A. alpha-beta法での探索の時の深さのことである。この深さの分だけ探索する。

Q. つまりdepthは注目している局面からのどこまで先の局面を探索するかを示す手数のことですか？

A. その通り。局面を「頂点」(node)だと考え、指し手を「辺」(edge)だと考えると将棋の局面の遷移は、グラフ理論で言うところの有向グラフである。depth 5なら、注目している頂点(局面)から辺を伝って4つ離れた(距離4の)頂点まで調べるということである。

Q. つまりalpha-beta法の疑似コードにある関数の引数のdepthとは、その局面から残りdepthだけまだ探索するという意味になりますか？

A. その通り。将棋AI界隈ではこのdepthのことを「残り探索深さ」とも呼ぶ。

Q. alpha-beta法で探索する時に置換表を用いると何が嬉しいのですか？Wikipediaのコードには置換表に保存するコードが出てきませんよね？

A. このalpha-beta法は、その局面の指し手を順番に試していくのだが、なるべく早い段階で良い指し手に巡り会えれば、そのあとの探索が端折れることがある。例えば詰将棋で言うと、開始局面で1つ目の指し手で詰むことがわかれば、2つ目の指し手を試行する必要がない(詰むとわかっているので1つ目の指し手で十分)というような理屈である。

ゆえになるべく早い段階で良い指し手を知りたいわけである。

この良い指し手を得るために、指し手を良い順番に並び替える「指し手オーダリング」(move ordering)を行う。指し手にスコアをつけて、その良い順番に試すということである。指し手オーダリングだけで本が数冊書けるほどのボリュームがあるので、その技法について書くのはまたの機会に譲るとして、一番効果が大きなアイデアとしては反復深化と組み合わせるというものである。

Q. 反復深化とは？

A. 反復深化というのは、alpha-beta法で探索する時に、少しずつ読みを深くしていくというものだ。簡単に擬似コードを示すと次のようになる。

Q. そのコードだと例えば開始局面ならば10回調べることになりません？これって相当無駄ではないですか？

A. そこで置換表が役に立つ。置換表に前回のiteration(上のコードで言う前回のiteration_depthの値)の時に探索した結果を保存しておくのだ。将棋のようなゲームには、浅い探索depthで探索した時のbestmoveと深い探索depthで探索した時のbestmoveが同じであることが多い。3手先まで読んで飛車をただ取りできる指し手が見つかったとして、5手先まで読む場合にもやはり3手目で飛車をただ取りする変化を選ぶのが最善である、みたいな理屈だ。

Q. つまり置換表には前回の反復深化のiteration時の指し手が登録されているということですか？それは何の役に立ちますか？

A. 上で書いたようにalpha-beta法では早い段階でいい指し手が見つかると残りの枝を枝刈り(pruning)できることがある。つまりは、残りの指し手を調べなくて済むことがある。

Q. 枝刈りできるのでトータルで見ると上の無駄は実は無駄ではないということですか？

A. その通り。

Q. ある局面についての情報を保存しておくと役に立つことはわかりました。そこになぜ置換表が必要になるんですか？局面の構造体があったとして、そこに指し手とその指し手を選んだ時に遷移する局面へのポインタがあれば十分ではないですか？つまり、疑似コードで言うと次のようなコードです。

A. 実際、ふかうら王やdlshogiのように1秒間に10万局面程度しか探索しないならそういう方法でも十分である。

Q. ええと、やねうら王では1秒間に何万局面探索しているんですか？

A. 3995WX(AMD Ryzen Threadripper PRO 3995WX)で、1秒間に8000万局面程度。

Q. 「1秒間に1億手を読む」とされるコンピューターと比較し、(それを上回る読みであるから)「1秒間に1億と3手読む」と言われた佐藤康光九段の話を思い出しました。

A. あれは2017年の話なので当時はまだ1秒間に1億手は読めてなかったけどね。

Q. それで1秒間に1億局面調べるとして、1億=0.1G(ギガ)ですよね。上のPosition構造体のサイズですが、将棋のある局面の指し手の平均は100手程度と言われていますから、指し手Moveが2バイト、Position*(ポインター)が8バイトで10バイト×100手で1KB程度ですね。0.1G×1KB = 100GB。一秒ごとに100GBあれば十分…って大きいか。

A. ある局面で100秒思考するのに10TB必要になるね。

Q. じゃあ、static_evalとsearch_evalとbestmoveだけの次のような構造体を用意して、この構造体に対してC++のunordered_mapなどで紐づければどう？

A. お手軽にはそうすることもある。実際、CodinGameなどのオンラインのゲームAIコンテストではそういうコードを書いている人も多い。しかし、unordered_map、言うほど速くはないのでもっと速い方法が望まれる。

Q. じゃあ、固定配列で次のように確保して、局面からこの配列の添字(index)を何らか求めてそこにアクセスすれば？

A. それが置換表のアイデアそのもの。局面からindex(配列の添字)を求めるのに何らかのhash関数を用意する必要がある。

Q. 更新コストの小さなhash関数がいいね。

A. それがZobrist Hashである。

【決定版】コンピュータ将棋のHASHの概念について詳しく
// Zobrist Hashの説明もここにある。
https://yaneuraou.yaneu.com/2018/11/18/transposition-table-details/

Q. でもこの方法だとhash衝突して異なる局面なのに同じindexのところに格納しようとしたりしない？

A. する。これを回避する仕組みが必要である。

Q. hash関数が64bitの値を返すなら、その下位16bitをindexとして、残りの48bitをPositionInfoに格納しておき、この48bitが一致するか比較すれば、本当にその局面の情報なのかがわかるね。(2の64乗分の1でそれでも間違って一致してしまうが)

A. その部分は、やねうら王は実際それに近いコードになっている。

Q. でもその時に他の局面の情報があると書き込めなくて困らない？反復深化で調べていくのに価値の高い情報が格納されていて、それを潰してしまうと、反復深化の効率激減しない？

A. その通り。だから、同じindexを示す局面の情報を複数格納できるようにしてある。それがTTClusterという概念で、これはTTEntry(局面1つの情報)を複数個格納しておける。

Q. つまり、こんな感じになっているということ？

A. そう。それが置換表の正体だ。

Q. でもこれだと、TTEntryに空きがない時にどの情報を潰していいか迷うよね。

A. 価値の低い情報を潰すよりない。

Q. 価値の低いということは、例えば、depth(残り探索深さ)だよね。alpha beta法のalpha_beta関数の引数のdepthが仮に7なら、この関数を抜ける時には7手先まで調べたということだから、この7をTTEntryに書き出しておく。いまTTClusterのTTEntry[0],[1],[2],[3]に空きがない時、どれかを潰さないといけないけど、このdepthが大きいほうが調べるのにたくさんのコストを要したということだから、大きいほうを残しておきたいよね。だから、空きがない時は、TTEntry[0].depth , TTEntry[1].depth , TTEntry[2].depth , TTEntry[3].depthの一番小さいTTEntryを選んでそこを潰す。これでいい？

A. 正解。やねうら王ではそういうreplacement strategy(新しい情報を格納するために価値の低いTTEntryを探し置き換える戦略のこと)を採用している。

Q. ああ、それがさっき言ってた置換表に書いてあるdepthの正体か。

A. その通り。

Q. だけどこれ、対局が進んで次の局面を思考する時はどうなるの？普通対局だと2手先の局面が来るよね。

A. そこで出てくるのが置換表の世代(generation)という概念である。次の局面が来る時、この世代を加算する。

Q. あー、わかったかも。2手前の局面で7手調べた情報の価値は、現局面から5手調べた情報の価値と同じぐらいだから、TTEntry.depthを比較するのではなく、置換表世代をgenとして、TTEntry.depth – gen * 2 を比較する感じ？

A. 次の局面が来るときにgenをインクリメント(1足す)してるということで？

Q. うん。そのつもり。

A. やねうら王では、置換表の世代カウンターは、新しい局面について思考する時に8足してるね。これはStockfishというやねうら王が参考にしているチェスのソフトがそうなってるからだけど。

Q. えー。8足すのか。つまり、(genをインクリメントしているとしたら)、TTEntry.depth – gen * 8を比較してる感じだよね。2手前に15手調べたものと現局面から7手調べたものとが同じ情報的な価値があるとみなしているということだよね？あー、そうか。2手前の15手先って、現局面の13手先とは限らないんだね。

A. そういうこと。現局面の13手先に2手前の15手先の局面がすべてあるとは限らないからね。

Q. そう考えると確かにTTEntry.depth – gen * 2はおかしいわけか。もっとペナルティを与えておかないと。それがどれくらいが適切かはわからないけども。

A. そうだね。Stockfishはこういうところ、変数にしておいて実際に自己対局させてその変数の値を最適化するテスティングフレームワークがあるんだ。おそらくこの8という数字は、テスティングフレームワークによってこれが最適であると判明した数値だよ。

Q. この8は、ゲームによって違ってくるよね。

A. うん。ゲームの性質や、探索の性質によって違う定数になるだろうね。

Q. 置換表の世代を8ずつ足していくのはわかったけども、これ、どこかで0に戻らない？何バイトなの？

A. やねうら王では1バイト。つまりは、0から255までしかカウントできない。

Q. それ困らない？あー、depthも128には収まるから、引き算したあとuint8_tとみなして比較するわけか。

A. そうそう。そんな感じ。

【以下、やねうら王に特化した話】

Q. いまやねうら王のGitHubのソースコードのtt.cpp見たけど、これ探索スレッドごとにTT用意する機能あるね。これなんで必要なの？

A. 教師局面の生成をする時に、スレッドごとに異なる局面を探索したいから。

Q. 全部のスレッドで1つの局面を探索するのでは駄目なん？

A. alpha-beta法を用いる並列探索では、探索効率は並列数の平方根ぐらいの実効(実際にはもう少し良い)と言われているので全部のスレッドで1つの局面を探索させるのはもったいない。

Q. えーつまり16スレッドあっても4倍にしかならないってこと？

A. うん、そう。

Q. それならプロセス(実行ファイル)わけて生成したらどう？こんなプログラムぐちゃぐちゃになるより、一つのプロセスでは1つの局面を思考させたほうがよっぽど楽なのでは？

A. それはそうなのだが、そうすると128プロセスで教師生成することになって…。

Q. それ実行速度的なオーバーヘッドあるかな？それぞれのプロセスがファイルに書き出すから、128並列でファイルに書き出すことになってファイルI/Oで少し損をしそうだけど。

A. 評価関数パラメーター、これが、以前はファイルサイズが1GB近くあって、それを丸っとメモリに読み込むからメモリを1GB必要とした。128プロセス起動するとそれだけで128GBで…。

Q. いや、それおかしいよ。Windowsのshared memory(共有メモリ)使えば、1つ分で済むよ。

A. やねうら王にはその機能もあったのだけど、Linuxでも同様に動かないといけなくて…都度そういうコードをLinuxでも動くように移植するのに疲れて。

Q. バイナリ(実行ファイル)に埋め込めばいいよ。バイナリに埋め込まれていれば、実行ファイル自体は複数プロセスであっても共有されるので物理メモリは1つ分しか消費しないよ。

A. やねうら王プロジェクトでは、Windows向けには水匠5の評価関数ファイルを埋め込んだバイナリを配布してるけども、評価関数の差し替えができなくてあまり便利じゃなさそうで。ビルドプロセスも工程増えるし。

Q. なるほど。一つのプロセスで異なる局面を並列的に思考させたいという動機はわかった。だとして、置換表を並列数だけ用意するのってコードがぐちゃぐちゃになって嫌じゃない？

A. 嫌か嫌じゃないかで言うと嫌なんだけど、これどうしようもないよね？置換表世代、いつ進めるの？

Q. 各スレッドが新しい局面について探索するタイミングで…だと、128並列だとどんどん世代が進んでしまって、価値のある情報が(価値がないとみなされて)上書きされてしまうのか…。

A. その通り。

Q. 進めなければいいんじゃない？

A. それだと、TTEntryにdepth 31 , 30 , 30 , 10 みたいな状態になって、毎回この10のところが潰されるよ。

Q. あー、それだと実質的にTTClusterにTTEntryが一つしかないのと同じか。hash衝突して同じTTClusterが選ばれるごとに前の情報潰されちゃうわけだから探索効率すごく悪そう。

A. だね。その場合、TTClusterなんて採用しないほうが(メモリが4倍置換表に割当てられて)まだマシなぐらいで…。

Q. 教師生成時に置換表が並列数だけ必要だということはわかった。置換表というか、置換表の世代カウンターがスレッドごとに必要なんだね。だとして、これ、置換表をスレッドごとに持たせるのに、やねうら王ではLEARN版としてビルドした時しか有効にならないよね。これなんで？

A. やねうら王は当初、OOP(オブジェクト指向プログラミング)っぽく書いていたのだけど、Stockfishの探索部を参考にするようになったころから、その書き方だとStockfishとの差分が大きくなって、メンテナンスしていくのがしんどくなったんだ。なるべく差を小さくしようと思い、結局、純粋なOOP風に書くのをある程度諦めて現在に至る。

Q. やねうら王とふかうら王とC++の #ifdef で切り替えてあって同時に一つのプロセス空間で動かすの、すごく大変くさいよ。

iPadでやねうら王とふかうら王を同時に動作させる 標準入出力衝突回避編
https://select766.hatenablog.com/entry/2023/05/02/190100

A. それは本当に申し訳ない。

【まとめ】

・本記事ではゲームAIで使える(ことがある)置換表の詳しい仕組みとreplacement strategyについて解説したよ。
・やねうら王で教師生成部を自作する時は、LEARN版でビルドするか、1プロセス1スレッドでの探索にして並列数分だけプロセスを起動するかしよう。