オセロAIのおはなし
この記事は、OIT Advent Calendar 2017の17日目の記事でした。
弊学はオセロプログラミングコンテストという、選手が作ったAI同士で戦わせあう大会が年に1回開催されていて、面白そうだなと思って参加してみました。
申し込んだときはAIというものが全く分かっていなかったので、先輩に教えてもらったりgoogle先生に調べてもらったりしながら開発していきました。やればできるものですね。(先輩に感謝)
バグがでてくる度に髪の毛が抜けていくような感覚でしたが、なんとか1完成させました。
大会当日は別のイベントへ参加することになったので、同級生にプログラムを託して結果を待つことにしました。
お昼過ぎたあたりに、同級生から「優勝したよ」というメッセージが届いたときは、すごく嬉しかった。
AI自体はまだまだ発展途上といった感じで、来年のコンテストに向けて改良したい...と思っています。最近は機械学習やディープラーニングが流行っているので、どっちにしようかなという感じ。
使ったアルゴリズム
nega_alpha
nega_max
とalpha_beta
を組み合わせたもの。
move_ordering
枝刈りが効率よく行われるように、探索する順番を入れ替えます。自分は速さ優先探索を用いました。
空所表
探索を開始する前に、石が置かれていない場所を配列に格納しておきます。終盤は石を置く場所がほとんどないので、高速化に役立ちます。
やりたかったこと
反復深化探索
ゲーム木の構造体を作っておけば良かった(怠慢)。
nega_scout と 置換表
ば
ぐ
っ
た
Probcut
難しかった。
その他
オセロを作ってるとき、makegirlsmoeが流行ってたので、それで生成したアイコンをAIのキャラクターにした2。
参考になったサイト、本
オセロAI(odan's diary)
Visual C++ を使ってオセロを作ってみよう
ゲーム計算メカニズム (コンピュータ数学シリーズ 7)