# 高専プロコン

# 高専プロコン競技部門

APIの仕様をちゃんとは見ていないので、APIの仕様と合致しなかったらごめんなさい

評価関数がまともならそれだけで勝てるので、評価関数以外はそんなに気にしない

毎ターン、「理想のフィールドを求める」→「理想のフィールドを作る」という順で処理を行う
理想のフィールドを求めるのは、主に二つのアルゴリズム(焼きなましorサーチ)のスコアが高い方を採用する
理想のフィールドを作るのは、最短経路を求めて手堅く行う

毎ターンの理想のフィールドと移動経路探索結果は保持しておいて、メモ化等…
前回ターンの理想フィールドと今回ターンで求めた理想フィールドの差分が少ない場合や移動経路探索結果が似ている場合は、相手職人の影響度を考慮した上で前回と同じ経路を辿る(毎ターン経路探索を行った場合、同じところを行き来する可能性があるので、それをケアする)

## 理想のフィールドを求める

職人が目指すべき場所を**ターゲット**と呼ぶことにする
ターゲットには城壁の設置場所、相手職人の妨害場所等が含まれる

城壁の設置の場合のターゲットの場所は、理想のフィールド計算結果をそのまま参照する
城壁を壊す場合
相手職人の妨害の場合は後述する方法によってターゲットの場所を求める

### 焼きなまし法

形成したいフィールドの状況を焼きなましで求める

### ビームサーチ/chokudaiサーチ

理想を言えば、焼きなましの方がスコアが高くなることが多いが、現実的にはビームサーチの方が手堅いし、今回は並列実行に制限がないので、焼きなましと並列で実行して、スコアの高い方を採用する

chokudaiサーチが実装できそうならそっちの方が都合が良いかも

### ヘルパ関数

評価関数を求める過程で必要となる関数群

### 領地を求める

未分類のランダムな点から城壁まででBFSを行い探索する
BFSの各タイミングでのキューの要素数がその領域を領地にするのに必要な残りの城壁の数なので、各タイミングでのキューの要素数と、その時の領地のポイントをメモする
複数回探索を行うといずれフィールドの全ての領域が探索済みになる

### 各職人の移動量を求める

移動距離はA*で求める
移動スコアは移動経路探索に基づく

以降、移動スコアが正の意味(移動によって実質的にポイントを得る)と負の意味(移動によって実質的にポイントを失う)の両方の意味が混在する
アルゴリズム上でも正の意味と負の意味を持つスコアは分けて計算する
`移動スコア=正の意味*係数A+負の意味*係数B`なお、係数A,Bはデフォルト1で式によって適当に調整する

### 職人のスコアを求める

職人が城壁を設置した場合に取得するポイントや、失うポイント、職人が他陣営職人を邪魔する可能性などを職人のスコアと定義
自職人と相手職人ともに計算し、スコアの高い順に優先的に処理を行う
e.g.相手職人のスコアの方が高い場合は、自職人は妨害を試みる等(妨害の意思決定を行う際は評価関数とコンクリフトを起こさないようにする)

| 種類 | 概要 | 算出方法 |
| --- | --- | --- |
| 城壁を設置する | もし、相手が城壁を設置したらどうなるか | 城壁を設置した際に取られるポイントと失うポイントを計算 + 移動スコア |
| 領域を壊す | | 上と同じような感じ |
| 他陣営の職人を妨害する | この職人がある職人を妨害した際に妨害された陣営に生じる見込みスコアの損失量 | 全ての職人のほか全てのスコアを算出した後に算出を行う<br>from 他陣営職人 where この職人から妨害対象までの移動スコア < 妨害対象が正常に動作を行った時のスコア && 妨害対象が目的を達成するまでの間にこの職人が移動可能であること |

### 移動経路探索

ベルマンフォード法で移動する
フィールドに対して適切なスコアを付与する
探索テーブルは職人で共通して持つことで、職人同士でルートの取り合いになったり、譲り合いになったりするのを防ぐ→ある職人が決定したルートはスコアを下げることで他の職人が通りにくくなる
移動経路についても焼きなましで求めると相手職人の動きを想定して行動することができる→計算量に余裕があればやるべき

### スコア例

| 名称 | 値 | 備考 |
| --- | --- | --- |
| 平地 | 0 | あるいは微量の+ |
| 池 | —— | 通れない |
| 城 | ++++ | 高得点 |
| 自陣地 | + | 0.5 |
| 中立 | ++ | 1 |
| 相手陣地 | +++ | 2 |
| 自分の城壁 | - | |
| 相手城壁 | + | |

### 評価関数

評価関数は、あるターンの行動が終わったときの盤面のスコアを評価するもので、直前の状態に依存しない(当たり前)

評価関数は妄想なので、ビジュアライザーをつくって試してみる

値の動き方を見ながら数学関数を差し込む

> [!WARNING] 一般的に評価関数はビジュアライザーで試行錯誤することが多く、私もそうする予定だったので、評価関数の候補はあくまで未完成
>

この規模の評価モデルならDeep Learning使って評価したほうがスコア出る気がする…

- 単一の領域の評価 = α * CastlePoints + β * TerritoryPoints + γ * WallPoints + δ * DistanceValue + + ε * EnemyPositions + ζ * TeamPositions

ギリシャ文字はそれぞれの自由に設定可能な任意の係数を表す

EnemyPositions,TeamPositionsはそれぞれ最も近い職人の距離を表す

- 職人の環境評価 = sumAllField( 移動スコア ) + 職人スコア

sumAllFieldは全てのフィールドに対して、()内の評価を行う

移動スコアは距離に対して(-log+E)つけたり-expつけたりして、距離が0から離れたときに急に小さくなるようにした方がいい

- フィールドの評価 = sum(自陣の領域評価) -sum(相手の領域の評価)

相手の領域は壊せばポイントが失われることから、正の評価としたい気分

- 職人の位置による優位性 = (-log(自陣営移動系 - 相手陣営移動系)+e) * (自陣営ポイント系 - 相手陣営ポイント系)

ヘルパ関数の領地を求める関数を使用。全ての職人が近くの他陣営領地を破壊するとした時に、ポイントがどれだけ動くか

自陣営移動系 = -自陣営の職人が相手陣営を壊すのにかかる最小移動スコア + 壊された領域を相手職人が復旧するのにかかる最小移動スコア

自陣営ポイント系 = 領地を壊した時に相手が失うポイント

評価関数は上記の項目を任意の係数をかけた上で足し合わせたものとする

## 実装について

毎ターン、フィールドの状況を入力した後に、「数ターン先のフィールドを評価」→「評価値の高いフィールドを作るための行動」というふうに処理をする

### フィールドの評価

評価関数については上記のとおりで、評価対象は、次のターンにフィールドが取りうる状態

計算量に余力があるのならば、2つ次のターン、3つ次のターンに対しても評価を行う

(将棋ソフトとかだと数十手先まで評価を出す。基本的になるべく先の評価を出せるほうが有利)

相手の妨害の可能性を考えると、自→相の二回の行動フェーズ分ぐらいは評価を行うべき

### フィールドを作る

フィールドの評価で評価の高かったフィールドを作る

評価されたフィールドは現在のフィールドがnターン後に取りうる状態なので、そのような職人の行動は少なくとも一通りはもとまる

あとはその通りに動けば良い