2016-04-21

オセロ3

オセロ

そろそろまともな評価関数を作成しようと考えてリバーシの評価関数の最適化を読んで最急降下法の実装をしたけど，どこか実装がバグってるのか解が発散して困っていた．
最急降下法の練習にともうちょっと簡単な問題を設定してそれを解いてみようと考えて解いてみた．

問題

区間 $[0, 2 \pi$ ]を等分するM個の点 $x_1, x_2, ..., x_M$ を取り，関数 $\displaystyle f(\vec{w}) = \sum_{i=0}^{M} {(\sin(x_i) - \sum_{j=1}^{N} w_j {x_i}^j)}^2$ を最小化するベクトル $\vec{w}$ を求める．
つまり，sinと多項式の和との差の二乗を最小にする係数を求めることになる．

最急降下法

pdfの式変形に従うと， $\displaystyle r_i = \sin(x_i) -\sum_{j=1}^{N} w_j {x_i}^j$ とすると $\displaystyle \frac{\partial f}{\partial w_j} = -2 \sum_{i=1}^{M} r_i {x_i}^j$ になって，更新の式は $\displaystyle w_j^{(k+1)} = w_j^{(k)} + 2 \alpha \sum_{i=1}^{M} r_i {x_i}^j$ になる．
実際に実装して，取る点の数と多項式の次数を調整してどの程度近似出来るかデータを取ってみた． f:id:odan3240:20160421115240p:plain
縦軸が誤差の値，横軸が次数，各グラフは点を何個取ったか．表示されていないのは結果がNaNになった部分．
次数が8辺りで誤差が改善されなくなっているのと，点の数(学習に使うデータの数)が増えるとNaNに発散しているのがわかる．
オセロの評価関数のために書いた最急降下法の解が発散したのは学習データを用意しすぎたのが原因なのかな．

実装したコード
github.com

追記

学習率 $\alpha$ をデータの個数で割って正規化してやらないとダメで，その処理が抜けてました． f:id:odan3240:20160422094440p:plain

2016-03-31

自作クラスをunordered_mapに突っ込む

自作クラスをunordered_mapに突っ込むには、std::hashを特殊化してそのクラスにoperator==が定義されていないといけません。
operator==の定義はメンバ変数同士が等価か調べればいいとして、std::hashを特殊化する時にハッシュ値をどう生成すればいいのか問題になると思います。上手にハッシュ値を生成してやらないと効率の悪いunordered_mapになってしまいます。

boostにはこれに対するhash_combine(size_t & seed, T const& v);という解決策があるのですが、C++の標準ライブラリには入っていないようです。ググるとこの関数の実装がヒットして次のようになってます。
Reference - 1.55.0
まあこれを自作クラスのハッシュ関数に実装すればいいのです。ちなみに0x9e3779b9という数値の理由は2^32 / phi = 0x9e3779b9みたいです

stackoverflow.com

#include <bits/stdc++.h>
using namespace std;

struct Hoge {
    int n;
    double d;
};
bool operator==(const Hoge &lhs, const Hoge &rhs) {
    return lhs.n == rhs.n && lhs.d == rhs.d;
}
namespace std {
template <>
struct hash<Hoge> {
    size_t operator()(const Hoge &hoge) const {
        size_t seed = 0;
        auto n_hash = hash<int>()(hoge.n);
        auto d_hash = hash<double>()(hoge.d);

        seed ^= n_hash + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= d_hash + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};
    
}
int main() {
    unordered_map<Hoge,int> mp;
    
    mp[Hoge{0,1.0}]=1;
    return 0;
}

2016-03-13

RUPC2016参加記

一日目

RUPC1日目、omuさんとnisshyさんとでチームno2で参加します
— odan (@odan3240) 2016年3月6日

去年もチームを組んだomuさんと、くじ引きで引いたnisshyさんと参加した
まずA問題を担当した。一番端に取り付けるのが効率いいしそうしようと考えて実装して通したけど、解説で入力のたびにその反対側に同じ重さだけ取り付ければ良いと聞いて自分の頭の悪さにつらくなった。
D問題で最大値の最小化だし二分探索？何か良い貪欲があるのかな？とか考えていたらomuさんがDPだと言って通したり、E問題でわからないなあこれって考えていたらnisshyさんがメモ化再帰で深さが $O(\log N)$ だから大丈夫だと言って通していたりしているのを横で座っているだけだった。
チームとしてはA,B,C,D,Eの5完だった
ほぼ座ってるだけだった...

二日目

RUPC2日目、tsukasa_diaryさんとmotxxさんとでチームmottoで参加します
— odan (@odan3240) 2016年3月7日

まずB問題を担当した。場合分けミスりそう、サンプルケースが弱いから自分でケースを作らないとダメ、添字が0と1逆になってたとかで時間がかかり30分後ぐらいにACした。
D問題の場合分けのチェックをチームの人と考えたあとF問題を通してるチームが多いからF問題を考えると解法が思いつく。実装して提出するけどWA.チームの人に反転処理が間違ってることを指摘されて修正してAC.算数力がなくてつらい。E問題について考えていたらいつの間にかG問題が通っていてすげーってなる。
残りの時間でE問題とH問題を考えていたけど通せずに終わり。
チームとしてはA,B,C,D,F,Gの6完だった
D問題とかH問題はチーム内で会話しながら解法を詰めていったけどこれは初めての経験で新鮮だった。

三日目

RUPC3日目、kzyKT さんと立命の人(非HNぽい？)とでチームkaoで参加します
— odan (@odan3240) 2016年3月8日

まずB問題を担当した。考えても2重ループになる、約数の個数っていくつだっけ？ローリングハッシュを使えば通せそう？とか考えて疑いながらも実装して投げると通った。
F問題はデータ構造ぽいけど「きっちり」をどう判定するんだって考えていたら、D問題を通した後のkzyKTさんが真ん中で折り返せば良いと言ってすごいなあと感心する。F問題を実装しているのを観察して終了間際にAC. チームとしてはA,B,D,Fの4完だった
真ん中で折り返すって発想が出ないのが自分の弱いところだと認識できた。がんばりたい...

おわりに

チーム戦は個人戦とは違う面白さがあったり強い人の思想を知れたりして楽しかったです。コンテスト終了後も競プロについて話していてモチベが上がりました。
あと最近競プロ始めた学科の人を連れてきたんだけど彼も刺激になったらしくてよかった。
運営や作問の方々ありがとうございました。

2016-01-05

オセロAI2

オセロ

進捗メモ。続くかな

置換表のバグが取れた。バグの原因は同じ局面かつ次に打つ色が異なる場合を同じ状態として持っていたため。このような状態で置換表がバグると考えてはいたけど、実際には起こりえないとして無視していたら実際に発生したっていう。去年の本番直前にバグに気付けてほんとよかった。

Boardの着手可能手の列挙と反転処理の実装にSIMD命令を使ってみたがあまり速くはならなかった。使い方が間違ってるのか、これが普通なのか分からない。FFO40でしかベンチマーク計測してないけど
具体的には、着手可能手の列挙の部分に手を加えると2秒程度の高速化、反転処理の部分に手を加えるとむしろ遅くなった。反転処理の部分は条件分岐を消すために必ず16回ループを回すようにしているのが原因で、SIMD命令を使わない方が速い結果になったんだろうと考えられるけど、着手可能手の列挙の部分は原因不明。

あと、SIMD命令で条件condが真ならbを、偽ならcをaに代入するには以下のようにすればいい

a = (b & cond) | (c & cond)

maskを使えば条件分岐を消せることを知った時は感動した

2015-12-25

SIMD命令でプログラムを高速化

AVX命令入門―Intel CPUのSIMD命令を使い倒せ

作者: 北山洋幸
出版社/メーカー: カットシステム
発売日: 2015/02
メディア: 単行本
この商品を含むブログ (2件) を見る

学校でこの本を借りてちょっとかじってみた
1000行1000列の整数行列の積を計算

avx_test.cpp · GitHub

Visual Studio 2015で適当に最適化オプションを加えて実行したらそれぞれの実行速度が24368 [ms]と16447 [ms]になった。単純に8倍にならないのは予想してたけどそれでも思ったより速くならなかった

これ使ってオセロAIのBoardクラスを高速化したい

サイト

x86/x64 SIMD命令一覧表（SSE～AVX2）

Intel Intrinsics Guide

組み込み関数（intrinsic）によるSIMD入門

2015-12-14

オセロAI

学内では毎年12月にオセロAIのコンテストが開催されていて、今年は今月の12日にあった。CODE RUNNERと日程が被ってたから学科の友達にAIだけ渡して参加してもらったら優勝できたらしい。今回は1ヶ月前ぐらいから準備を開始したけどそれでも間に合わなかったから来年は今年実装できなかった部分を実装しきって参加したい(参加資格はB3以下だから次がラストになるし)。

書いたコード
github.com

作るにあたって調べたこととか来年の自分に向けてのメモ

参考にしたサイト

ThellというオセロAIのアルゴリズム解説。すごい詳細に書かれていてわかりやすい。 http://sealsoft.jp/thell/algorithm.html

vsOthaというオセロAIのアルゴリズム解説
vsOtha アルゴリズム解説 - 人生きつね色

東大のISで昔オセロAIの大会があったらしくその資料が置いてあるwiki.パワポを見るとオセロAIについて俯瞰できると思う(色々調べていたら上2つのAIはこの時開発されたものらしくてそれを知った時はとても驚いた)。 http://starlancer.org/~is2004/owiki/wiki.cgi?page=%A4%CA%A4%F3%A4%C7%A4%E2%A5%BB%A5%DF%A5%CA%A1%BC

Zebraという強いオセロAIの解説サイトの翻訳
強いオセロプログラムの内部動作

本

最初に借りた本。基本的なことから書かれていて読みやすかった
www.amazon.co.jp

Thellの開発者が書いた本らしい
www.amazon.co.jp

やったこと

bitBoard
negaScout
move ordering(速さ優先探索)
中盤12手、終盤20手完全読み
ラスト6手からは通常のnegaAlpha
中盤の評価関数はテーブルベース+着手可能数+確定石の数

やってないこと

定石
Book?
パターンを利用した評価関数の学習
並列処理(YBWC?)
キラー応手
置換表(途中までは実装に入ってたけど3日前にバグに気付き修正する時間はないと決めて取り除いた)
Prob Cut
ラスト1手展開
ラストn手展開
SSE4？を使ったビット演算の高速化

感想みたいなの

オセロについては既に研究し尽くされている感じがあって、調べれば調べるほど情報が出てきて楽しかった。
終盤のAIの高速化に殆どの時間を費やしたと思う。FFO test の40の読み切り時間は9秒だったけど、そこまでの高速化はしていないのに思っていた以上の速度が出たのはプロセッサの進歩のおかげなのかな。あとVisual Studioでx64のみに向けたバイナリを生成するようにすると実効速度が2倍速くなったけど、これと同じようなオプションってg++にもあるのかな(-m64がそれっぽいけどコンパイルして実行しても効果を感じることができなかった)。
-std::numeric_limits::min(); がオーバーフローすることに気づかず1週間ぐらい溶かした時はとてもつらかった。
それと前日の最終調整中に、ここで0を代入しているのに、coutすると0以外の数値が出力されるバグを見つけてしまって頭を抱えた。原因はVisual Studioでまずい文字コード(BOMなしutf-8)を使用していたせいで日本語コメントを全て取り除いたら期待通りの動作になった。
初めて単体テストを書いてみた。使ったフレームワークはGoogle Test.途中まではテストを書きながらコードを書いてたけど、最後の方は締め切りに追われてテストを書いている時間がなかったのでスケジューリングの重要性を感じた。

来年も勝ちたい

2015-12-13

CODE RUNNER 2015 参加記

予選A

ランダムに線分を選ぶんだ時の得点の平均を計算すると3本選んだ時が一番高くて、それを元に山登り法を実装したら開始1時間ぐらいで1位をとったりしてビビった。最終順位は18位まで落ちたけど50位以内に入れて満足だった。

予選B

前の部屋の1位の人が平均何秒待ってるか調べて、自分のそれを真似るみたいなことをしていたけど全く伸びなくて困る。部屋のログを眺めていると1位の人は3回ぐらいしか殴っていなくて、できるだけパワーを溜めるのがいいのかな？という考えになる。相手のHP/2だけのパワーを溜まると殴るようにしたらスコアが伸び始めたけど、気づいたタイミングが遅くて伸びきる前にコンテストが終了した。最終順位は100位ぐらいだったかな？

本戦

来年は交通費を用意できなくて、本戦は辞退したけど今年はお金があったので本戦も参加できた。
問題文を全部読むのに15分ぐらいかかって焦る。APIのリファレンスはtxtとjson両方を読む人はいないだろうからどちらか選べるようにして欲しいと思った。あと参加者のスコアグラフのページにある実数が何を表しているのかわからず、タイトルの"Assign Task"から請け負っている仕事の平均数かなって勘違いしてしまった。貪欲にある仕事が得意な人を降順にソートして仕事に間に合うように社員を割り当てる方針で書く。これで途中3位までに上がるけど、このぐらいのことなら誰でも考えつくだろうし後半失速するだろうなという考えがあったけど順位がいいから中々大きく方針を変更できずにいたら、コンテストが終わっていた。最終順位は20位だった。
順位に関してはコンテスト前は上位50人に入ることができれば十分かなって思っていたので満足しているけど、最初にガチャを回すという発想とか外注で仕事を選ぶ発想が全くなかったのは反省するべき点で、使用していない情報について利用しなくても大丈夫か？みたいなことをちゃんと考えるべきだった。他の競プロの大会と比べるとCODERUNNERはいい順位を取れることが多いし、来年も開催されるなら今年以上の順位を狙いたい。

ソースコード

gist.github.com