RAVEの効果
荒木 伸夫
コンピュータ将棋選手権参加者の皆さんはお疲れさまでした。
私はGWは有給を使って10連休にして、今までコンピュータ囲碁の改良に取り組んでいたのですが、
目立った成果が出なくて鬱になっています。
その取り組みの一つに、「RAVEを入れてみる」というのがあったのですが、
RAVEを入れても効果がありませんでした。
以前RAVEを入れた時も効果が無く、今回はいろいろ細かいところの微調整もしてみたのですが、
やはり効果が無かったです。
山下さんがWebで公開している資料も見たのですが、古い資料だと「彩ではRAVEは効果無かった」と
書かれているのですが、新しい資料だと効果があったような書き方をされていますね。
RAVEはどの程度効果があるものなのでしょうか?皆さんの体験談を教えていただきたく思います。
Hideki Kato
RAVE の論文が出てしばらくした頃，Computer-Go ML で上手く行かないという
話が出ました．GGMC Go ではそれ以前に 150～200 Elo 程度の向上を得て
Sylvain にも伝えていたので，Sylvain が Kato が追試して強くなったと聞い
ている，と答えたためにどういう実装なのか色々訊かれました．
その時の FA としては，３種類現れる色（手番）の扱いに注意することと，確
か Erik だったと思いますが，Progessive Widenning とは相性が悪いという
話になった様に覚えています (ですが MoGo の論文にある FPU に初期値を与
えることで PW と似た効果を得ることができます)．
加藤
--
Hideki Kato <mailto:hideki...@ybb.ne.jp>
Hiroshi Yamashita
> RAVEはどの程度効果があるものなのでしょうか?
2年前のデータを見ると
RAVEあり 0.539
RAVEなし 0.348
対MoGoの9路、4000poと10000po(MoGo)で。1000局
とかなりRAVEの効果はあるみたいです。
最初に組み込んだときは勝率が0.50 -> 0.53程度のかなり小さい
伸びだったような気がします。
他に、AyaではProgressive Windeningでplayoutの数に応じて上位
log(playout_sum/ 40.0) / log(1.4) +2
の手で枝狩りをしてるのですが、1手手を追加するときに、raveの勝率が
突出している手を優先的に追加する、というのを入れています。
これで、三目中手みたいな、発見が難しいけど有効な手を時々見つけてくれます。
ものすごく悪手が挙がってくることもあるので、そういうのは排除しています。
AyaではMoGOの論文そのままの足し方をしてるのですが
EricaのAjaはDavid Silverの式が一番良かった、といってました。
私はいまいちよく分かってない式なのですが・・・。
http://www.mail-archive.com/compu...@computer-go.org/msg10335.html
http://www.yss-aya.com/rave.pdf
山下 宏
Hiroshi Yamashita
山下 宏
typedef struct child {
int iti; // 手の場所
int games; // この手を探索した回数
float value; // この手の評価値(+1 で勝ち、0 で負け)
int rave_games; // RAVEでの探索回数
float rave_value; // RAVEでの評価値
} CHILD;
double go::uct_tree(int col)
{
for (loop=0; loop<upper_num; loop++) {
CHILD *pc = &phg->child[loop];
if ( pc->games ) {
double logdiv = log((double)phg->games_sum) / pc->games; // log や sqrt は非常に高速
double uct = FACTOR * sqrt( logdiv ); // UCB1
uct_value = pc->value + uct;
if ( pc->games > 0 && fRave && pc->rave_games ) {
const double K = 100.0; // 100対戦数ぐらいではraveを優先。
double rave = FACTOR * 1.0 * sqrt( log((double)phg->rave_games_sum) / pc->rave_games );
double rave_value = pc->rave_value + rave;
double beta = sqrt(K / (3 * pc->games + K));
double uct_rave = beta * rave_value + (1 - beta) * uct_value;
uct_value = uct_rave;
}
} else { // 未展開ノード
uct_value = 10000 + rand_mc_max(100);
}
if ( uct_value > max_value ) {
max_value = uct_value;
select = loop;
}
}
}
add_stone(p_te)
if ( pc->games < create_new_node_limit ) {
win = -mc_one_simulation_start(UN_COL(col)); // 1 or 0
} else {
win = -uct_tree(UN_COL(col));
}
}
if ( fRave ) mc_rave_update(win,p_te->iti,phg); // RAVEでの更新
del_stone(p_te);
float win_prob = (float)(pc->games * pc->value + win) / (pc->games + 1); // 単純平均
phg->games_sum++;
pc->value = win_prob;
pc->games++; // この手を探索した回数
}
// 1回のmcが終わった後に、残されたデータから打たれた手全部に対して更新する。-1 <= win <= +1。白番で来たとき反転する
void go::mc_rave_update(double win,int hit_z,HASH_GO *phg)
{
if ( hit_z == 0 ) return;
int col = board[hit_z];
char board_played[BOARD_SIZE];
memset(board_played,0,sizeof(board_played));
board_played[hit_z] = col; // これもRAVEでカウントするのは変だ・・・
int i;
go *pgo = &local[thread_id+1];
int loop = pgo->mc_one_simulation_loop;
for (i=0;i<loop;i++) { // 0番目の手は un_col から始まる。MCの手を追加
TE *p_te = &pgo->te[0][i];
int z = p_te->iti;
if ( z==0 ) continue;
if ( board_played[z] ) continue;
board_played[z] = p_te->color;
}
for (i=depth;i<mc_start_depth;i++) { // 現在の深さからUCTで降りた時の手を最初に追加。
int z = path[i]; // rootで mc_start_depth = 1, depth = 1
if ( z==0 ) continue;
if ( board_played[z] ) continue;
board_played[z] = (char)board[z];
}
int played_num = 0;
int child_num = phg->child_num;
for (i=0;i<child_num;i++) {
CHILD *pc = &phg->child[i];
int z = pc->iti;
if ( z==0 ) continue;
if ( board_played[z] != col ) continue;
float win_prob = (float)(pc->rave_games * pc->rave_value + win) / (pc->rave_games + 1);
pc->rave_value = win_prob;
pc->rave_games++;
played_num++;
}
phg->rave_games_sum += played_num;
}
----- Original Message -----
From: "荒木 伸夫" <ark_...@hotmail.com>
To: <computer...@googlegroups.com>
Sent: Thursday, May 05, 2011 10:48 PM
Subject: [cga:132] RAVE縺ョ蜉ケ譫
>
荒木 伸夫
荒木です。本当にお世話になっております。
>加藤さん
Progressive Wideningとの相性が悪いとおっしゃったので、MoGoの論文にある方式に
変えてみたのですが、明らかに弱くなってしまいました。
バグがあるかもしれないので、もう少し調査してみます。
>山下さん
コードまで見せてくださって、本当にありがとうございます。
読んでみたのですが、rave自体でやっている内容はAyaと私のプログラムで差はないように思いました。
>他に、AyaではProgressive Windeningでplayoutの数に応じて上位
>log(playout_sum/ 40.0) / log(1.4) +2
>の手で枝狩りをしてるのですが、1手手を追加するときに、raveの勝率が
>突出している手を優先的に追加する、というのを入れています。
>これで、三目中手みたいな、発見が難しいけど有効な手を時々見つけてくれます。
>ものすごく悪手が挙がってくることもあるので、そういうのは排除しています。
ひとまず試してみようと思います。
現在9路盤でGNUGo3.8 Level10相手に2000poで4割～5割くらいの勝率です。
(モンテカルロ碁を作り始めのころからpoの質はあまり向上していません。
poの速度は数倍になりましたが、それでも2000po/s～3000po/s@9路盤くらいです。)
不動碁が以前1000poで勝率5割とおっしゃっていたので、差はRAVEの有無だとおもっていたのですが
なかなかうまくいきませんね。
Hideki Kato
をお勧めします．
http://webdocs.cs.ualberta.ca/~games/go/fuego/fuego-doc/smartgame-doc/sguctsearchweights.html
加藤
Hiroshi Yamashita: <A4809267E5114EBDA600BEB63982B389@gah55md2h>:
荒木 伸夫
PWを外し、加藤さんのおっしゃっていた「FPUに初期値を与える」と言うのを組み込み、
バグを取ったところ、9路盤 2000poで GNU Go Level10 と100局対戦で
RAVE有：54%、RAVE無：47%
という結果が出ました。
100局では信頼度が低いので同様の条件で1000局対戦させてみました。
RAVE有：50.4%、RAVE無：39.0%
でした。
RAVEの効果があったようです。
加藤さんや山下さんに比べると薄いようですが。
山下さんのおっしゃっていた「RAVEの値が突出しているものをPWで加える」というのも
今度試してみます。
ありがとうございました。
Hideki Kato
>荒木です。
>
>PWを外し、加藤さんのおっしゃっていた「FPUに初期値を与える」と言うのを組み込み、
>バグを取ったところ、9路盤 2000poで GNU Go Level10 と100局対戦で
>RAVE有：54%、RAVE無：47%
>という結果が出ました。
>100局では信頼度が低いので同様の条件で1000局対戦させてみました。
>RAVE有：50.4%、RAVE無：39.0%
>でした。
>RAVEの効果があったようです。
>加藤さんや山下さんに比べると薄いようですが。
RAVE の効果はシミュレーション（の質？; 決定的な方が効く様な気がする）に
かなり依存するので，単純な比較はあまり意味がありませんが，上の勝率からど
の程度強くなったかを計算すると 100 Elo 弱，悪くないと思います．
＃FPU の初期値に何を使っているかが気になりますが．
>山下さんのおっしゃっていた「RAVEの値が突出しているものをPWで加える」というのも
>今度試してみます。
>
>ありがとうございました。
MCTS の性能に一番大きく効くのは（何と言っても）シミュレーションの質なの
で，こちらに注力するのもアリかと．
加藤
荒木 伸夫
>
> RAVE の効果はシミュレーション（の質？; 決定的な方が効く様な気がする）に
> かなり依存するので，単純な比較はあまり意味がありませんが，上の勝率からど
> の程度強くなったかを計算すると 100 Elo 弱，悪くないと思います．
> ＃FPU の初期値に何を使っているかが気になりますが．
>
「prior」と付いている部分のことだと解釈していますが、MCシミュレーションで
確率計算に使っている値を大体1.0～0.0の幅になるように調整して使っています。
> MCTS の性能に一番大きく効くのは（何と言っても）シミュレーションの質なの
> で，こちらに注力するのもアリかと．
GWが終わってしまいました。
Hideki Kato
>加藤さん
>>
>> RAVE の効果はシミュレーション（の質？; 決定的な方が効く様な気がする）に
>> かなり依存するので，単純な比較はあまり意味がありませんが，上の勝率からど
>> の程度強くなったかを計算すると 100 Elo 弱，悪くないと思います．
>> ＃FPU の初期値に何を使っているかが気になりますが．
>>
>FPUというのはhttp://www.geocities.jp/hideki_katoh/387.jp.pdfの論文の
>「prior」と付いている部分のことだと解釈していますが、MCシミュレーションで
>確率計算に使っている値を大体1.0～0.0の幅になるように調整して使っています。
どうスケーリングするか．線形か，対数か，それとも他に何か良いマッピングは
無いのか？ 実験で決めるしかないのか？ 等，課題は多々．
＃元は着手確率 (の対数尤度)？
>> MCTS の性能に一番大きく効くのは（何と言っても）シミュレーションの質なの
>> で，こちらに注力するのもアリかと．
>Simulation BalancingをGW中に試そうかと思っていたのですが、試さないまま
>GWが終わってしまいました。
バランスはもちろん大切ですが，中身が先かも．相手がアタリに継がない可能性
をどうやったらほぼゼロにできるかとか，シミュレーション中のシチョウは，中
手は，等々，たくさんあります．
荒木 伸夫
> どうスケーリングするか．線形か，対数か，それとも他に何か良いマッピングは
> 無いのか？ 実験で決めるしかないのか？ 等，課題は多々．
> ＃元は着手確率 (の対数尤度)？
元は着手確率ですね。
> バランスはもちろん大切ですが，中身が先かも．相手がアタリに継がない可能性
> をどうやったらほぼゼロにできるかとか，シミュレーション中のシチョウは，中
> 手は，等々，たくさんあります．
ので、そこを目指さないと。
そして私のプログラムはシミュレーションが遅いという。topとの差は開く一方ですね。
Hideki Kato
term) の係数を調整しないといけません．強いプログラムの場合，ほぼゼロにな
るのが普通の様です．
＃Olivier 曰く，RAVE が十分な擾乱を与えている．
加藤
荒木 伸夫: <BAY166-w56FD695DC...@phx.gbl>:
荒木 伸夫
加藤さんのこのメールを受けて、何回かパラメータ調整をしてみましたが、
今のところ効果は現れていません。
何か現れたら、お知らせします。
> Date: Sat, 14 May 2011 20:44:51 +0900
> From: hideki...@ybb.ne.jp
> Subject: Re: [cga:143] RAVEの効果
> To: computer...@googlegroups.com
Hiroshi Yamashita
> 今のところ効果は現れていません。
Ayaで加藤さんお勧めのFuegoの式を使ってみましたが、
19路での勝率が0.50 -> 0.56に上がりました。ただし9路では逆に
0.45程度まで落ちました。
double beta = sqrt(K / (3 * pc->games + K));
このbetaの計算を下のようにします。
double m_raveWeightParam1 = (1.0 / 0.9); // fuegoの式
double m_raveWeightParam2 = (1.0 / 20000);
double moveCount = pc->games;
double raveCount = pc->rave_games;
beta = raveCount / (moveCount * (m_raveWeightParam1 + m_raveWeightParam2 * raveCount) + raveCount);
MCは微妙なパラメータで勝率がころころ変わるので
CPUが余ってたら8通りなどを変えて一気に試す、と見つけやすいです。
Ayaでも上の0.9を20000をかなり変えてみましたが、そのままで最適のようです。
山下 宏