Codingame_Amadeusチャレンジにっき
Codingame Amadeusチャレンジ
ルール
目的：ゲーム終了時に相手よりも多くの惑星をコントロールする。
ーーーーーーーーーーーーゲーム
このゲームは、惑星を頂点としたグラフ上で行われます。
両方のプレイヤーはできるだけ多くの惑星を支配しようとします。
プレイヤーが相手よりも惑星に多くのユニットを送っている場合、惑星はそのプレイヤーの色の星に変換され、
その支配下にあるとみなされます。
各プレイヤーは、グラフの反対側にあるそれぞれの支配下にある惑星にから出発します。
ーーーーーーーーーーーーユニット
毎ターン：
あなたは5人のユニットに命令をする必要があります
すでに少なくとも一人のユニットのいる惑星とあなたがコントロールしている惑星の隣にユニットを送れます
あなたは隣接の惑星の数に関係なく、任意の惑星にいる5人のユニットを選んで犠牲にし1人のユニットをその惑星の隣に生成することが出来ますユニットスプレッドと呼ばれます（良く分からん）
ーーーーーーーーーーーー
一つの惑星には各プレイヤー5回だけしかユニットを送る操作が出来ません.
許容値はユニットスプレッドの影響を受けません。
ーーーーーーーーーーーー
近隣の惑星に自分がコントロールしている惑星よりも相手がコントロールしている惑星のほうが多い場合
その惑星のユニットは一人失われます
ーーーーーーーーーーーー制約
16<= planetCount <=90
10<= edgeCount <=200
最初のターンの応答時間<= 1000ms
1ターンあたりの応答時間<=50ms
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
研究室の後輩がプログラムのコンテストに興味を持ったらしく
とりあえずCodingameを勧めた。
人にこういうの勧めるのあんまり良くないなと思っていて。
自分が他人に何か勧められても「はいはいそれでマウント取りたいだけでしょ。絶対やんねー」ぐらいにしか思わないので。
その後輩に今回のコンテストを教えた結果、「出ます！」とのこと。他人に勧めておいて自分が出ないのはゴミなのでとりあえず出る
~~~~1日目
とりあえずサンプルを動かしてみてゲームの性質を眺める。
こんな感じのボードになっていた。
なるほど
緑のノードを取られてしまうとそこから下は相手のものになってしまうのか。
重要なノードがあるんでそこを死守しなければならないって感じのゲームですか。
とりあえず惑星に重要度をつける。
重要度はその惑星を取り除いたときにどれだけ到達できる惑星の数が変化するか+alphaでつけた。（alphaが何だったのかもう覚えていない...）
ページランクアルゴリズムはどうだったんでしょうね。
これで重要な惑星は絶対死守するプログラムを書いたが、
盤面には次のような盤面も含まれていた。
重要なノードをとってる間にもっと大きな空間で優勢を取られるケース。
直線的になっていて重要なノードだと認識してしまうノードばかりになってしまうケース。
なるほど。
こういうのと前線を守ったりするのを適当なifelseで処理(どんな処理だったのかもう思い出せない..)したらsilverランクに上がれた。
とりあえず探索をしたいんですよね。したいんだけど愚直な探索では50msという制約ではTLEするだろう
できないところはあきらめながらでもなんとか50msで探索できる効率的な方法はないか？？？
そこで思いついたのが指し手GA Softmax
ーーーーーーーーーーーー
最初の指し手生成
貪欲手法を３つ用意する
自分の領土を出来る限り広げようとする
自分の領土を出来る限り守ろうとする
重要な惑星を出来る限り確保しようとする
これら３つの貪欲手法にしたがって複数の自分の指し手を作成しそれらの指し手を評価する
ーーーーーーーーーーーー指し手の評価方法
それぞれの自分の指し手に対して
相手の指し手を３つの貪欲手法にしたがって複数用意する。
それらの動きで盤を更新してそれぞれに対して自分が支配している惑星の数を数える。
自分の支配している惑星の数の最小をこの自分の手の評価にする
しかしこれで重要なノードをちゃんとまもろうとするのか怪しいので評価関数はその辺考慮していじくる必要はありそう
ーーーーーーーーーーーー新しい指し手の生成
次にこのleafに訪れた場合
一番スコアの良い指し手を突然変異させる、または交配させることによって新しい指し手を作ってその指し手を評価し、
最善スコアを超えるかどうかをする。
もし指し手の数が一定に達した場合は最善だった指し手と相手の応手を用いて盤面を更新してツリーを深化させる。
ーーーーーーーーーーーーnodeの選び方
ノードの選び方は末端の評価値に末端までの遠さの割引項をかけて確率的に選択する（ボルツマン分布的）
なんかかっこよく聞こえるしうまくいきそうじゃない？
最初の貪欲指し手生成で強い指し手を生成できたほうがもちろん良いのでifelseベースの行動で強いのを作れないといけないし、まだユニットスプレッドを理解していないのでそれもちゃんと把握しないといけない
大変だなぁ。
まあ明日からやっていこうかなと思ったところで1日目終わり
~~~~2日目
後輩氏は進捗発表と院試の勉強で忙しいらしく参加は厳しいらしい。
まあそうですよね。私も研究あるしゲーム作る機運が高まっていたので終了(は?)。
ーーーーー感想戦（初日しか参加してないが）
というわけで，今回の戦略．
— Risen (@longsword5) 2018年7月23日
[合流点が存在し，状態は中立]
・ルールベースで合流点へユニットを送り込む
[合流点が存在しない or 合流点は中立でない]
・MiniMax亜種(最良ノードを展開し続ける．最大5手先まで)
・候補手はルールベースで敵味方7種ずつ挙げる
※合流点は，画像の10みたいな星のこと pic.twitter.com/9otne9PTRD
評価関数は，ゲームスコア(占領数の差分)を基本として，前線への配備度合いでタイブレイクという感じ．
— Risen (@longsword5) 2018年7月23日
にゃるほど
潜伏勢，容赦なくて笑った．
— Risen (@longsword5) 2018年7月23日
コドゲは相手の戦略が見えるので対策を立てられてしまうため強い人は潜伏する傾向が強いみたいですね
やったこと
— nyashiki (@sizensuN) 2018年7月23日
1. Goldまでif-thenで上がる（重要）
2. ヒューリスティックな評価関数を作る
3. 自分が取れる行動に対して、全探索を行い評価関数を呼び出す。
4. 3.をやるとTLEしてしまうので、ヒューリスティックを用いて対象のplanetを絞る
これでGold 30位-50位くらいをうろちょろする。
— nyashiki (@sizensuN) 2018年7月23日
このままでは相手の行動を考えていないので、改良する。
5. 3.を改良する。相手の行動を考えるため、全探索のあと1.で作ったif-thenを相手の行動として適用し、その後評価関数を呼ぶようにする。
これでGold10位後半-20位前半をうろちょろする。
1.をちゃんとやっておくのが重要で（探索を使わずにGoldに行く）、ほとんどコスト0で相手の行動も考慮できるようになる。
— nyashiki (@sizensuN) 2018年7月23日
序盤、切断点を抑えられてしまうとどうしようもなくなるときがあるので、切断点が近いとき用に定跡を埋め込んでます。
— nyashiki (@sizensuN) 2018年7月23日
にゃるほど
にゃるほどしか感想がでないのかよ
