プログラミングコンテストのすすめ
この記事は、 Kogakuin Univ Advent Calendar 2016 - Adventar 19日目の記事です。
目次
・この記事は
・私のプログラミング生活
・言いたいこと
・プログラミングコンテストの種類
・その後の私
・さいごに
この記事は
プログラミングが好きだけど何すればいいか分からない、または１人で何かを作って自己満足で終わってる人、に向けてメッセージを贈る記事です。私の経験を垂れ流しながら書きたいと思います。
私のプログラミング生活
私が本格的にプログラミングを始めたのは大学１年生の時です。当時はゲームや様々なシミュレーションを作って遊んでいました。
２年の冬、CODEVSというプログラミングコンテストに出会いました。ゲームAIを作って他の人が作ったAIと対戦するコンテストです。日本中の学生・社会人が参加します。
私は腕に自身があったので上位を狙って参加しました。
周りとの差に絶望しました。
予選にもかかわらず、ランキング上位のAIはありえないスコアを平然と叩き出しているのです。大学内ではダントツでプログラミングが出来るのに、まるで通用しなかった。
決勝会場には誰でも入ることができ、私も参加しました。自分も一生懸命挑戦したゲームの決勝戦、ランキング上位陣の試合を巨大スクリーンで見るのはとても盛り上がりました。
大会終了後の懇親会では、ランキング上位の方や社会人の方とお話することが出来ます。目の前にいる強い人から戦略やスキル、実生活のお話が聞けて、とても刺激を受けました。
また同じくらいの順位の方とは大体スキルが同じなのでより親近感がわき、それで話も盛り上がりました。
大学内ではダントツでプログラミングが出来る私は、その場ではごく普通の人でした。
言いたいこと
自分１人で勉強したり、大学内でしか関係を持たないのはもったいないです。だいたい井の中の蛙で終わります。外と接触し自分のスキルがどの位置にいるのかを知ることは重要です。
それにはプログラミングコンテストに参加することが一番です。
また１人でやるよりも、仲間やライバルを持ち、格上の人とのつながりを持つことは重要です。周りに人がいると刺激受け、モチベーションが上がり、脳のなんとかホルモンが増え、より効率良くスキルアップすることに繋がります。（気持ちは重要）
その周りの人を作るためにもプログラミングコンテストは使えます。
プログラミングコンテストは本当に使えます。積極的に利用していきましょう。
プログラミングコンテストの種類
コンテストには種類もいくつかあり、大きく言えば以下の３種類に分けられるんじゃないかなと個人的には思います。
・ゲームAIコンテスト系（codevs、samurai coding、codingame等）
・競技プログラミングコンテスト系（atcoder、code festival、topcoder等）
・作品コンテスト系（U-22プログラミングコンテスト等）
この分類は結構適当で、CTFやトラブルシューティングコンテスト、ISUCONなどまだまだたくさんのコンテストがあります。ぜひ調べてみてください。
その後の私
実は私よりプログラミングが出来る人が大学の後輩にいたり、大学の同級生に同じくらいの人がいて全然ダントツじゃなかったりってのが後から分かるんですが、まあ当然のように頻繁に集まるようになります。
やっぱり大学内にプログラミング仲間がいることは重要です。モチベーションの上がり方が違います。
またコンテストに参加したことで自分にはまだまだ努力が足りないことを知り、さらに勉強に励むようになりました。
そしてコンテストで知り合った方とSNSで繋がることで、様々な情報を得るようなりました。
そんなこんなで最初に参加したCODEVSから１年半後、CODEVS for STUDENT（ついこの間決勝があった）では、決勝３位という結果を残すことができました。
努力バンザイ
最後に
CODEVSは超オススメです。だってプログラミングで対戦が出来るんですよ！楽しくない訳が無い。
そして「決勝戦を見る」という形で２度楽しめることも重要なポイントだと思います。
他のコンテストにはなかなかない魅力ですね。
youtubeやニコ生タイムシフトに決勝戦の動画があるんで見てみてください。
CODE VS for STUDENT決勝で提出したAIの解説
CODE VS for STUDENTに参加し、決勝３位を取ることができました。（嬉し悔しい）
決勝で提出したAIプログラムについて詳しく書いていきます。
（初ブログなんでたくさん記事修正してくかも）
やったことリストは以下のようになります。
・ビームサーチ
・評価関数
・盤面の選択方法
・高い評価値を記録したコマンドリストの保存
・同スコアの盤面を間引く
・発火タイミング
・高速化
ビームサーチ
ゲームAIを作るときに定番のアルゴリズムで、強くなるためにはほぼ必須のものです。
私個人的には、高さはゲームによって変わるが、幅は広く、いかに多様性のある盤面を選定することが強さにつながると理解しています。
今回のAIでは大体高さ２０、幅３００となっています。
評価関数
このゲームで強くなるには、素早く大連鎖を作ることが求められます。そのためには「連鎖がどんどん伸びてゆく」状態の時に評価値が高くなるような関数をうまく作る必要があります。
採用したのは「ブロック１つを落とし、そこから発生した連鎖スコア」です（連鎖スコア：スコア+連鎖数）。これを１〜９の全番号のブロック・盤面中の１〜１０列目の全列にやるので、合計９０回調べます。９０個の連鎖スコア中もっとも高いものを評価値に加算します。
これで現在どのくらいの連鎖能力を持っているかが分かるので（個人的には潜在的連鎖スコアと呼んでます）、もし更に連鎖が伸びる一手を見つけた場合そちらの方に進化します。この進化を複数回やっていくと大連鎖にたどり着けます。
盤面の選択方法
上の評価の仕方では、「一見連鎖には関係ないように見えるが、あとあと大連鎖につながる一手」というパターンを評価できません。
これを評価する方法が全く思いつかなかったため、ランダムに盤面を選定することで偶然見つけることを期待することにしました。
盤面を評価値で降順でソートした時、上位は評価関数により「たった今連鎖が伸びた盤面」が来ます。そのため後半のものを集中的にランダムで選択しました。
また、実際に連鎖させた盤面からは更に先に探索しないようにしました。
このゲームのスコアは指数乗に上がっていきます。そのため同じブロック数で１０連鎖を２回よりも２０連鎖を１回やったほうが強いです。
そのため連鎖させたあと２発目をどう考えるかよりも、いかに１発を強くするかに思考時間を使うべきだと考えたため、連鎖させた盤面は選定をやめ、まだ連鎖させてない盤面（後出しのほうが更に強い連鎖を持っている）のみを次の探索に持っていくようにしてます。
高い評価値を記録したコマンドリストの保存
標準出力で送るパックの列・回転数をコマンド、２０ターン先読みした際の２０個分のコマンドをコマンドリストと個人的に呼んでます。
ビームサーチ時の盤面の選定には乱数要素を用いてるため、前のターンのコマンドを現在のターンでも探索で見つけてくれる保証がありません。せっかく乱数で偶然見つけた大連鎖の盤面も、全く同じ乱数を召喚しないとその盤面にたどり着けません。
これを回避するため、高い評価値を記録した盤面のコマンドリストは保存し、次のターンではそのコマンドまでの盤面は評価値を補正することで必ず生き残るようにしてます。また最初は２０ターン後での最高評価値のコマンドリストを保存してましたが、多様性を持たせるため各ターン後での最高評価値の分も含め合計２０個保存してます（直感なので、理論的に多様性が生まれるのかは不明です）。
また潜在的連鎖スコアとは別に、単なる発火でのコマンドリストも同じように２０個保存してます。
同スコアの盤面を間引く
これは偶然見つけたもので、
score += random()*0.01 → score += (int)(random()*10)*0.001
としただけで強くなったため採用したものです。
理論的には不明だったため、結果から憶測で「同じくらいの盤面をたくさん所持するより、数を限定することで探索を一点集中できるから強くなるんだろう」と思っていました。
しかし、あとで気づきましたがこれは「重複盤面の削除」を間接的にしていたことが関係しているかもしれません。これは強くするには重要で、一言で言うと多様性が上がります。（あまり詳しくないです）
また強いコマンドも間引く可能性があるので、結果的に強いときは強く弱いときは弱いAIが出来ました。（練習・評価用に作った「絶対に攻撃しないAI」を追い込み、大連鎖を打たせるくらい弱い）
発火タイミング
基本的には、１連鎖増えるたびスコアは1.3倍になるはずなので１ターン後に1.3倍以上増えなければ今連鎖させたほうがお得である、という考えです。
しかし実際は１つパックを落としても１連鎖増えないこともあるので、1.1~1.25の値を探っていました。
最終的には1.0+(ojama*0.0009)（→A）という形で落ち着き、nターン後は
score += point*(pow(A, 20-n))
というものになりました。
高速化
高速化することはビームサーチの幅を増やすことにつながるので、強くするには必須の要素です。
コード全体的に高速化できるか見てましたが、中でも評価関数の「９０回連鎖させる」というのが演算時間の９９％（直感）を使ってたので、ここを重点的に高速化しました。
「９０回連鎖させる」のうち、実際に連鎖するのは大体４分の１ほどでした。そのため１連鎖あるか調べることの出来る軽量のシミュレーターで判定し、実際に連鎖するものだけを実際の連鎖シミュレーターに投げました。
また、ブロックの落下点周辺以外のところや、２連鎖目以上のとき１連鎖前で消えたブロックから遠い場所では絶対に発火が起こらないため、そのような場所では発火判定を行わないようにしました。具体的には落下・発火ポイントから左右下方向に４マスまでの範囲しか調べてません。厳密にはこれでは発火判定されないパターンもありますが、あまり影響はありませんでした。また上方向には省略できないと考えたため上まで調べてます。
あとは条件分岐の数を工夫してできるだけ減らしました。一番ループの深い場所のif文を別の方法に替えただけで１秒早くなったこともあり、正直そこまで影響があるのかと驚きました。
あとは小さなムダを１つずつ削ってましたが、それは割愛します。
その他の高速化としては、連鎖シミュレーションした盤面を保存することで、次ターンでまた現れた場合はその盤面をそのまま取り出すことで無駄にシミュレーションさせないようにしてます。
決勝で提出したソースコードはgithubにあげてます。（初guthub）
