inani_waonの日記

コンテスト覚書

MM125 Lines 参加記録

TopCoderMarathon Match 125に参加しました。

問題はLines。ボールを5つ繋げると消えるパズルです。

www.topcoder.com

 

 

提出53人中、Provisional4位、最終順位6位でした。

ルール

ボールは空きマス4近傍を距離無限で移動できます。

・ボールを5つ以上直線に繋げた場合は、ボールが消えてその数に応じた点が入ります。

・ボールを5つ繋げない移動をした場合は、ボールが3つランダムに生成されます。

 ・ボールの生成により5つ繋がった場合も、移動で5つ繋げた場合と同様に消えます。

1000回移動するか、盤面がボールで埋まるとゲーム終了です。

 

あとこれはコンテスト終了後に把握した情報ですが、縦横斜めの複合で消すと別々に計算されるのではなくて消した総数に応じた点が入るっぽいです。†本質†情報では?

 

考察

序盤考察

MM123の焼き直しっぽい。というかサンプルコードのクラス名をJewelsから直し忘れていますね?

消す長さボーナスは、長さ5で10点、長さ9で38点、長さ11で71点と、MM123に対して緩やか(?)な伸び。また、ボールの消去を伴わない移動をするとボールが3つ湧いてくるので、MM123のように固定盤面を埋め込んで再現するのは無理そう。

実はボールの生成により2ライン以上を同時に消したり長さ11で消すことが出来る。長さ11の消しは同じ色のボールが偶然2か所に同時湧きしないと実現しないので切っていいかな。

縦横斜めの複合消しもボールが少なくて済むけど、閉路を生みやすそう。←この考察はルールの把握を間違えています。

ボールは消去を伴わない移動でのみ増加し、得点はボールを消すことでのみ増加する。そのためボール生成による消去が発生すると手数あたりのボール総数が増え、得点アップにも繋がりそう。

すぐ消す色と長く消す色を分けたり、マップ端で長く消すのを組んで中央では雑に消す、みたいな区分けをすると良いかも?

難しそうだけどとても面白そうな問題に見える。

中盤考察

フォーラム情報で、MM5と問題モロ被りであることが判明。公平を期すため、MM5の方針紹介スレッドが公開される。MM5フォーラムではこの辺りが有益情報に見えた。

・評価は長さを5乗した(17位、青)

・3手読みした(1位、赤)

・同じ色の交差部分にペナルティを与えた(1位、赤)

17位の人も1位の人も言ってることは一緒で、正方形的な物を作るのを避けて細長く連結しましょうということだと思われる。

終盤考察

生成による消しは、盤面がある程度埋まっていないと全然関係ない場所に生成される方が多いので期待できないうえ、盤面が埋まっていくと今度は加速度的に移動が制限されて手詰まりになるので利用は難しい。

1000ターン生き残るだけで3800点くらい入るので、これを伸ばすよりはより多くのケースで長生きすることを目標にした方がよさげ。

 

 

やったこと

Step1

まずは1手読み貪欲。ボールの移動自体が可能かは、空きマス同士を連結するUnion-Find木を作って確認した。*1長さ5の領域を全走査して、単色(1色+空きマス)であれば[ボールの最大の連結長^3]を評価として、その総和を取る。ボールを消した場合は[実スコア*100]を評価に足す。まだ高速化も不十分で、実はN11のケースではTimeoutしていた。

Step2

やる気を無くす。ぼくのかんがえたさいきょうのほうしんとほぼ同一のものが全体公開されてしまった。MM5って15年前だし、人員も変わってると考えたら仕方ないのかな…。

Step3

飛び石的な配置も評価できるようにした。長さ5の領域毎のパターンは、単色に限定すれば31パターンしかない*2のでビットパターン毎に評価を埋め込んだ。基本的にはボールの数で指数的に評価が増えるようにして、隙間があれば評価を少し下げた。

Step4

ビームサーチした。深さは2で固定で、幅はNによって決める。N=7であれば30、N≧10であれば4。多様性確保のため、[移動先の座標]毎にベストを4個取って、更にその中身をマージして、[消去発生][消去非発生]毎にそれぞれ幅の半分を取る。*3つまり、N=7であれば消去発生時と消去非発生時をそれぞれ上位15個まで持つ。N=11などは時間が間に合っていないので、1ターンあたり10msを目安として間に合わなさそうな場合は[ビーム幅を半分にする]または[深さ1にする(1手貪欲化)]で遅れを取り戻す。また、2手目で得られる評価は0.8倍とした。

ちなみに何のためにビームサーチ(複数手読み)するのかというと、邪魔なボールを動かすためや、長さ6以上で消す準備のライン延長をするため。

 

細かいパラメータ調整

・パターン毎の評価

十字や正方形を作りたくないので原則長くなるごとに8倍。4個揃いだけ4倍なのは消去スコア計算との兼ね合いだけど、もっと良いパラメータはあるかもしれない。これでも油断すると正方形的なものを作ってしまう。

const int partScore_1 = 10;
const int partScore_2 = 80;
const int partScore_1_1 = 60;
const int partScore_1_1_1 = 560;
const int partScore_2_1 = 560;
const int partScore_2_2 = 2240;
const int partScore_3 = 640;
const int partScore_3_1 = 2240;
const int partScore_4 = 2560;

・消去評価

原則[実スコア*800]としたが、無理ゲー(1000ターン完走できない)ケースでは短く消す方が嬉しいように式を弄った。*4

 ・通常ケース

  (len * len - 7 * len + 20) * 800

 ・無理ゲーケース

  ((len - 1) * (len - 1) - 7 * len + 39) * 800

 

高速化

・差分計算

消去が発生しない場合、移動元と移動先の座標を含む領域だけを再計算すれば良い。更に言えば、その領域計算は開始時に1回だけ纏めてすれば良い。

・連結数による足切り

同色が繋がっている数で色・座標毎に現在価値を決め、現在価値より2以上低い場所への移動を禁止した。ただし、より長い色の線を塞いでいるものを除ける操作は許可。

・消去操作による足切り

原則的に消去操作の方が圧倒的に評価が高いので、1手目で消去できるのにしなかった場合は2手目で必ず消去操作を行うことにした。また、時間切れで1手読み化している場合も、消去操作を見つけた場合は以後消去操作のみチェックするようにした。

 

やってみたけどダメだったこと

・斜めの評価を下げる

斜め配置は閉路を作りがちなので控えてくれると助かると思ったけどスコア上はそんなことはなかった。

・四隅に何かあると微ボーナス

端に詰めたり長く消す狙いだったけどスコア低下した。

・空きマスを評価

空きマス同士が連結していたら~みたいな感じで評価していたけど、重いうえにスコア低下した。評価方法が上手ければ上手く行ってたかも。

 

やりたかったこと

・2手目のペナルティを可変にする。

C3で盤面がガラガラで次に出現するボールが全て2手目で動かすのと同じ色というケースとその逆では、2手目に想定通りの手を打てる確率が全然異なる。ただこれを調整すると普段の消す消さないの挙動が不安定になるので手を付けられなかった。

・端に寄せる配置を高く見積もる。

長く消すためには端を埋めて最後に真ん中を詰めるという操作が必要だが、評価関数の都合上、外周2マスは評価が低くなりがちなので、真ん中を先に埋めて長さ6~7でしか消せなくなることが多かった。

・長さ5の領域内が多色だったときの評価

最終的に一律で0としたが、工夫すれば伸びていたかも。

 ・(評価が長さ^3だったときの検証)長さ^1とする

  スコア+1%だったけどあまりに誤差だったので外した。

 ・-10点とする

 ・2マス目で多色を検出したら-50点、3マス目で検知したら-40点、…

 ・隣接なら-50点、1マス空いていれば-40点、…

  2番目が一番良かったけど、あまりに根拠が不明確だったので外した。

 

他の人の解法を見て

え、斜めの方がいいの?(閉路が出来やすくないですか?)

端に寄せて真ん中を開ける方針だとその方が良いのかな。評価の組み合わせ相性は大事ですね。

ビジュアライザが動いて楽しい、それはそう。

 一番邪魔な場所に出てくるボール、嫌すぎる。(もしかして3ターン読みしてますか)

 

評価が難しいときはモンテカルロ、それはそう。

 4個揃えたけどあと1個が絶対に入らないみたいなのが稀によくあったので、これを計算出来てるのは強いですね。1000ターンもたないケースに強そう。

 

総合的に見ると処理時間内で読みの精度を高めるための工夫がそれぞれ違う感じで面白いですね。

 

こちらはTopCoderのフォーラム(要ログイン)

https://discussions.topcoder.com/discussion/4777/post-your-approach

 

感想

MMはTesterの機能が充実していて、純粋に問題を解くことに専念出来るのでありがたいですね。

MM5との問題被りというか、それによる情報公開で実装するだけゲーになった(実際はそうでもなかった?)ことでモチベーションが一時消失しましたが、15年前に当時の計算資源で同じ問題を解いてる人たちもいたんだな、ということに思いを馳せたりしながらなんとか完走しました。

最終形はハイパーパラメータだらけなので、もっと上手い方法は無いのかという感じでしたが、やること自体はシンプルに出来た(探索手法はそうでもない)ので理想の戦い方にちょっと近づけたかな、と思います。

 

*1:移動元の4近傍のrootいずれかが、移動先のrootと同じなら移動可能。

*2:32でないのは、全部埋まってるケースは消えるので。

*3:消去発生パターンの数が少ない場合はその分消去非発生に幅を割り当てる。

*4:完走出来る目安はN7C3,N8C4,N9C5,N10C5~6,N11C6。これよりCが大きいものは無理ゲー。

AtCoder Heuristic Contest 001 AtCoder Ad 参加記録

AtCoder Heuristic Contest 001に参加しました。

問題はAtCoder Ad。

制約に従うように広告(矩形)を配置して、満足度を最大化する問題です。

 

atcoder.jp

 結果は提出1505人、得点を得た人1369人のうち、暫定テストでは90位でした。

システスはかなり落ちてしまい118位。

 

考察

問題

敷き詰め問題(矩形パッキング問題)っぽいけど、一部設定が特殊。
・指定の座標を含む指定サイズにすること
・面積は指定されるが、厳密に守る必要はなく縦横比も自由であること

件数

広告の満足度を取るためには、点としては(y,x),(y,x+1)(y+1,x)(y+1,x*1)の4点を確保しないといけない。そのため完全に隣り合っている広告を両立させることは出来ない。広さ10000x10000*1に対して広告件数は50≦N≦200で、隣り合うことは理論上はあるが非常に稀。*2

形状

実は凄く細長いのが正解のケースがあるかも。干渉しやすさとか、サイズの調整しやすさとか、色々違いそう。

大きさ

小さい広告の方が狭い領域で多くの満足度を生む。衝突時は大きい広告のスペースを削る方が良い。スポンサー料金とは…?

スコア

言い換えをすると、広告毎に[過不足な領域の割合^2]の減点。割合は1以下なので二乗と言っても減少で、特に僅かな過不足であればスコアはほぼ減少しない。領域10%不足でスコア1%減。皆をちょっとずつ不幸にした方が総合的には得。極論、全広告を90%サイズにして完全に敷ければ暫定スコア49,500,000,000が可能。こういう得点ルールなので、基本的には全ての広告を希望位置に置く。

順位表

823,090点以降に同点がほぼいない。万人が使っている貪欲的なものはなさそう?

解法

矩形パッキングで調べると色々出てくる。

シーケンスペア - Wikipedia

ぱっと頭に浮かぶ分割統治法はスライス構造というもので、シンプルながら最高効率とは言えなさそう。シーケンスペアは効率が良さそうだけど、1週間で勉強しないといけないのは辛そうで、計算コストもある程度理解しないと見積もりできなさそう。

あとは最初の2x2(1x1…?)を拡張する方法もあるけど調べて出てくるものでもなかったので、*3スライス構造による分割統治法を使うことに決めました。*4

これは事後感想ですが、その場の分割は上手く行っても後でやっぱり大きいロスを出さないと分割できないというパターンが多く、低速に細かい位置調整をするよりも高速に分割順をガチャガチャ回す方が効果がありそうな気がしました。

 

最終的にやったこと

初期解の作成

初手のみ縦横それぞれ9999箇所チェック、以降は分割後の2つの領域を大きい1つの広告とみなして[分割後のSize] , [Rの合計] で満足度計算したもの*5*6の合計が最大になる場所で分割するよう貪欲する。9999*2のうち一番良いものを初期解として採用する。

一応書いておくと、広告が0件になる分割や、2x2(1x1…?)を分断するような分割は行わない。

山登り法

0.9を基準値として、評価が悪いノードの先祖(分割元)をランダムに1つ選んで、子孫を全て再構築する。[葉ノードの評価の合計]が改善されたら再構築したものを実際に適用する。0.9未満が無くなったり4000msが経過したら基準を引き上げる。

変形操作としては、階層ごとに以下のものを使った。

・貪欲(50%、もしくは広告数が2)

・[広告間の最善位置]上位20件からランダム(48%)

・全位置の上位50件からランダム(2%)

最終調整

まずは各ノードを基点に貪欲法で再チェックし、山登り法で緩慢になっている部分を引き締めた。その後[大きすぎる領域を縮小]し、[空きスペースを使った拡大]、[隣接広告を動かして拡大]、[隣接広告からスペースを奪う拡大]、という順番で行った後、50msほど[空きスペースを使った拡大]、[隣接広告を動かして拡大]を繰り返した。

特殊対応

広告が絶対にぶつかって両立できない場合、一方を最初から無かったことにして、最後に余ったスペースに詰め込んだ。基本的に97%くらいの点数は安定するので、テストケース1件を落とすデメリットはあまりに大きい。*7

 

技術的な小ネタ

座標によるソート

広告を希望位置XYそれぞれでソートしたものを作成しておく。

隣り合う広告が分かると分割処理がしやすくなる。

区間ごとの理論値

隣り合う広告を左右に分割する場合を考える。この場合、左端で分割したとき右側の疑似満足度が最も高くなり、右端で分割したときに左側の疑似満足度が最も高くなる。つまりこの2つの疑似満足度を足したものが区間内の理論値となり、理論値でも選別に漏れる場合は区間そのものの計算を足切りすることができる。区間を理論値が高い順に取り出せるよう、優先度付きキューに入れて処理した。

区間ごとの最善値

面積オーバーの満足度を1.0とすると、隣り合う広告間の満足度は弧を反対向きに2つ足し合わせたような山型になる。*8なので三分探索や黄金分割探索が可能。ただし満足度が2つの領域とも1.0になる丘(?)は発生するので、その扱いは要考慮。

全分割位置の最善を求める

区間ごとの最善値を求め、その中の最善値を求めると、愚直に全探索するより速い。

 

やってみたけどダメだったこと

黄金分割探索

高速化したもののスコアは落ちた。黄金分割が駄目だったというより、スペースが余って最善分割位置が複数ある場合の選び方が良くなかった気がする。

目標サイズを縮小

90%サイズを敷き詰めて99%点取れるなら最初から縮めておけばいいのでは?という浅慮。スコアは上がったか下がったか分からないような変動。言うまでもなく余る10%のスペースを上手く消費するのが肝で、上と同じ原因と思われる。

スコア最善のとき、最善範囲の真ん中で分割する

両方に余裕があればいいだろう、という話でもないらしい。真ん中というのが座標的な中央だったので、それぞれのサイズを考慮して余り率が同じになるようにとかすればまた違ったのかもしれない。

スコア最善のとき、最善内ランダム位置で分割する変形操作

これが駄目ならどうしろと。ただ試したのが中盤だったので、終盤また試しても良かったかも。

 

反省点

類似問題を調査したのは良いが、全く同じ条件ではないのだから(手法が見つかる=実績がある=それを使えばいい)というわけではない。*9

領域の拡大を入れてしまうとスコアがばらつき山登りの改善を目視しにくいので、遅めに実装することにした。中盤は山登りのアルゴリズム改善ばかりしていた。特に他の領域に干渉する拡大の実装は残り1,2時間でギリギリ完成だった。時間があれば縮小拡大の側をもう少し弄って何かできたかも。(縦横比を変えるとか、スライド移動させるとか)

今回はビジュアライザがテスターとしてのバッチ処理に使えなかったのもあり、もうちょっとデバッグ用の情報の吐き出し方を工夫してそこで作業を縛られないようにしたい。ついでにデバッグ並列実行もしたい。

上下左右にそれぞれ同じようなチェックをするのを上手くエコに書けなくてコード量がとんでもないことになった。

テスターを書くのをサボったので、暫定テストケース50件では同じプログラムで何回提出してもWAが出ないのにシステス1000件では6件落ちるみたいなのが起きた。

 

他の人の解法を見て

#AHC001 hashtag on Twitter

twitterハッシュタグ

AtCoder Heuristic Contest 001 AtCoder Ad - びったんびったん

暫定テスト1位の人

 

得点率98%(49G点)超えになると、伸縮したりする焼き鈍しを使っている人が多いように見えました。分割統治法は、スライス構造では四畳半的な配置が出来なかったのに加え、階層構造になることで上位階層の再考コストが高くなるのが難点だったように思います。後者については上位階層の再考が少なくなるよう調整できればまた違ったかも?初期解をビームサーチしたり、多点スタートして上位階層の再考を禁止したり。

 

あとは局所最適解に陥りやすいというのは共通認識のようで、それなら焼き鈍し(改悪を認める)を試すべきだったなーと思いました。†本物†の焼き鈍し、使ったことないんですよね…。

 

とりあえずはこんなところ。

分割統治法の人だけのまとめとかあれば見てみたいですね(他力本願)

 

感想

ラソンは、楽しい!

 

 

 

*1:厳密には9999x9999の気がする?

*2:3000ケース探して1件だった。

*3:矩形パッキングにサイズを変更可能という要件は無いのでそれはそう。

*4:実装コストや変形操作のしやすさも考え、二分木にしました。

*5:疑似満足度と呼ぶことにする。

*6:余った面積は後で削ぎ落すため面積オーバーによるペナルティは無い(疑似満足度=1.0)こととする。

*7:それが数千件に1件?みたいな出現度で、テストケース2000件というのは思う所がなくもない。

*8:上手く証明できないけど実験した感じ谷にはならないっぽい?

*9:その先入観が無くても伸縮する焼き鈍しをしたかというと微妙だが…。

Topcoder MM123 Jewels 参加記録

TopCoderMarathon Match 123に参加しました。

問題はJewels。マッチ3パズルです。*1

www.topcoder.com

結果は登録176人、提出67人中の6位。

レート1658→1924(黄)

 

考察

当方、パズルはパズドラを嗜んだ程度*2で、ぷよぷよテトリスもからっきしです。

 

とりあえず得点を見ると[(消した線の長さ-2)^2] * [Chain数] の合計ということで、とにかく大きいコンボを1発でも決めることが大事だと分かります。*3

盤面を見てコンボを探索するよりも、固定コンボを埋め込む方策が強そうですね。

 

大体同じコンボを繰り返すということで、

Score = [コンボの平均得点] * [コンボの実行回数]

となります。

 

上記の計算式より、

  • コンボの平均得点を最大化する(厳密には平均得点/手数のコスパを最大化する)
  • コンボの実行回数を最大化する(実行までの手数を最小化する)

という2つの問題をそれぞれ解くことになりそうです。

 

ここでL字などの複雑な形の得点が読み解けなかったのでテスターを使って手で問題を解いてみたところ、縦と横はそれぞれ独立した点が入ることと、Chainは消した連結成分の数ではなく落下が発生した回数であることが分かりました。コンボ作るの難しそうだな?

 

実装

とりあえず考えている方針で上手く回るかを見るために簡単なコンボパターンを埋め込んで回してみようということで、先に簡易的な(?)実装を行いました。セル毎に目標色を設定して、最後にコンボ始動用に発火する2点を交換する感じです。

この辺りでテスターを見やすくするために宝石の画像に数字を書きこみました。

 

回してみた感じ、以下の点がネックになりそうでした。

  • 移動しようとすると3つ揃えてしまうケース
  • 特定色の宝石が足りないケース
  • 行き場の無い宝石の追い出しが無限ループするケース

また、以下の改善点がありそうでした。

  • 交換する2マスの両方にメリットがある交換をする
  • 等価の盤面(色違いや左右反転)を評価して移動回数を減らす
  • 落ちコン*4でコンボが破壊されるのを防止する

 

問題点についてはパターン側で色の数を偏らせないようにしたり、盤面全体を使わずに余裕を持たせることで多少の数の変動に対応できるようにしました。それでも宝石不足が発生したときは、余っている色の宝石を消すようにしました。また、無限ループっぽいなと思ったら強制的にコンボを始動させるようにしていました。*5

移動の効率化についてはルール決めで2マスに得がある移動を優先したり、パターンの色C種類と実際に使う色C種類で不整合セル数の最小マッチングをしました。

落ちコン対策は、セル毎に禁止色のマスクを作ることで屋根と壁を作りました。ただ完全に防げるわけではなく、屋根が破壊されたうえで更にちょうどいい色の宝石が降ってきてコンボパーツが破壊されてしまうことがあります。しょうがないね。

 

パターン作り

手、もといExcelで作りました。

色々と試行錯誤した結果、1chain目で土台を破壊してコンボ始動し、2chain目で大量に列消し、3chain目以降で3セルずつ消してchain数を稼ぐようにしました。

 コンボの最後に列消しを行う形だと消す列数が制限されるうえ、落ちコンで事故が発生して期待した点数が出ないことが多かったです。

 

やれなかったこと

  • 不測の事態*6で挙動不審になりやすい件への対応
  • 連結成分単位での色の割り当て
  • 残り時間が少ないときに小さいコンボを組んだりして小さく稼ぐ
  • シミュレータを走らせてさいきょうのパターンを見つける

 

みんなの方針を見て

見た限り、ほぼ全員がパターン埋め込みをしていました。強めの人々は連結成分単位で色の割り当てをしていたようで、この辺りは典型なのかなと思いました。やり方は分かったので次があれば頑張ってみたいです。

あとはもう強いパターンを組めたかどうかという世界のようです。

 

感想

これはこれで楽しいけど、これはプログラミングコンテストなのか…?

 

 

*1:マッチョパズルではない。

*2:時期的には曲芸師の前後。

*3:便宜上、一連のChainをコンボと呼ぶことにします。

*4:落ちてきた宝石で3つ揃いが発生すること。

*5:パターン構築開始時に不整合セル数をカウントして、それと同じターン数が経過していたら無限ループと判断。

*6:色の枯渇とか。

My開発環境2020

年の変わり目ということで、なんとなく現在の自宅開発環境を書いてみます。

誰かに教えたいというよりは、将来振り返る時に見返したいとか、

もっと良い物があれば教えてもらいたいの気持ち。

レガシーなのを置き換えようとしている途中なので結構恥ずかしい。

 

ハード

PC

自作PC。Ryzen3700X + GTX1660。

フルスペックで回ることはあまり無く、マラソンのテスターがマルチスレッド対応だと全力が出せる感じ。グラフィック性能もごく稀に画面録画やCUDAを使用するくらいで持て余している。次はノートPCに一本化してしまうかもしれない。

 

モニタ

24型の16:10モニタを2台横に並べている。左が作業用、右がブラウザ用。

16:9は全く作業向きでないので、縦が1割長いことで便利に感じることは多々ある。*1

しかし16:9に最適化されたソフトのせいでトラブルが出ることも稀にある。

良い物ではあるが、配線が煩雑なので次はUSB Type-Cだけで繋がるやつが欲しい。

 

キーボード

HHKB Professional JP Type-S 白(日本語配列)。

指の移動量は減った気がするけど、作業効率が上がったかと言われるとどうだろう?

1個前はRealForceのテンキーレス。

更に前はバッファローのBSKBCG300BKのシリーズ。(の、旧モデル)

バッファローのが実売2000円程度の割に優秀で、3万円分までの差は感じない。*2

キーを減らす小型化も一長一短で、完全上位互換とは言えない。

割れてるキーボードはちょっと興味あります。

 

マウス

ロジクールのMX Anywhere 3。

性能的不満はほとんど無いけど、手へのフィット感は今一歩。

大体1,2年間隔でジプシーしている。

 

デスク

ダイニング用のコタツテーブル。

120x65cmという変則サイズに、天板は60cmとかなり低め。

小柄なのでこれくらいの高さが丁度いい。

 

椅子

オカムラのシルフィー。

これも小柄な人間向けに調整しやすいので。

ハイバックの背面メッシュ、座面クッション。

座面メッシュはスマートなようで、フレームが足の血管を圧迫しやすい。

 

ソフト

OS

Windows10 Pro。

UNIXは稀に触る機会はあれど全然上手くならない感。

 

IDEテキストエディタ

C#C++はVS。

JetBrainsは検討したけどVSと完全互換でなかったのでやめておいた。*3

JavaeclipseIntelliJの間でふらふら。Java自体今は使っていない。

その他の言語(PHPJavascript辺り)や、データの閲覧はVSCodeとメモ帳。

RustはコドゲIDE直書き。

C#+VS以外は使用頻度が低く、IDEを使いこなしているとは言い難い。*4

以前はサクラエディタも使っていたけど、最近はVSCodeに統一するために封印した。

メモ帳?起動が速いし余計な通知も出ない神ツールです。

VSCode拡張機能

・Japanese Language Pack for Visual Studio Code

日本語でおk

・PlantUML

簡単な図を書くのに使う。

Excel Viewer

実はまだ使っていないが、こんな機能あったなと思い出したので今入れた。

csvデータの閲覧にはExcelを使っていた。

 

Git

SourceTree。

他がトラブったり食わず嫌いでなんとなく使い続けている。

Bitbucketにプライベートリポジトリがいくつかある。

 

ランチャー

CLaunch。

1,2年前まで一切使っていなかったけど、試しに使ってみたら便利だった。

 

ブラウザ

Firefox

現在優位性があるというよりは、大きな不満が無いので継続して使っている。

 

まとめ

ハード環境は買い物記録というところですね。

ソフト環境は古くても開発は出来てしまう(してしまう)ので、

情報が入ってくる環境に身を置くことって大事だよな…と思います。

カスタマイズをあまり好まない性格なので、壁を打ち破る必要もあるかも。

高尚なものを使うことが目的ではありませんが、便利なものは使っていきたいですね。

 

*1:というのは半分嘘で、実際は不便さを感じない。

*2:打ち心地も"比較的"静電容量無接点方式に近いスコスコ感がある。個人の感想。

*3:業務、GUIクロスプラットフォーム等、全体で環境統一したい感じ。

*4:C#も使いこなしているかと言われると…?

Topcoder MM122 SuperMinesweeper 参加記録

 

TopCoderMarathon Match 122に参加しました。

TopCoderは初参加です。

問題はSuperMinesweeper。クソデカマインスイーパーです。

 

www.topcoder.com

結果は17位でした。(登録162名、投稿87名)

レート0→1,658(黄)

問題考察

マインスイーパー、以上。となるのでパラメータの考察を。

N

盤の1辺のサイズ。10~50。

大きいほど時間がかかる、多様な盤面を含む、初期位置が隅になりにくい。

D

セルの数字が示す範囲(後述)1,2,4,5,8,9,10。

大きいほど完全特定しにくい?

M

爆弾の数。N*Nの0.1~0.3倍。

大きいほど数字セルが減り情報が減る、運任せが失敗しやすい。とても影響が大きい。

Score

安全セルを開けた数 * (1 / 地雷を踏んだ数)

地雷を踏まないのが最も良く、1個踏むと全て開けても0.5。地雷を踏んでしまった場合は次のペナルティが相対的に軽くなるので、積極的に開けていくことになる。

数字の範囲

安全なセルには距離がabs(x1-x2)^2+abs(y1-y2)^2以内のセルの地雷数が表示される。式を書くより図の方が分かりやすいので下記参照。

D = 1

□■□

■◇■

□■□

 

D = 2

■■■

■◇■

■■■

 

D = 4

□□■□□

□■■■□

■■◇■■

□■■■□

□□■□□

 

D = 5

□■■■□

■■■■■

■■◇■■

■■■■■

□■■■□

 

D = 8

■■■■■

■■■■■

■■◇■■

■■■■■

■■■■■

 

D = 9

□□□■□□□

□■■■■■□

□■■■■■□

■■■◇■■■

□■■■■■□

□■■■■■□

□□□■□□□

 

D = 10

□□■■■□□

□■■■■■□

■■■■■■■

■■■◇■■■

■■■■■■■

□■■■■■□

□□■■■□□

 

やったこと

完全情報フェーズ

確実に地雷が無いセル、有るセルを特定する。基本的に出来る事は2つしかなく、自明なルールによる一定範囲内の個数特定と、有り無しを仮定した総当たり。総当たりは強いが時間がかかるため、軽くて雑な絞り込み>重くて丁寧な絞り込みの順で行い時間を節約する。1セル開けることでヒントが増えて更にセルを開けることが出来るので、軽くて雑な絞り込みも多様性があればそれなりの総合力になる。以下の順で行い、途中で何かが判明した場合は先頭からやり直した。

・数字セルの周囲が全て安全、または危険の判断

・残り地雷が0なら全て安全

・数字セル2つの関係から、共通領域・数字セルAのみにかかる領域、Bのみにかかる領域の地雷最大数と最小数を計算

・数字セル1つの範囲内を総当たり(K≦22) K=不明セル数

・数字セル2つの範囲の和を総当たり(K≦22)

3x3領域を総当たり

・残領域全てを総当たり(K≦26)

・数字セル全ての範囲内を総当たり(K≦26)

・5x5領域を総当たり(K≦18)

・→これでも何も分からない場合は不完全情報フェーズへ

不完全情報フェーズ

セルを開けた場合の期待値を雑に計算。しかしセルの座標ではなく全く関係ない添字を計算に使用しており、何故動いているのか分からない。直すと弱くなる…。

期待値が悪くしかならないケースのほか、Score0.4で打ち切るが、D=1かつM/NN>0.25のケースは地雷踏み連発で破滅しやすかったのでScore0.1で打ち切るようにした。

 

全列挙実装

以下の手順で行った。

・全列挙する不明セル群(以下、不明セル群)の座標をListに積む。

・不明セル群に対するD範囲内の数値セルを抽出する。

・各数値セルに所属する不明セルのListのindexをビットパターンにして覚えておく

・2^[不明セル群の個数]だけカウンタ++しながらループする

 ・実はこのカウンタ値はそのまま、どのindexの不明セルを地雷扱いするかのパターンになる

・数値セルのパターンとAndを取ると不明セル群内の地雷数が判明するので、上限数、下限数をチェックする

ただしこれだけではパターン数が膨大なため、代表的な数値セル1つを抜き出し、その地雷を許容する最大/最小数をチェックすることである程度高速化した。

 

Good
・領域の形に依存せず、全列挙自体を最小の手間で行える(5x5、D範囲内、残り全部など)
Bad
・部分的な制約を無視して全列挙する(1の数字セルの周りに地雷を3個置くパターンを延々試したりする)

・言うほど最小の手間ではない(高速化とデバッグにコンテスト期間のほとんどを費やした)

3x3版は>>9重ループ<<

 

 

やりたかったこと

1.自明なルールを論理的に分解。

処理時間がかかりそうなのと、ビット周りの実装に手間取りそうなこと、{1,0,1,0}か{0,1,0,1}みたいなパターンに弱そうなことから総当たりを優先した。実際は6時間くらいで高速なものを実装している人もいたので可能だったのかもしれない。

qiita.com

2.運任せの細かな確率計算。

確率だけ計算出来たところで、という感じだったので他を優先した。数字セルの範囲内にある不明セル数が100を超えると時間も不安だし。

qiita.com

3.運任せ後の盤面構築。

色々試したものの上手く性能向上せず、膨大な時間がかかりそうだったので断念。

dic.nicovideo.jp

4.地雷数の制約を考慮した全列挙

絶対バグらせると思って投げ捨てた。処理時間が間に合うかも不安だったし。

感想

問題として良かったか?と言われると良くなかった気はするけどそれなりに楽しかったです。C#(を使いこなす技術)の限界を感じる…。

 

たのしい

・パーツをたくさん作って繋げられるゲーム。

・座標毎に再考フラグを管理して無駄な処理を削ったりする作業。

 

たのしくない

・人間の能力があまりに足りないのでトレースしにくい。

・副作用の塊みたいな入出力。

・運任せフェイズの運任せ感。

C#、立っているビットのカウントくらい高速にやろうや…。

・BitArray君、All、Any、Equality、ビット数カウントくらい積んでほしい。

Topcoder君のUI。もうちょっとなんとかなりませんか…。

 

 

 

HTTF2021決勝オープン - マイニング 参加記録

ラソンコンテストのHTTF2021決勝オープンに参加してきました。

予選落ち用の誰でも参加できるコンテストです。

結果は本選出場者と合わせた提出者のうち、31/217位。

かつてない好成績で満足です。 atcoder.jp

問題

問題はマイニング。某建設案件かな? 鉱脈を掘ると利益が得られるが、隣接する採掘済のマス数に応じて採掘コストが変化するというものでした。

掘る順番こそあれど、"いつ"という時間の概念がほぼ無い問題のため、典型問題に対するアルゴ知識が薄めでも力押しで(ある程度は)なんとかなる問題だったと思います。一方で掘り始めは赤字スタートになるため、方針が立たないと正の点数を取るのが難しく、スタートはもたつく問題でした。

データの特性としては、一様ランダムではなく偏りが存在するもので、掘る順番通りに外側から探索するのではなく、内側に埋まっている美味しい場所を中心に探索するのが良さそうでした。

方針

ローグライクゲームのマップ自動生成に近いことをしました。

まず部屋に相当する、利益の大きい領域を抽出します。次に部屋同士および鉱山の外をそれぞれ最小コストで繋げば、おおよそ最適解が得られるだろうというものでした。上手く行かない部分は、3部屋以上を組み合わせて最適な経路を組む場合と、[利益<コスト]である採掘済のマス数に応じて利益が出るマスの扱いですね。

結果としてもまさにそんな感じで、採掘済隣接マスが1のときの利益は上手く拾えましたがそうでない部分で稼ぎが甘かったです。

方針の詳細

1.[利益>コスト]の場所を抽出。

2.利益大マス同士が連結しているもの単位でグループにする。

3.グループに対して2,3マス連結かつ[利益>コスト/隣接数]の場所も巻き込む。

4.グループ同士の結合コストが最小、かつ結合コストが弱グループの利益より小さく、かつ結合コストがいずれかのグループの外周からの採掘コストより小さいものを結合する(結合できなくなるまで繰り返す)

5.グループの評価が外周からの採掘コストより高いものを掘っていく。

6.あとは場当たり的に利益が出る場所があれば掘っていく。

細かいテクニック 

コスト節約

コストは

・k=1 1/1

・k=2 1/2(-50%)

・k=3 1/3(-16%)

・k=4 1/4(-8%)

でk(4近傍で隣接する採掘済マス数)の増加に対して減り方が一律でないので、なるべくk=1で取ることを避けると少しだけスコアが稼げました。取ることを決めた領域に対して、kが大きい場所から順に取るようにすると良かったです。(1/3ほど実装し損ねているような…?)

 

 反省会

解説配信的なものは今のところ無いようですが、出題者の方によるとフローを使うらしいです。用語が全然分かっていないので余力のあるときに勉強しようと思います。

  上位陣と差が付いたのは、利益が[コスト/3<利益<コスト]のようなマスを広く取れるかという部分のように見えました。コストを払うときにkがいくつか想定できずにシミュレーションに困ったのはありますが、矩形領域で取っていけば比較的計算しやすそうですね。

あとは例によってマラソン的な最適化を全く行っていないですね…。領域同士の結合はコスト最小から順番に結合というルールがかなり強く思えたので、必要が薄かったといえばそうなのですが。方針を立ててちょうど8時間使い切って実装が尽きたというのもあり、そこまで後悔は無いかも? 

 

要望的なもの

紛らわしい用語が多くて混同しがちでした。

・データに含まれる「外周」と、データに含まれない「鉱山の外部」

・「利益」に含まれない「コスト」 

ビジュアライザは良いところも悪いところもありました。

・一瞬だけ最終スコアが出て、その後は現スコアが出る挙動は考察で使いやすかった。

・コストは表示してほしかった(採掘過不足の判断が付かない)

・全体的に暗めで、特に簡易表示でないものや利益の低い箇所は見づらかった。

・簡易表示の、採掘済マスも色が見える印のつけ方が良かった。

全体としては、楽しみつつ考察の助けになるビジュアライザでとても良かったです。(お前は何様)  

 

完走した感想

コンテスト中は問題に言及禁止なのもありましたが、オープン参加者が少なくてTwitterで苦しむ仲間を見れなかったのがちょっと寂しかったです。皆も、走ろう!(マラソンハラスメント)

コドゲ常設コンペ(BOTプログラミング)紹介

前書き

コドゲは最近だと半年に1回程度のペースで新規コンテストを行っていますが、それとは別にいつでも挑めるコンペが開催されています。*1 常設コンペのうちコンテストと同形式である対戦型のものは、コドゲのトップページから[COMPETE→GAMES→BOT PROGRAMMING→VIEW ALL]で全て表示することができます。 以降、BOT PROGRAMMINGのものを指して常設コンペと呼びます。*2

 

常設コンペは執筆現在50種類以上のゲームがありますが、どれがどういう性質を持つゲームなのか分からなくなりがちなので、記録がてら紹介記事にしてみました。精進したり、沼るゲームを探すのにご利用ください。

 

目次

解説基準

基本的には二人零和有限確定完全情報ゲームであればシミュレートがしやすく、AIが作りやすいゲームです。そうでないゲームはシミュレートしにくかったり、意思決定時の選択肢が増えて難しくなります。

 

目安として、コドゲの公式タグと独断で付けた遊びやすさを書いてみます。

用語は適当です。

タグ

コドゲ公式がゲームに付けたタグです。攻略法であり、学びの目標にもなります。

単純度

ルール自体がシンプルか。ルールがシンプルでないものは実装が重くなりがちです。

初心者向けかの指標と言えるかもしれないけど主観は強め。

確定度

二人零和有限確定完全情報ゲームは星5、要素が欠けるごとに星を減らします。

ゲーム木探索の書きやすさと言えるかもしれない。

確定度が低い場合は、一部の情報を切り捨てて探索した方が良いこともあります。

明瞭度

ルールを読むだけでシミュレータを作れる場合は星5、情報が欠けると星を減らします。*3

コドゲのルールの不親切度(あるいはGoogle翻訳の原文破壊度)かもしれない。

想定ルート

Wood~で使用する技術→Silver~Legendで使用する技術(偏見強め)

ルールベースや貪欲法はいつでも使えるので、明記していないこともあります。

私のランク

これが高いほど解説が適切である可能性が高いです。

Silver以下のゲームはよく理解出来ていない可能性が高いです。

 

ゲーム紹介

Tron Battle

www.codingame.com

公式タグ:Flood fill, Pathfinding, Minimax 

単純度:★★★★★

確定度:★★★★☆

明瞭度:★★★★★

想定ルート:BFS(DFS)→ゲーム木探索

私のランク:Legend

何かとコドゲ入門で扱われがちなヘビゲーム。

4人ゲームで損得勘定や探索深度管理がややこしい点だけが厄介だが、ゲームルールは非常にシンプル。*4

 

Hypersonic

www.codingame.com

公式タグ:BFS, DFS, Simulation

単純度:★★★☆☆

確定度:★★★☆☆

明瞭度:★★★★★

想定ルート:貪欲法→BFS(DFS)→ゲーム木探索(ビームサーチ)

私のランク:Legend

ボンバーマン

4人同時着手なので、全員の動きを考慮するなら探索部分は苦労しそうだが、実際は自分の動き(+一部の特例)を探索すれば充分。

シミュレータがそこそこ重実装で、ルールに同時処理に絡む補足が多いので注意。

 

 

Coders Strike Back

www.codingame.com

公式タグ:Optimization, Multi-agent, Neural network, Distances Trigonometry 

単純度:★★★★★

確定度:★★★☆☆

明瞭度:★☆☆☆☆

想定ルート:ルールベース→不明(ルールベース???前評価???)

私のランク:Bronze

レースゲーム(?)

あらゆる条件や計算式がルールに明記されていない代物。解析ゲーなのか雰囲気実装ゲーなのか、ニューラルネットワークに丸投げゲーなのか…?Gold(複数機操作)まで全ルールは解禁されないっぽい。

突き詰めようとすると難しそうだが、Bronze到達までに自分で書くコードは10行程度なので入門としてやるのはあり。

 

Great escape

www.codingame.com

公式タグ:Pathfinding, Minimax

単純性:★★★☆☆

確定度:★★★★☆

明瞭度:★★★★★

想定ルート:BFS(DFS)→ゲーム木探索

私のランク:Gold

コリドールというボードゲームが元ネタの迷路作成&脱出ゲーム。相手がゴールしないよう妨害しつつ自分はゴールを目指す。

最大 3人ゲームなので損得勘定や探索深度管理は若干面倒だが、妨害する相手のセオリーはある様子? 現状1手読みまでしか作っていないが、144ヵ所の壁の有無が切り替わるのでゲーム木探索が本格化すれば計算量ゲーかもしれない。

 

Ultimate Tic-Tac-Toe

www.codingame.com

公式タグ:Monte Carlo tree search, Minimax 

単純度:★★★★☆

確定度:★★★★★

明瞭度:★★★★★

想定ルート:ゲーム木探索→ゲーム木探索(MCTS

私のランク:Legend

〇×ゲーム(3目並べ)の中に更に〇×ゲームが入っているゲーム。

ルールさえ理解すれば素直で計算量も多くない、二人零和有限確定完全情報ゲーム。

実装は重いというより、任意で高速化のテクニックが問われる感じ。

最終的には速度勝負な部分もあるので、高速言語への移植の練習にも。

 

Legends of Code & Magic

www.codingame.com

公式タグ:Card game

単純度:★★☆☆☆

確定度:★☆☆☆☆

明瞭度:★★★★☆

想定ルート:ルールベース?→ゲーム木探索?事前評価?

私のランク:Silver

マジック:ザ・ギャザリングトレーディングカードゲーム)のようなカードゲーム。*5

デッキに入れるカードをドラフトして、ドラフトしたデッキで戦う。

もちろん山札や相手の手札は見えない。使用可能な呪文の組み合わせ、クリーチャーの行動の組み合わせなど、組み合わせの最適解を探すゲームに見える。見えない情報が多いが、実際には見える情報の処理で手一杯な感じもする。

キーワード能力の組み合わせに対して説明が不足気味に見えたので、明瞭度は星1つだけ下げた。(接死トランプルの挙動は原作通りなんですかね…?)

 

Ocean of Code

www.codingame.com

公式タグ:なし(!?) 個人的にはPathfinding, 2D arrayあたり。

単純度:★★☆☆☆

確定度:★★★★☆

明瞭度:★★★★★

想定ルート:BFS(DFS)→パターン絞り込み→ルールベース?ゲーム木探索?

私のランク:Gold

海戦ゲーム。不完全情報を推理して敵の居場所を特定したり、逆に特定されないように立ち回ったりする。

初歩的な実装から始めて継ぎ足し強化がしやすく、他のゲームとは使用テクニックが違うこともあり、意外と万人向けな印象。逆に言うと競プロerでも詰まるときは詰まる。(相手のSILENCEへの対応が山場)

 

Spring Challenge 2020

www.codingame.com

公式タグ:Pathfinding, Multi-agent, Distances, 2D array

単純度:★★☆☆☆

確定度:★★☆☆☆

明瞭度:★★★★★

想定ルート:貪欲法→DFS(BFS)+焼き鈍し法or任意の探索法

私のランク:Legend

競争型パックマン

1プレイヤーあたり2~5体の同時操作かつ2プレイヤーの同時着手、衝突による移動の取り消しor殺害があり、さらに点アイテムも大半は視界外にある不完全情報っぷり。

 

Fall Challenge 2020

www.codingame.com

公式タグ:Monte Carlo tree search, BFS graph, traversal 

単純度:★★★☆☆

確定度:★★★☆☆

明瞭度:★★★★☆

私のランク:Legend

想定ルート:ルールベース→ビームサーチ?ダイクストラMCTS?(何も分からん)

センチュリー:スパイスロードというボードゲームのほぼクローンゲーム。

2人同時着手、山札(伏せカード)の存在があり想定が難しい。

どちらかというと相手を気にせずに1人で最適解を探すゲーム。公式タグが多様な通り、比較的好きなアプローチで挑める。実際にはビームサーチをメインに使う人が多い様子。

同じIDのBREWコマンドが再登場しないという点や、先読み税の前払い辺りが読み取りにくいので明瞭度を星1下げた。

 

有名デジタルゲーシリーズ

  • Code a la Mode(Overcooked)

私はやってないので、おそらく元ゲームと同じ性質としか言えない。

Code a la Modeは珍しい純協力ゲーム。

 

古典ボードゲームシリーズ

  • Checkers

単純度:★★★★☆

確定度:★★★★☆

明瞭度:★★★★★

 

ルールは元のボードゲームそのままなので、ルールで詰まることは無いのが安心。チェッカーは手数が有限か怪しいが、それ以外は二人零和有限確定完全情報ゲーム。*6

Woodリーグしかなく、登録人数は少なめ。

 

あまり向かなかったもの

Blocking

公式タグ:Monte Carlo tree search, Minimax

単純度:★★★☆☆

確定度:★★★★☆

明瞭度:★★☆☆☆

Blokusというボードゲームをインスパイアしたタイル敷き詰め(?)ゲーム。2人~4人の完全情報ゲーム。

入出力ルールの説明不足感があり、最低限のプレイがおぼつかなかった。多人数完全情報ゲーム+ビット管理してAndやOrを取るゲームとして見ると、他のゲームと被っている部分が多い。そのため解析に苦労してまでやりたいかと言われると微妙。せめて説明が充分なら…。

 

書いてないもの

他にもいっぱいあります。

やり次第書いていきます。(何年かかるやら)

 

目的別おススメゲーム

ゲームAIが初めて

Coders Strike Back。Bronze到達まではif文を書いたりパラメータを弄るだけ。クエストマップの対象でもあるので、おそらくはコドゲもここからの入門を推奨している。

BFS(幅優先探索)を使うならTron Battle。競プロから参入する人はこちらの方が馴染みやすそう。

ゲーム木探索を覚えたい

対戦相手を考慮せず自分の盤だけ考えたい → Fall Challenge 2020、Hypersonic*7

二人零和有限確定完全情報ゲームをしたい → Ultimate Tic-Tac-ToeOthello

3人以上のゲームに挑戦したい → Tron Battle(軽実装) > Great escape

MCTSを覚えたい → Ultimate Tic-Tac-ToeOthello

同時着手MCTSを覚えたい → Fall Challenge 2020

 

こうして見ると、ゲーム木探索関連は割とバランス良く参加できている気がしますね。

シミュレーションゲームやパズルゲーム、非グリッド座標ゲーム辺りの参加が足りていない気がします。

*1:コンテストという呼び方とは区別している模様。

*2:他にもコードゴルフ部門と最適化部門がありますが、ここでは割愛します。

*3:正確なシミュレータの作成に、サーバのソース解析等が必要になります。

*4:実は順位の損得勘定をしなくてもそこまで問題ない。

*5:ハースストーンの方が似ているらしい?

*6:チェッカーもコドゲのシステム上は上限ターンはありそう。

*7:情報を切り捨てて自分の盤だけ考えるくらいなら、最初から1人で完結する最適化部門(Optimization)をやった方がいいのでは…?