前回の続き。今回も評価関数を作っていきましょう。
この連載について
わりと反響があって驚いています。
この連載では、ショートコードのような可読性の悪いコードは書きませんし、bit演算のテクニックも出てきません。それでいて、50行程度の評価関数でプロ棋士レベルの強さの将棋ソフトにするという、壮大な目標にチャレンジしています。
ただし、その「50行程度」には、改行とコメント行は含めません。ついでに言うとテーブル初期化のコードも含めません。(それは評価関数本体とは異なるという考えです。)
あと、「コードは書いたけど、効果に乏しいからやっぱり没」みたいな手戻りを何度もやります。(やる予定です)
結論ありきの記事ではなく、その考え方、道筋まで見える記事にしたいと思っています。
optimizerについて
やねうら王では、パラメーターのチューニングを(半)自動的に行う、チューニングフレームワークがあります。これをこの連載では、optimizerと呼びます。
optimizerの使い方については、やねうら王のリポジトリのdocs/解説.txt の「探索パラメーターのチューニングについて」のところに説明があります。私以外の人にとって、あまり使いやすいものでもないでしょうから、これをそのまま使うのではなく改良して使っていただければと…。
optimizerから何がわかるか？
前回、盤上の駒の価値はその104/1024(おおよそ10%)が減じられるということがoptimizerによりわかりました。これは、盤上の駒の価値を手駒より104/1024だけ低い価値とした時に、自己対局の勝率が最大化されたからです。
つまり、手駒は盤上の駒より約11.3%増しの価値があるということですね。
// 1024/(1024-104) ≒ 1.113
これは、将棋指しにとって、興味深い知見ではないでしょうか？
「手駒は(その価値が盤上の駒の)11.3%増し」
というのは新しい格言になるかも知れませんね。
このように、具体的な値はわからないけども、「何らか係数があって、盤上の駒はその分だけ価値が減じられるはず」みたいな感じの仮説を立てた場合、それをコードに落とし込み、optimizerを適用するだけで結果が返ってくるわけです。
つまり、将棋の棋譜など一切見ずに、コードを書いて実行すれば結果として勝率が最大化されるパラメーターが得られるということです。ここまで抽象化されていると、これが将棋ソフトの開発をしているのか、温室栽培の野菜の収穫量を最大化しようとしているのか、わけがわからなくなりますね。😅
改良が良かったかどうかはどうやって判定するの？
optimizerによってABテストのようなことも出来ます。
Aのほうは基準ソフトに対して、1000勝500敗
Bのほうは基準ソフトに対して、1000勝490敗
だったよ、というような結果が得られます。
さて、このとき、AはBより優れていると言えるのでしょうか？95%以上の確率でAのほうが優れていると言って良いのでしょうか？
統計学に出てきそうな問題ですが、わりと難しい問題で、私はこれを計算するスクリプトを書いたのですが、積分するところ台形に近似して近似解なら得られるものの、解析的に解く方法は私にはよくわかりませんでした。
dlshogiの山岡さんによると「(解き方は自分もわからないが)自分はOrdoを使っています」とのことでした。
https://github.com/michiguel/Ordo
Ordoは、入力がpgnという形式で勝敗の結果を書いたテキストファイルです。
1000勝500敗のような勝敗情報から、このpgn形式のテキストを生成するスクリプトを作成すれば確かに実用になりそうではあります。
// 誰か、「1000勝500敗 と 1000勝490敗 に対して前者のほうが強い確率」を出力するようなPythonのスクリプトを作ってもらえると助かります。
成り駒の手駒化による価値アップは生駒（なまごま）の価値からのアップなのか？
前回、盤上の駒には、(手駒ではないことに対して)104/1024だけその価値を減ずるのが良いという話が出てきました。
しかし、馬は手駒には存在しない駒なので馬の価値と言う場合、盤上にあることが前提となっています。それに対して、歩は手駒の歩と盤上の歩との両方がありえます。
なので、PawnValue(歩の価値) = 90は、手駒の歩の価値と盤上の歩の価値を均した値だと考えられます。盤上の歩と手駒の歩で10%ぐらい価値に差があるということでしたら、盤上の歩 = 85 , 手駒の歩 = 95ぐらいでないとおかしく、盤上にあるからと言って、Pawn Valueの104/1024を減じるのは正確ではないことになります。
他には、「馬」であったとしたら、馬の価値×104/1024だけ引き算していましたが、馬は盤上にしかない駒ですから、この945は盤上にあることに対するペナルティ込みの値のはずです。なので、馬に対して、盤上にあるからと価値を減算する処理は正しくないことになります。
などと考えていくと夜も眠れなくなりますが、このAperyの駒割はもともと駒の価値は機械学習の時に(この値にするといまのところ最適だよ)と出てきた数値で、機械学習の進行度によっても値はころころ変わり、それほど根拠のある数値でもないので、ここをあまり深く考えても仕方ない意味もあります。
気にせず先に進みましょう！
盤上の升に発生した利きの価値について
将棋は王様を捕まえるゲームですから、王様周辺を包囲していく必要があります。包囲というのは、具体的には、相手の王様に対して、こちら側の(味方側の)利きを発生させるということです。つまりは、王様周辺の利きほど価値が高いと考えられます。
また、味方の利きと敵の利きとで、その価値の符号は逆になります。
味方の利きは嬉しいし、敵の利きはあると嫌ですからね。
あと、味方の利きと敵の利きとでは、その絶対値の大きさは、同じではないはずです。味方の利きがいくら自分の王様周辺にあったとしても、敵の利きが数個あるだけで王様が詰むことはありますからね。
そう考えると盤上の味方の利きと敵の利きの価値の評価に関しては別の係数が必要だとわかります。
また、王様から何升離れているかという距離に応じて、利きの価値が減じられるはずです。この減じられ方は、何らかの減衰曲線なのでしょうか？
つまり、王様からd升離れた場所に味方の利きがあるときに、例えば、指数関数的な pow(0.8 ,d) のような価値が発生するのか、それとも、単に反比例的な、1 / (d + 1) みたいな価値が発生するのか。
私はおそらく後者であろう予想しましたが、自信はありませんでした。そこでoptimizerの出番です！
利きの価値を確かめるためにコードを書く
ある升sqに味方の利きがあるとします。王様からsqまでの距離をdとします。
ここで、dは、マンハッタン距離(筋の差 + 段の差)ではなく、筋の差と段の差の大きいほうとします。玉は8方向に移動できますから、何手で移動できるかというのを考えるとしたら、こうなっているほうが合理的だと私は考えたからです。
この距離を求めるコードは、次のようになります。これは、やねうら王にはdist()という関数がこれと同等の実装になっているので、そちらを用いても構いません。
|
1 2 |
// 筋と段でたくさん離れているほうの数をその距離とする。 int d = std::max(std::abs(file_of(sq) - file_of(king_sq)), std::abs(rank_of(sq) - rank_of(king_sq))); |
あと、利きの情報が使いたいので、やねうら王の場合、
|
1 |
#define LONG_EFFECT_LIBRARY |
と、config.hで定義してやります。そうすると、
|
1 2 |
// この升の先手の利きの数、後手の利きの数 int effects[2] = { pos.board_effect[BLACK].effect(sq) , pos.board_effect[WHITE].effect(sq) }; |
のようにして盤上のある升の利きを取得できるようになります。
利きの価値を確かめるためにoptimizerを適用する
さて、私は以下のようにコードを書いて、optimizerを適用しました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
for (auto sq : SQ) { // この升の先手の利きの数、後手の利きの数 int effects[2] = { pos.board_effect[BLACK].effect(sq) , pos.board_effect[WHITE].effect(sq) }; for (auto color : COLOR) { // color側の玉に対して auto king_sq = pos.king_square(color); // 筋と段でたくさん離れているほうの数をその距離とする。 int d = dist(sq, king_sq); int s1 = effects[ color] * 68 * dist_value_for_us [d] / 1024; int s2 = effects[~color] * 96 * dist_value_for_them[d] / 1024; // scoreは先手から見たスコアなので、colorが先手の時は、(s1-s2) をscoreに加算。colorが後手の時は、(s2-s1) を加算。 score += color == BLACK ? (s1 - s2) : (s2 - s1); } } |
// ~color は、Color型に用意されているoperator~()によって、手番を反転させます。color == BLACK(先手)ならWHITE(後手)に、WHITEならばBLACKになります。
値は、前回書いたように小数を使いたくない＆割り算をしたくないので1024倍してあります。
// 1024が1.0であるような固定小数だと考えてください。
また、68,96という係数は、
dist_value_for_us[0] = 1024
dist_value_for_them[0] = 1024
と距離0のときの価値は1024に固定した時にoptimizerがこの係数の値が最適だよと導き出した数値です。
dist_value_for_us[1]～dist_value_for_us[8]
dist_value_for_them[1]～dist_value_for_them[8]
を私はoptimizerに尋ねました。
ある升に発生した利きの価値は、王様からの距離に反比例するのですか？それとも何らかの減衰曲線なのですか？と。
さて、optimizerは一体、何を我々に教えてくれるのでしょうか？
AがBより強いという検定の話、中心極限定理使っちゃ駄目なんですかね？サンプル数多いなら相当な精度で近似できると思うのですが。
AがBより95%以上の確率で強いとわかった時点で自己対局を打ち切りたい(or パラメーターを動かしたい)ので…。
自分でサンプル数を動かしているのにサンプル数固定の通常の仮説検定を適用しちゃうとまずいから、ベイズ統計を使っていらっしゃるということですか？
もしそうなら勝率パラメータの事前分布をベータ分布にすれば事後分布も同様にベータ分布になって、計算がしやすいはずです。ベータ分布の密度や累積分布を扱うPythonのライブラリーはいくらでもあるでしょうし。
おー、そうなんですか…。← 統計学の知識が足りてなくて、勉強するところから。
ありがとうございます。
カイ二乗分布を使った独立性検定を援用してみた。
from scipy import stats
# カイ二乗値を求める
def chi2_calc(rv1, rv2):
# 実測値
rvalue = rv1 + rv2
# 実測値の構成比から期待値を求める
all = sum(rvalue)
ratio_ai = ((rv1[0] + rv1[1]) / all, (rv2[0] + rv2[1]) / all) # ai1とai2の試合数の比率
ratio_wl = ((rv1[0] + rv2[0]) / all, (rv1[1] + rv2[1]) / all) # 勝数と負数の比率
lvalue = (ratio_ai[0] * ratio_wl[0] * all, ratio_ai[0] * ratio_wl[1] * all,
ratio_ai[1] * ratio_wl[0] * all, ratio_ai[1] * ratio_wl[1] * all)
# 実測値と期待値からカイ二乗値を求める
chi2 = sum(((rv – lv) ** 2 / lv for rv, lv in zip(rvalue, lvalue)))
return chi2
# ２組の実績値（勝数・負数）から、それぞれが強い確率を求める
def win_prob(rvalue1, rvalue2):
chi2 = chi2_calc(rvalue1, rvalue2)
# 自由度１のカイ二乗分布に対応した上側確率（群に差がある確率）
p_value = stats.chi2.cdf(chi2, 1)
# 下側確率（群に差がない確率）は1/2を両方に配分、上側確率（群に差がある確率）は勝率の高いほうに配分
win_prob1 = (1.0 – p_value) / 2 + (p_value if (rvalue1[0]/rvalue1[1] > rvalue2[0]/rvalue2[1]) else 0)
win_prob2 = (1.0 – p_value) / 2 + (p_value if (rvalue1[0]/rvalue1[1] < rvalue2[0]/rvalue2[1]) else 0)
return win_prob1, win_prob2
if __name__ == '__main__':
print(win_prob((1000, 500), (1000, 490))) # 1000勝500敗 vs 1000勝490敗 ⇒ (0.3974570777326721, 0.602542922267328)
(ﾟдﾟ)!!!!!!
これは、コンピュータ将棋へのすごい貢献ですよ！！
山岡さんたちにお披露目してきます！！
めちゃくちゃ勉強になりました。ありがとうございます。
一点、
stats.chi2.cdf
は、「下側」確率でしょうか。念の為。
自然数m,nに対して、不定積分
J(x;m,n):=int[y=0~x] y^m(1-y)^n dy
を考えると、部分積分によって
(m+1)*J(x;m,n)=x^(m+1)(1-x)^n+n*J(x;m+1,n-1)
と漸化式を得ることができ、これを用いて
J(x;m,n)=sum[i=0~n] {m!/(m+i+1)!}{n!/(n-i)!}x^(m+i+1)(1-x)^(n-i)
と書き下せます．
これと、J(1;m,n)=m!n!/(m+n+1)!に注意すれば、
基準ソフトに対してN戦W勝L敗のAとn戦w勝l敗のBがあったとき、
AがBに対して真の勝率で上回る確率を
{(N+1)!(n+1)!/(N+n+2)!}{1/(W!L!)}
*sum[i=0~l] {(W+w+i+1)!/(w+i+1)!}{(L+l-i)!/(l-i)!}
と計算できると思われます．
うおー?!?!ありがとうございます。山岡さんにご報告だだだ。
補足しておくと、ここでは真の勝率の事前確率分布(基準ソフトと対戦を行う前の確率分布)が0~1の一様分布になるという仮定を置いています．
このような仮定の下で、m勝n敗したソフトの真の勝率がx~x+dxにある微小確率は
x^m(1-x)^ndx/{int[y=0~1] y^m(1-y)^n dy}
と計算できます．
あとは、Aの勝率がx~x+dxにある微小確率とBの勝率が0~xにある確率の積をx=0~1で積分して上の式が出ます．