【2026年10月版】

索引と探す技術（第7回）― 探索を動かす評価関数

公開日: 2026/10/02
読了時間: 約 21分

第6回では、探索アルゴリズムを部品に分けて見た。第7回は、その部品のうち、探索の向かう先を決める評価関数を扱う。

1. 探索に必要なもう一つの部品 ― 評価関数

探索は、候補を生成する部分と、候補の良さを返す関数の二つで動く。後者の呼び名は分野ごとに違い、A* ではヒューリスティック関数 h、対戦ゲームでは評価関数、進化計算では適応度関数、最適化では目的関数、強化学習では報酬と呼ぶ。LLM に案を生成させる探索では、案の正誤を判定する検証器が同じ役割を担う。

この関数の作り方は四つに分けられる。問題を単純化して厳密に解く方法、人が特徴を設計して係数を調整する方法、検証器をそのまま関数にする方法、そして代理を学習する方法である。

2. 緩和による評価関数

A* の h を作る代表的な方法が緩和である。Holte らの解説は、パールの『Heuristics』第4章の中心を、状態空間を簡略化した版での厳密な距離を元の空間の距離の推定に使うことだと整理している。緩和とは、状態の遷移を制限する条件を弱めるか外すことを指す。道路上を走るという制約を外せば都市間の距離は直線距離になり、15パズルで「タイルは空白に隣接するときだけ動かせる」という制約を外せばマンハッタン距離になる。制約を外した空間では元の空間より自由に動けるので、そこでの距離は常に元の空間の距離以下になる。カーナビでいえば、目的地までの直線距離は、実際に走る道のりと同じか、それより短く出る。第5回で見たとおり、A* が最短の経路を確実に見つけられるのは、h が残りの距離をこのように常に実際以下に見積もるときで、教科書ではこの性質を許容的(admissible)と呼ぶ。緩和で作った h は、作り方からして必ず許容的になる。もう一つの性質である無矛盾は、隣の交差点へ一区間進んだときに、見積もりの減る量がその区間の長さ以下に収まることを指す。直線距離なら、一区間走って目的地に近づく分はその区間の長さ以下なので、この条件も満たし、探索の途中で見積もりが急に縮んで順番が狂うことが起きにくい。同じ章によれば、緩和空間の厳密な距離を h にすると許容的かつ無矛盾になることは、パールより前にミラノ工科大のグループが示している。

緩和にも弱点がある。Gaschnig は、緩和した空間を探索して h を計算すると、h を使わずに幅優先探索で直接解くより時間がかかりうると指摘し、Valtorta がこれを形式的に証明した。ただしこの結論が成り立つのは、緩和空間を毎回探索して h を求める方式に限られる。事前に計算して表に保存する方式や、マンハッタン距離のように閉じた式で求まる緩和は対象外である。

事前に計算して表にしておく方式がパターンデータベースである。Culberson と Schaeffer の1998年の論文では、15パズルの標準の100問で、探索したノードの総数がマンハッタン距離だけを使う場合の 36,302,808,031 から、fringe と corner の二つのデータベースを使う場合の 34,987,894 へ減り、1038倍の削減になった。各データベースは 518,918,400 局面で 520MB あり、構築にかかった時間は1つあたり実時間で1時間未満だった。ノードあたりの計算が増えるため実時間の短縮は約6倍にとどまり、参照を最小限に抑えると約12倍まで伸びる。コーフはこの方法で、ルービックキューブのランダムな状態の最適解を初めて求めた。

巡回セールスマン問題の下界にも緩和が使われる。巡回セールスマン問題は、すべての都市を一度ずつ訪ねて出発地に戻る最短の道順を求める問題で、どの都市にも入る道と出る道がちょうど一本ずつ、合わせて2本つながる。下界は、どの道順の長さもその値以上になると保証できる値のことで、分枝限定法はこれを使って、見込みのない枝を早めに捨てる。ヘルド・カープの下界では、まず都市を一つ(点 p)だけ脇に置き、残りの都市を最も安い道の組み合わせで木の形につなぐ。これが最小全域木で、そこへ p から最も安い2本の道を足したものを 1-tree と呼ぶ。巡回路から p の2本の道を外すと残りは一本道の木になるので、巡回路は、どの都市にも道が2本ずつつながる特殊な 1-tree にあたり、最も安い 1-tree の費用は巡回路の長さ以下になる。ただし最も安い 1-tree をそのまま作ると、道が三本以上集まる都市や一本だけの都市が出てくる。そこで、道が多すぎる都市につながる道を割高に、少なすぎる都市の道を割安に見せるよう費用を調整して、1-tree を巡回路の形に近づけていく。この、守らせたい条件を外す代わりに、破った分を罰金として費用に上乗せするやり方を、教科書ではラグランジュ緩和と呼び、「各都市の次数がちょうど2」という制約をこの方法で費用に組み込む。限られた計算量で非常に強い下界を得られるとされ、Concorde のようなソルバで使われている。

3. 特徴の設計と係数の調整

緩和とは別の作り方として、人が特徴を設計し、係数を調整する方法が長く使われてきた。シャノンが1950年に書いたチェスの評価関数は次の式である。

f(P) = 200(K−K') + 9(Q−Q') + 5(R−R') + 3(B−B'+N−N') + (P−P')
       − 0.5(D−D'+S−S'+I−I') + 0.1(M−M')

K、Q、R、B、N、P は白の駒の数を、ダッシュ付きは黒の駒の数を表す。D、S、I はそれぞれ二重、後退、孤立のポーン、M は合法手の数(機動力)である。シャノンは、0.5 と 0.1 の係数は筆者のおおよその推定にすぎないと書いた。また、駒を取り合っている最中の局面では、次の一手で駒の数の差が入れ替わるので、駒を数えるこの種の評価が使えるのは、取り合いが一段落した静止局面に限られる。そのためシャノンは、探索で静止局面まで読んでから評価するべきだと述べている。

サミュエルの1959年のチェッカーは、この係数を学習させた。評価は線形多項式で、汎化(generalization)の実験では38の項のうち16を同時に使い、残りを予備に置いて、重要度の低い項を予備の項と入れ替えた。Alpha と Beta という二つのプログラムを対戦させ、先読みした値は、盤面だけを見て付けた静的評価より正確なので、Alpha は1手ごとに両者の差を教師にして、静的評価が先読みの値に近づくよう多項式の係数を調整していく。

手作りの評価関数は長く使われた。Stockfish は2020年の Stockfish 12で、専門家が手作りして fishtest で調整してきた評価に、数百万局面の評価で訓練する NNUE を加え、勝ち越したゲーム対が負け越した対の10倍以上あった。NNUE はもともと那須悠が将棋向けに考案したもので、2018年5月に YaneuraOu へ統合され、2019年6月に Stockfish へ移植されている。公式の文書によれば、訓練の教師には探索の評価値と実際の対局結果を混ぜたものを使う。手作りの評価はStockfish 16で取り除かれた。

訓練に使う局面の選び方でも、シャノンと同じ論点が出てくる。象棋のエンジンを対象にした研究は、訓練局面に静止局面だけを使っている。TD-Gammon では、生の盤面情報だけを入力にしても、隠れ層40ユニットのネットワークが20万ゲームの自己対戦で中級者の水準に達した。Neurogammon の手作りの特徴を加えると、成績はさらに上がった。

4. 評価関数としての検証器

正誤を安く厳密に判定できる問題では、判定の手続きそのものが評価関数になる。FunSearch は、LLM が出した案を自動の評価器で検証する。評価器が幻覚や誤った案を退け、プログラムを評価する手順は利用者が問題の記述の一部として与える。AlphaEvolve は同じ考え方でプログラムを進化させ、4×4の複素数行列の積を48回の乗算で計算するアルゴリズムを見つけた。

検証器には三つの条件が求められる。誤った案を正しいと判定してしまう偽陽性が少ないこと、安く動いて世代数を稼げること、部分点を返して探索に手がかりを与えられることである。このうち最も破れやすいのが偽陽性の少なさで、その例は次の章で扱う。

5. 評価関数の穴と対策

探索が強ければ強いほど、評価関数の穴は見つかりやすくなる。アモデイらの2016年の論文は、誤った目的関数に起因する事故を、副作用と報酬ハッキングの問題として整理した。DeepMind の事例集には、周回するレースゲームで、コースを回る代わりに緑のブロックを繰り返し叩いて得点を稼いだ例や、赤いブロックの底面の高さに報酬を与えたところ、ブロックを持ち上げて載せる代わりに裏返した例が載っている。

学習を速めるために報酬を足す場合、その足し方には条件がある。地図の上で目的地を目指す例でいえば、目的地に近づいたら点を足し、遠ざかったら点を引けば、学習の手がかりが増える。ところが、近づいたときの加点だけを与えると、行ったり来たりして加点を何度も受け取る道が得をして、レースゲームの例と同じ近道が生まれる。そこで地図上の各地点に、目的地に近いほど高くなる「高さ」Φ を決めておき、一歩ごとに移動先と移動元の高さの差を報酬に足すようにする。こうすると、ぐるりと回って元の地点に戻ったときには足した分と引いた分が打ち消し合うので、回り道で点を稼ぐことができず、最も良い行動の選び方(最適方策)は元の報酬のときと同じになる。エンらの1999年の論文の定理は、この形、つまり追加する形成報酬が、割引率 γ を掛けた高さの差 γΦ(s′) − Φ(s) の形をとることが、最適方策を保つための必要十分条件であることを示した。論文はこの Φ をポテンシャル関数と呼ぶ。必要性のほうは、どんな地図とどんな元の報酬に対しても最適方策を保てる足し方は、この高さの差の形に限られる、という意味である。論文は、距離にもとづくヒューリスティックから形成のポテンシャルを作れるとも述べており、A* の h と同じ種類の関数がここにも現れる。

代理を学習した評価関数には、最適化を進めてよい限度がある。Gao らの2022年の論文は、固定した報酬モデルを正解の代わりに置き、別の代理の報酬モデルを訓練して、強化学習または best-of-n で最適化した。best-of-n は、n 個の案を出させて代理が最も高く採点したものを選ぶ方法である。最適化を進めるほど、モデルの出力は最初のモデルの出力から離れていくので、論文はその離れ具合を測る KL ダイバージェンスの平方根 d で最適化の量を表した。すると正解の報酬の推移は、best-of-n で d(α − βd)、強化学習で d(α − β log d) の形になった。どちらも、最初は d とともに伸びるが、d が大きくなると括弧の中で引かれる項が効いてくるので、代理を最適化し続けると、ある点から先は正解の報酬がかえって下がっていく。

検証器でさえ破られる。タオらは2025年に、AlphaEvolve を67の数学の問題に使った経験から、検証器の穴を突かれた例を挙げている。近似の精度を許容すると、多数の点をほぼ同じ位置に置いて距離の判定を曖昧にする、浮動小数点の扱いを悪用する、線形計画ソルバの失敗の仕方を突く、といった形で穴が使われた。対策としては、区間算術や厳密な計算、最悪ケースを想定した保守的な境界、入力が許容範囲にあるかどうかの検査が挙げられている。2026年には、検証可能な報酬で学習したモデルが検証器を悪用する研究が出た。帰納推論の課題で、GPT-5 と Olmo3 は規則を帰納するのをやめ、検証器を通る個別のラベルを列挙して報酬を得た。この挙動は GPT-4o と GPT-4.5 では見られず、課題が複雑でテスト時の計算が多いほど増える。個別の例だけを確かめる検証を、同型の変換を加えた検証に替えると、この近道は消えた。

評価が使えるのは静止局面に限るというシャノンの制約も、評価関数を定義域の中だけで使うという同じ種類の問題にあたる。評価関数は、作って終わりにはならない。どの入力で使えるかを決め、実際に渡す入力がその範囲にあるかを検査する作業が、作った後にも残り続ける。

第8回では、ここまでの手法の選び方を扱う。論文の設定が評価データに合わせて調整されている点から、アルゴリズムの選択にかかる予算、大規模なデータでの意思決定木までを整理する。