- AHCは過去3回参戦
- Rating: 835(緑)
- 山登り･貪欲･エスパーを武器に戦ってきた
- メイン言語はPythonだが，今回初めてRustを使用
- Rustの方が高速な分，シミュレーションで打てる手数が多いだろうと予想
- メモリ管理も頑張りようがある
- ソースコードが膨大になってもバグをはらみづらい
- などが表向きの理由で，本心はなんかかっこいいからです
- 始まりました
- 何もしないを提出 → 2,869,199
- ウェブ版シミュレータで遊んでみる
- 1回も解けない
- こういうパズルに詳しくもないのでドメイン知識がない状態で方針を考え始める
- scoreの計算ロジックを見る
- 木は大きいほどいい
- 全域木は少ない手番で完成したほうがいい
- score計算関数を実装する
- 考察をする
- 基本的にはグラフのように扱う
- 与えられたタイルを扱いやすくする
- 各タイルを3x3に細分する
- '#': 通れない, '.': 通れる
- タイル0: [['#', '#', '#'], ['#', '#', '#'], ['#', '#', '#']]
- タイル7: [['#', '.', '#'], ['.', '.', '.'], ['#', '#', '#']]
- タイルf: [['#', '.', '#'], ['.', '.', '.'], ['#', '.', '#']]
- 元のNxN盤面を各タイルを上のように変換することで，3Nx3Nのタイルにし，グラフとして扱いやすくする→実装
- 例えば木の大きさは，この3Nx3Nグラフ上の任意の視点から到達可能な頂点のうち，3x3タイルの真ん中の個数
- これは，BFSで出せる→実装
- 閉路があると木としてカウントされない
- 閉路検出はDFSでできる→未実装
- 各タイルを3x3に細分する
- 山登り(?)をする
- 山登りと貪欲の区別があまり明確についてないです
- 空きマスの上下左右の動かせるタイルのうち，動かすことでそこを始点とした木の大きさが最も大きくなるタイルを動かす(伝われ)
- 最大T回までの試行の中で，最も木が大きくなった手順を保存し，最後に出力する
- 7,016,380で少し改善
- その他
- この日のABCは爆死して，レートが下がりました．茶色安定です．
- プライベートの用事で不参戦
- 山登りを少し改良
- 前回提出は山登り1回のみだったが，繰り返しシミュレートするようにした
- 各手番で取りうるアクションからランダムに選び，木の大きさが改善するなら即採用，すべてのアクションで改善しないならランダムにどれかをやる
- 回数制限Tまで登ったらそれまでのベストの手順を保存し，再度1からシミュレートし始める
- 13,134,145でそこそこ改善
- 長らくこのスコアを塗り替えられなくなる．．
- ビームサーチを検討する
- 山登りはゲーム木を考えると，自身の子だけをずっと葉まで見続けるイメージ
- 別の兄弟を辿っているともう少し良い手がありえたかもしれない
- 盤面の状態を保持するGameState構造体を作成
- 各手番で，木が大きい順に4(beam幅)個のGameStateを優先度付きキューから取り出し，それらの合法手をすべて試して優先度付きキューに入れる
- 競プロスマブラ部でお世話になっているサンダーさんの記事を参考に
- https://qiita.com/thun-c/items/058743a25c37c87b8aa4
- C++で書かれているが，がんばってRustに移植
- beam幅を変えたり色々やってみるものの，10,000,000前後を停滞
- 収束が早く，局所解にすぐに陥っていそう
- chokudaiサーチを検討する
- ビームサーチは根本が同じ盤面を探索するので，解の収束が早い
- そこで，一度深くまで探索しても再度浅い位置から探索をやり直し，多様性を持たせるためにchokudaiサーチを入れる
- 配列beam[T]に優先度付きキューをT個初期化
- 手番iでbeam[i]からGameStateを取り出す
- 合法手をすべて試し，結果のGameStateをbeam[i+1]の優先度付きキューに入れる
- T回探索したらもう一度1から探索を再開する
- このとき，各手番iでbeam[i]から取り出したGameStateを再度見ることがないので，同じ手を評価することなく浅いところから再度やり直せる
- しかし，ここらから実行時間とメモリ制限がきつくなってくる．．．
- しかもせいぜい11,000,000くらい
- やり残したことを考える
- 閉路検出
- さくっとDFSで実装
- こいつのお陰で13,521,742となり，初めて山登りに勝つ
- たまに検出できないことがある．．かも
- 隣接リスト表現のグラフのDFSはやったことあるが
- 行列形式のグラフのDFSの正解を知らない
- ハイパラ調整
- chokudaiサーチのビーム数やビームの深さを増やすと有意に木の大きさは大きくなる
- TLE/MLEしないギリギリを探る
- システスが怖いので，2500ms/900MBくらいに抑えたい
- 速度のボトルネックになっている部分を探す
- 意外なことに，GameState構造体に例えば木の大きさを測る関数を定義して毎回の手番ごとに計算させるより，構造体の外で木の大きさを量る関数を定義して呼び出すほうが早い(謎)
- メモリを大量に使っている部分
- big_boardの二次元ベクタが大量にある
- ベクタにせず，配列にしてヒープ領域を使わないようにできるか
- chokudaiサーチの探索の深さはTより浅くてもいいかも
- 評価関数設計
- どういう状態がいい状態なのか
- 木が大きい
- ループがない
- 手順が少ない
- 木を構成するタイルが密に敷き詰められている
- 例えば，一番外側の枠だけで木を構成することが理論上可能だが，中のタイルが使われていないと木として大きくならない
- 閉路検出
- 続やり残したことを考える
- cargo-profilerというのを使って速度のボトルネックを探す
- なんかCのメソッド？が出てきてよくわからない．
- ビームサーチ系はたぶん筋が悪い
- 盤面の状態数が多すぎる
- 時間やメモリが無限ならさらに良い解を出せるが，たぶんもう少しうまい解法がある
- パズルの知識を使えるようなもの
- 15パズルの難しいバージョンと考えられないか
- 15パズルは向きとかは考えなくていいが
- 仮に各タイルをどこに持っていきたいかがわかれば，A*なりなんなりで解けるらしい
- 評価関数設計
- 木が密
- 木を構成するタイルのうち，もっともx座標最小，x座標最大，y座標最小，y座標最大を考える
- 木を覆う最小の長方形の面積はS = |x_max - x_min| * |y_max - y_min|
- 使われているタイルが少ないのにこれが大きい状態になっていると，解が改善しづらいであろう
- 矩形の面積は段々と大きくなるのがいいだろう
- 木の大きさと矩形の面積の差が小さいのがいいだろう
- 木が密
- 初期解をいい感じにする
- 上に道があるタイルが上にあるのは意味がない
- 半分よりは下にいてほしい
- 任意のタイルを任意の位置に動かす方法
- 上に道があるタイルが上にあるのは意味がない
- cargo-profilerというのを使って速度のボトルネックを探す
- 続々やり直したことを考える
- DFSループ判定のバグを修正
- たまたまけんちょんさんのDFS/BFSのQiitaを見ていて気づいた
- 14,552,219にまで回復
- 同じ状態の盤面を二度と見ない
- これもけんちょんさんのDFS/BFSのQiitaにあったα-β 探索法から着想した
- なんらかの方法で3nx3nの盤面をハッシュ化し，構造体のメンバ変数として保持
- たぶんzobrist hashが活躍するとき．．．
- 同じのが来たらqueueに入れない→たぶんメモリ節約･高速化･多様化する
- あまり効果がなかった
- DFSループ判定のバグを修正
- 二日酔いで目覚める
- 予定があってあまり本腰を入れられない
- 実行時間･メモリともに余裕のものを提出して終了した
- システムテスト結果を受けて最終順位が確定
- 366位, 864,025,515, pef1311, rating835→970
- 反省
- good
- Rustで初めてコンテストに参加した
- move難しい
- trait難しい
- ビームサーチやchokudaiサーチを初めて実装した
- ただし合っているかわからない．．
- AHCで3連続水パフォを獲得した
- Rustで初めてコンテストに参加した
- bad
- 一度立てた方針から大きく脱却できなかった
- ビームサーチ系を中心に攻めすぎた
- 焼きなましだと全域木が見つかる場合が多かったようだ
- ローカルテストをしなかった
- なんと，提出プログラムの出力をコピーしてWeb版シミュレータにペーストです(!)
- 特に，ローカルでテストケースをたくさん作ってシステスに耐えうるか試すとかは上位陣はいつもやっている印象
- ローカルシミュレータをうまく使いこなせなかった
- 若干私生活に支障が出た
- 昼夜逆転してしまった
- 椅子に長時間座って腰痛が．．
- 一度立てた方針から大きく脱却できなかった
- good
- 感想(小並)
- 個人的にはアルゴ系のコンテストより楽しく取り組めた
- アルゴも精進が足らなすぎるのでそれはそれでやる
- 自分程度の知識で水パフォだと，まだまだブルーオーシャンだなと思った
- ビッグウェーブが来たときには強くなっておけるように今頑張るのはいいかも
- 他コンテストへの参加にも前向きな気持になってきた
- TopCoder Marathon Match
- CodinGame
- 英語．．．
- 個人的にはアルゴ系のコンテストより楽しく取り組めた
- つよつよさんの参加記を読んで復習するまでがAHCです
- terry_u16さんがマラソン本出すらしいので楽しみだ