Codingameの「Fall Challenge 2020」に参加しました。ルールはtsukammoさんのブログ記事が分かりやすいと思います。英語のルールを読むのは自分には結構大変で、この記事でルール概要を把握してから挑めたのはありがたかった。正直なところ、この記事がなかったら参加していたか怪しいです。
結果は、全体513位/7011人、Gold League内で433位/464人でした。最終日にGold Leagueにはなんとか上がれたものの、そこで何もできず終わった感じですね。初参加にしてはまあまあ良かったとみるか、まだまだ頑張りが足りなかったとみるか。微妙なところですね。
始めるとき、密かに目標していたのは、（あまり交流があるわけではないですが）ツイッター上で良く見かけるprd_xxxさん、AT274さんでした。prd_xxxさんは偶然（後述しますが、偶然としか言いようがない）上回れましたが、AT274さんはLegend League入りを達成され、ライバル視できるような状況には全くなりませんでした。それはちょっと悔しいです。
各リーグで書いたもの
・WOOD２
BREWしかないので、貪欲にpriceから高いものから使っていきました。 → 一発クリア（11/13）
・WOOD1
基本スペルが追加され、CASTできるようになりました。
とりあえず、使えるアクションをランダムに選択したものを書く → ルピーを得られずダメそうなので提出せず。
各成分の価値を1,3,4,5と決め、price/価値のもっとも高いものを作り、BREWするようにしました。 → これを提出してクリア（11/14）
・BRONZE
ここでルールが出揃います。
各成分の価値を1,2,3,4と普通に戻しました。
まず、LEARNする呪文の戦略として、得られるコストの差分からtaxを引いたものが3以下なら覚えるようにしました。
その後、盤面に対する評価関数を（適当に）作成。次のターンで評価値が最も大きくなるような行動を取るようにしました → クリア（11/19）
・SILVER
一手先しか読まないのはさすがにダメだろう、とは思っていたので、再帰を用いてDFSで全探索するものを実装します。しかし、BRONZEのとき+1手しか読めず（これでもときどきTLEした）、もう一手読もうとTLEしてしまいます……。
困ったものの、評価関数を多少直して提出 → SILVER内50位くらいまで上がる！
さらに、ちょっとバグを修正して提出 → 順位が若干落ち、SILVER内103位。このとき、prd_xxxさんが102位で上下に並ぶ！
しかし、時間が経つと順位が上がり、SILVER内15～20位前後に来る。ただ、対BOSSの勝率はあまりよくないため、GOLDに上がるのは厳しそう。
そして最終日。あまり良い改善を思いつけていないまま、でもGOLDには行きたい、という気持ちで評価関数の調整や多少の高速化・バグ修正をしていると、朝7:30頃にGOLD昇格のお知らせが来た！
提出していないのに、こんなことあるんですね。なんかこの頃、ボスと対戦させたら、（サーバーの具合で？）ボスがTLEして負けたりしていたので、そのせいかもしれません。
・GOLD
GOLDに上がったコードはそのままGOLD250位あたりまで行ったが、その後だんだんと落ち、300位を割った。
そのあたりで、修正していたコードを提出。明らかな改善はしていないものの、一応、前の提出には勝ち越しそうだった。 → GOLD450位付近（最下位付近）でも勝ち越せず、順位が上がっていかない。
このとき、余裕がなかったので、前の提出の簡易なバグだけ修正したものを投げたりするも、やはり400～450位程度。さらに、元の250位あたりまで上がった提出を再提出したりしたけど、400～450位程度。
この辺り、混乱してしまいましたが、まあどれも実力はそう変わらないはずなので、最初のコードも、時間が経てばGOLD最下位付近まで落ちたのでは、と思っています。
でも結局、GOLDに上がった提出と新たに作った提出の良いとこどりをしたつもりのものを作って、最終提出しました。
やったこと
基本は、評価関数を決めて貪欲。一手先を全探索して評価値を調べているけど、評価値を調べるときもう一回探索しているので、実質二手後を見ていました。
評価関数は、
・素材の価値は30, 55, 70, 85（BRONZEの頃とは変えています）、スコアは200点。種類数ボーナス有。
・一つの素材が多くなり過ぎても意味がなさそうなので、個数で補正。
・序盤LEARNしやすく、後半LEARNを減らすため、CASTのlengthで補正。
・CASTの中身を評価。製造前と製造後の価値の差、repeatableか、製造前素材の価値が少ないほど評価（作りやすいので）、製造後の個数が少ないほど評価（作りやすいので）
・BREWしにくい組み合わせになってハマるのを避けるため、「今の素材から初期呪文でどれかBREWできるようにできるか？ 大体、何ターンでいけるか？」で補正。
あたりを考えて実装しました。
良かったこと
普段競技プログラミングの問題を解くばかりで、こういう、ある程度長いコードを書いた経験がなかったので、それが書けたのは良かったです。
普段はIDLE（Pythonデフォルトのエディタ）を使っているのですが、今回はVSCodeを使いました。色々とありがたかったです。特に、「定義した関数のところに飛べる」というのは有難いですね。
IDLEは軽くて、電卓代わりに使うにはとても良いと思っているのですが、まともにプログラムをしようと思ったらエディタもちゃんと考えなければいけないですね。勉強になりました。
反省点
コンテスト終了時に思っていたのは、
・どうやれば良いかはよく分からないものの、パラメータ調整のためにローカルで動かす環境を作らなくてはいけなかった
というのが一番でした。
しかし、他の方のブログやValGrowthさんの反省会を見て、ちょっと印象が変わりました。
一番反省すべきは、ゲームの本質が分かっていなかったことかもしれない。BREWした後に素材を残し、repeatableな呪文を使って連鎖的に素材を作っていく……というのをあまり重要視していなかった。素材がなくなってもBREWした方が良いと思っていた。この辺りが分かっていれば（もしくは、検索などで調べていれば）評価関数をちょっと変えられたかもしれない。
あと、高速化をもっとすべきでした。
本当に高速化したいならC++など他言語への移植を考えるべきだけれど、Pythonのままでも高速化できるところはあった。どうせPythonのままだと限界があるので……という甘えがあった気がします。
DFSのとき、全部のデータを送ってましたが、idだけにすれば速くなるはず、というのは気付いていたのに実装しなかった。
単純なDFSじゃなく、枝狩りを入れる（これをビームサーチって呼ぶんですね）ことは考えましたが、上手くいかなそうと思ってしませんでした。これは、その時点の評価値だけだと、BREWのしやすさが分からず、枝狩りしてしまう可能性があると思ったためです。
しかし、他の方の記事を見ると、今回はビームサーチが正解だったようです。
連鎖させることの重要性が分かっていれば、BREWした後の素材の組み合わせが大事なので、評価値で枝狩りすることは有用だと思えたはず。そうしたらもっと深くまで探索するため、高速化を追及できたかもしれない。
このあたり。技術力がなかったせいではなく、考えが浅かったため上手くいかなかったというのは悔しいですね。
次回もし参加できたら、もっと良い順位を取りたいです。
0 件のコメント:
コメントを投稿