この記事は，OIT Advent Calendar 2016の11日目の記事です。
改めて自己紹介
2日目にも記事を書きましたがもう一度
現在OITのIS科3回生です．
IM科の研究室に所属しています．
HxS*1とか競技プログラミングチーム*2に所属しています．
このOIT Advent Calendarの企画をした人です．
オセロ大会
オセロ大会とはIS科学科長のF教授がOITの内部で年に1回開催している，オセロゲームプログラミングコンテスト(学内のみ)のことです．この大会は1回生から3回生に参加資格があります．
勝敗の判定は，AI同士の対戦は先手後手を入れ替えて2回対局し，最終石差によって勝者を決めるというものです．
大会の形式は参加者を4つの予選ブロックに割り振った中で総当たり戦を行った後，予選ブロック上位者が決勝に進みそこでも総当たり戦を行って優勝者を決めるというものです．
なんやかんやで1回生の時から3年連続で参加し続けており，今年度の大会がちょうど昨日で，大会に参加出来るのは3回生までというルールもあって引退(?)となったので，オセロの盤面の表現，評価関数, ゲーム木探索アルゴリズム，大会の様子辺りを中心にこれまでの振り返りをしたいと思います．
1回生
オセロ大会を知ったきっかけは何だったか明確には覚えていませんが，きっと競技プログラミングチームに参加するうちにF教授に勧誘されたんじゃないかと思います．
- 盤面の表現
4回生の先輩から受けたアドバイスもあってオセロの盤面は64bitの整数型2つで表現していました． しかし手の生成は愚直にfor文でループを回すものだったため激遅でした．これで爆速になると勘違いしていたのだから恥ずかしい． - 評価関数
局面の評価関数はとても単純なもので，自分の石の数に隅を取っている数を足したものでした．中盤終盤共に同じ評価関数を使っていたし，この頃の自分にはゲームAIにおける評価値って概念を持っていなかった気がします． - 探索アルゴリズム
オセロAIについて解説しているサイトに必ずと言っていいほどMinMax法なるアルゴリズムが紹介されていたため，これを実装してみることにしました．競技プログラミングで再帰関数は書き慣れているためか簡単に書き上げることができました．
その後AlphaBeta法を知るけど時間もなく一応動いてるものを壊したくない思いもあって実装せず，本番はMinMax法を実装したAIで大会に参加しました． - 大会の様子
C#のスレッドを使って探索を並列化したと言っている人や，ちゃんと中盤と終盤でAIの方針を切り替えている人がいて，自分のプログラムではきっと太刀打ちできないだろうなあと不安でした．しかし実際対戦してみるとその人達のAIがバグっていたせいか，相手を全滅させて予選を勝ち抜くことができました．
決勝でもなぜか勝ちを重ねることができ，最後の試合は自分と同じく競技プログラミングチームに所属している3回生の先輩との対戦でした．
1回目の対局では1-63で大敗し，2回目の対局もそうなるだろうと予想していましたが，先輩のプログラムの思考時間が制限*3に引っかかり幸運にも64-0*4で勝つことができました．結果的に2局の合計最終石差では自分が1石差でリードしているため勝ち判定になりました．最後は怪しい勝ち方でしたがオセロ大会で優勝することができました．1回生が優勝するのは大会史上初だったらしいです．
2回生
この年が一番オセロAIの開発に打ち込んでいました．The FFO endgame test suite の#40の完全読みにかかる時間をひたすら短縮していました．最初は完全読みに5分ぐらいかかっていたけど最終的に12秒までに短縮できました．
詳しいことはここに書いてあります．
odan3240.hatenablog.com
盤面の表現
手の生成もビット演算で行う所謂BitBoardを実装しました．これでFFOの#40が1分以内に終わるようになった記憶があります．評価関数
機械学習ベースのものにしようと考えていたけど時間が足りず，人間が盤面1マスずつ重みを付けたもの+辺や角を意識した評価値になりました．探索アルゴリズム
中盤のアルゴリズムは以下の本を参考にNegascout法を採用しました．中盤では11手先を読むように設定していました．終盤はZebraの作者が速さ優先探索*5がいいと言っているらしい*6のでそれを採用しました．これによってFFOの#40が20秒台になったはず．
- 作者: 岸本章宏,柴原一友,鈴木豪,小谷善行
- 出版社/メーカー: コロナ社
- 発売日: 2010/02/08
- メディア: 単行本（ソフトカバー）
- 購入: 3人 クリック: 66回
- この商品を含むブログ (7件) を見る
空きマスが20個以下になったら完全読みするように設定していました．大会の様子
前日までAIのバグ取りをしていました．Visual StudioでBOM付きじゃないUTF-8を使うと意味不明なバグを踏むので気をつけましょう．
この年はCODE RUNNERと日程が被っていたので，学科の友達にAIだけ預けました． その友人に結果を聞いたところによると，ランダムに手を打ってくるAIに時間超過で負けた以外は全勝で優勝したらしいです．
終了直後は来年はもっと強いAIを開発して優勝しようなという気持ちに溢れていました．
3回生
1年前の大会直後は意気込んでいましたがこの年が一番やる気がありませんでした(悲しい)．
プログラム自体は1年前のものとほぼ変わらず，置換表のバグを修正した程度でした．
- 大会の様子
F教授曰く参加者のレベルが低調な大会だったらしいです．参加者に1回生，2回生が1人もいなかったし，強制参加のF研の人たちは200行程度のとりあえず動作するオセロプログラムだったし僕も全く取り組んでなかったし仕方ないねって感じです．
無事3連覇できたけど真面目に取り組んでなかったためか，喜びは薄かったです．
できればtensorflowで機械学習をやり直したり，Lazy SMPを実装したり，将棋所みたいなGUIのアプリを組んで参加したかった...
終盤ソルバの高速化に喜びを覚えたように評価関数のlossを小さくすることに喜びを覚えるようになったらまた開発を再開するのかなあ
おわり
結局一番オセロAIの開発の打ち込んでいたのは2回生の時でした．情報収集とコーディンを繰り返す日々で，OBの人のオセロAI開発ブログを発掘するなんてこともありました．
この時の経験によってプログラミング技術の向上だけでなく，単体テストを書いてTravis CIでコードの品質を担保するなど開発体制の勉強にもなったので，大会に参加出来たことに自分は満足しています．夏休みのインターンに申し込んだ時は話すネタにもなって選考を通過できましたし．
真面目に取り組むとAIを強くすることは楽しいしメリットもあるので，参加資格があるOITの人は是非参加してみるといいですよ．
