MON.T+α ProgrammingRoom

MON.T+α Programming Room

MON.T+αの活動を綴っています。

【Postmortem】トヨタ自動車 実課題プログラミングコンテスト 2023 Spring

AtCoder Postmortem

※画像は公式Visualizerよりお借りしています。

 

はじめに

　この記事は2023/03/05 - 2023/03/19にAtCoderで行われました実務解決型のコンテスト「トヨタ自動車 実課題プログラミングコンテスト 2023 Spring」の解法を紹介するものになります。

　3/5から3/19の二週間、トヨタ自動車 実課題プログラミングコンテスト（以下実課題コンテスト）に取り組みました。Visualizerが3Dなうえに、荷物しきつめ問題のプログラムは一度書いてみたかったので終始楽しみながら取り組むことができました！

　 まだシステスは行われていませんが暫定2位ですシステス後も2位でした。

　ところどころ間違っているかもしれません。間違いを発見されましたら優しく教えていただけるとありがたいです。

問題の概要

こちらは問題文を見ていただいたほうが早いと思われるので割愛します。簡単に言えば「コンテナ内に直方体の荷物を積み込む」という問題です。

問題文はこちら

atcoder.jp

 

ここで用いる独自の表現

（荷物の）依存関係

　私のプログラムでは、山登りの際にどの順に荷物を積むかは確定させず、荷物の配置だけを考えます。しかし、その配置計画を採用して実際に積む際には、荷物の配置によって「この荷物を先に置かないとあの荷物は置けない」という縛りが発生します（わかりやすいのは「あの荷物はこの荷物の上に載っている」という配置）。この、配置計画における荷物同士の順序の縛りを依存関係と呼びます。

最終提出の解法

以下、最終提出の概要です。

言語:go言語

　これはただの好みです。goの並行処理で100ケース試すものを作ったり、今回は実行時間を気にするタイプの解法だったのでgoのpprofでプロファイリングしたりとそれなりに利点はありました。

解法:乱択+部分破壊による山登り法

　以下はTwitterで行った解法ツイートです。

もう少し詳細を確認していきます。

乱択で荷物を積み上げ

　まずはランダムに荷物を積んでいきます。荷物の配置を決める順ですが、このフェーズが来る度に

・底面積の大きい順

・完全ランダム順

のどちらかを採用します。

　荷物を積む際はすでに配置の決まった荷物の角（と四隅の角）と荷物の回転方向をランダムに選択します。そして、その角に対して下の図のように四方向からくっつけてみます。

　ケースによりますが、これらの設置の仕方は高確率で不正な設置になるため、不正でない設置が見つかるまで再挑戦します。ある程度再挑戦しても見つからない場合は候補手なしとみなしてこの積み上げフェーズを終了します（速さを優先したために実は有効手が存在しても少ない場合は見つける前に終了します）。

　積み上げの際には、これまでにしてきた最善の積み上げ結果を上回るようなペナルティを受けてしまうようなものは不正な設置とみなします（過激派）。これによりこれまでの積み上げよりも悪い積み上げを長々としてしまう可能性を防ぐことができます。

　ペナルティの計算について、正確な順序ペナルティを計算する際には積む順番を確定させる必要がありますが、この段階では順番を確定させていないため厳密な値とは違う値で計算しています。　最善の配置を見つける段階では「各荷物はその上に載っている荷物やさらにその上に載っている荷物よりも先に置かなければいけない」というのを利用し、その依存関係において荷物の種類番号が逆転していないかを確認します。逆転している場合は荷物の種類番号の差を仮転倒数として追加します。これは荷物の種類番号が近い場合（特に連続している場合）にはこれによる転倒数は1で済みますが、種類番号が離れている場合には他の場所でも順序入れ替えが発生したときに大幅に増加する恐れがあるからです。順序最適化についてはまた別の部分で紹介します。

　上で述べたペナルティですが、はじめのうちは順序ペナルティを一切許容せずにやっていきます。順序ペナルティありである程度の解ができてしまうと順序ペナルティなしの状態への遷移が難しくなってしまうのが理由です。

 

配置計画を評価

　乱択で配置計画ができた(or途中で候補が見つからず打ち切った)ら、配置計画を評価するフェーズになります。基本はペナルティ（順序関係については上述）をもとに評価しますが、荷物がコンテナをオーバーしている場合には追加の評価基準が与えられます。この追加基準はコンテストのスコアに基づく評価ではなく、山登りにおいて登りやすくするための評価であり、解が改善しにくそうな状態に減点が入ります。

より具体的には以下の要素がおよそ同じくらいの影響力になるように設定しています。

・x,yがそれぞれ0付近のエリアにおいて隙間がないか（これによりx=0,y=0側のコンテナの壁は比較的しっかりと埋まる）
・荷物が高いところにないか（下が密、上が疎になっているほうが破壊→積み上げをした際に改善させやすい）
・コンテナ内の荷物の表面積が大きくないか（荷物同士がくっつくと無駄がないので改善させやすい）

　この評価がこれまでのもっともよい評価を超えていたらこれを最善の配置計画として更新します。

 

部分的に破壊

最善の配置計画を部分的に破壊します。

まずオーバーしている荷物は問答無用で破壊します。転倒数0での収容に成功していて高さ勝負となっている場合は一番高い荷物も破壊します。

その後の破壊方法は3つあります。いずれも、対象のものを破壊したのちにその荷物の上に載っていた荷物を順次破壊します。

・（収容成功した場合に限り）荷物の依存関係で順序関係が入れ替わっているものをランダム選択し、どこかにねじ込む。その際めり込んだものを破壊

・ある程度の隙間ができてしまっているところを探す。その付近に直方体エリアを設定してエリア内の荷物を破壊

・各荷物を確率pで破壊

　一つ目は転倒数最適化において効果を発揮する破壊方法なので、まだコンテナを超えている段階や、転倒数0が達成された場合には使われません。

　破壊活動が終わったところで、再び乱択フェーズに入ります。

 

破壊の様子

 

最善の計画を行動として出力

　約0.6秒制限で3回上記の山登りを行います。その中でもっともよかったものを行動として出力するわけですが、ここにきて初めて荷物の積み込み順を考える必要があります。

　まずは、貪欲に順序を決めます。貪欲の方法ですが、「上に荷物がのっていない荷物で種類番号が最も大きいものを選び、取り除く」を荷物がなくなるまで繰り返します。そしてこの順を逆順にすることで貪欲な積み込み順が完成します。

　続いて順序をswapして最適な順序を求めます。ランダムに荷物を一つ選び、荷物の積み込み順を今の順番より後のどこかに設定します。この荷物と依存関係にある荷物はそれに合わせて移動したりします。（うまく伝えられないので下の例を見てください）

例：

荷物5の上に荷物6、さらにその上に荷物3があるとし、それ以外の荷物は離れ離れに置いてあるとします。また、設置順として1,2,5,6,3,4,7,8,9というものが貪欲で得られたとします。

このとき、荷物5の順序を2つ後ろに設定するというのはこのような遷移を表します。

荷物3や6は5と依存関係があるのでswapはできず後ろに続いていきます。

仮に荷物7が荷物5の上に載っている場合は次のような遷移になります。

転倒数の変化は途中の過程を追うことで求まるので、「ランダムで選んだ荷物に対しいくつ後ろに下げるのが最もよいかを求める」を繰り返すことにより短い時間で（ほぼ）最適を得ることができます。

おわりに

　ここまで読んでくださった方、ありがとうございました。この頃はコンテストに出るたびに自分が少しずつ成長できているのを実感できてうれしいです。

　Visualizerが3Dなのには驚いたとともに、自分のプログラムが荷物を積み込んでくれる様子がとても感動的でした（「えっそこ入るのに・・・」みたいなもどかしさもしばしばありましたが）。巷では次のヒューリスティックコンテストが始まっているとか。さすがにしばらくは体を休めて、落ち着いたらそちらのコンテストも見てみようかなあなどと考えています。改めて、このコンテストの開催に携わっていた方々、他の参加者の方々、楽しい時間をありがとうございました！

おまけ

以下は解法の補足情報を雑多に書いたものです。

・有効手の計算を行っていないために、一つの荷物を設置するために数十～数百回も設置を試みなければいけない。そのため、かなりの高速化が必要だった。

・有効手の計算を行わないことによる他の欠点として、合法手が作りにくいケース（上に荷物を載せられないもの・底面変更不可の大きなものがあるケース）では、山登りに十分な試行回数が確保できていないという点があった。

・「確率pで破壊」がほぼ全破壊の可能性もあるので十分な時間があれば必ず大域解に到達できるのだが2秒（0.6秒）ではケースによってほぼ無理だったり。山を登りきれていない印象が強かった。

・「順序入れ替えありなら収容できる」というケースは想像以上に少ない(seed0~99だと10ケースもなかったと思う)上に、頑張って収容させた結果転倒数勝負でほとんど相対スコアがもらえない可能性も高いので、まずは順序入れかえなしで血眼になって探すのがスコア的には良さそうだった。3回に分けたのも局所的なところに陥って順序入れ替えなしの解を逃すことが減るようにだったりする。代わりに時間が足りず収容できるとこまで登れなかったりするのでここはトレードオフ。

 

以下はコンテスト中・後に思ったことを雑多に書いたものです。

・言及可コンテストだったので最初の解法くらいは共有したいなあと思ったけど最後まで解法を変えなさそうだったので控えた

・中盤以降は新しいアイデアもなかったので高速化に躍起になっていたが、終盤で「速度を多少失ってでも一回一回で出て来る解をまともにしたほうが良いのでは」となり微改善した

・焼きなまし、optuna使いたいけどどちらも全く使えなかった。使い方が下手なのかもしれない。

・今回ローカルでの実行を並行処理にできたのは革新的だったが、コア数を上回らないように制限しているにもかかわらずパフォーマンスが安定しなかった。

・Visualizerは作れなかった。どちらかというとスコアやデバッグ情報とにらめっこする時間が多かった。

・実課題なのに「荷物を破壊」とか「ねじ込む」とかいう表現してごめんなさい

・プログラム中の構造体の名前がいつもの癖でGameStateとかActionとかになってる

・Goは十分速い言語だと思っているので言語の実行速度は言い訳にできないんだよなあ・・・

・コンテスト後半は微改善しつつ順位表で上振れを引いて相手を絶望させる戦術をとっていたんですが、逆に火をつけてしまったかその上振れさえも超えられてしまいました・・・

・bottom-left法・・・。知識不足でした。調べてきます

・複数コンテストの取り組み方の最適化に失敗。逆にAtCoderのヒューリスティックコンテスト開催日時をユーザーの満足度について最適化してもらったほうがいいのでは？

・どうやら0.6秒制限の試行のうち一回でもvalidな解の形成に失敗してしまうと、積むことのできた荷物まででペナルティ計算してしまい採用してしまうっぽい。多分システスの2WAはこれ。

【Postmortem】RECRUIT 日本橋ハーフマラソン 2023冬(AHC018)

AtCoder Postmortem

※画像は公式Visualizerよりお借りしました

はじめに

　本日は2/18 - 2/26の期間にAtCoderで開催されたコンテスト「RECRUIT 日本橋ハーフマラソン 2023冬(AHC018)」についての記事になります。全文に目を通してられない方は上の目次だけでもぜひ見ていってください。

　2/18-2/26日の間、AHC018に取り組みました。AHC017に参加できなかった悔しさもあり相応の時間を費やしまして、最終順位は23位でした（システス後まで順位表一ページ目は保てなかった・・・）。AHCに参加するのはこれで四回目ですが、過去最高順位（そして初橙パフォ）でした！

問題設定も面白く、ヴィジュアライザで自分のプログラムの解を眺めるだけでも楽しかったです。

　Postmortemの経験も増えてきましたが、いまだ用語がよくわかっておらずところどころ間違っていたりすると思います。発見された方は優しくご指摘いただけると嬉しいです。 

問題概要

問題内容は、私自身が伝えるより問題文自体を見ていただいたほうが伝わるとおもうので以下にリンクを張っておきます。

atcoder.jp

　簡単にまとめると「水道を引きたいんですが地質調査してないのでいい感じのルート見つけながら掘ってください」という問題でした。

この記事で用いる独自表現

・flow

　水が流れているマスのことを言います。すなわち、

・水源マス

・水源マスとつながっているすでに掘削されたマス

の二つを指します。

 

最終提出AIの詳細（戦術など）

seed:0での様子を貼っておきます。

言語:Go言語

　いつもの。個人的な好みであり、特に言語的な利点はないです。

解法

以下、AIの概要です。

・基本は2フェーズ

掘削計画の基本は二つのフェーズからなっています。

 

フェーズ1: investigate

このフェーズでは代表点をとり未知のフィールドの様子をざっくりとつかみます。

1. 200*200のフィールドを12マス間隔に取った代表点のフィールド(以下ミニフィールドという)に落とし込む

2. 各代表点の頑丈さの推定値から、ミニフィールド上でflowから最も近い家とその最短路を求める

ここでもしミニフィールドの最短路上の代表点で壊せていないところがなければフェーズ1を終えフェーズ2に移行

3. ミニフィールドの最短路上の代表点でこれまでに加えた力が最も小さい場所を掘る。

4. 壊せた・壊せなかったに応じて代表点の頑丈さの推定値を変更

 

フェーズ2: destruct

このフェーズではフェーズ1終了直前に求めた最も近い家をflowにくっつけます。

1. ミニフィールドの頑丈さの推定値によりフィールドの各マスの頑丈さの推定値を補完

2. 頑丈さの推定値からflowまでの最短路を求める（掘削ルートはこれで決定）

3. 掘削ルートで、まだ掘られていないところがあまりに連続しているところはより良い推定のためにサンプルとして少し掘削（ルート変更はしない）

4. 家側から順番に掘削

 

もう少し詳しいところは以下で見ていきます。もし長い文字列で目が滑ってしまうような場合には、上に乗せたseed=0での様子と照らし合わせてみるとよいかもしれません。

・フェーズ1: investigate

1. 200*200のフィールドを12マス間隔に取った代表点のフィールド(以下ミニフィールドという)に落とし込む

落とし込み方としては「家、水源、flowを最も近い代表点に丸める」という方法があると思いますが、最終提出では「左上、左下、右上、右下方向でそれぞれ一番近い代表点（計4点）に分裂させる」という手法をとっています。

 

2. 各代表点の頑丈さの推定値から、ミニフィールド上でflowから最も近い家とその最短路を求める

Dijkstra法です。

ミニフィールド上では、移動は8方向にとります。これは、200*200フィールドにおいて、代表点間は縦→横→縦→横→・・・と繰り返すことで上下左右の代表点に近づくことなく斜めの代表点に移動できることが関係しています。

　移動コストを考えるときには、各代表点の頑丈さの推定値を用います。

壊したことのあるマス・・・壊すまでにかかったパワー

パワーを加えたことがあるが壊せていないマス・・・そこに費やしたパワー×5

パワーを加えたことがないマス・・・C×5

といった具合に雑に推定しておきます。×5としているところを増加させると寄り道を考えずらくなり、逆に減少させるとあちこち調査するようになります。

　また、移動コストの計算は縦横移動と斜め移動で多少変わります。代表点を12マス間隔でとると17×17のミニフィールドが出来上がるわけですが、以下ではわかりやすく2×2のミニフィールドでいくつかの移動コスト例を見ます。

S_{i,j}を(i,j)の頑丈さの推定値とする。

(0,0)から(0,1)（横移動）のコスト: \displaystyle (\frac{S_{0,0} + S_{0,1}}{2}+C) \times 12

(0,0)から(1,1)（斜め移動）のコスト: \displaystyle (\frac{1}{3} S_{0,0}+\frac{1}{3} S_{1,1}+\frac{1}{6} S_{0,1}+\frac{1}{6} S_{1,0}+C) \times 24

(0,0)から(1,1)への移動の仕方は以下の3つが考えられます。

・(0,0)→(0,1)→(1,1)

\displaystyle (6 \times S_{0,0} +12 \times S_{0,1} + 6 \times S_{1,1}+24 \times C)

・(0,0)→(1,1)

\displaystyle (8 \times S_{0,1} +4 \times S_{0,1} + 4 \times S_{1,0} + 8 \times S_{1,1}+24 \times C)

・(0,0)→(1,0)→(1,1)

\displaystyle (6 \times S_{0,0} +12 \times S_{1,0} + 6 \times S_{1,1}+24 \times C)

この計算式により、(0,1),(1,0)の頑丈さによっては、斜めに突っ切るほうが近いと判定してもらえることがわかります。

なお、このコストの式はフェーズ2での補完の値との整合性が取れるようになっています。

 

3. ミニフィールドの最短路上の代表点でこれまでに加えた力が最も小さい場所を掘る。

パワーは

・まだ掘ったことがないなら、Cの値と同じだけの力で掘る

・掘ったことがあるならこれまで累計で与えた力と同じ力で掘る

といった具合です。この掘り方では最悪のケースでも最適な掘り方の二倍のコストで掘ることができます。

 

4. 壊せた・壊せなかったに応じて代表点の頑丈さの推定値を変更

今回掘ろうとしたマスに累計で与えたパワーを更新しておきます。

 

・フェーズ2: destruct

このフェーズではフェーズ1終了直前に求めた最も近い家をflowにくっつけます。

1. ミニフィールドの頑丈さの推定値によりフィールドの各マスの頑丈さの推定値を補完

以下は10マス間隔で代表点を取っていたころの図ですが、4つの代表点から正方形エリアをこのように補完します。（線型）

（この図は左下と右下が比較的柔らかく、左上と右下が硬い場合です）

この補完は補完の仕方よりもPhase1のミニフィールドでのコストの式と整合性をとることが重要です。

整合性が取れてないとこんな悲しいことに・・・

 

2. 頑丈さの推定値からflowまでの最短路を求める（掘削ルートはこれで決定）

お決まりのDijkstra法になります。

 

3. 掘削ルートで、まだ掘られていないところがあまりに連続しているところはより良い推定のためにサンプルとして少し掘削（ルート変更はしない）

追加調査前

追加調査後

このくらいの幅でサンプルを取っておくと頑丈さを大きく外すことはないので、これ以上幅を小さくしてもあまり効果はなかったです。

 

4. 家側から順番に掘削

「思ったよりも掘削に力が必要だった」、逆に「ちょっと軽めにたたいたつもりだったのに壊せちゃった」があれば、前後の掘削ルートの頑丈さの推定値を微妙に操作します。これも「微妙な操作」の式自体はあんまり関係がなくて（実際雑です）、「想定よりも硬い・柔らかい」が減衰しながら次以降の掘りに反映されているところが大事だと思われます。

 

おわりに

　ここまで読んでいただきありがとうございます。過去最高順位をとることができたのもうれしかったですが、何より自分のプログラムがしっかりと硬いところを避けて掘削しているのをVisualizerで見ることができて感動しました。私は戦略性+Visualizer（ゲームをするかのような頭の使い方と視覚的な要素）からヒューリスティック系のコンテストに興味を持ったタイプで、毎度公式Visualizerが用意されているのには頭が上がりません。

　次に参加するコンテストをどれにするかは未定ですが（早ければ今週末のあれかも）、次回コンテストでもまた楽しんでいきたいです。お世話になった方々、ありがとうございました！

 

おまけ

基本的にPostmortemは以上になります。ここからは見出しにもある通り完全におまけですので、見ても有益なものはないかもしれません。

 

思ったこと、追加情報をまとまりもなく書きとどめておきます。

追加情報

・Phase1での横移動・斜め移動のコストは、Phase2で補完したときの横移動×12の総コスト・（横移動＋縦移動）×12の総コストとほぼ一致する

・ミニフィールドに落とし込む際には、flowなどと代表点の距離を用いてDijkstra法の際に初期値を増やしておくことで誤差を減らすことができる

・掘削で頑丈さを計測する時、「計測を正確にしたい」と「破壊までにかかる回数をおさえたい」がトレードオフな関係なので、あまり丁寧な計測は効果がなかった

・Phase2の代表点間の補完は線形より良い近似もあるが、追加サンプルもふまえると正確さとしてはそれ以上突き詰める必要は感じなかった

・道をつなげるとき、一発目はCに応じて予想コストの0.8倍~0.95倍で掘削していた

・ローカルで実行する際、「phase1でかかったコストを無視するか」「最適な力で掘削するか」などフラグを用意しておくと自分のプログラムの問題点が把握しやすくてよかった

 

考えたこと

・インタラクティブ問題はローカルでの実行に壁を感じて参加者が少なくなるかと思ったけどそんなことなかった

・問題見たときに「水道つなげる前に地質調査しようよ」と思ったけど、本当に最初に地質調査する問題だった

・最も柔らかい部分と最も硬い部分の差が500倍もあるというのがあまり実感がわかず、最初は調査すると自明解より弱くなるんじゃないかと思っていた

・人間の温かみのあるパラメータ調整が自分の武器だと思っているので、全人類がOptunaをうまく使えるようになってしまうとなかなか苦しい

 

次回以降に向けて思ったこと

・みんなの自作ビジュアライザがかっこいいので自分も作りたい。（他の方のVisualizerって毎回すごい見た目してるけど典型みたいなものはあらかじめ持ってるのだろうか？はたまたコンテスト中に０から作っているのか・・・？）

・ローカルで大量テストができる環境作りたい。

・コンテスト中に焼きなまししたい。（ほんとは今回するつもりで意気込んでいたんだけど・・・）

【おまけ】Fall Challenge 2022の諸々

CodinGame 検討

 

 

はじめに

　今回のコンテストでは6位と自分の中ではかなり良い順位ではあるんですが、一方で最上位に数歩届かず悔しい思いもあります（もともとLeaderBoardで雲の上とみていた憧れの人たちとLegendリーグでマッチングしているだけでもうれしいんですが）。そこで、次回こそは勝ってやるんだという気持ちでもう少しまとめてみます。

　AIの方針はPostMortemにすでに書いた通りなのですが、もう少しだけ具体的にどう実装していたかを書き残しておきます。また最後の「解法の選択」はより次回以降のコンテストのために今の自分をまとめておこうと思い書きました。（次のコンテストまで意外と期間が空いたりして今の自分が得た知見が失われていたら嫌なので・・・）

　結構長くなりますので、読んでいただける方は目次から気になるところだけ読んでいただけたら。

　前提となっている自分のPostMortemはこちら

montplusa.hatenablog.com

 

いくつかのトピック

ユニットの割り当て

　以下で説明するのはあくまで自分のbotの元となるアイデアです。

下のような場面を考えます。

（これはPostMortemの衝突地点の話で使っていたものです。）

DefencePoint（青）は自分のユニットのほうが近いマスなのでまずはDefencePointを確実に塗りたいところ。

　まずは自然にこれらの衝突地点に一番近いユニットを割り当てるというのを考えました。どの衝突地点から割り当てるかで変わってきますが、以下が一例です。

　このように3体を配置したところで、まだ割り当てていないユニットではDefencePointを守り切れない（残っている一体は相手よりに先に到達できないので向かっても確実に塗れるとは限らない）ので手詰まりになってしまいました。

　ここで、DefencePointは本来「順当にいけば確実に塗れるはずの場所」だったことを思い出すと、DefencePointを担当したユニットは絶対に敵ユニットと相殺されない、つまりその他のDefencePointも担当できるのでは？という考えが浮かんできます。

　具体的には以下のようにDefencePointから距離が増加する方向へは複数のDefencePointを担当することができます。これは各衝突地点を頂点とした有向グラフとして保存しておくと何度も割り当てを考える際に比較的高速に処理が可能です。

（このほか衝突地点はおおよそのケースで64に収まるのでbitboardをつかって高速にする方法があります。が、今回は全力で高速化、というほどまでは詰めなくても割り当て速度が問題になることはなかったです）

一例として、この複数を担当することを考えると、このような割り当てを考えることができました。すべてのDefencePointを塗ることができ、また、いくつかのNeutralPointにも割り当てることができるようです。

　加えて、相手より2ターン早く到達できるDefencePointには最前線へのスポーンも有効です。これも考慮することにより、以下のような割り当ても可能になります。

（黄色の線は新たにスポーンさせ、そのユニットに割り当てていることを明確にするために色を変えただけです）

　これによりさらに割り当ての幅が広がります。あんまり変わらないように見えるかもしれませんが、中央に一人多く送り込むことができたりするだけでかなり多くの有利が取れる場合があります。

　最前線に間に合わないユニットの割り当ても同じロジックで考えることができます。例えば、上での到達ターン制限を+1すると1ターン遅れて到着するものも考慮することができます。特にNeutralPoint（到達に必要なターンが両者同じマス）では、最速で到達できるユニットが相手と同数の場合に、最速で到達できるユニット同士が相殺され、その次のターンに送り込んだユニット数勝負になることもしばしばあるので有効です。なお、2ターン以上遅れるとなると防衛の割り当て数などが不正確になっていくので、私はどの衝突地点にも2ターン以上で遅れてしまっているユニットは最寄りの衝突地点に向かわせていました。

 

　大事だと思う衝突地点から順に割り当ててそれを行動として出力してもよいですが、これらの割り当てを得点化し、良いものを採用するとよりよい動きをしてくれるようになりました。

　この例の試合では結果として序盤の中央勝負で有利をとることができました。

（うっすらと見える青、黄、赤はゲーム開始時点での衝突地点）

 

以下のリプレイでも真ん中一列をとることができ、これが勝因になりました。

https://www.codingame.com/replay/689120836

各地点間の距離計算

　本当ならばマップ上のすべての地点間の距離を知りたいところですが、最大のマップサイズでは12*24=288頂点となってしまいとても50msでは考えられそうにないです。

そこで、各ターン必要になりそうな距離だけをいわゆるBFSによりに求めます。今回はRecyclerでいずれ緑化するマスがあるのが特に逆順で距離を求める際に悩みました。

 

1. 自分のユニットのいるマスを距離0、ユニットのいない自分のマスを距離1として、そこからBFS→自陣から各地点への距離がわかる

2. 相手のユニットのいるマスを距離0、ユニットのいない相手のマスを距離1として、そこからBFS→敵陣から各地点への距離がわかる

 

ここで、1.と2.で得た距離の差が2以下の点を衝突地点として登録します。

 

3. 衝突地点を距離0としてそこからBFSを衝突地点ごとに行う→各地点から各衝突地点への距離がわかる（注意：衝突地点への距離を衝突地点から逆にたどって求めているのでrecyclerによる緑化判定が少し複雑になります！）

 

この場面での距離を見てみます。

1.はこんな感じに。recyclerの影響で行けない場所があったり、遠回りを要求されているところがあったりします。

2.はこんな感じに。

3.はこんな感じに。（下画像黄色の四角で囲んだ衝突地点についてBFSを行っています）

この3.は以下のような緑化による最短経路の違いに対応する必要があります。

おおよそこれで行動を選択するのに必要な距離がすべて手に入りました。

（衝突地点の数が膨れ上がっていて3.が時間がかかってしまう可能性が指摘されそうですが、通常の試合ではその点は問題ありません。厳密には敵と市松模様のような模様をつくられると全地点間距離を求めることになり時間をオーバーしてしまいますが、こちらが協力して自陣に入れない限りはそうはならないです。）

 

 

解法の選択

　これは良い手を探すのにどのような手法をとるかという他のコンテストを含めた話題になります。これはあくまでまだ新参者の自分の感覚で、一般的に正しいものであるというわけではないことにはご注意願いします。もしマラソン系、対戦系コンテストを始めて少しという方ならなんか得られるものがあるかも。逆にマラソン系、対戦系コンテスト玄人の方、ご指導ご鞭撻のほどよろしくお願いします。

　問題のテーマによってどのような手法が適用しやすいかは変わってきます。ここでは、自分が適用したことのある手法と適用しやすいと感じる問題のタイプを書いておきます。解法自体の説明については自分が説明するよりも他サイトの素晴らしい解説を見たほうが良いので割愛します。

 

全探索

　自分が全探索を使ったことがあるのはCodinGameのGreenCircleなど。

　全探索の雰囲気は「いや、全部自前のシミュレーターで試したらいいやん」というもので、実際のところ、ゲーム終了までのすべてのパターンを試せるならこれが最強です。

　ところが、大体のコンテストを見てみると、パターン数が膨大ですべてを試すことができないので、「1~3ターン先までの行動をすべて試す」or「ありえない手は外してもう少し先まで試す」という風に使っています。そもそも次ターン以降の自分の状況が予測不可能だったりする場合は消去法的によくこの手法を選んだりします。

　全探索の場合、自分は評価関数はその盤面に将来性があるかなどを考慮して比較的複雑なものにする傾向があります。深さが浅い全探索自体には将来性が反映されていないのと、全探索は深さが1増えるとパターン数が跳ね上がるために多少高速化しても深さを1増やすことはできないからです。

例えば、CodinGameのGreenCircleでは、カードのドロー後からターン終了までの可能なアクションは相応に限られていたので1ターン全探索を行いました。逆にこのコンテストでは次ターン以降はカードのドロー次第で状況が変わるので読みづらいゲームでした。

 

ビームサーチ

　自分がビームサーチを使ったことがあるのはCodinGameのMadPodRacing、SpringChallenge2021など。

　ビームサーチと全探索はかなり近い手法と思っています。ビームサーチは評価値の上位のものだけ次のターンを考えていくことで全探索に比べて時間やコストを節約できます。

　ターン制の対戦型コンテストにおいて、状況を得点化して、nターンの良さげな行動を探すというのが自分の中では多いです。しかし、ビームサーチ（と後述する焼きなまし）自体は相手の動きの影響に対して弱い（と私は思っている）ので、一ターンの敵の行動によって大きく状況が変わってしまうゲームよりは、敵の影響がある程度小さいゲーム、あるいは敵との衝突要素がないマラソン系だと考えやすいです。また、結構ターン（順序関係）を意識した手法な気がします。順序関係がないものでは無理やり順序関係を作ったり、重複を除去するなどの工夫が重要になりそうです。

　ビームサーチの場合、自分は評価関数は盤面の将来性があるかなどを考慮しつつも全探索よりは軽めにする傾向があります。将来性をある程度見積もらないと数ターン後に盤面がよくなるような手がビームサーチの幅から外れてしまい探索できない可能性がある一方で、軽めにすることで幅が増やせたり、深さが深くなったりするのが理由です。

例えば、CodinGameのMadPodRacingは1ターンでマシンの向き変化はせいぜい18度ほどなので、1,2ターンでの敵の動きは台風の予測円みたいにある程度のぶれに収まります。したがって、敵の妨害などがある場合でも、敵がある程度巧みなプレイヤーでなければマシンを走行可能でした。

SpringChallenge2021は、1ターンに複数行動ができるゲームでしたが、1ターンに得られるマナ（いろんな行動のもとになるもの）がそれなりに少ないので行動数がある程度限られたことや、アクションが種を植える、木を育てる、収穫といった具合でユニットが移動するタイプではなかったので相手の影響はある程度小さいゲームでした。

 

山登り法・焼きなまし法

　自分が山登り法を使ったことがあるのはCodinGameのSmashTheCodeなど。

また、ランダム+貪欲も個人的には山登りとほぼほぼ同じものだと思っています。

　ビームサーチの場合だと「これをしてから、これをして・・・」というような順序関係が根本にあるのですが、山登りは順序関係がないものにも使いやすいです。今回のコンテストだと1ターンのユニットの動きは「どのユニットから動かす」みたいな要素がないので、ユニットを雑に動かして、山登りにより改善、みたいな発想もあるかもしれません。（私は当初はこの予定でした）

　焼きなまし法は山登りの際に確率的に悪化するものを採用するということでかなり山登り法と近いものを感じます。採用しすぎると山登りよりも悪い結果になることもありますが、基本的には山登りよりもポテンシャルのある手法だと思います。（コンテスト期間中に実装した経験なし）

　例えば、CodinGameのSmashTheCodeはいわゆる「ぷよ〇よ」だったのですが、相手による影響は「連鎖を打ってくるか打たないか」の二択だけだったので、打った場合と打たなかった場合で6手の置き方の山登りを行いました。「ぷよ〇よ」は手順のあるゲームですが、連鎖を組む行為がしばしば「一時的に連鎖をつぶす・連鎖を打たない」というタイプの行為になるので、途中段階での評価が難しく、ビームサーチを私はうまく使えませんでした。

モンテカルロ木探索（MCTS）

　自分がモンテカルロ木探索を使ったことがあるのはCodinGameのUltimateTicTacToeなど。

　モンテカルロ木探索は自分と相手が交互に手を打つ場合に使いやすいと感じています。特にボードに駒を交互に置いていくタイプのゲーム（〇×ゲーム、五目並べ、オセロなど）では手を適用するのが高速で、ランダムな手でゲームの最後までをシミュレーションするのもかなりすぐに終わるので回数を稼ぎやすく、使いやすいです。

　一方で可能な手が多いタイプのゲームだと純粋に使うことはあまり効果が期待できなくて、ありえないと思われる手（五目並べで遠い彼方に駒を置くみたいな手など）を省くなどして対策するのがよさそうです。ゲームの最後までをランダムな手で実行するタイプの場合は評価値として勝ち/負けが利用できるので、良い手が人間では想像がつかない場合にも有効な気がします。

　例えばCodinGameのUltimateTicTacToeは、いわゆる〇×ゲームの革命的な拡張版ですが、人間では何が良い手なのかいまいちわからない問題でした。一方でマスは9*9、出てくるマスは〇と×だけ、駒の移動もなしというゲームなので、ゲーム終了までランダムな手で実行するのは比較的高速でした。

 

MiniMax法

　使ったことがあるのはCodinGameのUltimateTicTacToe（Goldリーグにいたころ）など。

　この手法も交互着手だと使いやすいです。あらかじめ候補手を絞らない場合は全探索と同じ感覚だと認識しています。なお、αβ探索に切り替える（不要な計算を省く）ことで、思ったよりも先の手まで探索することができたりしました。

　　CodinGameのUltimateTicTacToeは交互に行動するタイプであったためにMiniMax法が利用できそうな問題でしたが、UltimateTicTacToeのゲーム性が難しく、うまい評価関数が見つからなかったためGoldで止まってしまいました。もちろんMiniMax法を使うLegendの人もいるので、Goldで止まるのは自分の力不足です。（ゲーム終了までシミュレートするMCTSに切り替えたところLegendに到達しました。）

　今の自分はおおよそこんな理解です。まだコンテスト経験のない機械学習、遺伝的アルゴリズムなどはまだまだ感覚が得られていませんが、いつか挑戦できたらと思っている手法ではあります。

 

 

　さて、今回の問題で考えてみると、大量の候補手やゲーム終了状態までの長さ、同時着手ということからMCTSは不向きだと思っていて、全探索やビームサーチもパターン数的にあり得ない手を削るor一つ一つのユニットを独立に扱う必要がありそうです。Minimax法も相手の動きを仮定してから自分の動きを決めてしまうのをある程度解消しなければという感じがしました。必然的に貪欲or山登りあたりが自分の手持ちかな・・・と考えてました。自分は機械学習は門外漢なので機械学習なんかも得意なタイプなんじゃないかなあなどと考えていましたが、マップのサイズやコード長制限など、機械学習にも困難があったみたいです。

この他if文の条件分岐のみで行動を決定したり、目標に向けて貪欲に行動を決定していくのも有効です。個人的には貪欲法を実装したら「多少のランダム性をつける＆評価関数を作る」「部分的に破壊して適用し直す」へもっていくのが安心安全の流れだと思っています。

　ところでルールベースっていったいどういう区分なんでしょう？自分の中では結構あいまいなんですが・・・。

 

おわりに

　この駄文をここまで読んでくださった方いるんでしょうか・・・という感じですが、ここまで読んでいただきありがとうございます。今後のコンテストに向けて自分が成長できるように書いたものでもあるのですが、もし今読んでいる方のお役にも立てていたら幸いです。

【Postmortem】Fall Challenge 2022

CodinGame Postmortem

※画像は公式Visualizerよりお借りしました

 

はじめに

　本日は12/13 - 1/5の期間にCodinGameで開催されたコンテスト「Fall Challenge 2022」についての記事になります。全文に目を通してられない方は上の目次だけでもぜひ見ていってください。

　CodinGameコンテストに参加するのは今回が4回目だったのですが、前回に引き続きLegendに到達することができました！

最終順位は

世界6位/4577人、日本4位/201人でした！（JP強すぎないか？？？）

　いまだ用語がよくわかっておらずところどころ間違っていたりすると思いますが、発見された方は優しくご指摘いただけると嬉しいです。

（早く公開することを第一にしたために「何をしたか」しか書いておりません。解法共有の重要ポイントである「どのようにしてやったか」をかけていないので、諸々の箇所に「詳細を聞きたい方がいらっしゃれば教えてください」みたいな部分があります。該当箇所にかかわらずお気軽にお申し付けください。）

→おまけとしていくつか書いてみました。

montplusa.hatenablog.com

 

　前回書いたAHC016 のPostmortemはこちら

montplusa.hatenablog.com

 

ゲーム概要

　ゲームルールにつきましては、おそらくここにたどり着いている方の多くがご存じだと思いますので割愛します。雑にいえば色塗り合戦です。

最終提出AIの詳細（戦術など）

言語:Go言語

　いつもの。特に言語的な利点はないです。

解法:ランダム＋貪欲

　いわゆる乱択貪欲というものになるんでしょうか・・・。もともとLegend解放前は貪欲で戦っていたので、順当に時間いっぱい考えるようにした結果です。

以下、AIの概要です。

・衝突地点を割り出す

各ターンマップ上のマスのうち以下のような点を取り出します。

・自分のほうが1or2ターン早く到達できるマス(DefencePoint)

・両者同じターンで到達できるマス(NeutralPoint)

・相手のほうが1or2ターン早く到達できるマス(AttackPoint)

主にこの点を守るor攻撃することを考えます。

 

例として、ある試合のゲーム開始直後の衝突地点は以下のようになっています。

青:DefencePoint　黄:NeutralPoint　赤:AttackPoint

数字は近い側の陣営が到達するまでのターン数



（Recyclerなどによりあと何ターンでマスが通れなくなるかなどを考慮しながら各陣営からの距離を求めます。このあたりの詳細が知りたい方がいらっしゃれば教えてください。）

・衝突地点にユニットを割り当て

これら3種類のマスにそれぞれ4段階の割り当て数目標を与えます。ここでは次ターンで敵が攻撃に来うるようなDefencePointでの基準をやんわりと書きます。

 

1.隣接している敵が、防衛用のユニットを残したと仮定して、攻めてくる数

2.隣接している敵が、周辺のユニットをかき集めて防衛用のユニットを残したと仮定して、攻めてくる数

3.隣接している敵が全員で突っ込んできた場合の数

4.次ターンまでに突っ込んできうる最大数（つまり、3.に加えてspawn→moveの流れできうる数、距離2にいる敵なんかも加算されます）

（4は満たされることはほぼほぼないと思います）

割り当て可能なユニットが複数いる際は等確率で選び出します。

 

（DefencePoint、NeutralPoint、AttackPointに割り当て続けていたらユニットが足りなくないか？みたいな部分はもし聞きたい方がいらっしゃれば教えてください。）

・割り当てを評価

　上の割り当て方ですが、どの衝突地点から割り当てるか、どのユニットを割り当てるかによって解は大きく異なります。したがって、評価関数を用意し、最高点を出せた割り当てを採用します。

各衝突地点のスコアは

（衝突地点の重要度を数値化したもの）×（衝突地点の基準充足状況を数値化したもの）

を基本として、全衝突地点のスコアを足し合わせたものが割り当てのスコアになります。

・recyclerのbuildは割り当てとは無関係に雑に行う

　recyclerの設置は上の割り当ての前に以下を鑑みて設置します。

・自身のエリア確保状況（戦闘が終わりかけていて不利だとrecyclerは自陣を減らすことになるので基本置きません）

・ユニット、保有matter(戦線で戦えるユニット数や保有matterで上回っていると、マター集めのrecyclerはよほどの効率がないとしません。)

・隣接マスにいる敵ユニット(隣接する敵が多い場合など、防御効果が感じられる場合は防衛することがあります)

recyclerの設置で失う土地については

(消える自陣のマス)-(消える敵陣のマス)+(消える中立のマス)+(到達不可能にしてしまうマスの数)

として、この値と設置した場合に得られるmatterを天秤にかけて最終的に設置するかを考えます。

（到達不可能にしてしまうmatterの数はどう計算したのみたいなことが聞きたい方がいらっしゃれば教えてください）

弱点

序盤はなかなかに長期のコンテストで万事を尽くせるなどと思っていましたが、最終提出の自身のbotには数々の粗があります。うち、特に問題のある点を残しておきます（未来の自分がもしこのコンテストを継続する場合のことも考えて書き記しておきます）

・recycler設置係とユニット割り当て係のディスコミュニケーション

　これは最大の問題点。前のrecyclerの方針では「隣接マスにいる敵ユニット(敵が多い場合など、防御効果が感じられる場合は防衛することがあります)」などと書いておきながら、recycler設置係はあまり賢くないので切迫した状況にもかかわらず適当なところにbuildして、前線にspawnさせるためのmatterが足りなくなることが結構あります。

・割り当て評価のスコアが雑

全力でspawnしていたら最重要ポイント（ここはとれなかったら負け確定みたいな点）を守れていたのに、分散して守らせてしまったことにより敗北するというのもしばしばありました。今回終盤に割り当て評価をガラッと変えてしまったので調整が不完全です。（ここは多少のじゃんけん要素の絡むところではありますが・・・）

 

途中で世代交代となったbotたち

Wood Killerくん

　これは相手の陣地に全力で迫っていくタイプのもの。WoodBossを倒すことを目標に育成しました。WoodBossはmatterを使い切らないうえにbuildもしないので、毎ターン1スポーンすれば数で押し切れると思い、ただただ敵陣に向かって突っ込むように実装しました。BronzeBossもbuildをしないタイプだったので結果的にBronzeKillerにもなりました。

Falconくん

　silverでは、WoodKillerくんはrecyclerでマター集めをした人たちに返り討ちにあったり、そもそもrecyclerで進路が阻まれたり。そこでsilverリーグで限界を迎える初代 WoodKillerくんに代わる2代目Falconくん登場。Falconくんには高い周囲観察力や攻防の機敏さを期待してこの名前を付けました。

　FalconくんにはWoodKillerくんの数々の弱点を克服してもらいました。「防衛地点にユニットを割り当てる」という基本方針をここで固めました。また、Recyclerを、消してしまう土地に対して得られるmatterが最大のところに置くようになりました。

　他にも戦闘終了後に自陣を塗ったりなど、最後まで必要になる根幹はここで生まれました。割り当て順を工夫するなどしてFalconくんは当時の50位付近まで成長しました。

（ここで成長できたのがこの後コンテストへのモチベーションを保てた気がします）

Radial Flowくん

　RadialFlowくんはFalconくんの突撃体質による防御面の弱さを治すことを目標に生まれました。距離計算の際にrecyclerによる緑化を考慮したり、複数体スポーンさせないと守れないような衝突地点をBuildで防いだり。DefencePointを一体で複数カバーできる場合もあるので、複数に割り当ててみたり。RadialFlowくんは当時のメモによると12月末Goldリーグの14位まで行けたらしい。

Towering Cliffsくん

たぶんこのときのやつ。3代目RadialFlowくんの負けた試合を見ていると

「いや、ここはこのユニットに任せておけば真ん中一足先にとれるぞ」

「いやいやここはスポーンで対応したほうが・・・」

みたいな盤面をちょくちょく見かけました。これは山登り法を実装するときなのでは（あわよくば人生初焼きなましを・・・）、と思い、ToweringCliffsくんの育成に取り掛かりました。

まず山登りを実装する（割り当てをやり直したりする）にあたって、持っている割り当て情報をもう少し扱いやすくしなければならなかったので、RadialFlowくんのコードはほぼほぼ解体しました。また、扱いやすさのためにこれまでに実装していた多くの機能を失うことになりました。

　ツイートではn日かかるといっていましたが、ゲームのアクションをかなり制限した形での実装に2日、RadialFlowくんの持っていた機能の8～9割の復元にさらに2~3日かかっており、実装力のなさに危機感を覚えております・・・。それも結果的に山登りではなく貪欲を時間いっぱいやり直すという方針になりました・・・。

　ToweringCliffsくんはさらに、Recyclerを置いた際に自陣に到達不可能なマスを作ってしまうという問題や、無限ループ時に自分の拠点を塗らない問題を解決し、リサブの上振れ次第でちょくちょく1位に上がることもありました。（あれは潜伏、リサブの下振れ等いる中の仮初の1位だと思っていますが・・・。）

　なお、最終提出のThe Bumpinessくんとの違いは、「顔文字を出力するか」と若干のパラメータ調整くらいしかないです。

　

おわりに

　ここまで読んでいただきありがとうございます。CodinGameのコンテストに前回参加したのはGreenCircleになりますが、その時に引き続き一桁順位をとれたのがとてもうれしかったです。（もともと3桁順位の住人なので・・・）

　大変長いコンテストでしたが、コンテストを開催してくださったCodinGame様、Arenaでお世話になった皆さん、楽しい時間をありがとうございました！

【日記】HTTF（AHC016）

AtCoder 日記

以下はHTTFコンテスト期間時に考えたことをそのままメモしたものです。公開にあたって改めて見直していますがメモ程度のものだったので誤字脱字多いかもしれないです、コンテスト前半は体験記、問題の考察中心で、中盤以降は改善点中心です。

 

参加登録

　HTTFが今年も行われるみたい。去年は都合が合わず参加できなかったけど今年は参加したい。本選は数年ぶりのオンサイトらしく、大変めでたい話だ。就活一本の人もいるだろうから24卒対象者ではないとしておくか・・・。一応24卒対象者以外でも最上位10人は行けるみたいだが、そこまでの実力がないことはわかっているので、マラソンの経験を積むために参加させてもらおう。

一日目(11/11)

　問題文を読みました。

　よくわかりませんでした。よくわからないのでVisualizerにあるinputを使ってサンプルコードで試そうとしましたが、なぜかうまくいきませんでした。いつもはこれで問題がつかめるのに・・・。問題をよく見るとかなりインタラクティブなようで、これはローカルにいろいろ用意しなければという気持ちになりましたが、それは明日以降の自分に託すことにしました。

 

今日の取り組み

　・使うグラフの頂点数は少ないほうが良い

　・正答率は高いほうが良い

の二点から、可能な限り極端なグラフを用意して判別するのがよさそう。上で述べたグラフの頂点数が少ないほど正答率下がってしまうのでちょうどよいところを探したいが、それは序盤にやるべきではなさそう。（前科あり）

　極端なグラフといっても、頂点の番号を入れ替えると似たようになるものは、Hの生成方法を考えると判別しにくそう。雑にMと同じだけ頂点を用意してみるか・・・。辺の数が0~N-1個で判別しようとするとエラーに弱いので、等間隔に辺の数を離して 0~N(N-1)/2個で判別したほうが確実かな・・・？

　ん？だとするとエラー率が十分小さいときはそんなに頂点いらないのでは・・・？まあ考え出すときりがないので明日以降にするか・・・

上はそれぞれのGからエラー後の辺の数の期待値をとり、それが最も近いものを選んだ場合

下は頂点数N＝Mで、Gのうちで辺の数が一番近いものを選んだ場合

　辺の少ないグラフは基本エラーで増えるし、辺の多いグラフは基本エラーで減ってしまうので、確かに上のほうが合っていそう。

　どうしても問題が気になるので考察を続行した。

頂点の数少なくしすぎて全然判別できなかった。最終提出が採用されるので間違えたものを提出すると順位表駆け下りていくの面白い。

これらは自己記録よりかなり下だが、順位表ではベストとおなじくらいだった。相対評価、かなり奥が深い・・・

この日はいろいろやってみたがあまりつかめなかった・・・（まだローカルでテストできないけどたぶん正答率結構低い気がする）

　まだサンプルコードを流用しているのである程度考察出来たらGo言語で書いていきたいなあ・・・

 

 

二日目(11/12)

　まだコンテストも序盤、そう焦ることはないはず。この日はあまり取り組みませんでした。

 

　今日の取り組み

　初日のコードをGo言語で実装し、正答率を確認してみる。Seed=2での結果がこちら。

やはり正答率が厳しいか。かといってM=100,ε=0.40でまともに当てる方法も思いつかない。上位陣はどうにか判別できるのだろうか。

　なお、M,εがかなり大きい場合はあきらめてN=4にしたほうが良いんじゃないかと思っていたけれど、そんなことはなかった（最悪ケースではよくなるみたいだが、たぶん最高点からの相対得点ではほぼ無だろう）。ビジュアライザを見る限りもう計算のバグはなさそうなのでシンプルに新しい方針が必要。

　いったんHTTFから離れていると、各グラフから、与えられたHが生成される確率を正規分布に近似した確率計算により求めるのがよいのではないかという結論に至った。どうやら良い方針のようで、この時43位になった。

 

三日目(11/13)

　今日はほとんどコードを書きませんでした。前日に思いついた正規分布に近似した確率計算に希望を見出したのでそれをもとに構想を練っています。

今日は

・ローカルでseed=0,...,99の100ケースを試す機能

・より筋のよさそうな確率計算

をして多少改善しました。

 

四日目(11/14)

　三日目に考えていたことと合わせて、一応今回のコンテストでの方針を固めました。今回は順位表が相対評価であることもあって、どの部分に伸びしろがあるのかよくわからないです・・・。

 

今日の取り組み

今回の方針をまとめてみる。

1. epsが大きくなるにつれて極端に頂点数が増えるようにNを設定（(1-2*eps)が分母に入るようなのが正解か・・・？）

2. Gとして極端なグラフを用意（一部の頂点から大量に辺が伸びているのがよさそう？）

3. 与えられたHをGに可能な限り寄せる

4. GとHの差を確認し、その差がありえるかどうか計算する（各頂点で、辺の数の差は頂点数が十分大きいなら平均(N-1)*eps,標準偏差*1^(1/2)に従う？）

 

と書いたところで、突然強くなった。

　これはM個の極端なグラフの取り方によるものであろう。Gとして下の二種類を考えてみると、パターン1とパターン2は意外にも各頂点から出ている辺の数という点では十分区別できるようだ。

上二つは一部の頂点からあらゆる頂点へと辺が伸びている一方、下二つは一部の頂点間でのみ辺が伸びているため、3でのグラフの寄せ方次第ではかなりの差が生まれる。

パターン1

パターン2

この二タイプが区別できないようなエラー率のものはもともとはもっと壊滅的なので、純粋に全ケースで改善したと思われる。

一方でGの多様化により従来の3.の寄せ方（辺の多い頂点順に並べる）ではあまり正しく近づけなくなったので、3.の寄せ方として「i番目とj番目を入れ替えてみて、グラフの差が小さくなれば採用する」を繰り返すというのを実装するのがよさそうだ。

 

五日目(11/15)

　昨日はかなり得点を伸ばせたのでこの調子で進みたいところですが、今日は少しおやすみ。少しコードがまとまっていないので、最低限整理していきます。

　脱線しまして、ちょっとしたお話。私のコンテスト中の取り組み方は

思いつきを雑に実装→良ければ採用→思いつきを雑に実装→良ければ採用→...→一旦雑な実装を整理→思いつきを雑に実装→...

という風になっています。こうやって見ると山登り法みたいですね。思いつきは採用されないことも多いので、思い付きを実装するときに形を整えてしまうと時間がかかってしまいます。また、一つの思い付きを採用したのちにすぐ整えてしまうと直後の思い付きで破壊されることもあるので、ある程度良いタイミングを見計らって整えています。ほかの方はどうなさっているんでしょうか。

今日の取り組み

　昨日の実装で、方針3.のグラフの寄せ方としてグラフの頂点のswapを考えることになったので最低限の高速化が必要か。とりあえず文字列として辺の情報を持っておくのはあらゆる点で効率が悪く、早急に作り直したほうがよいだろう。ということでbitBoardになった。

あまりに思いつくままに書いていたので構造体、関数定義をしながら、HをGにできるだけ寄せる作業ができているか確認。

　swapも実装できたが、ちょっとswapの性能に自信がないので正規分布による確率計算ではなくグラフの差を評価基準に提出してみた。合計点が下がったが、意外と正規近似の際と張り合っている。

 

六日目～(11/16~11/20)

　急に雑になりました。というのも、この日以降なかなか改善ができない中でMON.T+α本人が執筆をあきらめてしまったからです。というわけで、コンテスト後の私がこの後の改善についてお話します。時間がたってしまっていることもあり、かいつまんでの紹介になります。紹介する順番ですが、互いに関係するところのみ時系列順です。

　六日目以降の取り組み

・確率計算、もうちょっとしっかりさせてみる

以下のようなHを考える

今回注目してほしいのは二列目の部分。上のHの二列目の形は下二つのGならどちらから生成されただろうか？

　

確率的に高いのは圧倒的に右（後者）である。これの詳しい話はAtCoder公式解説放送でお話しされていたので割愛。一方、5日目までのの計算システムではepsが小さめの時「わずかに右のほうがあり得る」といった結果だった。

　よくよく考えれば、「本来あるはずの辺がなくなっている」「本来ないはずの辺がある」数のカウントは足し合わせないほうが良い気がする。この二つを区別すると、左のグラフでは「5本のうち2本の辺がエラーでなくなった」右のグラフでは「なかった9本のうち2本の辺がエラーで増えた」となり、しっかり確率に差がつきそうだ。多少改善した

・確率計算、もっとしっかりさせてみる

　今の確率計算、そもそも問題点として、「エラーの起こる数の確率分布（二項分布）が正規分布に近似できるのか」という問題がある。

うーん・・・。epsが小さくて頂点数が小さいときは正規分布に近似できるかというとちょっと違うか・・・。と思うと同時に、「えっ頂点数少ないときは別に二項分布からそのまま計算したらいいのでは」ということに気づき実装した。

 

・eps=0のとき、あらかじめグラフ用意しておく

頂点数6のグラフは頂点の番号を区別しなくても100通りあるのであらかじめ100種類のグラフを用意した。

頂点数4,5のものも用意しておき、Mが小さいときは頂点数4,5のものを使用した。

 

・eps=0.01,0.02...のときもあらかじめグラフ用意しておく

epsがかなり小さいときはほとんどエラーが起こらないはずなので、互いのグラフの差が一定以上あるようなグラフ100個を用意すればよいということに気づいた。

大体eps=0.04くらいまでのものはN=15くらいまでで抑えられるようになった。

0.05あたりからは頂点数も増え、グラフを可能な限り近づける機能の能力限界により厳しかった

 

・与えられたHのグラフをGに寄せる方法、むちゃくちゃ無駄が多かった

これ、もう少し早く気づいていれば・・・。

swapを繰り返して求める方法、結局のところ行きつくのは局所解だったのだが、swapにおける局所解なら実はかなり簡単な貪欲法で見つけられたのである。そのうえ、こちらが決めたM個のグラフは形が単純なうえ大きく分けると二パターンしかなく、二パターン目は01を反転させたものになっているため、

貪欲法でHの頂点番号を決める→M/2個のグラフについてswapにおける局所解

Hの01を反転させた場合の貪欲法でHの頂点番号を決める→残りM/2個のグラフについてswapにおける局所解

となっていた。これにより超高速化を達成し、最終提出では1クエリ当たりこの貪欲法を無駄に数千回繰り返すものになっている。（一応初期解に多少依存するので、完全に無駄というわけではない）

おそらく大体こんなところです。

最終日のプログラムではSeed=2の場合はN=100で全問正解できるようになりました。二日目の自分にこの結果を見せたら喜ぶだろうなあ・・・

 

 

*1:N-1)*eps*(1-eps

【Postmortem】HTTF2023予選(AHC016)

Postmortem AtCoder

※画像は公式Visualizerよりお借りしています

この記事は11/11~11/20にAtCoderで開催されました、FUTURE様主催のHACK TO THE FUTURE 2023予選（AHC016）のPostmortemになります。

はじめに

　11/11~11/20の9日間開催されていた、HACK TO THE FUTURE 2023予選（AHC016）に参加しました。

　結果ですが、システス前54位、システス後は順位を一つ上げ53位でした。

　以下、最終提出について書いていきます。

この記事で用いる表現について

勝手に使っているあいまいな表現があるので書いておきます

・グラフの差

かなり直感的に考えていたのですが、あえてしっかりと定めるなら二つのグラフをそれぞれ01の行列の形で表し、そのxorをとったものです。xorをとったものの1の数を用いて差が大きいとか差が小さいとか言っています。他の方が的を得た表現をなさっていたので参考にしますと、おそらく辺についての編集距離というものです。

最終提出の概要

　言語はいつも通りGo言語です。

基本的にeps<=0.04かそれ以外の2パターンに分けて考えました。

eps<=0.04の場合

1.事前にグラフを用意しておく

2.与えられたHを頂点swapでM個の各グラフと差ができるだけ小さくなるようにする

3.差が小さかったグラフを答えとする

ちなみにグラフを大量に埋め込んでます。

magic4         形の違う11個のグラフ eps=0.00で使用

magic5         形の違う34個のグラフ eps=0.00で使用

magic6         形の違う100個のグラフ eps=0.00で使用

magic6_2     互いのグラフの差が3以上の13個のグラフ eps<=0.02で使用

magic7     　互いのグラフの差が3以上の37個のグラフ eps<=0.01で使用

magic8        互いのグラフの差が4以上の65個のグラフ 今確認すると不採用

magic9        互いのグラフの差が5以上の50個のグラフ eps<=0.02で使用

magic10      互いのグラフの差が7以上の25個のグラフ eps<=0.04で使用

magic10_2  互いのグラフの差が6以上の100個のグラフ eps<=0.02で使用

magic12      互いのグラフの差が9以上の100個のグラフ eps<=0.03で使用

magic15      互いのグラフの差が15以上の100個のグラフ eps<=0.04で使用

基本的に2k+1の辺の差があればk個までのエラーに確実に耐えられるので、そのあたりを考えつつ生成しました。

　これらのグラフの数はもっとうまくとればよりたくさん用意できると思いますが、そこまでは詰めませんでした。あんまりその頂点数のでの限界数もらっても、実際に5秒で走らせるほうのプログラムの差計算ががそこまで優秀でなかったのでちょっと間違って別の形のほうが近いといわれちゃうのは・・・。

公式解説放送やほかの方の解法を漁ってみたところ、差ではなくより確率的な計算をすれば、あるいはN=9ぐらいのところでグラフを100個用意できていたら、eps<=0.04で使う分にはN=15とかまで考える必要はなさそうです。

　与えられたHを上で用意したグラフそれぞれに寄せる際には頂点のswapによる局所解を500回くらい求めています。初期解を変えつつ500回こなせば頂点15でもそんなに間違えることはありません。

eps>0.04の場合

1.適当なdを求めて,k<M/2について

(A)1をd*k個並べたのちに残り0を並べる

(B)0をd*k個並べたのちに残り1を並べる

を考え、M個のグラフとして設定する

2.与えられたHに貪欲に頂点番号をつけていく

3.グラフの差について二項分布（頂点数が多い場合は正規分布とみなす）として確率を求める

 

2.の貪欲に頂点番号をつけるというのはepsが小さいときに行っていた「各グラフの形に近づける」という部分に対応しますが、以下のようにつけることで各Gごとに考える必要がなくなります。

2-0,Hの各頂点に頂点番号をつけておきます

2-1.最も辺の数が多い頂点を選びます（この頂点番号をiとする）

2-2.頂点番号iと1を入れ替えます

2-3.頂点番号が2以上の頂点のうち、頂点番号2以上への辺が最も多い頂点を選びます（この頂点番号をiとする）

2-4.頂点番号iと2を入れ替えます

2-5.以下同様にこれを頂点の数くらい繰り返します

 

最初に辺の数を計算してそこから入れ替えのたびに辺の数を更新していけば、この作業は非常に簡単に終わります。そしてこれは(A)タイプのグラフとの差を考える場合に、swap操作における局所解になります。（A）の01を反転させた（B）については割愛します。

注：一般にグラフ同士の差を考える場合はこのようにはいきません。あくまでM個のグラフを(A)(B)のようにとったからこそ使える方法です。

 

　実行時間に余裕があるので、初期値を変えつつ上の手法をやり直します。数百～数千回くらいやり直せましたが、多少精度が上がる程度です。

解法の大別

　様々な解法を拝見したのですが、おおよそ以下のように分類ができると思いました。

自分の最終提出は

・各グラフの合計の辺の数が全然違えばよいのでは？

・各グラフにそれらしい頂点番号をつけてみる

・「あるはずの辺がない」「ないはずの辺がある」これもある確率分布に従う？

を念頭に作られています。

（頂点番号をつけていますが、頂点番号の完全一致を目指すものではなく辺の多いグループと辺の少ないグループを当てることが目標なので、そういう意味ではグループ分けのほうが正しいかも？）

　エラー率が少ない場合(eps<=0.04)では

・グラフが形として全然違えばよいのでは？

・与えられたHにそれらしい頂点番号をつけてみる？

・「あるはずの辺がない」「ないはずの辺がある」をカウントしてみる？

を採用しています。

　エラーがひどい場合は諦めたらよいのでは？（つまりN=4にする）

というのは、最後まで採用するか悩みましたが、最悪ケースでもなんとかあきらめた場合と張り合えるようになったので採用しませんでした。

後悔している点

もっとグラフとしてとらえていれば・・・

　上の解法の紹介の段階でお気づきかもしれませんが、私MON.T+αは今回の問題を対称行列的にしか見ておらず、swapの実装もしっかり行列の行入れ替え・列入れ替えを念頭に実装してしまっています。頂点同士が辺でつながっているという感覚が全くありませんでした。結果、M個のグラフの選び方はPythonのサンプルコードの延長線でしかなく、クリーク（部分完全グラフ？）とやらのアイデアが浮かぶこともありませんでした。そういった解法を拝見した後で自分の解法を見ると、ある意味大きなクリークを埋め込んでいるとも言えるんですが・・・。次回はより広い視点で問題を見つめることで幅広い着想を得たいですね。

もっとM個のグラフについていろいろな場合を試していれば・・・

　これは問題の特徴をもう少し考えておくべきだったと反省しています。

　今回の問題、プログラムが考えるのは、

・M個のグラフを何にするか

・与えられたHがM個のどれから得られたものか

の二点ですが、「M個のグラフをどんな形にするか」を決めた時点で、ある程度取れる得点の限界が決まってしまいます。私は「生成が簡単かつ元のグラフの形を推し量りやすい」という理由で


上のようなグラフを採用してしまいましたが、これはバリエーション豊かなグラフの一部分しか使えていません。順位表といろいろな方の解法を照らし合わせてみると、たとえ各グラフからの生成確率を最も正確に判定しても、暫定テストのスコア限界は20~25Gなのではないかという気がしています（自分の前後あたりまで似た解法の方が多かった気がします）。特にエラーが少ない場合での頂点数が多くなりがちです。

　最終的に「与えられたHがM個のどれから得られたものか」の段階は十分妥当な結果を返しており、実行時間もかなりの余裕があったので、最上位陣のような「元の形を推し量るのに技術を要するが、推し量ることができたらかなり高得点」なグラフに挑戦してみてもよかったかもしれません。



頂点数N、ローカルで最善のものを探していれば・・・

　これはいうほどスコアにおいて致命傷になってるわけではないんですが、シンプルにローカルで試せることはいろいろ試しておくべきだったなと思っています。ローカルで回す分には特に何かを失うわけではないですし。

統計データ

ローカルでのSeed=0,...,99の得点

ローカルでデータを取っていたものの中での最高点を示しています。詳しくはわかりませんが、正答率100%をとれていないケースが20~25ケースほどあります。

Seed M eps Score
0 10 0 250000000
1 76 0.01 100000000
2 87 0.25 10309278
3 48 0.34 8100000
4 31 0.05 62500000
5 32 0.06 58823529
6 80 0.04 66666666
7 51 0.15 23809523
8 93 0.31 6561000
9 47 0.26 14285714
10 72 0.38 119725
11 41 0.36 6561000
12 39 0.28 13698630
13 69 0.04 66666666
14 35 0.16 27777777
15 26 0.15 37037037
16 32 0.4 646108
17 97 0.38 46383
18 83 0.16 17543859
19 75 0.14 20408163
20 58 0.13 25000000
21 57 0.27 11111111
22 70 0.03 66666666
23 63 0.32 7290000
24 17 0.27 26315789
25 67 0.32 7290000
26 91 0.34 1350851
27 75 0.13 21739130
28 45 0.06 40500000
29 88 0.11 21276595
30 64 0 166666666
31 11 0.24 40000000
32 49 0.24 14285714
33 50 0.19 18867924
34 72 0.15 20000000
35 29 0.03 83333333
36 54 0.05 43478260
37 33 0.05 56250000
38 34 0.33 10000000
39 66 0.04 66666666
40 17 0.28 20833333
41 36 0.16 27027027
42 89 0.01 100000000
43 15 0.08 71428571
44 33 0.18 25000000
45 83 0.36 423911
46 96 0.02 100000000
47 92 0.3 7290000
48 30 0.39 2058911
49 27 0.1 45000000
50 30 0.18 27027027
51 48 0.26 13157894
52 82 0.1 25000000
53 18 0.35 12500000
54 58 0.09 34615384
55 14 0.26 32142857
56 49 0 166666666
57 77 0.03 66666666
58 42 0.36 4782969
59 71 0.36 717897
60 92 0.21 12857142
61 14 0.25 37037037
62 98 0.03 66666666
63 11 0.39 10000000
64 20 0.37 10000000
65 13 0.06 90000000
66 77 0.08 27777777
67 83 0.09 25641025
68 17 0.16 47619047
69 84 0.18 15625000
70 99 0.31 4304672
71 100 0.02 100000000
72 54 0.1 30303030
73 97 0.38 46383
74 87 0.38 107752
75 29 0.16 36000000
76 13 0.39 9000000
77 93 0.33 2541865
78 75 0.19 16666666
79 70 0.19 16666666
80 61 0.04 66666666
81 77 0.23 12658227
82 62 0.3 10000000
83 97 0.3 5314410
84 60 0.05 38461538
85 33 0.31 11363636
86 76 0.11 23809523
87 93 0.28 9000000
88 56 0.04 66666666
89 56 0.23 15000000
90 41 0.19 20833333
91 22 0.03 100000000
92 51 0.3 10000000
93 50 0.05 45000000
94 56 0.19 18518518
95 66 0.35 2287679
96 81 0.4 11790
97 26 0.35 10000000
98 32 0.3 11904761
99 88 0.12 20408163

M,epsとNの値

最終提出は各M,epsに対して以下をNとして返すみたいです。

　比較的0.04<eps<0.3付近のNがかなり多く、その部分が弱点っぽいです。これは比較的エラーが起こらないにもかかわらず、M個のグラフとして最終提出の概要で紹介した(A)(B)しか用いていないからだと思われます。

　また、eps>0.04では二つの計算式のmaxをとっているために黄色のラインが途中で曲がっているのが読み取れます。

おわりに

　コンテスト期間外にいろいろ試したことや少しコンテスト経験を積んできたことが功を奏してか、前回参加したAHC014に続き、なかなか好順位につくことができたと感じています。今後も定期的に参加してステップアップしていきたいです。（願わくばまた長期コンテストを・・・）

　今回の問題も難しい問題で、約一週間の間いろいろな試行錯誤を繰り返して楽しめました。コンテスト運営に携わっていた方々、大変楽しい時間をありがとうございました。

【Postmortem】AtCoder AHC014

Postmortem AtCoder

画像は公式Visualizerからお借りしています(Seed=0)

はじめに

本日は、AtCoderにて9/17~10/1に行われましたAHC014の参加記録を記していきます。今回は最初に軽く最終提出を紹介します。また、最終提出に至るまでいろいろな提出を行ったのでそれらを日記風に時系列順にまとめて紹介をする流れになります。解説、検討というよりはどちらかというと日記です。

　なお、過去の自分の提出を見て振り返りながら書いているので、心情描写についてコードを書いた当時の心情と一致していない可能性もあります。

 

最終提出のプログラム

・Go言語

・評価値による貪欲

・評価値に多少の乱数を入れて時間いっぱい貪欲をやり直す

システムテスト前　50ケース最高記録　53.0M(58位)

システムテスト後　50ケースあたり　　52.4M(60位)

でした

 

コンテスト日記

9/17~9/20 コンテスト参加検討期

　今回は開催期間が2週間もあり、休日も多いので時間が取れるのではないか、と思い参加登録。このときはやる気十分だった。

　しかし、問題文を見るや否や、やっぱりやめておくか、となった。恥ずかしい話、最近はAtCoderのコンテストに出ていなかったので問題文のN,M,p,iや得点の計算式を受け入れることができなかったのである。

　以降、しばらく自分のいない順位表を眺めるだけであった。

　最初の週末を何も提出することなく過ごした自分に、天啓が降りる。それは、自明解である(気づくの遅くないか？)。入力を無視して０を出力すると、なんとACだというのだ。これを何の気なしに出してみると14M改善した(0M→14M)。斯くして正の得点を得た私は、抜け出せないコンテストの沼に足を突っ込んでしまったのである。

9/21~9/22基本方針確定期

　自明解の発見は14Mもの改善をもたらしたが、順位はあまり芳しくなかった。自分のプログラムで特に違和感を感じたのは、まだ格子上に点が置けるのに置かない点である。この問題を解消するため、各座標に対し、その場所に新たに点を置けるかどうかを返す関数を実装することにした。(正確にはその点を起点として作ることのできる四角形を列挙する関数)

　これが、書くのが遅い私にとっては難所となった。なおこれを書き終えたところであまり実用的な実行速度ではなかったのだが、このときの私はまだ何も知らなかった。

 

(少し実装の紹介)

判定の仕組みは非常に簡単である。スタートの座標から1マスずつ一直線に移動しながら、そこに点があるか、すでに間に線が引かれたかを確認する。線があればその段階で四角形は作れないことがわかるので中断する。すでに点がある座標に到着したら、時計回りに90度回転し、1マスずつ進んでゆく。これを繰り返し、スタートの座標に無事もどることができるか見れば良い。図付きの説明は最後の「よくありそうな質問」で。

 

この関数を実装し、置くことが可能な点を左下から探して見つけ次第おいていくことができるようになったのはn時間の実装作業の後だった。単純だが、スコアは自明解の比ではない。これを提出することにより・・・と思ったら提出していなかった。あまりに遅かったようで、ビット演算での処理が今後行えるよう点と線の情報をbitboardにしてから提出していた。(盤の情報をbitboardにするのはマラソンの問題で大いに役立つテクニックなので、もし知らなかった方がいれば一度調べてみてほしい)これにより16.5Mの改善(14.0M→30.5M)に成功する。

　このとき、上で述べていた判定の関数が遅かったので二手先などは考えず「この座標に点を置くこと亅に対して得点をつけることにした。すなわち貪欲である。この方針は最後まで貫くことになる。

　で、さっそくの手詰まりである。手動でテストケースをプレイしていても何もわからない。中心から遠いところに点がある方がいいのでは？と思い始めたころに上位の人が共有しているVisualizerを確認してみると、なんとめちゃくちゃ点が埋まっているではないか。

 

　したがって、「小さい長方形から優先して作る」というのが続いての目標となった。これは得点として長方形の外周の長さ×-1を採用することで完成した。申し訳程度に同じ大きさの長方形なら中心から遠いのほうを採用した。(30.5M→32.0M)

 

　ここで、一番小さい斜めの長方形の外周が8と計算されていたのでそれも斜めでない場合と同じ4となるように計算方法を変えて再提出した(32.0M→33.9M)

また実行時間2sと勘違いしていたので5sに変更(33.9M→34.0M)

（ランダム要素がないのに微増したということは一部のケースで2sでは間に合わず切り上げていたということに・・・）

 

さすがに実行速度が遅すぎてこれはやっていられない、と思い就寝。天井を見ながら「コンテストが終わるまでに40Mに到達する」を目標に掲げる。翌日は最低限の高速化に努めた。一番重かったテストケースがおおよそ3倍速に。(2300ms→800ms)

(点と辺のbitboardを上方向、右上方向、右方向、右下方向でもつことで長方形の大きさにかかわらず同じ時間で長方形が作れるか判定できるようになりました。このあたりの話は最後の「よくありそうな質問」で。)

時間に余裕ができたのでがちゃがちゃ評価関数をいじってみたけどほとんど変わらなかった。多分あまり本質的な部分ではなかった。(34.0M→34.2M)

 

時間に余裕ができたので、評価関数に若干の乱数を入れて時間いっぱいやり直すことにするとこれはかなり改善した(34.2M→37.2M)。とはいえ、一番重いケースだと6回くらいしか試せていないので乱数次第でかなり得点がぶれるようだ。乱数の取りうる範囲を狭めてみると多少得点は変わったが(37.2M→37.4M)、よくなったのかどうかわからなかった。

 

で、またしても手詰まりである。上位の人が共有しているVisualizerを確認してみる。よく見ると、小さい長方形が市松模様のように並んでいるではないか。こうして、「市松模様の形になるようにおける場合は特に優先するのがよいのではないか」という天啓を得る。雑な実装、より適切な実装、市松模様判定の高速化の段階を経て得点が伸びる。(37.4M→38.3M→40.3M→40.8M)

（実は作ろうとしている長方形で各頂点で辺をもう1マス伸ばしたところにすでに線が引かれているかでわかるのである。

一本でもひかれていれば、市松模様が繋がる。）

 

斯くして布団から天井を見て掲げた40Mの目標を早くも達成するのであった。

 

9/23~9/27 現実逃避期

 

　思いつくことを実装しきって40Mに到達したことで、非常に高い満足感を得るとともに、今の自分ではもうこれ以上は伸ばせないだろうという思いが湧き上がる。最終結果を知る今から見ればこの方針のまま少なくともあと13Mも改善できる余地があるのだが、一度こういう気持ちになってしまうと本当に何も思いつかないのでどうしようもないのである。

　うーん、AHCやめるかぁ・・・。

　この期間中何もしなかったわけではない。ローカルで50ケース程度の得点をとってみた。するとMが小さい（すなわち初期状態に置かれている点が少ない）場合は小さい長方形を優先的に選んだことでむしろ得点が悪化していることに気づく。おそらく小さい長方形を連鎖的にうまく作ることができないのだろう。よってMが小さいケースについては長方形の大きさによる評価値の影響を小さくし、苦し紛れの改善に成功する(40.8M→41.2M)。成功したのか？乱数の運程度の誤差ではないのか？とも思われるが、とりあえず成功したことにしないとこの期間の進捗はなくなってしまうのでこれは成功したことにする。

 

9/28　運命の日

 

　コンテストも終わりが近づいている。なんか順位もむちゃくちゃ下がっている。「ああ、やはり対戦botを作るタイプのコンテストのほうが得意なのかなあ。こういった得点最大化タイプのコンテストだと、自分のプログラムの粗削り感があらわれてしまうんだよなあ。」と思いながら試行錯誤していたところの出来事である。22日から変わらず市松模様の理想をベースに評価を加えていたところ、3M近く改善したのだ(41.2M→44.0M)。やはり市松模様が正解だと思うとともに久しぶりの大幅改善でやる気がよみがえってくる。

　また、ローカルテストで、Nが小さいときは選択肢が少ないため何度やり直してもほとんど決まった結果が出ていた。そのため、Nが小さいときは乱数の影響を多くしていろいろなパターンが出るのを期待した。(44.0M→44.8M)

 

　なぜ、40Mで止まっていた最高点を大幅に塗り替えられたのか。おそらくこれを読んでいる人（そもそもいるのだろうか）のほとんどはこの改善が気になることだろう。実際、この改善は自分のモチベーションとしても40Mから50Mへの要素としても重要な部分であり、おそらくほかにこれを実装している人はいないだろう。が、残念ながら語ることができない。なぜならば、「バグ」だったからである。私はこの時追加したものがバグでどのような評価を与えているかわかっていないからである。この時の私はバグには気づいていなかったので自分の発想が正しかったのだと思い込んでいる。一応、バグによる評価値の加減は最後の「よくありそうな質問」で述べている。

9/29~9/30 高速化期

 

　いよいよもう方針転換はできないころである。高速化して試せる回数を増やすほかないかと思う頃にまたしても自分に天啓が降りる。それは、有効な手を調べる際のループ回数の減少による高速化である。

アイデアは以下のとおりである。

・初期盤面ではN*N個の各座標から8方向に長方形を作ることができるか調べ、評価

・調べた結果を保存する

・最良の点を決定した後、次にその点を使って長方形を作ることができるかもしれない座標を、暫定的に作ることができる場所として調べた結果に追加する

・調べた結果を参照して、長方形を作ることができる場所が本当に長方形を作ることができるか調べ、評価

・調べた結果を保存する

・最良の点を決定した後、次にその点を使って長方形を作ることができるかもしれない座標を、暫定的に作ることができる場所として調べた結果に追加する

以下繰り返し

（この調べた結果もbitを使って保存するとかなり速かった）

 

これにより実行速度が大幅に改善した（5倍速くらい？）。これを提出することで数日の停滞を巻き返してゆく。(44.8M→46.2M→47.2M→49.4M)

 

これをきっかけとして、ほかの場所もいろいろと無駄があるのではないかという気がして、次々と高速化してゆく。この間、問題となっていたバグ部分を高速化しようとした結果さらに違うバグになっているのだが、なぜか気づかなかった。

 

これに評価値の調整を行い51.0Mまで到達する。

 

　また、高速化とセットで、ちょっと乱数の倍率を変更してみる。高速化のおかげで回数が稼げるので、前半は乱数要素少なめに貪欲を行ってもらい、貪欲のやり直し回数を重ねるごとに乱数を大きくすることで評価関数の型にはまりすぎて出にくかった結果にも多少到達できるようになった。仮に後半部分で良い結果が出なくても、前半部分で十分高得点が期待できるので良い方法に感じた。

　また、ついにバグに気づく。バグを取り除いてみる。ローカルで3M下がる。バグを戻してみる。ローカルで3M上がる。よって、バグを許容する。さらに、バグを改変してスコアの安定化に成功する。

乱数の運に左右されるので多少上下しつつ、最高53.0Mに到達する。

 

10/1 お祈り期

 

　もはや簡単に高速化できる場所はなくなった。実装の遅さに定評のある私は、一日にかけるコード量など微々たるものである（ちなみに短期コンテストにめったに出ない理由もそれである。逃げていても上達しないとわかってはいるが・・・）。雑なものを書いてそれが最終提出になってしまっては大事故である。したがって最終日は順位表の礼拝に努め、システムテストの得点の向上を祈った。

 

 

まとめ

　AHCに参加したのは久しぶり（おそらくAHC003以来？）になりますが、まさか黄色パフォーマンスに到達でき、レートも今回で水色になれるとは思っていませんでした。地道に実装力が上がっているということなんでしょうか・・・？長らく間が空いてしまいましたが、次回以降のAHCも時間を作って取り組んでみたいと思いました。

　（短期コンテストは苦手意識があるのでぜひ長期コンテストを・・・）

 

よくありそうな質問

 

・結局盤面ってどのように記録したの？

点、辺をそれぞれ上方向、右上方向、右方向、右下方向の四種類に分けて盤面を記録しました。以下の3*3の盤面での点の取り方を紹介します。辺は点の例の時に出てくる矢印に沿って同じように記録します

 

上方向は左の矢印から順に100,001,111（2進数）となります。

右上方向は上から順に001,000,100,110,100（2進数）となります。

右方向は上から順に101,100,110（2進数）となります。

右下方向は100,100,101,010,000（2進数）となります。

この形で持っておくことでの恩恵については詳細は省きますが、長方形が作れるかってどう判定したの？で若干触れます

 

・長方形が作れるかってどう判定したの？

上でも使用した3*3の盤面を使用して紹介します。

上のようにまず新しく起きたい場所からある方向に進みます。すでに点がある座標に到着したら、時計回りに90度回転し、また1マスずつ進んでいきます。これを繰り返し、スタートの座標に無事もどることができるか見れば良いです。上の例では戻ってきたので作ることができます。また、上の例の座標スタートでは、ほかの角度から始めるともどってこれません。

別の場所を起点にして何個か失敗パターンを載せておきます。

この次にぶつかる点までの距離は、一つ上の項目「結局盤面ってどのように記録したの？」で紹介したbitboardでは、1になっている位二つの間の距離を見ればよいです。このときbit演算を用いることであまり長さに影響なく高速に求めることができます。間に線がすでにあるかどうかについても同様に高速に求めることができます

 

・一応バグの部分教えて

一応、どんな値が加算されているかはコードを読んでわかっているので部分的に紹介しておきます。

「赤の四角を作る」という行動に対する評価値を考えるとき、緑の4辺にまだ一本も線が引かれていない場合、黄色の4頂点でまだおかれていない点の数だけ減点する。というものです。これを赤緑黄色の位置を90度ずつ回し計四回考えます。座標がずれた結果上のようなおかしなことになったのですが、上の赤の長方形と黄色のエリアの関連性が結果としてきれいな市松模様を構築することにつながったのだと思います。

 

 

・なんで焼かないの？

貪欲を時間いっぱいやり直すという方針をとったのは、当初、置くことができる座標を調べるのが非常に遅く、1回解を出すのに500msはかかるだろうと踏んでいたからです。本当は高速になり始めたころに焼きなましを考えるべきだったと思いますが、焼きなましのための一部破壊ができるようなデータ構造になっていなかったので、実装が間に合わないと判断しました。（嘘である。実行速度が遅かったのも理由だが、実はmontplusaは焼きなましの方法を知らないのでコンテストで焼きなませたことがないのである。そろそろ学ぶべきか・・・）

 

 

・天啓、多すぎでは？

天啓を得られるか、天啓が降りてくるかは運にもよるので今回は運がよかったと思いますが、より天啓を得やすくするためにできることもあります。（なんかスピリチュアルに聞こえますが違います）

・手動で試してみる（今回は手動で試してもあまり良い発想が得られませんでした）

・twitterで共有されていたVisualizerを見る

・トイレ、風呂、食卓、公共交通機関、外出先などあらゆる場所で問題を思い出してみる

このほか他コンテストの経験が活きる、他コンテストの解説記事が活きるなど、様々なきっかけで天啓を得ることができるので、天啓が得られそうなことをしてみるといいかもしれません。

（そもそも、私の「天啓を得る」の水準が低く、実は小発見程度である可能性もあります）