====== Bookとは ====== ~~SOCIAL_META: description = EdaxのBookについて調べてみました。 image = :edax:book_01.png ~~ Edaxについての情報を検索すると、Bookの作り方・学習方法に関するページが見つかります。Edaxを使い始めた時、こういったページを参考に棋譜を学習させたのですが、そもそもBookとは何なのかよくわかっていませんでした。まぁ、何となくは棋譜を元に評価値をうまく計算して記録しておいているのだろうということはわかるのですが、棋譜を元に何をしているのか、何をどう記録しているのかピンときていませんでした。「学習」という言葉からは、最近流行っている機械学習が連想されるので、評価値の出し方を何かチューニングするような効果があるかもしれず、自分で打った棋譜のように質の悪い棋譜を学習するとBookが劣化してしまうのではないかと心配したりもしました。 そんなわけで、今回はBookがどういうものなのかを調べてみました。 ===== Bookの構成要素 ===== Bookを知るためには、Bookファイルがどういうフォーマットになっているかを調べれば良いのではないかと思い、まずはフォーマットについて調べました。ただ、フォーマットそのものに興味がある方はあまり多くないのではないかと思いますので、フォーマットの説明はこの記事の後ろの方に載せておきます。フォーマットを調べることにより、Bookがどういう構成要素から成り立っているかがわかりましたので、まずはそこから紹介してみたいと思います。 {{ :edax:book_01.png?direct |Bookの構成要素}} この図のように、Bookは主に3つの構成要素から成り立っています。 ==== position ==== 図で濃い緑色で描かれている盤面が"position(局面)"で、盤面の状態を記録されています。 「局面」というとオセロで可能な展開は全て「局面」ではあるのですが、Bookにはありとあらゆる「局面」が登録されているわけではなく、登録した「局面」だけが登録されています(当たり前ですが)。ここではBookに登録されているもののみをpositionと呼びます。図で薄い緑で描いた盤面はBookには登録されていないので、positionとは呼びません。 また、回転対称や線対称などで本質的に同じ局面は同じ(1つの)positionとみなされます。なので、初手はf5に打ってもe6に打っても同じpositionにたどり着きます。 ==== link ==== position同士をつなぐ矢印が"link"です。適切な日本語がよくわからないので、この記事では"link"とそのまま表記することにします。「手」にも近いですが、あくまでもBookに登録されているposition同士を結んでいる手だけをlinkと呼びます。図では緑色の矢印で描きました。 少し言い方を変えると、Bookに登録されているあるpositionに対し、可能な手を全て列挙して、そのそれぞれの次の盤面を考えた時、次の盤面もBookに登録されていればその手はlinkになります。 ==== leaf ==== positionとlinkであとは何があるのかという気もしますが、"leaf"という概念が存在しています。これは何かというと、Bookに登録されているpositionに対し、その局面で可能な手でなおかつlinkでないもの(つまり次の局面がBook外になる手)の内、最善の手を表します。最善の手なので、1つのpositionに対して最大1つしか存在しません(linkは複数存在しても構いません)。図では黒い矢印で描きました。 leafという単語は葉っぱという意味です。グラフ理論をご存知の方はツリーの末端のノードをleaf node(葉ノード)などと呼ぶことをご存知かと思います。Bookの場合で考えると、Book外に出てしまう末端の手になるのでleafと呼ばれているようです。「葉」というのも違和感があるので、そのまま"leaf"と表記することにします。 ===== 記録されている情報 ===== 構成要素がわかったので、それぞれどんな情報が記録されているのかを見てみます。 {{ :edax:book_02.png?direct |記録されている情報}} ==== Bookの情報 ==== まずBook全体として管理されている主な情報です。図のように、レベル、深さ、序中盤誤差、終盤誤差が管理されています。 === レベル === ざっくりと言えば、Book内部で評価値を出す際にどのレベルで算出しているかという値です。[[edax:level|レベルの意味]]で調べた通り、どのくらいの深さでどれくらいのselectivityで読むかを表しています。詳細はpositionのレベルの項目で説明します。 レベルはBookを生成する際に指定します。最初についてくるBookのレベルは21のようです。レベルが高いほどBookの精度は上がりますが、作成するのに必要な計算時間もかかるようになります。 ヘルプを見ると''book deepen''というコマンドでレベルを上げられそうに見えますが、少なくとも私が持っているV4.3.2ではうまく機能していないようです。 === 深さ === 先読みする際の深さではなく、何手目までのpositionをBookに登録するかを表します。深さ37であれば37手目を打ち終わった局面までpositionとして登録されます。 深さもBookを生成する際に指定します。最初についてくるBookの深さは37です(中身は空ですが)。深さの値が大きいほど終盤に近い局面もBookに登録されますが、計算も時間がかかりますし、Bookのファイルのサイズや、Edaxを実行するのに必要なメモリサイズが大きくなります。こちらは、''book depth''コマンドできちんと変更することが可能なようです。 === 序中盤誤差・終盤誤差 === あまりよく分からない項目ですが、大まかな役割としては評価値がどの程度誤差を含んでいると思っておくかを指定する項目のようです。初期値では序中盤誤差は2、終盤誤差は1となっています。この項目についての詳細は、positionの上限・下限の項目で書きたいと思います。 ==== positionの情報 ==== === 石の配置 === 文字通り、その局面の石の配置です。 === 勝/敗/分け数 === 文字通り、勝った数、負けた数、引き分けの数なのですが、謎の項目の1つです。''book show''コマンドを実行すると、その盤面における勝ち・負け・引き分けの比率が出てくると思います((出てこないケースもあるかと思います。Bookの末端で完全読みが行われていないと出ないはずです。Bookのレベルが24であれば、少なくとも深さ36以上ないと出ないと思います))が、この比率の計算に使用されています。では何が謎なのかというと、勝ち・負け・引き分けの定義です。 {{ :edax:book_03.png?direct|勝敗のカウント}}最初は、学習させた棋譜の勝敗の数を記録しているのかと思っていたのですが、そうはなっていません。ではどうなっているかと言うと、leafを読んだ時に完全読みが行われていればその評価値がプラスかマイナスかゼロかに応じて、勝ち・負け・引き分けと記録されます。linkがあれば、linkの先の方から逆にたどって勝敗を積み上げて行きます。ただしlinkをたどると相手の番になるので、勝敗は逆転します(相手の勝ちは自分の負けなので)。言葉で説明しても分かりにくいので、図を描いてみました。この図のような感じで、下から上に勝敗・引き分けの数が積み上がっていきます。 勝敗数が学習させた棋譜の勝敗ではないことはわかりました。また、カウントの仕方も何となくわかりました。ただ、この意味をどう解釈するかはかなり難しいように思います。直感的には勝率が良い方が優勢な局面だと思いたいのですが、そういう理解をして良いのかどうか迷ういくつかの問題点があります。 * ある局面でほとんどの分岐は負けで、唯一の勝ち筋があるような状況の場合、この分岐を全てBookに登録してしまうと勝率の悪い局面だということになってしまうが、それは適切なのか？ * 一直線で勝ちの局面が最終盤近くまで登録されていると、1手ごとに勝ちが加算されてたくさん勝ったことになるが、それは適切なのか？ * linkを逆にたどって積み上げていくため、linkの先で同じ局面に合流する場合(虎定石と猫→虎変化とか、斜め取りで白がどちらを取っても対称形なだけで本質的に同じ局面になるとか)、その勝敗は二重計上され2倍の勝敗数にカウントされてしまう 問題点と言っても、実用上大した問題ではないのかもしれません。1点目に関しては、Bookは深さ30〜40くらいで作ることが多いかと思うので、そうすると終盤の局面は登録されません。中盤の局面で唯一の勝ち筋と負け筋を見極めるのは難しいことだと思いますし、1手以外は論外にひどい手だというようなわかりやすい局面なのであれば、その1手以外は評価値がかなり低いはずなのでBookにも登録されにくいと思われます。 2点目についても、完全読みをしている区間が長い場合の問題なので、深さ30〜40くらいであればあまり問題にならないようにも思います。 3点目については・・・これはそれなりに問題のような気がします。 ということで、この勝敗・分け数を使って計算される勝率等は、優勢・劣勢の傾向をある程度表しているかもしれませんが、個人的には話半分くらいに思っておいた方が良いように思います。 === ライン数 === 勝/敗/分け数は完全読みのもののみをカウントしましたが、完全読みのもの・完全読みでないものを全てカウントして積み上げていったものがライン数です。不完全読みのものも含まれるので勝ち負けといった区別はなく、何パターンの出口(Bookの外に出るという意味で)があるかを表しているようです。 これも勝/敗/分け数と同様、linkが合流すると二重計上されますが、そういう分岐の合流を含めてBook外に出るまでの手のパターンの数と考えれば一応意味のある数字であるような気はします。とは言え、このパターン数が何か役に立つのかと言われるとよくわかりませんが・・・ === レベル === Bookの項目としてもレベルがありました。ここはpositionとしてのレベルです。 先ほど"leaf"はあるpositionで可能な手でlinkでないものの中で最善の手だと書きましたが、その「最善」の手を探索する際にこのレベルで読んで評価値を計算しています。linkの方の評価値の算出には使わないの？という疑問が生じますが、後ほど説明するように直接的には使いません。 ではBookのレベルとpositionのレベルはどう違うのかという話になりますが、Bookのレベルは棋譜を元に局面(position)をBookに追加する際にpositionをどのレベルにするかを決める役割を果たします。そしてpositionのレベルは、上記の通りleafの探索を行う際に使われています。結局同じじゃないの？という気がしますが、確かに通常は同じ値になります。ただ、Bookをマージした場合に、positionのレベルはマージ元のレベルを保ったまま取り込まれるようなので、その場合はBookのレベルとpositionのレベルが異なる値になります。とは言え、多くの場合は同じ値でしょうから、Bookのレベルが探索に使用されているという理解でも良いと思います。この後の説明でも、特に支障がなければあまり厳密な使い分けはしないことにします。 === 評価値 === 最も気になる評価値です。ここはpositionの評価値について書くべき節ではありますが、linkやleafについても評価値という項目が存在しており、positionについての評価値だけを説明するのも難しいので、まとめて書くことにします。 {{ :edax:book_04.png?direct|評価値の算出}}ある局面(position)の評価値は、その局面から伸びているlinkとleafの評価値の中の最大値になります。図の真ん中にある「白番」の局面を考えると、linkが2本あり、それぞれの評価値は+4と+2になっています。leafの評価値は-2になっています。そこでこれらの中で最大である+4がこの局面の評価値になるのです。 ではleafの評価値はどうやって出てきたのでしょうか。leafの説明のところでも書きましたが、leafはこの局面から出ているlink(今回の場合は2本)を除いた手の中で最善の手です。この探索はpositionのレベルで行い、その際の評価値がleafの評価値になります。探索を伴いますので、この計算には時間がかかります。 一方のlinkの評価値ですが、これは簡単で、その先の局面の評価値から導かれます。「その先の局面」は相手の番ですので、相手(今の場合は黒)にとって-4の評価値であれば、自分(白)にとっては+4、というように先の局面の評価値のプラスマイナスを逆にしたものがlinkの評価値となります。単にlinkの先の評価値の符号を反転させたものですので、探索も必要ではありませんし、計算には時間はかかりません。先ほどBookのレベルの説明の中でlinkの評価値の算出には直接的には使わないと書いたのは、このようにlinkの先の評価値を見れば良いからです。「直接的」と書いたのは、このlinkを順々にたどっていくと各positionで1つずつleafが分岐し、最終的には末端のleaf1本しかない(linkが1本もない)局面に行き着き、これらのleafで探索を行って算出した評価値から順々に戻ってlinkの評価値が計算されているので、「間接的には」leafでの探索の結果が使われているからです。 この状況からわかることとして、例えばBookのレベルが24だとすると、黒い矢印(leaf)の評価値は全てレベル24で計算されていますが、緑の矢印(link)はその先でレベル24で読んだ黒の矢印から算出されていることになります。ということは、緑の矢印は結果的にレベル24以上の深さの(もしくはselectivityによる読みの打ち切りが少ない)読みで探索されていることになり、元の局面でレベル24で読むよりは精度の高い評価値になるはずです。なので、レベル24で作ったBookにはレベル24と同等もしくはそれ以上精度の良い評価値が記録されることになるのです。 === 上限・下限 === これは評価値の上限と下限を表しているようです。前の節で評価値の算出方法を説明しましたが、完全読みのleafの評価値に基づいて算出した範囲であればその評価値は正確なものになりますが、完全読みでないleafの評価値が入ってくるとその評価値は必ずしも正しいとは限らない値になります。そこで、その誤差はどれくらいであるかを見積もって上限値と下限値を記録しておくようです。「見積もり」なので、真の評価値が必ずこの間に入ることが保証されているわけではなく、大体この範囲であろうという程度です。 ここで使われるのが、説明を先送りしていたBookの序中盤誤差・終盤誤差の項目です。"leaf"での探索はpositionのレベルで行うと先ほど書きましたが、[[edax:level|レベルの意味]]で書いたレベルの定義から考えると以下の3パターンの可能性があります。 * 最終手まで読んでいない([[edax:level|レベルの意味]]の表で白い矢印がない範囲) * 最終手まで読んでいるが、selectivityは100%ではない([[edax:level|レベルの意味]]の表で白い矢印があり、かつ青以外の範囲) * 最終手までselectivity=100%で読んでいる(完全読み)([[edax:level|レベルの意味]]の表で白い矢印があり、かつ青の範囲) 1つ目のケースで読みを行った場合の誤差の見積もりが「序中盤誤差」、2つ目のケースで読みを行った場合の誤差の見積もりが「終盤誤差」となっています。もちろん、3つ目は最終手まで完全読みをしていますので、誤差はありません。 例えば、最終局面までselectivity=73%で読んだ結果の評価値が+4だったとすると、誤差は「終盤誤差」を使います。初期値の1であれば誤差±1となるので+3〜+5と見積もります。最終局面まで読んでいない局面での評価値が+4であれば序中盤誤差を使い、初期値2とすると+2〜+6と見積もることになります。ソースを見てみると、実は読みの深さと空きマスの偶奇に応じた謎の補正値があり、 * 読みの深さが偶数、かつ現局面が偶数空き：補正なし(+2〜+6) * 読みの深さが偶数、かつ現局面が奇数空き：プラス方向に1補正(+3〜+7) * 読みの深さが奇数、かつ現局面が偶数空き：マイナス方向に1補正(+1〜+5) * 読みの深さが奇数、かつ現局面が奇数空き：補正なし(+2〜+6) となっています。何のための補正なのかはよくわかりませんが、ソース上そうなっているのでとりあえず書いておきました。評価値そのものの補正は行っておらず、あくまで誤差の範囲を補正しているようです。また、最終局面まで読んでいる場合（つまり終盤誤差を使う場合）も補正は行っていません。 これでleafの評価値の誤差の範囲を見積もることができました((leaf自体の項目としては上限・下限はありませんが、アルゴリズムとしてはまずはleafの上限・下限を算出しています))ので、これに基づいて局面の評価値の誤差を算出したものが上限と下限ということになります。算出の仕方は評価値と大体同じで、leafの評価値の上限と、linkの先の局面の自分にとっての評価値の上限(相手にとっての下限をプラスマイナス逆にしたもの)の中で最大のものが局面の上限となります。局面の下限はleafの評価値の下限と、linkの先の局面の自分にとっての評価値の下限の中で最大のものです。 ここまで評価値の誤差を見積もる話をしてきましたが、結局誤差を見積もって何なの？という疑問がわき上がってきます。真の評価値の正確な範囲というわけでもないのであまり意味がないようにも見えますが、''book enhance''というコマンドを実行した時にこの誤差の見積もりを利用してBookを拡張しているようです。今回はBookの基本概念をメインに調査しているので、これ以上の深入りはやめておきます。また別の機会にBookに関するコマンドについても調べてみたいと思います。 ==== Linkの情報 ==== === 評価値 === これはpositionの評価値の項目で説明した通り、linkの先の局面(position)の評価値をプラスマイナス逆にして、link元側のプレイヤーの立場の評価値にしたものです。 === 手 === このlinkがどの手(f5とか)に対応するものなのかを表します。 ==== Leafの情報 ==== === 評価値 === これもpositionの評価値の項目で説明した通り、この局面でlink以外の手の中の最善の手をpositionのレベルで探索した時の評価値です。 === 手 === このleafがどの手(f5とか)に対応するものなのかを表します。 ==== コマンドの出力例 ==== ここまでで管理されている項目の意味がわかりました。これがわかると''book info''や''book show''などのコマンドの出力の意味も大分わかるようになります。 === book infoコマンド === ''book info''コマンドの出力結果例です。 Edax Book 4.3; 2017-7-9 12:26:08; Positions: 66272 (moves = 68022 links + 66261 leaves); Level 24 : 66272 nodes Depth: 38 Memory occupation: 5426028 Hash balance: 0 < 1 < 7 2行目にpositionとlinkとleafの数が出力されています。leafはpositionに対して1つずつあるので大体同じ値になるはずですが、ある局面で全ての手が登録されるとそれ以外の最善の手というものはなくなってしまいleafはなくなるので、leafの方が若干少ない値になります。 3行目はどのレベルのpositionがいくつあるかを表しています。通常はBookのレベルと同じレベルのpositionが全てだと思いますが、異なるレベルのBookをマージした場合は複数行出力されることもあるようです。複数行出力された場合、どれがBookのレベルなのかはここからはわかりません((試していませんが、おそらくBookのレベルと異なるレベルのpositionに関する情報が''book info''コマンドの冒頭に出力されることになると思います。なので、消去法的にBookのレベルが分かると思います。))。 4行目はBookの深さです。 5行目はBookが使っているメモリの量を表します。単位が書いてありませんがバイトです。 6行目は内部の管理状態を表している項目だと思われます。今のところあまり興味がないので、これ以上深入りはしないでおきます。 === book showコマンド === ''book show''コマンドの出力結果例です。 Level: 24 Best score: +0 [-3, +1] Moves: [C5:+0] [F6:+0] [E6:-2] [E3:-3] [F3:-9] Lines: 242 full games with 52.07% win, 19.83% draw, 28.10% loss 14696 incomplete lines. 1行目はpositionのレベルです。 2行目はpositionの評価値と、下限・上限を表します。この局面は評価値+2で、誤差の範囲は-3〜+1と見ていることになります。 3行目がlinkとleafの情報です。カッコの形の違いは、[]で囲っているのがlink、<>で囲っているのがleafの情報です。手と評価値の情報が出力されています。 4〜5行目は勝敗・分け数から計算したそれぞれの確率です。full gamesと書かれている242というのは、勝ち数・負け数・引き分け数の合計です。incomplete linesと書かれている14696は、ライン数のうちfull gamesを除いたものです。つまりこの先の分岐のパターン数の中で勝敗不明なものになります。先ほども書いた通り、勝敗数にしてもライン数にしても分岐先の合流があったりすると二重計上されていることになるので、この値を使って何かを検討する場合は留意する必要があります。 === hintコマンド === ''hint''コマンドの出力結果例です。 >hint 5 depth|score| time | nodes (N) | N/s | principal variation ------+-----+--------------+-------------+----------+---------------------- book +0 F3 e6 E7 d7 C5 c6 G6 f8 book +0 G5 e3 F3 g4 H3 book -2 B4 f3 book -6 B5 21@73% -07 0:00.074 831827 11240905 G6 c5 E6 e7 C6 d7 B5 b6 C7 ------+-----+--------------+-------------+----------+---------------------- 最初にbookと書いてあるのが、その局面に登録されているlinkやleafの手になります。「21@73%」というのは[[edax:selectivity|%の意味]]でも説明しましたが深さ21、selectivity=73%で読んだ結果を表しています。この手だけはその場で先読みしたもので、bookと書かれている手はあらかじめ計算しておいた評価値を出力しただけになっています。このように、あらかじめ計算しておくことですぐに評価値を出力できるというのがBookの存在意義の1つかと思います。 さて、右の方にprincipal variationという項目がありますが、これはその評価値を実現する進行の一例になっています。これはbookに直接記録されているわけではありませんが、Bookの中をその評価値を満たす手(の中の1つ)をたどっていくだけですぐに出力することができます。 ===== Bookに棋譜を追加した時に何が起きているのか ===== Bookの構成要素や記録されている情報がわかったので、Bookに棋譜を追加するとどういうことが起きるか何となく想像がつくようになってきましたが、復習を兼ねて整理してみたいと思います。 対局後に手動で''book store''コマンドを実行する場合も、''auto-store''オプションで自動で実行する場合も、Bookに棋譜を追加した場合は以下のような処理が行われます。 === positionを追加する === 棋譜の各局面が既にBookに存在するかどうかを調べ、存在しなければpositionとして追加します。その際、positionのレベルはBookに指定されているレベルとして登録します。棋譜は最終手まであったとしても、Bookの深さ分までしか追加しません。また、この棋譜に登場する局面で可能な手を全てチェックし、その先がBook内の局面になるのであれば新たなlinkとして追加します。 === leafを探索する === この棋譜に登場する各局面に対し、leafがなければ(この棋譜で新たに追加された局面や、局面自体は元からあってもこの棋譜を追加したことによって従来leafだった手がlinkになった局面など)、link以外の最善手をそのpositionのレベルで探索し、leafとして評価値とともに記録します。 === 新たなlinkがあれば追加する === 先ほどは棋譜に登場する局面からのlinkだけを追加していましたが、元から存在する局面も含めて全ての局面に対して可能な手を全てチェックし、その先がBook内の局面になるのであれば新たなlinkとして追加します。これによってleafがなくなった局面があれば、link以外の最善手をそのpositionのレベルで探索し、leafとして評価値とともに記録します。これをやっている間は、 Linking book... と表示されています。 === 局面の評価値・各種統計を計算する === Bookの全局面に対して、末端の方から評価値や上限・下限、勝敗・分け数、ライン数等を再計算していきます。leafの探索は既に行われておりここではその結果を使うだけなので、新たな探索が行われるわけではありません。これをやっている間は、 Negamaxing book... と表示されています。 === Bookを保存する === これでBookの中身の更新が終わったので、最後にBookが保存されます。 ===== 補足 ===== ==== Bookの評価値がおかしい場合の直し方 ==== 私レベルの棋力だとBookの評価値を信じるだけなのですが、有段者・高段者の方はBookの評価値がおかしいと思うこともあるかと思います。私が理解している範囲で例を挙げると、コンポスは互角(評価値0)と言われている定石だと思いますが、Bookによっては黒不利(例えば評価値-2とか)となっていることもあるかと思います。このような時、どうすれば正しい評価値にできるのかということを考えてみます。 今の例では、本来評価値=0のはずなのにマイナスと表示されています。Edaxとしてはこの局面の最善がマイナスだと思っているので、この局面では全ての手がマイナスだと思っていることになります。このような場合、Bookのレベルでは認識できていないけれども実は0になるはずの進行があるはずなので、その手をBookに加える必要があります。その手が元々Bookに登録されていなければそれで解決する可能性もありますが、既にBookに登録されていれば解決しません。いずれにしても解決しなかった場合は1手進めてみます。 1手進んだので今度は白の番になっています。この局面も本来は評価値=0のはずですが、Edax的には黒不利だと思っているので白にとっては有利、つまり白の評価値としてはプラスになっているはずです。局面の評価値は0であるべきなので、この局面で可能な手の評価値の最大値が本来は0のはずだということになります。ということは、Edaxがプラスだと思っている手は全ておかしい(先の変化が読みきれていない)ということになるので、プラスの手を全てBookに登録する必要があります。これで解決しなければ、その手に対してまた1手進めて対処する必要があります。 このようにBookの評価値がおかしい場合は、 * 本来よりも低い評価値が出てしまう場合は、本来あるべき評価値を実現する手を登録する * 本来よりも高い評価値が出てしまう場合は、その高く出てしまっている全ての手を登録する を再帰的に実行していけばどこかで正しくなるはずです。とは言え、「本来あるべき評価値を実現する手」がどの手かは自明ではないので、強い方の知識や経験がないとできない手順ではあります。 このように、Edaxが認識できていない最善進行や、最善だと誤解している進行をBookに登録することで、Edaxが出力する評価値をより正しくすることができるのです。これもBookの存在意義の1つです。 ==== ヘボ棋譜を登録しても評価値に影響は与えないのか？ ==== 冒頭に書いたように、Edaxを使い始めた時はこんな心配をしていました。結論から言えば、どんなヘボ棋譜を学習させたとしても評価値の質が落ちることはありません。 Bookの仕組みをおさらいすると、棋譜を登録した時に起きているのは、局面の登録、局面間のlinkの張り直し、leafがなくなってしまった局面のleafの探索のやり直し、その結果を元にした評価値等の再計算、でした。まずわかることとして、評価値を出す際のアルゴリズム自体に影響を与えるようなことは起きていないということです。あくまでもEdax自体が持っている評価値算出アルゴリズムに基づいて算出した値がBookに記録されただけで、アルゴリズム自体が変わるわけではありません。 でもある局面で大悪手を放った棋譜を登録してしまったら、そのlinkが登録されてしまうので評価値が悪くなってしまうのでは？という心配もありますが、そうならないためにleafというものが存在しています。ある局面での大悪手が登録されると、確かにその手のlinkが登録されますしそのlinkの評価値は悪いはずですが、leafはその局面でlinkに登録されている以外の手の最善手をEdaxが自分でそのpositionのレベルで探索して登録していますから、linkとleafの評価値の最大値である局面の評価値は少なくともEdaxが最善だと思う手より悪くはならないのです。 ということなので、自分のヘボ棋譜をいくら登録しても評価値の質が落ちることにはなりません。ただ、登録したpositionは最善ではないですし、Edaxが最善だと誤解しているわけではないでしょうから、Edaxの評価値をより正しくすることに寄与はしないでしょう。にもかかわらず、Bookのサイズは増えますし、読み込むのに必要なメモリ量も増えますので、評価値の質以外の部分でデメリットがあることになります。 なので、評価値に影響は与えないかという問いに対しては「与えない」が答えではありますが、闇雲にヘボ棋譜を読み込ませるのは避けた方が良いように思います。 ===== Bookのフォーマット ===== 最初の方に予告した通り、Bookファイルのフォーマットを調べたので載せておきます。これを元にバイナリエディタでBookを開いて編集すれば、Bookを偽造(?)することができます。ある意味、Bookの値がおかしい場合の究極の「直し方」です((万一試される方は自己責任でお願いします))。なお、各値は数値でも文字列でも[[https://ja.wikipedia.org/wiki/エンディアン#.E3.83.AA.E3.83.88.E3.83.AB.E3.82.A8.E3.83.B3.E3.83.87.E3.82.A3.E3.82.A2.E3.83.B3|リトルエンディアン]]で格納されています。 ^ 項目 ^ 長さ(バイト) ^ 内容 ^ |"EDAX"| 4 |固定値"EDAX"の文字列。間違って他のファイルを読み込まないための予防用の項目と思われます。| |"BOOK"| 4 |固定値"BOOK"の文字列。間違って他のファイルを読み込まないための予防用の項目と思われます。| |バージョン| 1 |バージョン番号。V4.3.2の場合は4| |リリース| 1 |リリース番号。V4.3.2の場合は3| |保存日時-年| 2 |保存日時の年| |保存日時-月| 1 |保存日時の月| |保存日時-日| 1 |保存日時の日| |保存日時-時| 1 |保存日時の時| |保存日時-分| 1 |保存日時の分| |保存日時-秒| 1 |保存日時の秒| |予備| 1 |いわゆるバイト境界の影響で生じている空きバイトです。| |レベル| 4 | | |空きマス| 4 |何マス空きの局面までBookに登録するかを表します((今回の説明では「深さ」として説明しましたが、内部的には「61-深さ」が空きマス数として記録されています。))| |序中盤誤差| 4 | | |終盤誤差| 4 | | |Verbosity| 4 |適切な日本語がわかりませんが、デバッグ用のログの出力レベルのようなものです。| |Position数| 4 |Bookに登録されているpositionの数です。| |Position情報| |下記position情報が、position数分繰り返し格納されています。| === position情報 === ^ 項目 ^ 長さ(バイト) ^ 内容 ^ |手番側の石配置| 8 |下記「石配置の格納方法」参照| |相手側の石配置| 8 |下記「石配置の格納方法」参照| |勝ち数| 4 | | |引き分け数| 4 | | |負け数| 4 | | |ライン数| 4 | | |評価値| 2 | | |評価値下限| 2 | | |評価値上限| 2 | | |link数| 1 |このpositionに登録されているlinkの数です。| |レベル| 1 | | |link情報| 2 * link数 |下記link情報が、link数分繰り返し格納されています。| |leaf情報| 2 |leaf情報が1件分格納されています。フォーマットはlink情報と同じです。| === link情報 === ^ 項目 ^ 長さ(バイト) ^ 内容 ^ |評価値| 1 | | |手| 1 |a1=0, b1=1, c1=2, ..., h8=63です。パスは64、手がない場合は65です| === 石配置の格納方法 === positionに記録されている石配置の格納方法について説明します。オセロは64マスなので、石があるかないかを1か0で表すことによって64bitで石の配置を表すことができます。C言語などではlong long型が64bitなので、これはまさに奇遇なのですが、残念なことにオセロでは石の色が2色あるのでlong long型では表しきれません。そこでEdaxでは自分の石の配置を表す64bitと相手の石の配置を表す64bitの2つの変数を用意してオセロの盤面を表しています。 bitの順番は、最下位のbitがa1、次のbitがb1、その次がc1の順になっており、最上位のbitがh8です。もちろん石のあるbitは1で、ないbitは0です。ファイルに格納される際は[[https://ja.wikipedia.org/wiki/エンディアン#.E3.83.AA.E3.83.88.E3.83.AB.E3.82.A8.E3.83.B3.E3.83.87.E3.82.A3.E3.82.A2.E3.83.B3|リトルエンディアン]]になっているので、ファイル上ではもっと複雑な順番になっています。 これでオセロの盤面を表すことができました。2つの変数で表しているため、同じマスに自分の石も相手の石も存在するという時間の切迫した終盤で稀に起きる現象も表すことができます(冗談ですよ、もちろん)。 さて、positionは回転対称や線対称は同一視しているということを最初の方で書きました。positionの石の配置はどう登録しているのでしょうか？これは、その局面の自分の石配置と相手の石配置の計128bitの値を考え、さらに * 線対称の局面が縦・横・ブラックライン・ホワイトラインを軸とした計4局面 * 回転対称の局面が90度・180度・270度回転の計3局面 の計7局面についても自分の石配置と相手の石配置の128bitの値を考えます。元の局面も含めると128bitの値が8個できたことになりますが、この中で符号なしで考えた時に最小のものを代表として選びます。これがpositionの「自分の石配置」「相手の石配置」に格納されることになります。linkやleafの手(f5とか)もこの配置を基準に考えて格納します。 positionの石配置がどのように格納されているかの説明をしてきたわけですが、1つ違和感のある言い回しをしていることにお気づきでしょうか？2つの64bitの変数について、「自分」と「相手」という言い方になっていて、黒とか白とかには触れていません。positionの他のデータ項目を見ても黒か白かを表すような項目はありません。つまりpositionには黒と白の概念がありません。もちろん打ってある石の数の合計が偶数か奇数かによって大体はどちらの手番かわかるかとは思いますが、途中でパスが発生している可能性もあるので厳密にはわかりません。あくまでも今手番の人(自分)の石の配置と、相手の石の配置、という考え方になっているのです。 今回調べた中で最も感心したことの1つですが、考えてみると今の手番の人の石の配置と相手の石の配置が決まれば、それが黒であろうと白であろうと最善の手は変わらないですし、どの手の評価値も黒か白かには依存しません。なので、黒と白は管理する必要がないのです。滅多に起こることはないと思いますが、「ある黒番の局面」と、その局面から「黒白を入れ替えた石配置の白番の局面」があった場合、この2つの局面は同じpositionとして扱われることになります。 Bookには黒と白の概念がありませんので、この文章の途中で出てきたBookの図の中に「黒番」「白番」等と描かれているのは実は嘘で、黒か白かはわからないのが実際です。ただ、「自分」と「相手」だとわかりにくくなるので、図としては黒と白という描き方にしてみました。 ===== 結論 ===== * Bookには主に局面(position)と、局面間の手(link)、それ以外の手の中で最善の手(leaf)が登録されており、あらかじめ評価値が計算されている * Bookの主な存在意義は、評価値の精度を高めることと、計算時間を短縮すること * どんな棋譜を読み込んでも、評価値が劣化することはない