codingame -Mean Max- 参加記

この記事はKogakuin Advent Calendar 2017 6日目の記事です。

Kogakuin Univ Advent Calendar 2017 - Adventar

今回は世界111/2512位、日本5/67位でした。前回から随分と順位が下がってしまい、悔しいですね。

  

今回のゲーム

f:id:kera6rhy:20171129144819p:plain

貴重な水を相手より多く集めろ!ってゲームです。(映画MadMaxのパロディらしい)

3種類の車を操って、灰色のタンク車を倒すことで水が出現します。

↓のゲームのプレイ映像を実際に見てもらったほうが雰囲気はわかります。

Coding Games and Programming Challenges to Code Better

 

今回のゲームの特徴(ゲームAI作成の視点から)

・車はx,yそれぞれ-6000~6000の範囲の座標を持つ(状態数が多い!)

・車を3台同時に操る必要がある

・車たちは簡単な物理演算にしたがって動く

・1対1ではなく、3人のプレイヤーで戦う

・各車はそれぞれ妨害スキルを使用することが出来る

 

各車が出来ることは2つ

1:指定した(x,y)の方向に向かって、指定した量のアクセルを踏む

2:指定して(x,y)の地点にスキルを放つ

 

となっています。

 

今回の方針

シミュレーションベースではなくルールベースでやってみました。理由は1ターンあたり制限時間50msで車の行動選択肢が多く、シミュレーションはできないだろうと思ったため。(上位陣はシミュレーションがほとんどらしく、この判断ミスが最大の敗因ですね)

 

実装

Reap→Dest→Doofの順に行動を決めています。

1つの車あたりの処理

1:行き先を決める(Reap→Wreck、Dest→Tank or Wreck、Doof→敵Reap)

2:1ターンで進むであろう(適当予想)移動ベクトルを求める

3:移動ベクトルを加算した時に、他の車と衝突しなくなるまで移動ベクトルを回転させる

4:現在の車の速度を考慮して、求めた移動ベクトル通りに進むように、加速ベクトルを求める

 

今回は4番について詳しく解説します。

 

行き先ベクトルをそのまま加算しても、車はその方向には進みません。現在の車の速度ベクトル+移動ベクトルとなってしまうためです。

f:id:kera6rhy:20171129173751p:plain

正しく移動させるには、以下のような加速ベクトルを求める必要があります。

f:id:kera6rhy:20171129173809p:plain

この加速ベクトルを求めるには、余弦定理を使います。今回は式変形したこちらを使います。

f:id:kera6rhy:20171129164333p:plain

式の各変数を以下の図のように当てはめます。

f:id:kera6rhy:20171129161011p:plain

 

ここで、|b|を最大の600と決めます(移動は常に最大加速で進みたいので)。するとcの長さが決まり、-a+c=bによってbの速度ベクトルが求まります。

この速度ベクトルを出力すると、行き先ベクトル方向にきれいに進むようになりました。

 

細かく言えば他にも、cの長さが行き先ベクトルより長かった場合の処理(通り越してしまう)や、そもそもbが存在しない場合の例外処理も実装しましたが、(適当な処理でごまかしただけなので)解説は割愛します。

 

 感想

 ルールベースを実際にやってみたところ、かなり実装コストが高かったためかなり時間を取られました。1つ1つのルールの実装コストは低めですが、大量のルールを実装しなければならない、といった感じです。

対して、シミュレーションベースは初回にシミュ完成させるまでは実装コスト高ですが、それ以降の実装のノビが良い気がしました。

正直、ルールベースが大変なんてことは常識なのですが、「ちょっと挑戦してみたい」という気持ちが消化できて良かったです。二度とルールベースはやりません。

 ルールベースが適切な問題のあるらしいので、これからは問題に対して使用する手法をよく吟味しようと思います。

 

 

パーセプトロンを多層にするとなぜXOR回路を表現できるのか

自分なりの考察をまとめました。

 

なぜ考察するに至ったか

単層パーセプトロンは線形であるのに、多層になっただけでなぜXORの非線形領域分類ができるのか疑問であったが、手元の資料では解説されてなかったため。(論理回路的にはAND、OR、NANDの組み合わせで出来るから、それを真似れば出来ます〜程度であった)

 

 解説

単層パーセプトロンは線形領域でしか分類できません。これは式を見ても明らかです。

f:id:kera6rhy:20170612231239p:plainf:id:kera6rhy:20170612231651p:plain

そのため、単層パーセプトロンではXOR回路は表せません。

f:id:kera6rhy:20170612232105p:plain

 

一方、AND回路、OR回路、NAND回路は単層パーセプトロンで表せます。

f:id:kera6rhy:20170612233352p:plain

f:id:kera6rhy:20170612233334p:plain

f:id:kera6rhy:20170612233345p:plain 

 

 

そして、論理回路的にはXOR回路は以下のように表せます。 

f:id:kera6rhy:20170612232536p:plain

 

これを上で書いた各回路のパーセプトロンでそのまま置き換えるとこのようになります。

f:id:kera6rhy:20170612232740p:plain

 

 このうちの2層目であるAND回路部分が、今回私が疑問に思った点です。

「NAND回路出力結果とOR回路出力結果を、AND回路に入力する」とは、一体なんなんだ....

図を用いてしばらく考察したらイメージできました。

 

f:id:kera6rhy:20170612234936p:plain

このようなイメージのことを言っているのだと分かりました。

 

OR回路、NAND回路の入力はともに重みw=1なので、右のグラフ中では赤:1,青:1、灰:2となります。この値を高さと見れば、グラフの軸が3次元方向にもう1つ追加された感じでしょうか。

この内、高さが1.5以上であるのは灰部分のみであるので、その領域にある黒点がヒットし、XOR回路が表現されるという仕組みです。別の言い方をすれば、非線形領域を分類できる仕組みです。

 

考察

層を増やすということは、グラフの次元を1つ増やすことなのでは?と思った。

グラフの次元を1つ増やし3次元方向の高さを自在にコントロールすれば、非線形どころか飛び飛びの領域も分別できるなーと思った。

 

 

 

ちなみに、NAND回路のみでXOR回路を表現した場合は以下のようになり、先程のものと異なった形となります。ぜひ自分で確認してみてください。

f:id:kera6rhy:20170701144646p:plain

 

 

CodinGame - Code4Life - 参加記

keraです。

 

いつもCodinGameはタイトルが何かしらの映画タイトルになっているはずなのですが、今回の元ネタはよくわかりませんね。

 

今回のゲームは、市民のために薬を開発してスコアを稼ぐゲームです。

今回の順位は世界8/2366位、日本3/48位でした。

 

 

今回のゲーム「Code4Life」の概要

 とりあえず、こんなゲームです。

↓ゲーム画面

www.codingame.com

 

研究室のロボットを操縦して、様々な病気に対する薬を生産することが目的です。色々ルールがあります。

 

・市民に蔓延している病気の(病原体?)サンプルが配達される

・サンプルを解析すると必要な材料が特定できる

・材料には5種類の分子が存在する

・必要材料が揃えば、そのサンプルに対する薬ができ、スコアをもらえる

・サンプルにはランクがあり、高いものほどスコアと必要材料が多い

・薬を作成するとロボットのスキルが上がり、以後、作成の必要材料数が減る

・最終ターン時に、相手よりスコアが高ければ勝ち

 

これに加え、いくつか制限があります。

制限

・一度に持てるサンプルが3つまで

・一度に持てる分子は10個まで

・研究室で同時に存在する分子は、常に各5つ(ある条件下で6つになるが無視)

 

つまり一言でいうと、限られた資源をいかに上手く利用するか、いかに相手の邪魔ができるかが勝負のキモとなります。

 

 

 

実装したアルゴリズム

※この部分はプレイした人向けなので、説明してない部分が大量に出てきます。

基本設計方針

ステートマシン、だと思います。(定義をあまりしらない)

つまり、SAMPLES、DIAGNOSIS、MOLECULES、LABORATORY別にそれぞれ独立した関数を持っていて、ロボットがいる場所を担当する関数しか実行しません。

共有している変数があり(ほぼ全て)、それを利用して各処理が連絡を取り合ってます。

 

基本戦術

高ランクのサンプルはほぼ無視して、扱いやすいランク1サンプルを集めながら相手の妨害を優先します(同時に自分の専門スキル上げも狙います)。すると相手は諦めてクラウドにサンプルを上げるので、それを奪います。

奪うのには以下のメリットがあります。

・相手が自分の代わりに解析してくれるので、時間節約につながる

・相手が諦めるのは自分がそのサンプルの材料を持っているからであり、つまり相手が上げたものは自分にとって美味いサンプルである

まあこの2点が論理的に正しいかはわかりませんが、大体その通りに動きます。

 

どれくらい相手の邪魔をするかというと、相手がサンプルを解析しに行った段階で自分の行動をキャンセルし、分子供給場に向かって妨害待機するくらいです。

 

薬の作成

今回はいかに節約するかが大事なので、薬を提出する順番による専門スキルアップの差も考慮した最適・最小数な方法を追い求めるようにしました。

実装としては、薬の全提出パターンをシミュレートして、最も少ない分子数だったパターンを採用するような形です。

 

相手の妨害

相手が必要としている分子について、相手より先に集められそうならば集めます。自分の薬作成をそっちのけで妨害に走ります。

妨害は自分の手持ち分子が10個になるまでやり尽くします。

 

サンプルのアップロード

いらないサンプルをむやみにアップロードするということは、結局、すぐ相手に持って行かれ(上記の理由より)自分が不利になります。

ここでその時1位だった人の戦術を真似し、既にクラウドにいい物がある時に限り、手持ちのサンプルと素早く交換するようにアップロードするようにしたところ、確かに強くなりました。

 

 

感想

まあまあ満足です。

今回は一日平均3時間しかかけないでこの記録を出せました(今までは平均約9時間)。Ghost in the Cellの記事で書いた今後の目標の「最低限文化的な生活を送りながら」という部分が達成できたと思います。

 

また、今回は前回のCODERS OF THE CARIBBEANの記事でも書いた、コンテストにおける知見・改善案を実践してみました。以下の2つです。

・バグ撤去よりも新機能の実装を優先する

・上位陣の戦略をよく観察する

2つ目はいいと思いますが、1つ目に関してはこれが良い決断かは断言できません。しかし、実際にこうして好成績を残せたのは事実です。考察の余地はあるのではないでしょうか。

ちなみに、実は最終提出AIには(割りと致命的な)バグが有りました。結構頻繁に無限反復横跳びやり始めます(もちろん負けます)。これがなければもう少し順位上がったと思いますが、時間がありませんでしたね。

やっぱりバグ撤去と新機能の実装はトレードオフなんですかね。バランスが大事なんですかね。

 

一度でいいから優勝したい。

 

Codingame - CODERS OF THE CARIBBEAN 参加記

 

 

CODERS OF THE CARIBBEAN、タイトルからして海を連想させますね。

今回は船から大砲を撃って敵を倒すゲームです。

今回の順位は世界66/3623位日本5/69位でした。

↓ゲーム画面

www.codingame.com

 

今回のゲーム

・2人プレイ、ターン進行系、六角形タイル状マップのゲーム

・1人で1〜3隻の船を操作する

・船は地雷の設置や大砲の発射、船自体を衝突させるなどができる

・船は常に燃料を消費し、尽きたら沈む

・海に散りばめられている樽を回収すると燃料が補充できる

・相手の船を全て沈めれば勝ち

というものです。

 

実装したアルゴリズム

基本方針

船1隻に対して個別に2ターン先までを全探索(残り1隻のときは3手先まで)。

1ターンで船1隻が行える行動は、待機、加速、減速、左旋回、右旋回、大砲の発射の計6パターンと見て実装。

最初は3隻の移動パターン全ての全探索(1ターン:6×6×6=216通り、2ターン:216×216=46656)を実装したが、処理制限時間である50msを越えてしまうため、このような(6×6×3(隻))^2=11664通りで省略する形となった。(1ターン先しか読まないと詰み攻撃を回避できないため、2ターン先読みは外せない)

 

移動系

基本は近い樽に向かって移動。燃料を相手より多く保持するかが重要なため、意図的に樽を入手するタイミングは遅らせたりしている。

次ターンで敵攻撃の被弾(地雷や大砲)が確定してしまうタイルには触れない。

樽を全て回収した後は、敵の船に近づかせる。

何かあった時すぐ移動できるように、船の前方は空きタイルを保つ。

マップの端にいるにも関わらず、船がマップ外の方向に向いていたらペナルティ。(逃げ道が確保できない)

 

攻撃系

大砲の発射は、敵がそのまま真っすぐ進んだ場合の場所を狙う。

地雷も設置出来るが、戦略的な重要性が良く分からず実装はやめた。

自分より相手の近くにある樽に対しても大砲で狙い、敵の樽回収を妨害する。

 

生贄

実は燃料を残したまま被弾して一気に燃料0になると、その場に樽を残していく。その樽をうまく回収すれば自分の燃料がまた増え、相手より長く生き続けられる。これを狙うためにわざと自分自身を攻撃してその場に樽を出現させる戦術がある。(生贄)

樽を全て回収した時点で相手の方が燃料が多かった場合、自分の船1隻を生贄に捧げる。

 

感想

コンテスト期間10日間中95時間もかけてこの結果なので、正直なところ惨敗という感じです。

シミュレーターのバグを除去することに手こずり、勝利要素の考察に時間を使っていませんでした。(結局コンテストが終わってもバグは無くならなかった)

ランキング上位の動きを見てみると、いかに詰み攻撃をするかという攻めの戦略をしてましたが、私が必死で実装してたのはどのように敵より長く生き残るかと言った守りの戦略でした。上位陣の試合は常に見れるはずなのに目の前のバグに四苦八苦して、考察を疎かにしたことが敗因です。

 

改善点を挙げるならば、目の前にあるバグを完全に除去することよりも新しい機能・戦術の実装を優先すべきである、といったところでしょうか。

次回も頑張ります。

 

 

 

Codingame - Ghost in the Cell の参加記

keraです。

世界4位という肩書をもらえて幸福度が絶賛上昇中です。

↓順位表へのリンク

www.codingame.com

 

内容

・codingameとは

・今回のゲームの概要

・コンテストを振り返る

・本コンテストで必要だと感じたスキル

・感想

 

 

Codingameとは

・世界中の人が参加できるゲームAI系のプログラミングコンテスト

・年に5~6回のペースでコンテストが開催

・1週間ほどの制限時間の中で戦う

Webページ上で参加できるので、参加するためにまず○○を導入する(よくこれに結構時間がかかる)というものが無い点では、初心者に優しい。(ただしページは英語)

 

 

今回のゲームの概要

今回のGhost in the Cellというゲームは、簡単に言えば軍隊に指示を出して敵を倒すゲームって感じです。(似ているゲームが思いつかない...よくストラテジーゲームと言われるものに近いかも)

ゲーム勝利条件は相手の軍隊の殲滅か、最後に軍隊数が多かったほうが勝利となっています。

↓のリンクに実際のゲーム画面が載ってます。

https://plus.google.com/+Codingame/posts/AnXzBKaSaUH


ゲーム自体は質素に見えるかもですが、自分の作ったAIが世界の誰かが作ったAIと勝負すること自体に燃えるので意外と楽しい。

 

 

コンテストを振り返る

今回の期間は2017/2/26(日) 2:00(深夜)~2017/3/6(月)4:00(深夜)

(フランス企業が主催なのでどうしても時差が)

ちなみに学生で春休みだったので毎日6〜14時間ほどやってました。

 

2月26日

朝起きたら日本のスタートダッシュ勢の一人が暫定世界一位を獲得!この人を目標に頑張る

 

2月27日〜3月1日

ずっとバグに悩まされる。やればやるほど弱くなっていって自信を無くしてた。

コードが汚いのが原因だと考え、一度コード全体を整理整頓した。コードの全体像を把握することができ、そして必勝法を思いついた(あとで考えてみればそうでもなかった)。

 

3月2日

ひらめいた戦略(攻撃型ではなく防御型が最強なはずだ!)を実装したら順位が急上昇(確か3000人中500位→40位) 

細かい付け足しの後、暫定世界一位に (一瞬)

 

3月3日〜6日

終盤に入り、強い人が続々と追い上げてきた頃。

・細かいバグ取り

・対戦してわかった戦略上の穴を埋める

・強い人の戦略を盗み取る

をひたすら繰り返す。(ちなみにコンテスト中は自分のAIがずっと他の人と対戦してます)

そして最終的には世界4/3508位、日本1/81位に決定!(ちなみに学生のみなら世界1/1150位)やったぜ!

 

 

 本コンテストで必要だと感じたスキル

考察力

・このゲームはどのような戦略なら勝てるか

・ルール上の穴は無いのか

・相手の戦略は何が来そうか

のようなことを考える力

 

観察力

・なぜ今この相手に負けてしまったのか(相手との差は何か)

・相手のAIから盗めるものは何か見つけられるか

・今の自分のAIにバグのような挙動は見られるか

のようなものを対戦リプレイから見つける力(コンテスト中は対戦のリプレイを見ることができる)

 

実装力

・いかに制限時間内に頭の中の戦略をソースコードに変換できるか

・いかに早くバグに対処できるか

のような、いわゆるプログラミング力

 

逆を言えばこれらの力が身についたと感じました。

 

 

感想

今回僕が上位に行けた要因は、多少の考察力・観察力・実装力に対してのドーピング役となる「有り余る時間」 があったからですね。いわゆる時間パンチです。(あとレッドブル毎日飲んでました)

つまり他の全てのことを犠牲にしてるので、あまり賢くないです。

今後の目標は、このようなコンテストがあっても自分の勉強や文化的生活レベルを犠牲にする必要がない程度まで、 考察力・観察力・実装力をあげることですね。

 

追記 4/4

Github上に載せていた最終版AIのコードを削除いたしました。

Codingameはコンテスト終了後も同じゲームを継続してプレイできることが特徴です。

実は私のコードを丸コピしてプレイしている人が一定数いるらしく、コンテスト後の継続プレイに対する楽しみ(トップを目指す楽しみ)を奪ってしまうことに繋がるため、今回のような削除をしました。(私の配慮が足りていませんでした。)

 

裏を返せば(?)、いつでもGhost in the Cellをプレイできます!みなさんやりましょう!

 

  

プログラミングコンテストのすすめ

この記事は、 Kogakuin Univ Advent Calendar 2016 - Adventar 19日目の記事です。

www.adventar.org

 

目次

・この記事は

・私のプログラミング生活

・言いたいこと

プログラミングコンテストの種類

・その後の私

・さいごに

 

この記事は

プログラミングが好きだけど何すればいいか分からない、または1人で何かを作って自己満足で終わってる人、に向けてメッセージを贈る記事です。私の経験を垂れ流しながら書きたいと思います。

 

私のプログラミング生活

私が本格的にプログラミングを始めたのは大学1年生の時です。当時はゲームや様々なシミュレーションを作って遊んでいました。

 2年の冬、CODEVSというプログラミングコンテストに出会いました。ゲームAIを作って他の人が作ったAIと対戦するコンテストです。日本中の学生・社会人が参加します。

私は腕に自身があったので上位を狙って参加しました。

 

周りとの差に絶望しました。

予選にもかかわらず、ランキング上位のAIはありえないスコアを平然と叩き出しているのです。大学内ではダントツでプログラミングが出来るのに、まるで通用しなかった。

 

決勝会場には誰でも入ることができ、私も参加しました。自分も一生懸命挑戦したゲームの決勝戦、ランキング上位陣の試合を巨大スクリーンで見るのはとても盛り上がりました。

大会終了後の懇親会では、ランキング上位の方や社会人の方とお話することが出来ます。目の前にいる強い人から戦略やスキル、実生活のお話が聞けて、とても刺激を受けました。

また同じくらいの順位の方とは大体スキルが同じなのでより親近感がわき、それで話も盛り上がりました。

 

大学内ではダントツでプログラミングが出来る私は、その場ではごく普通の人でした。

 

言いたいこと

自分1人で勉強したり、大学内でしか関係を持たないのはもったいないです。だいたい井の中の蛙で終わります。外と接触し自分のスキルがどの位置にいるのかを知ることは重要です。

それにはプログラミングコンテストに参加することが一番です。

 

また1人でやるよりも、仲間やライバルを持ち、格上の人とのつながりを持つことは重要です。周りに人がいると刺激受け、モチベーションが上がり、脳のなんとかホルモンが増え、より効率良くスキルアップすることに繋がります。(気持ちは重要)

その周りの人を作るためにもプログラミングコンテストは使えます。

 

プログラミングコンテストは本当に使えます。積極的に利用していきましょう。

 

プログラミングコンテストの種類

コンテストには種類もいくつかあり、大きく言えば以下の3種類に分けられるんじゃないかなと個人的には思います。

・ゲームAIコンテスト系(codevs、samurai coding、codingame等)

競技プログラミングコンテスト系(atcoder、code festival、topcoder等)

・作品コンテスト系(U-22プログラミングコンテスト等)

 

この分類は結構適当で、CTFやトラブルシューティングコンテスト、ISUCONなどまだまだたくさんのコンテストがあります。ぜひ調べてみてください。

 

その後の私

実は私よりプログラミングが出来る人が大学の後輩にいたり、大学の同級生に同じくらいの人がいて全然ダントツじゃなかったりってのが後から分かるんですが、まあ当然のように頻繁に集まるようになります。

やっぱり大学内にプログラミング仲間がいることは重要です。モチベーションの上がり方が違います。

またコンテストに参加したことで自分にはまだまだ努力が足りないことを知り、さらに勉強に励むようになりました。

そしてコンテストで知り合った方とSNSで繋がることで、様々な情報を得るようなりました。

 

そんなこんなで最初に参加したCODEVSから1年半後、CODEVS for STUDENT(ついこの間決勝があった)では、決勝3位という結果を残すことができました。

 

努力バンザイ

 

 最後に

CODEVSは超オススメです。だってプログラミングで対戦が出来るんですよ!楽しくない訳が無い。

そして「決勝戦を見る」という形で2度楽しめることも重要なポイントだと思います。

他のコンテストにはなかなかない魅力ですね。

youtubeやニコ生タイムシフトに決勝戦の動画があるんで見てみてください。

 

CODE VS for STUDENT決勝で提出したAIの解説

CODE VS for STUDENTに参加し、決勝3位を取ることができました。(嬉し悔しい)

決勝で提出したAIプログラムについて詳しく書いていきます。

 

(初ブログなんでたくさん記事修正してくかも)

 

やったことリストは以下のようになります。

・ビームサーチ

・評価関数 

・盤面の選択方法

・高い評価値を記録したコマンドリストの保存

・同スコアの盤面を間引く

・発火タイミング

・高速化

 

ビームサーチ

ゲームAIを作るときに定番のアルゴリズムで、強くなるためにはほぼ必須のものです。

私個人的には、高さはゲームによって変わるが、幅は広く、いかに多様性のある盤面を選定することが強さにつながると理解しています。

今回のAIでは大体高さ20、幅300となっています。

 

評価関数

このゲームで強くなるには、素早く大連鎖を作ることが求められます。そのためには「連鎖がどんどん伸びてゆく」状態の時に評価値が高くなるような関数をうまく作る必要があります。

採用したのは「ブロック1つを落とし、そこから発生した連鎖スコア」です(連鎖スコア:スコア+連鎖数)。これを1〜9の全番号のブロック・盤面中の1〜10列目の全列にやるので、合計90回調べます。90個の連鎖スコア中もっとも高いものを評価値に加算します。

これで現在どのくらいの連鎖能力を持っているかが分かるので(個人的には潜在的連鎖スコアと呼んでます)、もし更に連鎖が伸びる一手を見つけた場合そちらの方に進化します。この進化を複数回やっていくと大連鎖にたどり着けます。

 

盤面の選択方法

上の評価の仕方では、「一見連鎖には関係ないように見えるが、あとあと大連鎖につながる一手」というパターンを評価できません。

これを評価する方法が全く思いつかなかったため、ランダムに盤面を選定することで偶然見つけることを期待することにしました。

盤面を評価値で降順でソートした時、上位は評価関数により「たった今連鎖が伸びた盤面」が来ます。そのため後半のものを集中的にランダムで選択しました。

また、実際に連鎖させた盤面からは更に先に探索しないようにしました。

このゲームのスコアは指数乗に上がっていきます。そのため同じブロック数で10連鎖を2回よりも20連鎖を1回やったほうが強いです。

そのため連鎖させたあと2発目をどう考えるかよりも、いかに1発を強くするかに思考時間を使うべきだと考えたため、連鎖させた盤面は選定をやめ、まだ連鎖させてない盤面(後出しのほうが更に強い連鎖を持っている)のみを次の探索に持っていくようにしてます。

 

高い評価値を記録したコマンドリストの保存

標準出力で送るパックの列・回転数をコマンド、20ターン先読みした際の20個分のコマンドをコマンドリストと個人的に呼んでます。

ビームサーチ時の盤面の選定には乱数要素を用いてるため、前のターンのコマンドを現在のターンでも探索で見つけてくれる保証がありません。せっかく乱数で偶然見つけた大連鎖の盤面も、全く同じ乱数を召喚しないとその盤面にたどり着けません。

これを回避するため、高い評価値を記録した盤面のコマンドリストは保存し、次のターンではそのコマンドまでの盤面は評価値を補正することで必ず生き残るようにしてます。また最初は20ターン後での最高評価値のコマンドリストを保存してましたが、多様性を持たせるため各ターン後での最高評価値の分も含め合計20個保存してます(直感なので、理論的に多様性が生まれるのかは不明です)。

また潜在的連鎖スコアとは別に、単なる発火でのコマンドリストも同じように20個保存してます。

 

 同スコアの盤面を間引く

これは偶然見つけたもので、

score += random()*0.01 → score += (int)(random()*10)*0.001

としただけで強くなったため採用したものです。

理論的には不明だったため、結果から憶測で「同じくらいの盤面をたくさん所持するより、数を限定することで探索を一点集中できるから強くなるんだろう」と思っていました。

しかし、あとで気づきましたがこれは「重複盤面の削除」を間接的にしていたことが関係しているかもしれません。これは強くするには重要で、一言で言うと多様性が上がります。(あまり詳しくないです)

また強いコマンドも間引く可能性があるので、結果的に強いときは強く弱いときは弱いAIが出来ました。(練習・評価用に作った「絶対に攻撃しないAI」を追い込み、大連鎖を打たせるくらい弱い)

 

発火タイミング

基本的には、1連鎖増えるたびスコアは1.3倍になるはずなので1ターン後に1.3倍以上増えなければ今連鎖させたほうがお得である、という考えです。

しかし実際は1つパックを落としても1連鎖増えないこともあるので、1.1~1.25の値を探っていました。

最終的には1.0+(ojama*0.0009)(→A)という形で落ち着き、nターン後は

score += point*(pow(A, 20-n))

というものになりました。

 

 

高速化

高速化することはビームサーチの幅を増やすことにつながるので、強くするには必須の要素です。

コード全体的に高速化できるか見てましたが、中でも評価関数の「90回連鎖させる」というのが演算時間の99%(直感)を使ってたので、ここを重点的に高速化しました。

「90回連鎖させる」のうち、実際に連鎖するのは大体4分の1ほどでした。そのため1連鎖あるか調べることの出来る軽量のシミュレーターで判定し、実際に連鎖するものだけを実際の連鎖シミュレーターに投げました。

また、ブロックの落下点周辺以外のところや、2連鎖目以上のとき1連鎖前で消えたブロックから遠い場所では絶対に発火が起こらないため、そのような場所では発火判定を行わないようにしました。具体的には落下・発火ポイントから左右下方向に4マスまでの範囲しか調べてません。厳密にはこれでは発火判定されないパターンもありますが、あまり影響はありませんでした。また上方向には省略できないと考えたため上まで調べてます。

あとは条件分岐の数を工夫してできるだけ減らしました。一番ループの深い場所のif文を別の方法に替えただけで1秒早くなったこともあり、正直そこまで影響があるのかと驚きました。

あとは小さなムダを1つずつ削ってましたが、それは割愛します。

その他の高速化としては、連鎖シミュレーションした盤面を保存することで、次ターンでまた現れた場合はその盤面をそのまま取り出すことで無駄にシミュレーションさせないようにしてます。

 

 

 

 

 

決勝で提出したソースコードgithubにあげてます。(初guthub)

github.com