MM 99

chokudai(高橋 直大)@AtCoder社長 @chokudai

いずれにせよ、これが有効な条件は、「1ターン差分が小さい」「戻る側の差分計算もらくちん」「盤面の全構成は大変」って感じなので、そこまで有用な範囲が広いわけではない。（こういうパターンは無限にあるので、「ビームサーチそのまま」とか「焼きなましそのまま」とか思考停止すると弱いのです）

コルン @colun

@chokudai 木を戻ることしかしないため、各頂点から見て戻り先の頂点（および使用する辺）は常に一つしか存在しないため、「１ターン差分が小さい」なら「戻る側の差分計算も常に小さい」のじゃないかな、とは思います。

コルン @colun

@chokudai むしろアダムが近い方が高速化につながるので、多様性が失われている方が爆速になる様な気がしています。

コルン @colun

@chokudai あ、具体的なことを何も書いてなかったですが、要するにUNDOリストを使えば常に行きがけのコストと戻りのコストは同程度になり、これはスタックに積めば問題なく管理できます。

chokudai(高橋 直大)@AtCoder社長 @chokudai

@colun たしかにそうですねー。（使ってみた経験的に、「逆向きの計算はできないから、後ろに戻りたいなら変更差分を持たないと行けない」って場合だと、ステップ進めるコストが2倍近くになって有効になりづらい、って経験が結構あるので書いちゃいました）

chokudai(高橋 直大)@AtCoder社長 @chokudai

@colun これもとても微妙な話で、「爆速になる」はその通りなんですけど、それが良いとも限らない・・・みたいなところもある話です＞＜　（大局的に見て10箇所くらい、みたいになってるとかなり理想的なイメージがありますｗ）

chokudai(高橋 直大)@AtCoder社長 @chokudai

@WA_TLE そこは確かにそのとおりで、むしろ「差分で計算可能な評価にする」は、半分以上のマラソンにおいて有効な戦術だと思ってます。

chokudai(高橋 直大)@AtCoder社長 @chokudai

とてもよく言われる （今回自分の言ってることは、図とかを出すとまだまともに説明出来る気はする。colunさんの方は、colunさん用語を常日頃から追いかけてないととてもつらいけど、追いかけてれば今回のはそこまで難しくないかも。） twitter.com/not_522/status…

not @not_522

ちょくだいさんとcolunさんの議論、ただのポエムにしか見えないのに世界最高レベルのマラソンマッチの考察なので困る

2018-04-18 19:51:19

chokudai(高橋 直大)@AtCoder社長 @chokudai

DFSにしてどうにかする、は、無茶苦茶上手いこと制御しきらないと難しいと思うのだけど、自分の奴はそこまで制御むずかしくないと思ってるから、12時間マラソンでも、調整含めて制御可能なラインかなぁ、と思ってる。（難しいのは使用するノード数予測で、それミスるとバッサリ切れちゃう）

hakomo @hakomof

先読みによって評価値の瞬間的なV字遷移への耐性を上げつつ、速度もペイする（というかお釣りがくる）みたいな感じですか？もはや魔法では 1週間前におわったyandex opt 2にこれが適用できてスコア爆あがりする気がする（めっちゃタイムリー）（もっと早く教えて欲しかった）

hakomo @hakomof

差分更新の回数が最小になるようにソートするあたりにMo's algorithmみを感じる

シャマル @shamal_ref

輪講の順番とmm100の期間が被ってて忙しい1週間になりそう

えりすしー @eris_c

焼きなまし法、うまくいってるようないってないようなでよく分からない。

えりすしー @eris_c

最終結果と同じ総距離でしか評価してないのがいまいちなのかもしれない。うーん。

Yuichi Sayama @xyz600600

忙しかったけど、明日から1週間はそこそこ安心して定時で帰れるようにしてきたつもり。頑張るぞ～

ツカサ し・×・U。@洗濯洗剤を買う @tsukasa_diary

起きたらMM100か～ がんばるぉ

ツカモ @tsukammo

「何？MMは一発イエローで、コドゲはレジェンドに入った！？そうかそうか、ほれ、これ今月のお小遣いやで。いつもより分厚い？かまへんかまへん、それで美味いもんたらふく食べや。」みたいなんになる。（謎の関西弁）

えりすしー @eris_c

seed=1が1428.63になった。何が分からないのかも分からない状態だけど、とりあえずこれで終わろう。 pic.twitter.com/85JZpEkDHG

拡大

せにもち@2時に寝る @ceni1055

今日からMMってマ？

ツカモ @tsukammo

@eris_c これ、状態遷移何でやってます？交差する線があるので、そこがネックになってる可能性大です。

庶務 @shomu_match

@tsukammo ところでわがままを言うと、お金だけ頂くよりは、一緒にご飯を楽しみたいです

ツカモ @tsukammo

@shomu_match （ホントこいつ可愛いな。）いつでも奢ったるで。（やはり謎の関西弁）

えりすしー @eris_c

@tsukammo ランダムで選んだ2つの線の接続を入れ替えて総距離が短くなったら採用みたいな感じです。繰り返したら解消されるかなと思ったらあまりされなくて。見様見真似の焼きなまし法が入ってます。

ツカモ @tsukammo

@eris_c 2-optですね。んー、だとすると交差点が出るのは解せないんですよねぇ…。（交差線が選ばれた時点で確実に交差が解消されるので）

~ @kosakkun

@tsukammo @eris_c ベストスコアの状態を出力していないとか ( 参加し始めの頃はこういうしょうもないミスが有りました... ).