マラソンマッチ談義

コルン @colun

@chokudai ちなみに、ソートコストは多少かかっているもののそんなに大きくなく、ハッシュ生成コストに関して言えばxor１回分余計にかかったぐらいです。（破壊した鏡のハッシュ ＝ 前局面のハッシュ xor 今回局面のハッシュ）

コルン @colun

@chokudai なお、ソートに関しても、ビーム幅4096ぐらい（実際は時間制限で2500〜600ぐらいしか回ることができない）に対してのソートになるので、かなり小さめの計算コストです。ハッシュ２でソート→ハッシュ２が同じものは隣接するので重複除去→ハッシュ１でソート→…

コルン @colun

類似ハッシュを複数使っての重複除去ビームサーチでは解決できなくて、chokudaiさんのビームサーチ亜種だと解決できるパターンについては後ほど考察してみよう。。。（ツイッターにポストするとは限らないですが。

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

@colun おー、マジですか。同ターンで同じ手が打て局面が複数存在する場合はその手のうち上位いくつかしか採用しない、みたいな感じですか？　それはなんかビームサーチならではな感じがしていいですねー。

コルン @colun

@chokudai そうか、ソートしてるから完全な重複除去じゃなくて、上位3つまでとかの制御もできるんですね。気付きませんでした、ご指摘ありがとうございます。

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

@colunさんの実装凄く良いな。ビームサーチの利点を凄く生かしてる感じがする。順番に処理することで、出来ること出来ないこと生まれると思うんだけど、ビームサーチを選択するならそういうアドバンテージを生かしたいなぁ。

コルン @colun

（とりあえず、再びマラソンマッチにおけるノーフリーランチ定理の否定を行なう立場に戻ってしまった。

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

@colun 類似局面の影響が大きいほど、その判定は容易になることが多そうなので、ある程度は正しいと思いますー。ただ、類似局面と判定するのが難しいorコストがかかってしまうケースってそのうち出てきそうで、完全否定はしたくないですねー。ある程度否定出来る、であれば同意です。

おたっくす @otaks21

コルンさんとちょくだいさんの会話が追いきれてないのですけど、このまま流してしまうにはおしいとても大事な会話がされている気がしています。個人的にあとでまとめてじっくり読み返す必要がありそうです。