個人的学び

https://beta.atcoder.jp/contests/hokudai-hitachi2017-1/tasks/hitachi2017_1_a

近傍を混ぜる

shindannin.hatenadiary.com

2*2ブロックのswapを実験したけど、当然のごとく性能が悪かった。
けど、それを普通の2頂点swapと混ぜるみたいな発想が無かった。
良くない。

ばね

実際的に、有効かどうかはともかく発想として無かった。
良くない。

真ん中

山登りの解を初期解にすると少し改善することが分かっていたけど、理由が謎だった。
検証してないが、真ん中の状態がその方が良いからかもしれない。

真ん中が焼き鈍されにくいのは、言われてみれば極めて当然なのだけど発想としてなかった。
極めて良くない。

北大日立マラソン1stで考えるマラソン入門

前提

https://beta.atcoder.jp/contests/hokudai-hitachi2017-1/tasks/hitachi2017_1_a

この問題を前提にして、他に

  • 山登り、焼きなましの概要は分かってる
  • マラソンに1度くらいは参加したことがある

を満たしていると、分かりやすいかもしれません。

80点を目指して

マラソンをやる上で、勝とうとした時に基本方針が違うと絶対に勝てません。
何で勝てないの、と問われると簡潔な答えは持っていなくて、経験則なやつです。
今回で言えば、山登り系は焼きなましに勝てない。

基本方針といっても膨大にある訳ではなく

  • 山登り系(ビームサーチ・chokudaiサーチ等)
  • 焼きなまし

の2択です。
ほとんどのマラソン問題が何れかの解法になります。(異論でそう)

まずこの2択を間違うと上位に入ることが難しいので、これを正しく選択するのがマラソンの入り口かなと思っています。
(自分もよく間違う)

型にはめる

!!!蛇足!!!

マラソンマッチにおける精神論 - chokudaiのブログ

chokudaiさんの記事より引用

今回は関係ないけどさ、これないとマラソンマッチは死ぬし、これがマラソンマッチで一番技術的に大切なことだと思うんだけど、みんな型にはめるの大好きだから、やれビームサーチだの、やれ焼きなましだの言うんだよね。そんなん最初覚えないでいいっつーの。最適化に必要なのは、「出来たものをちょっとだけ変える」とか、「出来るだけ小さい単位で構成していく」とかで、そこの一つの実装方法としてビームサーチやら焼きなましがあるだけなんだから、それに固執させるのは絶対良くないと思うんだよね。まぁそれで強い人が出てきちゃってるからきっとそれでもいいんだよね。うん。なんか気に食わないけど。

chokudaiさんの意図を正確に理解できているか謎だけど、自分の考え、この記事の目的と真っ向から反する感じで面白いので紹介。
マラソンの本質的なものという観点でいえば、chokudaiさんと何も相違がない。だけど、モチベーションの問題として基本方針を間違うと上位陣と必要以上に実力の差を感じるし、基本をおさえると序盤とかはとくに簡単に上位に入れるので、マラソンを続けるために型にはめた方が楽だと思います。

方針の見分け方

それぞれの方針には特性があって、それを正しく認識してるのが強いマラソンプレイヤーです。
そういう意味で、これは今自分が認識していることになるので、そのくらいのレベルと認識して下さい。

マラソン強い人は最初から正しい方針であることがすごい多い!

焼きなまし

初期状態がそのまま解になる

焼きなましをやるにはいくつかの必要条件があって、その1つがこれです。
適当な例が思いつかないのですが、将棋等のターンを含む問題は、焼きなましにするのは難しいです。
将棋は2人ゲームですが、1人ゲームでターンでゲームが進行しスコアを最大化するタイプの問題の場合は、大体ビームサーチです。

近傍がシンプル

今回の問題では、2頂点のswapが基本的な近傍だと思います。
これは極めてシンプルですが、近傍が複雑な適当な例が思いつかないので、思いついたら追記します。。。

何で、近傍がシンプルである必要があるかといえば、イテレーションを増やすためです。
焼きなましは、イテレーション=正義みたいなところがあり、複雑な近傍は計算が重くてイテレーションが減るため大抵うまくいかない印象です。

イテレーションは特に重要なので、実装をする前に処理が軽そうか考えると良いと思います。

解空間がそこまで大きくない

焼きなましは局所解に入ってからが本領発揮みたいなところがあるので、解空間が大きくて局所解にもなかなかならないような問題には向きません。

japljさんの画像がわかりやすいので使わせてもらうと、画像の横軸の1000~2000でイテレーションが終わってしまうような問題の場合は、劣化山登りになる場合があるので注意しましょう。

過去にTopCoderで出題されたMM 94で解空間について話題になりました。
この問題は焼きなましできるけど、ビームサーチが正解という問題でした。

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16958&pm=14678
MM 94 - Togetter


山登り系

山登り(Greedy)とビームサーチ等を、自分は特に区別してなく、同じ特性があると思います。

状態が進行していくような問題

焼きなましの「初期状態がそのまま解になる」と同じ内容ですが、ターンで進行するゲームの問題はほぼビームサーチです。
対戦ゲームのような複数プレイヤーがいる問題は、ゲーム木探索を勉強しましょう。

文脈とは

文脈要素が強い問題は焼きなましより、山登り系の方が良い可能性があります。
文脈とは、自分的理解だとこれまでの決定したきたものが評価する対象になること(自分でも微妙な表現)で、「Aが~こうなっているならば、Bにすると効率が良い」という感じです。
焼きなましはイテレーション内で完結し、それぞれが独立しているので文脈的な要素を受けるのが難しいです。

今回の問題でいえば、辺が極めて少ないテストケースは文脈要素が強そうでした。
極端な例ですが、頂点が2つで、辺が1つの問題の場合

焼きなましの場合
f:id:hoshi524:20171201032655p:plain
赤を緑に隣接させたい場合、かつランダムな頂点をswapするのが近傍だった時、赤がランダムで緑の隣に移動するのは無駄がありそう(全セル/2くらい遷移しないとダメそう)ですが、山登りの場合は赤か緑を置いた後、隣に残りを置くだけです。
ちょっとまった!これはランダムに頂点をswapするのが近傍だった場合の話で、上位の人がやっていたように辺に注目した近傍の場合は、辺が1つしかないので山登りと同様に効率が良いです。
なので今回の問題は、近傍をうまく設定すれば文脈の問題は回避できました。

上に例に出したMM 94は文脈要素も強く、今回の問題のように回避するのができなかったのもMM 94でビームサーチが正解だった要因だと思います。

山登りの欠点

山登りには明確な欠点というか、損をする箇所があります。

f:id:hoshi524:20171201035856p:plain

この中央の頂点を決める時に、評価の対象になるセルは赤、緑、青の3セルのみで、?のセルについては評価できません。
焼きなましは一応全ての周りのセルが評価できるので、その分だけ山登りは最適解がでにくいと考えられます。

今回は焼きなまし

考えてみると今回は焼きなましに都合が良い問題設定でした。
焼きなましの要件は満たしてます。問題の解空間の大きさについては、事前に、実装する前に把握するのは難しいです。
やってみると、そこまで解空間は大きくなくなかなか良いところまで焼き鈍せている印象でした。

焼きなましは要件が多く、適用できないこともあるので適用できそうな問題だったらとりやえずやってみると良いかもしれません。
上にも述べたように、適用できる=焼きなましが正解という訳でもないので、その辺は経験を積んで理解していくところかと思います。

焼きなましの詳細については

焼きなまし法のコツ Ver. 1.2 - じじいのプログラミング
焼きなまし法の真実 – システム工房コルン

焼きなましを主体に扱ったブログあるので、それを参照するのが良いかと思います。

あとがき

自分はそこそこマラソン強いつもりですが、中身は感覚的に理解してるものが多くふんわりしてます。
強い人ほど理論づけがしっかりしてると思いますが、そこそこレベルであればふんわりいけます。

それを超えて、1位になりたいとか、世界クラスと戦おうとする時、根気とか、泥臭さとかが重要になってくるので、そこまで戦うかはその人次第じゃないでしょうか。

Shadow of War

Middle-earth™: Shadow of War™ on Steam


面白かったのでブログに残しておこう。
攻略に関してネタバレを入れるので、嫌な方は見ないでください。

評価

序盤はプレイヤーがオークを倒すが、後半になるにつれて支配したオークで敵オークを倒すゲームになってくる。特に防衛戦。
アクションよりシミュレーション要素の強いところが、個人的嗜好と合っていたかもしれない。

レベル上げ

4章の序盤あたりで、レベル上げに困ったのだけど4章のメインクエストを進めていくと自然と最大levelになるように設計されてるので、レベル足りないと思っても進めた方が速い。

4章

4章を冗長と評価する人がいるみたいだけど、慣れると大したことない。

基本的には、防衛戦をすることになるが、防衛戦で負けた後に攻城戦で勝てば、次に進めるようなので、わざと防衛戦で負けて攻城戦で攻略する方法もあるかもしれない。
そのケースは1度しかやらなかったので、詳細は分かってないけど。

闘技場

防衛戦をやるにあたって、難易度がノーマルのプレイヤーと同等レベルのオークで固めれば簡単に勝てる設計になっていた。

レベルを上げる方法は、訓練命令は現実的ではないので、闘技場で勝って育てるか、恣意的に強いオークに負けてそれを支配する方法がある。
レベルが低いオークを参加させると頻繁に蘇生させる必要ができて面倒になるので、育てるか、見殺しにするか、参加させないか、する必要がある。

闘技場で負けた場合、闘技場に勝ち残ったオークがいるので、すぐに向かうとそのまま支配できる。
それに気づかないと、支配するのが大変になるので、4章が嫌になるか決まる気がする。

オークのダメージ低減

極めて効果が高いと思っていて、使うと4章が簡単になる。

f:id:hoshi524:20171024204541p:plain

ルーンに[味方のウルクが受けるダメージ-50%]があり、緑の宝石で[支持者に対するダメージ-x%]がある。
検証はしてないが、それぞれの効果が加算になってる気がしていて、-75%とかになっている可能性があり、
味方オークが死ぬことがほぼなくなり、敵オークに勝ちやすくなり、蘇生をする必要がないので安定する。

A地点

これもあまり検証できてないのだが、4つ防衛する拠点を占拠される毎に、敵オークが追加される仕様っぽいので、1つも拠点を占拠されないのが理想であり、
最も占拠されやすいのが手前にあるA地点なので、そこにはオークを3体設置するのが良いかもしれない。

f:id:hoshi524:20171024205441p:plain

赤枠のどちらかがA地点に対応するはず・・・。

裏切り

裏切りは、乱数的なものより内部パラメータが重要そうなので、気をつければまず起きない気がしている。

オークの好感度を上げそうな行動は
・闘技場で勝利する

下げそうな行動は
・プレイヤーが死ぬ?
・味方オークを殺す
・他の拠点で時間を消費する

あたりな気がしている。

エンドコンテンツ

エンドコンテンツが実質的になく、4章を終えてしまうとモチベーションが無くなってしまった。
今後、DLCで追加されていくとは思うが。

防衛戦に関しては、4章のメインクエストしかなく4章を終えてしまうとやるところがなくなってしまう。

装備収集

プレイヤーのlevelとオークのlevelの平均値?の装備を落とすので、最大値がプレイヤーのlevel以上になる。
62levelまでは確認している。これらの収集はエンドコンテンツではあるが、使う場所が特に無い。

オンラインコンクエス

唯一あるエンドコンテンツだが、リターンが特に魅力を感じないのと、味方オークが不用意に死ぬのがつらい。
敵オークを支配しても残らないし、殺しても装備はドロップしない。

また、攻城された履歴も残るようだけど、1度しかされてない。
あまり活発でないのかもしれない。

オークの選別

エピック特性でも強弱があって、エピック・レジェンドが必ず強い訳じゃない。
プレイヤーを対象にするか、オークを対象にするかでも変わって

プレイヤーを対象にするなら
・遠隔無効
・無慈悲(アサシンしかもってないが)

オークを対象にするなら
・激昂しやすい

あたりが重要になりそう。
バーサーカーは闘技場で強いので、手元に残りやすいが暴走があると味方を攻撃して面倒なので使いにくい。

RCO presents 日本橋ハーフマラソン 本戦

rco-contest-2017-final.contest.atcoder.jp

参加記を書こう

本戦結果

総合3位で、望外の結果だった。
予選の結果から考えて、平均、40名くらいいたので20位前後になれれば充分だと思っていたので意外だった。
社会人だから貰えなかったけど、賞金に絡める順位になるとは・・・。

予選との感触

個人のパフォーマンスでいえば、予選とあまり変わらずだった印象で、順位だけ上がったので周りが奮わなかったのかな、という印象。

誤読・勘違い

他の方の参加記や自分の感想から考えても、誤読や勘違いが与える影響が大きい。

自分の例でいうと予選のA問題

A: Multiple Pieces - RCO presents 日本橋ハーフマラソン 予選 | AtCoder

ポリオミノが理解できずに、一筆書きみたいな制約があると誤読したまま終えてしまった。
誤読が無かったとしても、大きくスコアが向上することは無さそうだったので、大した問題じゃないけど。

あと本番の

A: 石油王Xの憂鬱 - RCO presents 日本橋ハーフマラソン 本戦 | AtCoder

だとsell後に、タンクが交換されることを忘れて10分前後の時間を消費してしまったのは無駄だった。

そういった意味で、問題理解を焦らないのが重要かな、と思った。

A問題

問題設計の点で気になるところがあった。

move コマンドを利用するのが難しく

Beaker | Aizu Online Judge

みたいな感じで利用するのかと想起したけど、実装するのが大変だし(個人的な技量の影響が大きいけど)、実装できてもプラスに働くか明白ではなかった。
このコマンドは必要だったのか疑問。

実装は単純なことしかできなかった。

Testerがjavaで書かれていたので、javaを使ってると複数ケースで修正点の計測を簡単にできるので、パラメータ調整とかは有利に働いた。
かといって、パラメータの細かい調整より自明に良くなる修正を繰り返すのが大事なので、少し有利になる程度の印象。

Submission #1174095 - RCO presents 日本橋ハーフマラソン 本戦 | AtCoder

B問題

B問題の印象は、1位の人のスコアが飛び抜けていて、その時の自分の順位は良かったけど、伸び代が大きいことが分かって、後で抜かれるだろうと予想してたのだけど、最後まで周りの人のスコアが伸びてこなかったのが意外だった。
市松模様等の実装が大変な方針を取った人がコケてしまったのかな、という印象。

あと、問題設定が簡単すぎて題意を掴めなかったところ(問題名ちゃんとみろ)、マップサイズに対して車が多いことに気づいて、なるほどと思った。
瞬間的に想起した車の量はもっと多くて、全然動けない問題なのかなと思ったけど、思ったほどではなかった。

実装については
目的地から遠い車を優先させて移動させると少しスコア上がったのと
ビジュアライザをみると中央に固まってるのが明白だったので、中央に斥力をもたせると移動が速くなった。
あとは、偏りありのランダム移動を終わり際は目的地でちゃんと止まるようにすると、スコアが何倍かになった。

Submission #1174208 - RCO presents 日本橋ハーフマラソン 本戦 | AtCoder

2問合わせて

強い人と比較すると、実装がとにかく遅いと感じた。
それぞれの問題のベースになるコードを作成するのに、50分前後かかっていて、2問のベースを作り終えると2時間近く消費していて、そこが強い人と比較して大きく違うように感じた。

1戦2問の是非?

マラソン系の問題を2問だしてどうやって時間配分をするか、面白い部分ではあるけど難しくしている部分でもあり、そこまで難しくする必要があるのかと思った。
一長一短で、1問にするべきだとは思わないけど、このコンテストの特徴的な部分だと感じる。

懇親会

uwiさんと話して過ごした。
あとは、nico_shindanninさんを初めて拝見したり、hirose_golfさんと少しお話したりした。
あとCODE VS勢が何人かいた(話してない)。

感想

予選の順位があまり良くなかったので本線に出場できたこと自体に驚いた。
あまりないコンテスト形式で、楽しかったのでまた開催されると良いなぁ、と思います。

過去のブログ記事

過去の記事を読み返してると、こいつは何を言ってるんだ?という気分になってやばいことに気づいた。
正直、消し去ってしまいたいが、未熟なころを振り返れるようにしておいた方が良いと思うので、残しておいた方が良いだろう。
(今現在が未熟ではないという意味ではない)

ストリートファイター5

f:id:hoshi524:20160307011621p:plain

なんとか2000LPになれた。
スト4シリーズと比較して設計思想は断然良い。

具体的には、初心者目線でスト4シリーズは無敵技の反撃が難しいとか明らかに頭悪い感じだったけど、そういったのが緩和されて無敵技は発生後も非カウンター判定になった。
ガードした時のリターンが昇竜系(無敵技)に対して大体2.5倍以上はあるので、暴れる側のリスクが上がった。
スクリューの発生が遅くなるとか、初心者が格ゲーらしいゲームを楽しむ段階の前に起こる不快な要素が軽減されてる。

キャラクターのモーションだけはスト4シリーズの方が好みだった。
今作は海外のクリエイターが主導なのではないかと個人的に思ってるのだけど、どうなんだろう。

Vetruvian

f:id:hoshi524:20160212104146p:plain
が強すぎるらしいので、vetを使ってる。(そのうちnerfされるだろう)
強すぎカードはmustで入れるから良いのだけど、vetのカードで強いのか判断に迷うカードが結構あってどうしたものかと思う。

f:id:hoshi524:20160212104537p:plain
はjaxiが居なければ最強候補なのだけど、jaxiが2コス汎用性最強なので、その環境下でも入れた方が良いのか迷う。

f:id:hoshi524:20160212104858p:plain
これも同様にjaxiと相性が悪いけど(これ問わずjaxiとArtifactsがそもそも相性が良い)、よくある
f:id:hoshi524:20160212105034p:plain
を相手が使った場合、Hexbladeで除去して相手は4点回復、自分は1点ダメージで耐久値が2残る。
この状況がアドを取れたというほどじゃないけど、悪くない。
小さいミニオンが多い場合は微妙だけど、大きいミニオンの処理が楽になるので、結構強いのではという気がする。
4コスで3点ダメージなのでリーサルにも微妙に使える。

追記:無事弱体化され、Vetruvianは死んだ気がする
Scions_Third_Wishを弱体するのは良しとしても、全体としてVetが弱すぎる気がするけど、現状の話でその内変わるのかもしれない。