# 高専プロコン競技パンフ

## 1. はじめに
今回の競技部門ではアルゴリズム同士の対決が行われるが、これは非常に難しい問題であると私達は考えている。非常に僅かな差や見落としが勝敗を分ける可能性があるため、様々な戦略を比較検討し最善の道を模索することにする。
## 2. アルゴリズム
今回のルールではすべての職人の位置と各マスまでの距離が戦略を立てる上で必要になるが、壁の設置により、毎ターン各グリッドにたどり着くのに必要な距離が変動する。そのため、ターンのはじめに各職人のマスから幅優先探索を走らせることによって距離を再計算する。計算量は大きくなるが、マスの数も職人の数もそこまで大きくないうえ、少し工夫を加えて高速化することによって、問題なく幅優先を走らせるようにする。

また、壁の建設中に相手チームから妨害を受ける可能性がある。そこで相手チーム移動の履歴や、実際に用いるものより更に高速なアルゴリズムを相手チームの職人に適用することによって、相手チームの行動を予測し危機を回避する。

そしてこれらの計算に加えて様々な手法によるアルゴリズムを作製し、比較検討することでより良い戦略を構築する。

## 3. UI
matplotlibを用いて競技ボードの詳細を表示する。多様な戦略に柔軟に対応できるようにリアルタイム表示を行い、緊急時は人の手によって指示を下す。

## 4. 開発環境

OS:Windows,ArchLinux

使用言語:C++,Python

使用ライブラリ:matplotlib

## メモ
・障害物によって毎回距離が変化するため、幅探索によって再計測する

    〇ただし、毎ターンこの処理が入ることが予想されるため最大限の高速化を行う(メモ化等だが表記はしない)

・相手チームによる妨害を考慮したシステムを構築する

    〇妨害をうまくいなす、妨害を逆手に取る

（1,2ターン前の相手チームの行動から相手の各職人の移動の方向ベクトルを割り出し、妨害されそうか否かの予想を立てる）

・相手チームの職人と並走して壁を建てることで妨害や妨害の対策を行いやすくする

・様々な手法によるアルゴリズムを作成し、比較検討することでより良い戦略を構築する

(・人工知能によるシミュレートも実施予定(するとは言ってない))

(・そのマスに移動することによって得られる得点の期待値の計算)