AHC011参戦記

久しぶりのブログ更新です。

ABCにはほぼ毎回参加している状況ですが、C問題までの復習のアウトプットはしばらくお休みしていました。
再開予定は未定です。

今回はAHC011の参加記録です。
結果は483位performance1205と長期コンテストの中では伸びなかったコンテストでした。
今回の問題は終始、「何もわからん」状態で参加していました。

アイキャッチ右下に移っているスライドパズルは、コンテスト2日目に息子がもらってきたパズルです。
すごいタイミングでもらってきて一人笑ってました。
「お父さんも今、スライドパズルやってるんだよ。難しいよね。」という話をしていました。

問題

問題概要：木の模様のスライドパズルを完成させる。

詳しくはこちらを確認してください。

基本方針

ランダムにスライドさせて適宜(N回ごとに)スコアを計算して、その時のスコアと盤面を保持しておく、時間いっぱいまで試行して、最大のスコアの行動を提出する。

工夫した部分

完全ランダムでは点数が伸びなかったため、以下のような工夫を実装しました。

(初期)盤面の評価と予備動作

タイルの使い道がない場合はマイナスの評価をして移動させる。(例えば、1のタイルが左にある場合、マイナス評価として、右に移動させる。1のタイルが右にある場合はプラスの評価とする。)
fのタイルは中央に寄せる。(fのタイルが端にある場合はマイナス評価として、中央に移動させる。)

各タイルの評価値の総和を盤面の評価値とする。

ランダムに移動させる前の予備動作として、マイナス評価のタイルを目的地まで運んだらスコア計算と盤面評価を実施しスコアと盤面を記録する。
盤面の評価値が基準値を超えたら、予備動作をストップさせる。

この操作後の盤面のスコアをソートして、一番高いスコアの盤面をランダムにスライドさせていくことにしました。
但し、この状態からスタートして、スコアが良くならなかった場合は、2番目にスコアが高かった盤面を利用して、スライドさせていくことにしました。

スライドさせる範囲の限定

移動させる位置が端ばっかりでも盤面があまり変化しないため、はじめは中央だけを移動するように、中盤から後半にかけて、端まで移動しても良いことにする。

直前の動作の逆の動作を禁止

右に移動した直後に左に移動しても意味がないので、そのような行動をすることを禁止しました。
(下に移動した直後の上移動も同様。)

木を壊さないような動きの導入

完全にランダムに動いていると、木を壊してしまう動きをすることがあります。

木を壊してしまう動きには2つの側面があって、
一つは、一度木を壊してしまうが、その後により大きい木になるために必要な場合
もう一つは、二度と大きい木が出来上がることはない場合

木を育てるほうが良い場合と、今の木の状態にこだわらない場合を区別するために、次の目標スコアを導入することにしました。

目標スコアの導入

ここまでの実装でのスコアは大体以下になることがわかりました。

完全にランダムに動いていると、木を壊してしまう場合があります。
移動できる回数の終わりが見えているのに、木を壊してしまうのはもったいない一方、まだ序盤の内は局所解にはまるより、一度木が壊れることも許容するほうが全体的なスコアは伸びそうな感じでした。

ここで以下のようなルールで、「木を壊さない」 or 「木を壊すことを許容する」　を制御するようにしました。

現在のスコアが目標スコア以上の場合、「木を壊さない」。

現在のスコアが目標スコア未満の場合、「木を壊すことを許容する」。

目標スコアは保持しつつ、木を育てていけるようになりました。
また、目標スコア以上をとった場合は、目標スコア自体を底上げしていくようにしました。

焼きなまし法(っぽい何か)の導入

木を壊すことを許容するアイデアは焼きなまし法から得ています。
焼きなまし法は、上位陣が良く使う手法ですね。私は、概念だけ理解したつもりになっているやつです。
通常は、近傍の解から得られるスコアから、遷移するかしないかを確率的に選択する。というものかと思います。
得られた近傍解から、スコアを計算するときのスコア計算に時間がかかると試行回数が減ってしまい十分な結果を得ることが出来ません。
私は今回の問題で、スコア計算を高速にすることが出来ませんでした。
現在の状態から、木を壊さないようにするチェックするのは、範囲外に移動していないかのチェックと同じ要領で組み込めるため、
現在スコア >= 目標スコアの場合、木を壊さない近傍を得られる関数を使用
現在スコア ＜ 目標スコアの場合、木を壊すことを許容する関数を使用
という実装になりました。

木を壊すことを許容する確率は、条件を満たす場合は、常に1になるような関数で、シグモイド関数というのがあることを覚えていたので、調べ、急遽それっぽい実装してみたところ、スコアが飛躍的に上がりました。

翌日、そのシグモイド関数っぽいものを見返してみると、わけのわからない関数だったため、訂正しました。
訂正するとスコアが明らかに下がったため、不本意ではありますが、謎関数のまま本番提出しました。。。

保持しておくデータの型について

この問題を解くにあたって、利用した主なデータと、それらのデータをどのような形で保持しておいたかについても、記録に残しておきます。

盤面

盤面に関しては、二次元配列で持つと、次のような不都合な点があることがわかりました。
・どこからでもアクセス出来てしまう。
・状態を別のものとしてコピーするのに時間がかかる。
・二次元配列は、一次元配列より計算時間がかかる。
これらを解決するのに、基本的には、一次元配列を文字列に変換したものを保持するようにしました。
必要に応じて、その関数の中で一次元配列にするが、処理結果は文字列として返すようにしました。

最大の木を構成している部分を示す盤面

木を壊さないように動かす関数で使用するため、最後の方で追加されたデータ。

スコア計算した際に、スコアに寄与しているマスを”#”、そうではないマスを”.”で表した配列を文字列に変換したもの。

行動記録

答えはLURDから構成される文字列なので、文字列または、文字を構成要素に持つ配列で持ちたくなりましたが、直前の行動と逆の行動は、無効としたいので、数字(の文字列/配列)で持ちました。
具体的には、Lが0、Uが1、Rが2、Dが3、として持つようにしました。
こうすることで直前の行動と反対の行動か否かは、(直前の行動+2)%4 == 今回の行動 で判定できるようになりました。

答えを出力する用の辞書

スコアをkeyにした辞書で、valueは、配列で、[行動記録, 盤面, 予備動作の最高点を利用中かの真偽値]

今回、私は、入力された盤面から予備動作をした後に、ランダムで動かすようにしました。
このため、予備動作に関する辞書も次のような形で用意しています。
keyは処理順番、valueに[その盤面のスコア, 盤面, その時点の行動]

ローカルテストについて

今回、手元で1000ケース回してエラーが出なかったもの、前回のコードよりも得点が上がっているものを提出するようにしました。

Python3でマルチプロセスで実行することが良いことは、TLで教えてもらっていたので、調べてみましたがすぐにはわかりませんでした。

こちらの動画を見て、何となくわかったので、自分でマルチプロセスの実行コードを書いてみました。

うまく動いていそうなことが分かったので、結果をパース出来るようなコードも書いて、csvに出力できるようにしました。

マルチプロセスで実行する部分は以下のようなコードで可能です。

import subprocess
from concurrent.futures import ProcessPoolExecutor

def multi_process_func(seed):
    str_seed = str(seed).zfill(4)
    global runfile
    path = "/usr/bin/python3 /workdir/" + runfile + " < /workdir/tools/in/" + str_seed + ".txt "        
    proc = subprocess.run(path, shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE )
    # print(str(proc))
    return str(proc)

N = 1000 # 回したいテストケースの数を指定
runfile = "AHC011.py" # 実行ファイルを拡張子含めて指定
with ProcessPoolExecutor(max_workers=8) as executer:
    results = executer.map(multi_process_func, range(N))
res = list(results)
print(res)

上記のコードから、マルチプロセスで runfile のプログラムを実行することが可能です。
このコードの変数 res の中に、print() で出力した値が入っています。

このresの中身をパースして、csvデータを取得していきます。
各配列の要素はstrなので、find() で見つけました。
もっと良い方法もありそうな気もしますが、ひとまず目的は達成できているので良しとします。
csvファイルには、seed, N, スコア, 答えの出力文字数, 答え を書きだせるようにしました。

ローカルテストの失敗について

ローカルテストでの失敗についても記録しておきます。

Python3のコードから、プログラムを並列実行して、バグがないだろうことを確認していました。
しかし、本番提出では、WAが出ることがあります。
これは、プログラムとしては、配列外参照をしていないことや、無限ループになっていないことをある程度保証してくれてはいますが、本当に正しいスコアであるや、有効な答えになっていることの保証はしてくれていないことに気づきました。

今回のタイプの問題では、出力した答えを、ジャッジするプログラムも書く必要があることに気づきました。

ローカルテストの実行結果

今回提出した、コードの手元での結果は以下の通りです。
なお、この実行結果はPython3の結果なので、pypy3だと実行回数が増える分上振れします。

コードの良し悪しはPython3で判定できると考えて、ローカル環境にpypy3の実行環境は作っていません。