MM165 | jiyucho

補足

各コードに対するスコアはseed = 49 の結果です。

目的

なるべく少ないコストで、全ての船のマスを攻撃することです。

規則的にマスを攻撃していく

r(=i, 0-index) + c(=j, 0-index) % 2で偶奇を決めることで全マスの1/2を規則的に撃てる

例えば、N = 4 とします。

(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)

ここで各マスについて r + c を計算します。

さらに偶数か奇数かだけを見ると、

※ E = Even (偶数), O = Odd (奇数) を表します

E O E O
O E O E
E O E O
O E O E

になります。

E が (r+c)%2 == 0、O が (r+c)%2 == 1 です。

偶数のマスを攻撃するならこうです。

※ X = 攻撃するマス, . = 攻撃しないマスを表します

X . X .
. X . X
X . X .
. X . X

奇数のマスを攻撃するならこうです。

. X . X
X . X .
. X . X
X . X .

この 2 種類が盤面をちょうど半分ずつ分けます。

この考えを利用して最初に (r+c)%2 == 0 のマスを左上から行優先で撃っていきます。 N * N のマスを一周してもまだ船が残っていれば次に (r+c)%2 == 1 のマスを同じく行優先で撃ちます。

もし船のマスを攻撃できたらそのマスに隣接するマスを続けて撃ちます。順番は固定で、

上, 下, 左, 右

の順にマスを探して撃ちます。

さらに、ヒットが 2 個以上たまって同じ行または同じ列に並んでいると判断できた場合、その直線方向の端を延長して撃ちます。例えば横に 2 マス HIT していれば、左端の左、だめなら右端の右を狙います。

スコア

Score = 329.0

規則的にマスを攻撃

ベイズ推定を使う

概要

P <= 0.48 では行・列カウントを先にスキャンし、残数制約を配置候補と射撃候補に反映
P > 0.48 では 3回の大矩形スキャンで 2x2 象限カウントを取り、高 P でも安く密度情報を使う
行・列制約に合わせて船のスコア行列を反復スケーリング
ベイズ推定 (観測結果で候補分布を更新していく) を採用

詳細

※ 閾値は 0.48 と決定しました(LLMを使って)

P <= 閾値の行・列カウントスキャン P がそこそこ安いと判断し、最初に各行・各列に船セルが何個あるかを調べます。

例: N=8, 船セル総数が 14 だとして、行カウントがこう分かったとします。

rowRemaining = [0, 3, 0, 2, 4, 2, 3, 0] colRemaining = [1, 0, 2, 4, 3, 0, 2, 2]

この時点で、

row 0, 2, 7 はもう撃つ必要なし
col 1, 5 も撃つ必要なし
(4, 4) は候補だが、(4, 5) は col 5 が 0 なので絶対に船ではない

となります。

P > 閾値の 2x2 象限スキャン P が高いと判断すると全行・全列をスキャンするコストが重すぎます。そこで盤面を 2x2 に分けて、3回だけ大きな矩形をスキャンします。

例: N=20 なら、

左上 10x10 | 右上 10x10 左下 10x10 | 右下 10x10

3回スキャンします。

top = 上半分全体の船セル数 left = 左半分全体の船セル数 topLeft = 左上の船セル数

すると残りは計算できます。

左上 = topLeft 右上 = top - topLeft 左下 = left - topLeft 右下 = totalCells - 左上 - 右上 - 左下

たとえば船セル総数 70、top=20, left=45, topLeft=15 なら、

左上 15, 右上 5 左下 30, 右下 20

右上が薄い、左下が濃い、という情報が分かります。以後は右上のスコアを下げ、左下のスコアを上げる方向になります。

行・列制約に合わせたスコア行列の反復スケーリング元々の solver は、配置候補から各セルの「船っぽさ」を計算しています。たとえばこういうスコア表があるとします。

row 0: 0.2 0.3 0.1 row 1: 0.4 0.5 0.2 row 2: 0.1 0.2 0.3

でも行スキャンで、

rowRemaining = [0, 2, 1]

と分かっているなら、row 0 の合計は本来 0 でないといけません。そこでスコア表を何度も補正します。

手順はざっくりこうです。

各行のスコア合計を、その行の残船セル数に合わせる
各列のスコア合計を、その列の残船セル数に合わせる
これを 20 回繰り返す

例:

row 1 の現在スコア合計 = 1.1 rowRemaining[1] = 2

なら row 1 の各スコアを 2 / 1.1 倍します。

上記の例で2 / 1.1 倍する理由

これは「各セルのスコアを、期待される船セル数として扱っている」から
です。

たとえば row 1 に未探索セルが3つあり、今の推定スコアがこうだとしま
す。

row 1: [0.2, 0.5, 0.4]
合計: 1.1

この 0.2, 0.5, 0.4 はざっくり「それぞれのセルが船である期待値」で
す。合計 1.1 は「row 1 には船セルが期待値として 1.1 個ありそう」と
いう意味になります。

でもスキャンで、

rowRemaining[1] = 2

と分かっているなら、row 1 には未射撃の船セルが 必ず2個 あります。
つまり、この行の期待値合計は 1.1 ではなく 2.0 になってほしい。

そこで、行内の相対的な強さは保ったまま、合計だけを2に合わせます。

倍率 = 2 / 1.1 = 1.818...

元: [0.2, 0.5, 0.4]

それぞれの値を 2 / 1.1 倍する
例えば0.2を 2 / 1.1 倍すると
0.2 * 2 / 1.1 = 0.363636... ≒ 0.36
↓
新: [0.36, 0.91, 0.73]
合計: 2.0

重要なのは、順位や比率は保っていることです。

0.5 が一番怪しい
0.4 が次
0.2 が低い

という情報は残しつつ、「この行には合計2個ある」というスキャン結果
に合わせています。

次に列側も同じことをします。行を合わせると列が少しズレ、列を合わせると行が少しズレるので、反復で近づけます。

ズレを繰り返す具体例


ここでは 2x2 盤面で、目標をこうします。

rowRemaining = [1, 1]
colRemaining = [1, 1]

つまり、

row0 には船セルが 1 個
row1 には船セルが 1 個
col0 には船セルが 1 個
col1 には船セルが 1 個

という整数の観測結果です。

初期スコアは同じくこれにします。

      col0   col1
row0    0.4    0.2    row合計 0.6
row1    0.3    0.1    row合計 0.4

col合計 0.7    0.3

1回目: 行を合わせる

row0 は合計 0.6 を 1 にしたいので 1 / 0.6 倍。
row1 は合計 0.4 を 1 にしたいので 1 / 0.4 倍。

      col0    col1
row0    0.667   0.333   row合計 1.000
row1    0.750   0.250   row合計 1.000

col合計 1.417   0.583

行は合いましたが、列は目標 [1, 1] からズレています。

1回目: 列を合わせる

col0 は合計 1.417 を 1 にしたいので 1 / 1.417 倍。
col1 は合計 0.583 を 1 にしたいので 1 / 0.583 倍。

      col0    col1
row0    0.471   0.571   row合計 1.042
row1    0.529   0.429   row合計 0.958

col合計 1.000   1.000

列は合いましたが、今度は行が少しズレました。

2回目: 行を合わせる

row0 は 1 / 1.042 倍。
row1 は 1 / 0.958 倍。

      col0    col1
row0    0.452   0.548   row合計 1.000
row1    0.552   0.448   row合計 1.000

col合計 1.004   0.996

行は合いました。列のズレはかなり小さくなりました。

2回目: 列を合わせる

      col0    col1
row0    0.450   0.550   row合計 1.000
row1    0.550   0.450   row合計 1.000

col合計 1.000   1.000

ほぼ両方合っています。

最終的にはだいたいこういう値に収束します。

      col0      col1
row0    0.44949   0.55051
row1    0.55051   0.44949

row合計 1.00000  1.00000
col合計 1.00000  1.00000

ここで重要なのは、rowRemaining / colRemaining は整数ですがscore は小数のままという点です。

rowRemaining[0] = 1

は「row0 に未発見の船セルが 1 個ある」という確定情報です。

一方で、

score[row0][col0] = 0.44949
score[row0][col1] = 0.55051

は「row0 の 1 個の船セルが、col0 より col1 にありそう」という期待値・重みです。

小数スコアの合計が、行・列ごとの整数の残船セル数に合うようにするについての補足

rowRemaining = [1, 1]

なので、

row0 に 1 個
row1 に 1 個
合計 2 個

です。

同時に、

colRemaining = [1, 1]

なので、

col0 に 1 個
col1 に 1 個
合計 2 個

です。

ここで行側の合計 2 と列側の合計 2 は別々の船セル数を足して４個になるという意味ではありません。
同じ 2 個の船セルを、行方向から数えると 2 個、列方向から数えると 2 個、というだけです。

たとえば船セルが対角にある場合：

X .
. X

行で数えると：

row0 = 1
row1 = 1
合計 2

列で数えても：

col0 = 1
col1 = 1
合計 2

船セルは 4 個ではなく 2 個です。

スコア行列でも同じです。

      col0      col1
row0    0.44949   0.55051
row1    0.55051   0.44949

行合計は：

row0 = 0.44949 + 0.55051 = 1
row1 = 0.55051 + 0.44949 = 1

列合計も：

col0 = 0.44949 + 0.55051 = 1
col1 = 0.55051 + 0.44949 = 1

そして盤面全体の合計は：

0.44949 + 0.55051 + 0.55051 + 0.44949 = 2

です。

つまり、

行ごとの制約の合計 = 2
列ごとの制約の合計 = 2
盤面全体の船セル期待値 = 2

で、全部一致しています。

N = 20回ズレの修正を繰り返す理由

この処理の計算量はだいたい 20 * N * N であり、N <= 20 なら最大でも 20 * 400 = 8000 セル程度の補正でかなり軽いからです。

ベイズ推定の候補分布更新

ベイズ推定の式

事後確率
= 尤度 * 事前確率 / 周辺尤度

をこの問題に合わせると

(あるセル、またはある船配置が正しい確からしさ)
= (観測結果とどれだけ整合するか)
* (もともとその配置があり得そうだった度合い)
/ (観測結果全体が起きる確率での正規化)

として求めていきます。

最初は「このセルが船である確率」を、置ける船配置候補から作ります。

例:

長さ4の船がこのセルを通る候補が多い
まだ長さ4の船が残っている
その配置が MISS/KILL と矛盾しない

なら、そのセルのスコアは高くなります。

そこに観測結果を追加します。

観測A: row 3 には船セルがあと 0 個観測B: col 5 には船セルがあと 2 個観測C: 右上象限には船セルがあと 5 個

この観測に反する配置やセルは消す、または重みを下げます。観測と合う配置・セルの重みは相対的に上がります。

つまり、

事前分布: 船の配置候補から見た確率観測: SCAN / HIT / MISS / KILL 事後分布: 観測に合うよう更新した確率

という流れです。

スコア

Score = 251.50469067294793

ベイズ推定を使う