codevs for studentに参加しました。

codevs for studentに参加しました。
https://student.codevs.jp/


上位30%位以内を目標としていました。結果は29位(学生でない参加者を含む)。
まぁ良いんじゃないですか。


・ざっくりとした実装内容
・考察
・頑張ったとこ・ダメなとこ
・スパゲティ



ざっくりとした実装内容


探索


chokudaiサーチだと思います(?)。
17ターン先まで見る。2~4秒間探索できるだけ探索しますが、探索幅は10前後だった。


局面評価


大規模チェインを起こしたいターンのパックを落としたときのスコア。
このスコアが高ければ高いほどその局面を探索する価値があるとみなす。


コマンドリスト評価


それらのコマンドを入力し、最後のコマンドを入力した直後のスコア。


アルゴリズム(雑説明)


コマンドリストが空ならば、探索してコマンドリストとそのスコアを生成する。
コマンドリストが空でなくても探索して、それよりもスコアが良いならば、コマンドリストとスコアを置き換える。



考察


局面評価の難しさ


ブロックが少ない状態はチェインを起こしにくいので良い局面では無い。
だからといって、ブロックが多くても、チェインが起こせるとは限らないので良い局面とは言えない。

コミットログのSubmit1がこんな感じで、チェインの起こし方が分からず、頭抱えてた。

自分なりの答えは、上に示した通りです。


予測可能


codevs5.0と異なって、相手からお邪魔ブロックが挿入されない限り、完全に予測が可能。

なので、最初の1ターンで8秒程度思考して、15ターン当たりまでコマンドを生成してしまえば、
思考せずに出力を返してしまっても良い。

コミットログのSubmit6当たりまではこの方針で実装しているが、それ以降はあえて探索している。


要らないブロックの処理


obstacleブロックはもちろん、数字の大きいブロックも消しにくいので、側に寄せたり沈めたいところ。

なので、そのようなブロックを右側に寄せるようなアルゴリズムをコミットログのSubmit4,5,6辺りで実装した。

実装当時はいい感じだったが、試合後半であまり効果が得られない、
むしろ局面評価の邪魔をしていることが分かったので、このアルゴリズムを削除した。


相手の局面を読む


とある1ターンについて、「そのターンで得られる最大スコア」を計算するのは容易。
すなわち、予兆を探知することは出来る。

このタイミングで自分側でchainを起こして、相手側にobstacleを落とすことで、
大規模chainを阻止しよう、と考えることもできる。

自分側のフィールドで大規模チェインが起こせなくなるので辞めました。



頑張ったとこ・ダメなとこ



シミュレータが高速化できなかった。終始ノーアイデアでした。


Fieldクラスの内部が動的配列で実装されているのはパフォーマンス的にも良くないらしい。
std::allocatorを勉強したい。


相変わらず実装が汚い。でも今回は割りと気にしたほうだと思っている。


初めてchokudai searchとbeam searchを実装した。
ただ、このchokudai searchの利点を説明したサイトが1つも無く、よくわからなかった。


BGMを探しましたが、1曲しか見つかりませんでした。
「月とイルカ / 甘茶の音楽工房」です。



スパゲティ


https://github.com/buyoh/codevs_for_student/blob/master/codevsFS/main.cpp
前半に250行程度の実装メモがありますが、アイデア出しノートなのでスルーしてください。
間違い(149行目 → しゃくとり法)もありますし。





こんな感じかなぁ。

決勝の皆さんは頑張ってください!



追記:

こういう話を見かけた。

次回は無効化されるかもしれないけれど。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1139位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
191位
アクセスランキングを見る>>