« 決戦前夜 | Main | Thell3に向けて »

August 15, 2004

オセロ大会終了

去る8月13日、オセロ大会が開催された。俺はThellの新思考エンジン"spot"で挑んだ。

結果から書くと、3勝3敗で2位であった。優勝はH氏のvsOthaで5勝1分。やはりスタートラインが違うvsOthaとの勝負は分が悪かったか…。しかし、一般リーグ4人の中で最も評価関数の実装が遅れていて一時は絶望感も漂っていた俺だが、よくここまで健闘できたと思う。勝因は高速な評価と、Buro先生のお言葉に従って作られた安定した評価関数か。

簡単に結果を書いておくと、
Thell3(黒) 対 vsOtha 13.06(白) 30 - 34
vsOtha 13.06(黒) 対 Thell3(白) 34 - 30
Thell3(黒) 対 Neothec3(白) 12 - 51 (時間切れ)
Neothec3(黒) 対 Thell3(白) 23 - 41
Thell3(黒) 対 Oxelon(白) 34 - 30
Oxelon(黒) 対 Thell3(白) 30 - 34

今回の大会で最も悔やまれることはタイムマネジメントをこれ以上ないほど軽んじていたこと。結果、タイムオーバーで1試合落とし(タイムオーバーがなければ4勝2敗だった)、もう1試合も制限時間ぎりぎりの4分58秒使い切るというきわどさで辛うじて勝利したので、タイムマネジメント機能の軽視が悔やまれる。とはいえ、タイムマネジメントに手が伸びなかったのはひとえに俺の実装力のなさとそのための余裕のなさのせいであるので、大いに反省すべきところだ。

大会には参加者以外にも先輩方や生物情報実験組もギャラリーとして現れて、なかなかの盛り上がりだった。また、H氏の友人のP氏(オセロ6段保持者)も駆けつけてくれて、特別ゲストで我々のプログラムと対局して下さった。結果、プログラムの完勝。とりあえず6段以上の実力にはなったということか。旧Thellが1級程度と評されていたのでこれはsignificant improvementと言ってよいだろう。

以下、簡単にオセロ大会までの俺の動向などをまとめてみる。結構日記では秘密主義を貫いてきたために重要な事は書いていなかったりするのだ。

7月2日
オセロ大会開催が決定される。vsOtha作者が同じ学科のH氏であることが明らかに。

7月3日
再びBuroの論文を読み始める。高速な着手、置換表などについて考え始める。

7月14日
各辺のインデックスをベースに着手可能位置をテーブルから引くという現在のボードの実装を始める。この設計のおかげで評価関数が超高速に。

7月17日
「ちょっと改善すべき点」→vector::reserveを使うこと。劇的な効果があった。

7月21日
「着手を大分高速化」→それまで着手のたびに最初から計算し直していたインデックスを、必要な部分のみ書き換えるように変更すること。→実装

それ以降、評価関数を作るためにパターンの設計などをはじめるものの、Windows Internalの講義に阻まれたりして思うように進まず。

7月31日
やっと学習プログラムが書き上がる。が、このときのコードはあまりにもバカでテスト用データでの1回のiterationに30分かかるというありさまで実用不能だった。「もう一つの評価関数」→この頃は、というか直前までLogistello風の評価関数とKeyano風評価関数の両方を作って試そうと思っていた。結局Logistelloの方だけで十分忙しくてKeyanoは試せなかったが。

8月1日
評価関数作成の目処が立たなくてなので気分転換に秋葉へ。このとき買ったCPUファンはそれから非常に役立つことになる。

8月2日
置換表ができる。

8月3日
秋葉の電脳な空気がアイディアをくれたのか、学習プログラムを書き直したところ劇的に高速に。「30分が1.5秒に」とか書いてあるが、1.5秒もほぼ100%I/Oという罠。「parityが負」→parityの計算を間違えていた。

8月5日
実用的な棋譜データに対して回帰計算が終わり、後処理も終わる。このときのコードは回帰分析後に対称形パターンについて加重平均を取るという形になっていた。しかしながら弱い。旧Thellに勝てる程度でベアには勝てない。これは棋譜の誤りのせいだろうと判断、徹底的に棋譜の終盤訂正を行うことにする。このとき使っていたfeatureはmobility/parity/potential mobility(開放度)/horz2-4/vert2-4/diag5-8/edge+2X/triangle。

これ以降しばらく棋譜訂正の計算を続けるため大して進展なし。この間に簡単につくれるKeyano風評価関数を作ろうかと思ったりもしたがあまり進まず。探索に関するベンチマークなども、まともな評価関数がない限り意味がない数値となるので何もできず。この点で評価関数から手をつけなかった俺は明らかに失敗であって、他の3人が正しかった。

途中、クラスタなども使って棋譜訂正を加速しようかと試みるが直後クラスタを落とされるという悲劇が。しょうがないのでそれまでちょっと使っていたScrZebraに全面的に頼ることにする。

また、対称形の考慮を回帰計算前に行うように変更した。

8月10日
棋譜訂正が終わる。すぐに回帰計算へ。時々学習係数betaの値を増やしてみて収束を早めるという工夫を加える。

8月11日
起きてみると計算が終わっていたので早速評価関数に適用。しかし大して強くない。うちひしがれる。あまりにショックでどの程度の強さだったか覚えていない。確か、6手読みだとぎりぎりベアに勝てる程度、なぜか先読み手数を増やすと負けるとかそんな感じだったと思う。
最も根拠の不明なfeature、開放度を省いてみることを思いつく。開放度の係数が異様に大きく、開放度が評価を支配していることが見て取れたからだ。また、開放度はボード全体をループで回して加算するため、評価関数を遅くしているという問題もあった。もし開放度を削ってよい結果が出れば一挙両得である。
開放度を削って回帰計算開始。収束を早めるノウハウがある程度たまっていたので5~6時間で計算終了。今度はベアに勝利。先読み手数を伸ばせば伸ばすほど強くなるようになった。ついにsignificant improvement。vsOtha13.02にも勝ったり負けたり。

8月12日
いまいち打ちミスがあるのが気になって、これを改善する方法を考えた結果、これまで不要として削っていたcorner2x5を加えてみることにした。2時間ほどでfeature分析コード、回帰計算コードを書き換え、計算開始。
計算終了後いろいろ検討してみた結果、corner2x5があった方がmove ordering成功率が高いようなのでそっちを使うことにする。

以降、徹夜でプレゼン資料を作りつつ先読み手数のチューニング。


……とこんな感じである。評価関数にひたすら手間取っている様子が手に取るようにわかる。

いろいろあったが、とてもいい勉強になった。最急降下法による回帰分析計算なんて、どんな統計の教科書にも書いてないし。俺一人だけではとてもここまでたどり着けなかっただろう。ライバルがいたからこそ必死になって続けられたのだと思う。オセロ大会参加者のみんなに感謝したい。

|

« 決戦前夜 | Main | Thell3に向けて »

Comments

お疲れ様です。結果報告まだかなーってずっと見張っていました(笑)
気になるプレゼン内容とかありました?

Posted by: NIES | August 15, 2004 09:38 AM

O氏のCPC(Continuous ProbCut)とかU氏のQuad Parity(盤面を4分割してparityを計算)、bitboard、H氏の終盤読み切りルーチンの高速化手法の解説なんかが興味深かったですね。
プレゼン内容はそのうち各参加者から一般公開されるんじゃないかと思うので(←とプレッシャーかけておく)、そしたらリンクを張ります。

Posted by: fujita.h | August 16, 2004 12:18 AM

Post a comment



(Not displayed with comment.)


Comments are moderated, and will not appear on this weblog until the author has approved them.



TrackBack


Listed below are links to weblogs that reference オセロ大会終了:

« 決戦前夜 | Main | Thell3に向けて »