# CodinGame Spring Challenge 2021

これは競技中の私用のメモであって参加記ではないです。なのでここに書いてあることは試して採用しなかったこと、そもそも試さなかったことなどが大量に書いてあります。私の最終的な手法は18ターンまで貪欲 + 18ターン目からDUCTになりました。(303位)

* 前半ビーム + 後半DUCT
* とりあえずDUCTを実装する
* DUCTの最初の部分の対称な操作を取り除くとかなり読めそう
* 状態をまとめる？
* とにかく回数回ってなさすぎ！なんとかしてくれ

## 囲碁とか打てる手多いだろどうやってんの？
* Progressive Widening(これよくわからん)
* 囲碁の知識を用い、良さそうな手から順に候補手をソート
* それを徐々に探索木に加えていく
* 要するに前向き枝刈り
* All Moves As First (AMAF) (これもよくわからん)
* プレイアウト中に打たれた初手のみを用いるのが通常の考え方だが、AMAFでは、全ての手を初手に打ったとみなす
* Rapid Action Value Estimation (RAVE) とも呼ぶ
* 手順を無視して近似する
* 勝ったプレイアウトで打たれた手は全部良い手
* ゲームの特性を活かし、手を絞る←これが良さそう
* ありがちな一本道を高い確率で通るのが良い(プレイアウト)
* プレイアウトを打ち切って盤面を評価する←これも本命
* R. J. Lorentz, “Amazons Discover Monte-Carlo”, Computers and Games (CG2008), pp.13-24, 2008.
* J. Kloetzer, H. Iida, and B. Bouzy, “The Monte-Carlo Approach in Amazons”, In Proc. Computer Games Workshop, 2008.
* ノードの合流は大変さに比べてあまり有効ではないっぽい
* プレイアウトは完全なランダムじゃなくてある程度強い手を指したほうが良いっぽい(ビーム撃つか？w)(いや撃てないでしょ)
* UCBをオレオレ関数で置き換える(強いらしい)
* Simulation Balancing(プレイアウトを木探索と組み合わせる)
* Mix UCTってなに？

参考:
http://cedec.cesa.or.jp/2009/ssn_archive/pdf/sep2nd/PG90_yoshizoe.pdf
https://ibisml.org/archive/ibis2014/ibis2014yoshizoe.pdf

囲碁、なんで1秒間に1万プレイアウトもできるの？平均手数200以上やぞ

本質的にはノードの展開が遅くてプレイアウトあまり関係ない？ なんとかしてくれ 質の良いプレイアウトの方が良さそう
そんなことなくて，プレイアウトは全体の60%を占めている
vectorのallocateが遅いので先に確保したほうが良さそう
サイズ3の木から動かす

## 結局何する
* プレイアウトでSEEDの確率を下げる(SEEDの割合が高すぎる)
* うまくいく1ターン貪欲を使ってその評価値をプレイアウトのリターンに使う
* 20ターン目からSEEDを消す
* Progressive Widening
* LorentzのAIは40回訪問でノード展開
* 1000回で5手追加
* これスコア差分計算できるな
* 伐採の価値を常に高めても良さそう
* これやった時に価値の高いの選ぶと収束してないことがあるね
* 多様性があるとよくて，各行動の1番上を最初に入れると良さそう
* AMAF
* 囲碁と違って日を跨ぐと同じ手でも違う意味を持つが...？
* え，waitはずらすと明確に意味がちがく内科
* プレイアウトで評価のいいやつの確率高くしようとしたけど，めんどくさすぎ！
* Cを小さくしたほうが良さそう
* もうプレイアウトしないっていうのどう？笑(始めから評価関数を返す)
* 評価関数の値を返すよりどちらが優勢かを返すほうがいいらしい ほんまか？

## 評価関数
* g(i) = 6日間のサンパワー収入 * 残りの日数 / 3 + スコア (プレイヤーiについて)
* f(x) = g(0) / (g(0) + g(1))
* 重すぎか？
* これだとseedの評価が0
* 評価する木の個数に制限を賭ける
* 相手が刈った時の評価も入れると自然か？
* WAITした後の評価をする(WAITが不当に高くなるの防止！w)←これ強い
* 優勢劣勢の判断が出来ててることと手の強さの評価をするのは違う？
* 盤面評価の時はsun_bonusを下げたほうが良いかも知れない

### 差分計算

g(i)の差分計算
g[i] = (game.sun[i] + mean_sun[i] * rem_day) / 3 * sun_bonus * rem_day + game.score[i]
これrem_day^2がかかってるのおかしくないか？なんの値だっけ(とりあえずこのまま)
伐採できない木の評価はしない

#### WAIT
#### SEED

diff = 0
for (dir)
    for (d)
        check()
    if (!is_shadow)
        diff += weight[0]
diff /= 6

return rem_day^2 * bonus * diff / 3

#### GROW
これよく考えたら相手のスコアにも影響を及ぼすな めんどくさすぎ！
やる

diff = 0
for (dir)
    for (d)
        check()
        if (dtree.size == 3 or dtree.size < 3 and d == 3)
            for (int d2 = 1; d2 <= 3)
                flag |= cells[dtree.idx][(dir + 3) % 6][d2].tree.size >= dtree.size and d2 <= d2tree.size
            if (flag)
                diff -= weight[dtree.size]
    if (prev_shadow and !is_shadow)
        diff -= weight[from]
        diff += weight[to]
diff /= 6

return rem_day^2 * bonus * diff / 3

#### COMPLETE
よく考えたら木の分のweightも差し引かなきゃ！めんどくさすぎ！

diff = 0
for (dir)
    for (d)
        for (int d2 = 1; d2 <= 3)
            flag |= cells[dtree.idx][(dir + 3) % 6][d2].tree.size >= dtree.size and d2 <= d2tree.size
        if (!flag)
            diff += weight[dtree.size]

diff /= 6

sun_diff = diff_sun_point / 3 * sun_bonus * rem_day

return rem_day^2 * bonus * diff / 3

### 検証
* alpha = 0 vs 0.4(choose 0) → 0.4(choose 0)の方が良い(600戦)
* alpha = 0.4 (choose alpha) vs 0.4 (choose 0)
* win1: 0.42844825(1160 plays)
* 同じ日だけのAMAF vs 0.4(choose 0)
* win1: 0.500947(5280 plays)
* c = 2 : 1
* win 1 0.493889(1800 plays)
* バグ修正 vs バグ未修正
* win1 0.52115375(520 plays)

### 検証2
* c = 0.7 vs 0.9 (day < 18)
* win1: 0.48104825(2400 plays)
* c = 0.7 vs 1.1 (day < 18)
* win1: 0.4873625(3700 plays)
### 未検証

* 評価関数じゃなくて1-0で返す
* LorentzのCは0.35らしいよ
* これ実はかなり調整が重要らしい
* やる
* Lorentzのプレイアウトは6手先までのランダムらしい
* 知識あり探索 vs なし探索
* 知識ありプレイアウト vs なしプレイアウト
* 終盤のみDUCT

### 高速化
* treeにプレイヤー情報をもたせる
* 近傍をbitで表す
* プレイヤーが持ってるTREEをSETの代わりにBITで持つ