colunさんのマラソンマッチ関連の話

ビームサーチの評価関数や文脈について
0
コルン @colun

以上で、【評価関数関連 - ビームサーチ編】を終了とします。

2015-09-20 06:05:17
コルン @colun

「同じビーム内の評価関数結果同士の比較がうまくいくかどうか?」は、基本的には、具体的な評価関数が手元になくても、何度かマラソンマッチをこなしているうちに感覚的にだいたい分かる様になります。なので、具体的な評価関数を考えなくとも、文脈設計は可能です。

2015-09-20 06:04:40
コルン @colun

ちなみに、「同じビーム内の評価関数結果同士の比較がうまくいくかどうか?」を基準に、それを満たす様な「文脈」と「世代」を定める必要があります。 しかしながら、評価関数を設計するのは文脈設計の後にした方が良いです。

2015-09-20 06:03:43
コルン @colun

また、終局局面が遠い場合と近い場合とで、評価関数が変わっていくべきである場合もあります。ビームサーチの場合、異なる世代での比較を行わなくて良いため、終局までの手数で評価関数をガラリと変えても、うまく行く様な調整が比較的簡単にできます。(同じビーム内で基準が異なる場合は注意が必要)

2015-09-20 05:58:12
コルン @colun

スコア関数から考えると結構脈絡のないものも混じってきますので、計算可能なものは何でも試してみて、感覚を養う必要があります。 この時にも、基本的には「人間の思考に近い」ものを基準に実装すると、だいたいうまくいきます。

2015-09-20 05:52:46
コルン @colun

さてところで、具体的にはどういうものを評価関数にしたらよいのでしょうか? この部分は、非常に問題固有になります。 たとえばオセロを考えると、スコア関数(終局局面)としては白の数と黒の数になりますが、評価関数(非終局局面)としては「打てる場所の数」「表面積」「石同士の配置」など、

2015-09-20 05:50:27
コルン @colun

このため、「人間の思考」は、局所評価極振りになってることが多くあります。ここから「広域評価」へと昇華させなければならず、、、この部分に関してはコンピュータに実際に計算させた結果を見ながら調整していくしかありません。調整をたびたびやっていると、なんとなく広域評価が見えてきます。

2015-09-20 05:46:30
コルン @colun

評価関数に関しても、やはり、「人間の思考に近い」方が優秀である場合が多いです。 ただ、気を付けて頂きたいのは、人間は多くの場合に枝刈りしまくりの深さ優先探索とビームサーチを組み合わせた様な思考になっていることがほとんどで、ビーム幅は非常に狭いです。

2015-09-20 05:44:31
コルン @colun

よほど局面情報のビット数が少ない場合はこの限りではないですが……そういうパターンは今まであまりないですね。。。(今すぐに思い出すものとしては、コラッツの時ぐらいかな?)

2015-09-20 05:40:39
コルン @colun

子(遷移)の計算時には、仮にシミュレートするとしても、局面全部をコピーしていたら計算量的に合わなくなるので、UNDOリストを作りながらシミュレートして、シミュレートが終わったらすぐUNDOすることになります。

2015-09-20 05:39:18
コルン @colun

逆に言えば、子(遷移)の計算時は、局面のシミュレートは間違っていても良くて、不安定な絶対評価差分と一時評価さえ計算できれば良いことがほとんどです。 親(前処理)の際に、そこまでの局面を正しくシミュレートできれば、ズレは蓄積されませんので、そういう実装を行うことが多いです。

2015-09-20 05:37:03
コルン @colun

評価関数は、計算量の都合上、可能な限り、差分で求めるべきです。 少しシミュレータの話に戻りますが、多くの場合に計算量の問題から、子(遷移)の計算コストは可能な限り小さくするのが通例で、この時に、遷移の際に評価が変化する部分だけをシミュレートすることになります。

2015-09-20 05:34:03
コルン @colun

なお、局所評価の極限が一時評価になります。各評価要素の文脈依存性(近い遷移過程を経ているもの同士でなければ評価の比較が安定しないこと)がどのぐらいあるのかは、常に意識した方が良い気がします。

2015-09-20 05:31:44
コルン @colun

狭いビーム幅で調整を行うと、局所評価で調整されます。最初から広いビーム幅で調整を行うと、広域評価で調整されます。なので、プロジェクトの開始当初からビーム幅は最終的に予測されるビーム幅と同等だけ取っておきましょう。

2015-09-20 05:28:56
コルン @colun

しかしながらビーム幅を増やしていくと、ある時、はたと気が付きます。5世代前まで遡っても違う、10世代前まで遡っても違う、、、となってくると、あまりに局面が異なり過ぎて、広域評価を意識していない絶対評価の実装では局面比較が上手く機能しなくなることがあります。

2015-09-20 05:24:30
コルン @colun

さて、実装上の絶対評価と一時評価とは別に、理論上の広域評価と局所評価があります。 ビームサーチのビーム幅が狭いうちは、ビーム内において、「爺ちゃん以前は皆一緒」ぐらいの、近親局面ばかりのビームになりますので、広域評価と局所評価をあまり意識しなくてもどうにかなります。

2015-09-20 05:20:42
コルン @colun

対して一時評価というのは、兄弟と差をつけるために、一時的にその遷移に関してのみ意図的につける評価のことです。これは、孫に引き継いではいけない場合がほとんどです。実装上は、これらの評価を分けて管理することがしばしばあります。

2015-09-20 05:16:45
コルン @colun

絶対評価というのは基本的に蓄積型で考えることができる場合が多く、親から子へと評価のほとんどが引き継がれます。その際に差分評価が発生し、それは孫へと引き継がれていくだろうものです。

2015-09-20 05:15:35
コルン @colun

広域評価、局所評価、絶対評価、一時評価は、それぞれ、今僕が暫定的にそう呼んだだけで、そういう専門用語があるわけではありません。門外漢ですので、マラソンマッチを理論化していく上で、概念に名前がついていない場合、名前がついてるかもしれないけれどそれを調べる術がない場合が多くあります。

2015-09-20 05:10:41
コルン @colun

さて、前置きはともかくとして…… 評価関数を考える際、理論上の広域評価と局所評価、実装上の絶対評価と一時評価を意識しましょう。 絶対評価は多くの場合に、親(前処理)で最初から計算するか、子(遷移処理)で差分計算します。場合によっては、親(前処理)での差分計算だけにする時も。

2015-09-20 05:07:57
コルン @colun

評価関数とスコア関数は根本的に異なります。終局以外の局面に対してスコア関数を適用することに関して、もうちょっと意識的になってください。 「ある局面に対して、そこから遷移可能な終局局面の中から比較的良いもののスコア関数を推定する関数」が評価関数です。

2015-09-20 04:56:33
コルン @colun

まず、評価関数が何であるかを勘違いしてる人が多い気がしているので、その辺に関して念押しをしておきます。 ゲーム終局時、その局面をゲームルールに従って計算すれば、カンペキに評価できるでしょう。 これを私は、評価関数とは区別してスコア関数と呼んでいます。(正しい専門用語かは不明)

2015-09-20 04:53:15
コルン @colun

【評価関数関連 - ビームサーチ編】

2015-09-20 04:45:57
コルン @colun

以上が【文脈関連 - ビームサーチ編】になりますかね。。。 具体例は出してないかもしれませんが、根本的に、こういう視点(概念)がある……という風にお考え下さい。

2015-09-20 04:45:27
コルン @colun

(場合によっては3手目は選択するけれど、1手目と2手目はそれによって半自動的に一意に定まる……ほとんど差がないから、条件を満たしているものなら何でも良い……場合もあります)

2015-09-20 04:45:04