AIChallenge 2018 参戦記

公開日:2018-11-25
最終更新:2018-11-25

CODE FESTIVAL 2018 併設のAIChallenge2018に参戦しました

結果

予選結果は4位、決勝進出ならず。

一応上位8名までが決勝進出ボーダーだったが、もう一つの決勝進出条件であるCODE FESTIVAL本戦参加をしてなかったのでそもそも資格がなかった。終わってから気づいた。

ルール概要

  • 対戦型2048
  • 1ターンがMoveフェーズとAttackフェーズに分かれている
  • Moveフェーズでは上下左右のいずれかの手を打ち、この時に同時に消したタイル数Nが次のAttackフェーズに影響を与える。このフェーズで盤面に変化を与えられなければ詰みとして、敗北決定
  • Attackフェーズでは 任意の数n (0≦n≦N) を選び、 2^(n+1) が書かれたタイルを、2^(N-n) 枚、敵の陣地の任意の場所に配置できる。
    • 例えばMoveフェーズで1枚も消せなかった(N=0)なら、2と書かれたタイルを1枚好きなところにおける。3枚消せた(N=2)なら 2を4枚(n=0)、4を2枚(n=1)、8を1枚(n=2)のいずれかを選び、任意の場所に置ける。
    • この時相手の陣地に空きスペースが不足していたら、配置できず敗北となる
  • 1手1sec以内、最大1000ターン、全ターンの合計は100sec以内。1000ターン経過時点で決着がついていないならスコアの大きいほうが勝ち。それも同点なら後手勝ち。
  • 普通の2048が4x4なのに対し、コンテストは5x5だった。

感想

  • シンプルでいい問題設定だった
  • 特にMoveで消したタイル数がAttackに使える、というのが良かった
  • 優勝プログラムのコンパイル時間の使い方が目からウロコだった
    • コンパイル時間である2分の間にTD学習をして、その結果だけ対戦で使う、というアプローチ。
    • そんな発想全く無かった。事前に学習済みデータを同梱するには提出ファイル制限が小さい、という事情から生まれた方法らしい。同形式のSamurai Codingで応用できるかも。

アプローチ

  • 2手まで展開したMCTS
  • プレイアウトの設計は以下の通り
  • Moveフェーズでは4通りの手をランダム。それが仮に反則手であっても1枚も消せない手として継続する。
    • プレイアウト中の合法手の判定をする計算コストを省略する意図
  • Attackフェーズは常にn=Nとなる手を選ぶ前提でランダムな位置に配置
    • このときに配置できない=空きが無い時、攻撃されている側を敗北とする
  • 8手先まで決着がついてなければそこで打ち切り、盤面の空きます数の差を適当に正規化した値を評価に使う
  • 次のプレイアウト対象はUCB1を使って評価した。Tunedではない。
  • 高速化として、列(行)ごとのキャッシュを作っていた。これはよく効いた。
    • 前提:盤面のタイル数値は必ず2のべき乗になるので、タイルの表現は2の何乗であるかを使う。ただしタイルが置かれていないところは例外として0。
    • 例えば 0,1,1,0,2 を左に操作すると 2,2,0,0,0 となる
    • 操作結果は上下左右のどれにでも適用できるため、5x5x5x5x5の組み合わせ分だけこのキャッシュを作れば全組み合わせの列挙ができる。
    • 試しに実装してみたところ、キャッシュの作成には30msecくらいしかかからなかった

Keep

  • 短い時間で4位なら悪くなかった。今回は1日出遅れたこともあって、実装時間は2時間x4日+休日12時間の20時間くらいだった。
  • 最終日は付箋を使って何を優先して実装し、何をしないかを簡単に整理しながら進めた。タスク管理の練習のつもりだったが、思ったより捗った。今後も使えそう。
  • はじめは組み合わせが多すぎて盤面キャッシュが使えないと思いこんでいたが、高速化を始めた段階ですぐに気がついたのが良かった
  • UCB1-Tunedを捨ててUCB1を使う、という発想は今後に活かせそうな成果。
    • UCB1は計算するためにsqrtを1回使うのに対し、UCB1-Tunedはlogが1回、sqrtが2回必要
      double ucb1(int totalCount)
      {
        if(mCount == 0){return std::numeric_limits::infinity();}
        return mSum/mCount + sqrt(2*log((double)totalCount)/mCount);
      } 
      double ucb1Tuned(int totalCount) const
      {
        if(mCount == 0)
        {
            return std::numeric_limits::infinity();
        }
        double avr = mSum / mCount;
        double s = log(totalCount) / mCount;
        double vj = mScoreSqSum / mCount - avr * avr + ::sqrt(2 * s);
        return avr + sqrt(s * std::min(0.25, vj));
      }
      
    • もし同じ回数だけプレイアウトを行って、より高い報酬を得る、という問題であればUCB1-Tunedのほうが良い結果が出るだろう
    • しかし同じ時間だけプレイアウトを行って、という話になると、UCB値を計算するための時間がプレイアウトの時間を削るようになるのでトレードオフが生まれる
    • どちらのほうが良いかは問題による気がするが、今回の設計では単にUCBの方が良さそうだった。
  • 前回投稿バージョンとの比較のための次のワークフローは良さそうだった
    • 投稿時に作ったバイナリをバージョン名をつけてリポジトリに保存
    • 手元の対戦用シェルのバージョンを書き換え、最後に投稿したバージョンにする

Problem & Try

  • 時間が取れなかったので、修正したプログラムが前回の投稿より強くなっているかの判断をだいぶ雑にしてしまった。
    • 具体的には前回バージョンと5回戦わせて5戦全勝したら次のバージョンとして投稿する、という感じ
    • 本当なら100回とか戦わせて勝ち越したら、位にしたかったけど、計算時間とかバージョン管理が複雑化しそう。汎用な仕組みを作っておきたいけど、コンテストごとの事情もあるし、なかなか...
    • 本気でやるならクラウドに投げて自動で対戦し続けて詳細を吐かせるのだろうけど、コンテストのたびにそんな環境つくりたくないな...
  • プレイアウトのスコアリングがいまいちだった
    • いろいろ試したけど、最初の方に作ったバージョンよりはっきり良い評価は見つけられなかった
    • Try: 強化学習の導入。今回はTD学習を使った日本語の論文があったし、TD学習が使えるよい機会だった。その場合はMCTSじゃなくてプログラム同様にαβのほうが良いかも。
    • Try: MCTS型の探索と、盤面評価関数を組み合わせたバージョンを考えてみたい
      • MCTSの評価は必ずしもプレイアウトじゃなくてもいいはず、と以前から考えてまだ試せていない。
      • 階層をまたいで最良優先的な動きを見せるαβとか。(IDDFSやMTD(f)は同じ階層のもの同士で最良優先という理解。調べたらどこかにはありそうだけど...)
記事が少しでもいいなと思ったらクラップを送ってみよう!
90
+1
論文紹介、知った技術、競技プログラミング参戦記書いていきます

よく一緒に読まれている記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる

技術ブログをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

技術ブログを開設する

Qrunchでアウトプットをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

Markdownで書ける

ログ機能でアウトプットを加速

デザインのカスタマイズが可能

技術ブログ開設

ここから先はアカウント(ブログ)開設が必要です

英数字4文字以上
.qrunch.io
英数字6文字以上
ログインする