CGF2008/04/12 総会発表
用語の解説
連のデータ構造
連のデータ構造(構造体)
playout
3x3のパターン
UCT
現在の棋力
GnuGoとの対戦のさせ方
All Moves As First(AMAF)、(別名RAVE)について
気づいた事
サンプルコードなど
最重要論文
用語の解説
MC ... Monte-Carlo
playout ... 乱数で手を選ぶ、を繰り返して終局まで1回打ち切ること。
po ... playoutの略。
UCB ... Upper Confidence Bound. 信頼上限。
イメージとしては10台のスロットマシーンをそれぞれ何回か試して
どの台を集中的に選ぶか、という感じ。あまり試していない台が選ばれやすい。
多く試した台では勝率が高い台が選ばれやすい。
UCT ... Upper Confidence bound for Tree
UCBを各深さで行う。最良優先のような探索になる。
AMAF ... All Moves As First。最初に黒が打った手だけでなく、
playout中で黒が打った全ての手を「最初に打った」と仮定して
手の計算する方法。評価が雑だが高速になる。
RAVE ... Rapid Action Value Estimation。AMAFと同じ意味。
RL ... Reinforcement Learning. 強化学習
ELO ... レーティング。棋力を示す。勝つと上がり負けると下がる。200点差で勝率が0.75になる。
PW ... Progressive Widening。playoutが増えるほどに徐々に候補手を増やす前向き枝刈り手法。
データ構造
彩のデータ構造は下のような感じです。
・ダメの情報（位置、数）を常に正確に保持する。
・石の数
・連同士が融合したとき、小さい方の連は大きい連番号を参照するようにする
特徴としては連構造体の中に「仮の連番号」というのを持っていて
たとえば下図で、★に黒が打った場合に、
ＡＢＣＤＥＦ 1番の連 (C3) 仮の連番号 1
１┌┬┬┬┬┬ 2番の連 (E4) 仮の連番号 2
２├○○○┼┼
３├○●●★┼ これが★に打った場合、
４├┼┼┼●○
５├┼┼●●○ 1番の連 (C3) 仮の連番号 2
６├┼○○○○ 2番の連 (E4) 仮の連番号 2
というようにしてC3にある石の連番号を求める時に、仮連番号を
たどっていく、という構造にしています。
ただ、ダメの位置、を正確に持つために大きな石同士が融合するときは
かなり重いです。
Core Duo1.83GHz(シングルスレッド)で初手で打つ速さは
9路盤 40000po/秒 平均 77.5手 パターンなし。データ構造のみ(ルール無視で81回石を置くだけ)
19路盤 9300po/秒 平均354.4手 パターンなし。データ構造のみ
9路盤 7890po/秒 平均 99.8手 playoutのみ。6270po/秒 UCTあり
19路盤 1830po/秒 平均422.4手 playoutのみ。1660po/秒 UCTあり
連のデータ構造(構造体)
#define KOKYU_MAX 229 // この数以上ならば呼吸点位置は無視（計算上は19路で229個）
#define ADJACENT_MAX 10 // 19路で理論上は132個？隣接する敵の連
typedef struct {
int kari_ren; // 仮の連番号
int ishi_num; // 連の石の数
int col; // 連の色（ある方が絶対に便利なので）
int start; // 開始石番号
int end; // 終了石番号
int kokyu_num; // 呼吸点の数
int exist; // 盤上に存在していれば1、取られたら0
short kokyu_iti[KOKYU_MAX]; // 呼吸点の位置
int adjacent_num; // 隣接する敵の連の数
int adjacent[ADJACENT_MAX]; // 隣接する敵の連の番号(重複を許可。石が取られたときに削ってない）不正確！
} STRING;
連の石の位置は int ishi_list[BOARD_SIZE] という配列を一つ持って、
C3の黒石の隣、C4に黒を打った場合、ishi_list[C3] = C4, ishi_list[C4] = NULL
というようなリスト構造にして連の構造体には最初の座標だけを持つようにしています。
石をたどるときは、このリストをたどっています。
後は彩も3x3のパターンを使って、1手ごとに白と黒の確率分布を
更新しているのですが、これもかなり重いです。
後はplayoutでは石を戻さずに、最後まで打ったら次回にはコピーしなおしています。
playout
セキの扱い
石を打った直後にダメが1になって4子以上取られるなら別候補を
5目中手は読めない
パスは打つところが完全になくなった場合だけ選ぶ。
乱数での手の選び方
自殺手などはいったん、確率を0にして別の手を捜す。見つかれば戻す。
3x3のパターン
・プロの棋譜1万局から収集
・何回その形が出現したか、と実際に次に打たれた回数で、着手確率を求める。
彩では対称性を無視すると、 3x3 で 3^8 = 6561 通り、に
盤端の状態を含めて x25、 さらに8マスで直前に石が打たれたかどうか、で x9
これに白黒用で x2 、合計 6561 x25 x9 x2 = 295万パターン、を保持してます。
ＡＢＣＤＥ 盤端の状態25通り
１┌┬┬┬┐
２├┼┼┼┤ 周りが全部中央(C3)。上だけ盤端(C2)、上と右が盤端(D2)
３├┼┼┼┤ という感じで5路盤のどこを中心に3x3を取るか、
４├┼┼┼┤ という感じで25通りを保持してます。
５└┴┴┴┘
3x3のパターンの部分更新は、 1手ごとに
・自分が打った位置の周り8箇所（確率が高くなる）
・相手が直前に打った場所の周り8箇所（高い確率を戻す）
と最大16箇所更新しています。（他にも連が取れる場所などを高得点に）
UCT
UCB = その手の勝率 + α * sqrt( log(すべての手を試した回数) / その手を試した回数 )
その手を100回試して67回勝った場合、「その手の勝率」は0.67
すべての手を試した回数が1200回ならば
UCB = 0.67 + α * sqrt(log (1200) / 100 )
がその手のUCBの点数になる。UCBが一番高い手を選ぶ。
試した回数が少ないうちは誤差？が大きいので選ばれやすい。
回数が増えると勝率が高い手が選ばれる。
浅い読みで良さそうな手を優先的に深く読む最良優先探索のような感じになる。
α：0.3-1.2 ぐらい。実験で決める。
log の底は自然対数 e
UCTのサンプルコード
http://www32.ocn.ne.jp/~yss/uct_aya.cpp
現在の棋力
KGS(無料の囲碁サーバ、GTPが使えれば簡単に接続できる)で3級
日本の棋力になおすと初段程度？
AyaMC 3k (2.9k) 160000playout (Xeon 2.66GHz 8core、1手8秒ほど) AyaMCのグラフ。棋譜
AyaMC2 6k (5.5k) 10000playout (Opteron 2.2 GHz 2core、1手2秒ほど) AyaMC2のグラフ
対局条件：持ち時間10分切れたら30秒。ただし30秒x5回の考慮時間
16倍時間をかけると約2.6kほど棋力が上がる。
GnuGo 5k
彩(クラシック) 8k
銀星囲碁7との対戦成績
28勝5敗 勝率 0.84 (30000playout x8 = 240000 po)
http://www.yss-aya.com/bbs_log/bbs2008.html#bbs91
GnuGoとの成績(gnugo 3.7.10 Level 10)
19路
10000playout 44勝107敗 勝率 0.291
9路
1000playout 587勝413敗 勝率 0.587
playoutを増やした時の勝率の変化
--- 連続 GNU Go 3.7.10 - Aya 6.19d, mt=1, 2007-10-13
0.613 10000po 116/300 GnuGoの116勝、300局
0.723 20000po 83/300
0.731 40000po 136/505
0.813 80000po 88/418
0.813 160000po 96/512
0.852 320000po 49/330
0.898 640000po 32/315
0.888 1280000po 33/295
19路（GNU Go 3.7.10 標準）ですと
0.132 40000po 209/241
0.400 160000po 21/ 35
0.235 40000po 91/118 mt=4 合計で160000po、効率悪い（2007-12-18版）
ランダム（少しアタリ逃げ確率アップあり）playout ＋ UCT (2006-12-02版)
playout数 約 10000 playout/秒
123勝177敗 勝率0.41 思考時間 1局 11分 (Opteorn 2.2GHz)
147勝153敗 勝率0.49 思考時間 1局 17分
168勝132敗 勝率0.56 思考時間 1局 40分
114勝 56敗 勝率0.67 思考時間 1局100分
http://blog.livedoor.jp/yss_fpga/archives/50287760.html
GnuGoとの対戦のさせ方
GTP(Go Text Protocol)を使う。
GTP(思考エンジンを独立して作り、碁盤GUIと手の受け渡しをする。標準入出力のstdin、stdoutを使う)
http://www.lysator.liu.se/~gunnar/gtp/
2007年の電通大で使った解説資料、サンプル
http://www.yss-aya.com/gtp_uec.zip
gtptest.cpp は、ほんとに最小限なので、
実際はそのディレクトリの下にある
gtp_rand.cpp を参考にされた方がいいと思います。
このソースはGNUGOの gtp.h gtp.cpp play_gtp.cpp をそのまま使ったサンプルです。
実際は play_gtp.cpp の中の gtp_genmove とかの一部の関数を少し書き換える方が、後々便利（死活判定とか
KGSので人間と打たせる場合に石を打ち上げるオプション追加などで）だと思います。
GoGuiを使えば便利
http://gogui.sourceforge.net/
CgfGoBanでも
http://www32.ocn.ne.jp/~yss/cgfgoban_j.html
All Moves As First(AMAF)、(別名RAVE)について
RAVEというのはAll Moves As First(AMAF)とも
呼ばれている手法で、私の理解が合ってれば、
仮に黒D5白E7黒E6・・・とplayoutで打った場合に、
最初の黒D5と黒E6の順番が仮に変わっても結果は一緒だろう。
だから黒D5と打って勝ったのなら、黒E6と打っても勝った、として
計算してしまおう、という手法です。これを拡張してもし黒が
勝った場合、黒が打ったすべての手を「最初に打たれた」と仮定して
全部更新してしまおう、という非常に乱暴な手法です。
9路なら半分の50手ぐらいが1回のplayoutで更新できるので
50倍くらい手の評価速度が上がります。
追記
----------------------------------------------------------------
あの方法はAll Moves As Fist(AMAF)
（すべての着手を最初に打たれたとする）と呼ばれている手法で、
去年MoGoの作者が、通常のUCTで手を選ぶ部分に、この結果を
混ぜるとレーティングで300点ぐらい上がる、というのを発表しました。
MoGoの論文では、この組み合わせ方を
RAVE（Rapid Action Value Estimation）と勝手に造語で呼んでいるようです。
もともとのAMAFは一番最初の1993年のモンテカルロ法の論文にも登場します。
http://www.ideanest.com/vegos/
Brunoの論文にも解説があります。
http://www.ai.univ-paris8.fr/~bh/articles/acg10-mcgo.pdf
メインとなったMoGoの論文はこちらです。
Combining Online and Offline Knowledge in UCT
http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf
加藤さんの和訳がここにあります。
http://www.geocities.jp/hideki_katoh/387.jp.pdf
ただ、この論文は強化学習の専門用語がたくさん使われているの
非常に難しいです。
Hydraの作者のChillyも「分からん！」と文句をつけていました。
重要なのは以下の式だけです。
>> The most important thing in the paper is how to combine RAVE(AMAF)
>> information with normal UCT. Like this:
>>
>> uct_value = child->GetUctValue();
>> rave_value = child->GetRaveValue();
>> beta = sqrt(K / (3 * node->visits + K));
>> uct_rave = beta * rave_value + (1 - beta) * uct_value;
http://computer-go.org/pipermail/computer-go/2007-July/010380.html
論文の著者がChillyの苦情に答えて翻訳リストを作ってくれています。
Here is quick and dirty RL<->Computer Go translation
http://computer-go.org/pipermail/computer-go/2007-July/010394.html
彩ではほとんど効果なかった。UCTの候補を絞るところで前向き枝刈をしているせいかも.
枝刈をしない9路盤とかだと効果は高い？
また、RAVEは3目中手の手とかも見つけてくれたりするので
（打たれた回数が少なくても、打つと勝率が極端に上がるので）
便利そうなのですが、結局playoutの質が全てのような気はしてます。
気づいた事
・モンテカルロ法とはいえ、死活を間違うと致命的に間違う。
・隅の死活はダメ。
・連絡や石の強さ、中で生きられない厚み、などの微妙な判断は優れてる。
・playoutで死活を判断した手を打つ必要がある。
例：次に三目中手で活きますよ、と打たれたら中手を打って殺さないとダメ
サンプルコードなど
彩で使っているUCT部分のサンプル
http://www32.ocn.ne.jp/~yss/uct_aya.cpp
19路盤で乱数分布から1手を選ぶ方法
http://www.yss-aya.com/bbs_log/bbs2007.html#bbs337
マルチスレッドでの乱数の失敗（乱数の変数はスレッドごとに持たせる）
http://www.yss-aya.com/bbs_log/bbs2007.html#bbs336
19路盤でのモンテカルロ法テスト
http://www32.ocn.ne.jp/~yss/pattern.html
Visual Studioのrand()を使うと危ない場合
http://blog.livedoor.jp/yss_fpga/archives/50351066.html
最重要論文
Computing Elo Ratings of Move Patterns in the Game of Go
http://remi.coulom.free.fr/Amsterdam2007/
Remi Coulomさん、Crazy Stoneが19路版でGnuGoを超えた手法の解説。
Modification of UCT with Patterns in Monte-Carlo Go
http://hal.inria.fr/inria-00117266
Sylvain Gellyさん、他。9路でUCTを利用、3x3の手作りパターンの成功。MoGo
Combining Online and Offline Knowledge in UCT
http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf
playoutでRAVEを利用してレーティングが300点ぐらい9路で上昇。
強化学習の特殊用語が難解。
加藤英樹さんの日本語訳があります。
http://www.geocities.jp/hideki_katoh/
元のページに戻る