#しぶんぎメモ

なんもわからん。

TSPの近傍

TSPを部分問題として持つマラソン問題を解く際に思ったことを書き残す。

始点、終点が固定されているケース

巡回順の配列seq について次のような遷移を適用。
最初と最後の
ただし、seq[0] = 始点、seq[N-1] = 終点

int a = rand()%(N-3); // 0 <= a <= N-4
int b = rand()%(N-a-3) + a + 2; // a+2 <= b <= N-2
if(cost[a][a+1] + cost[b][b+1] > cost[a][b] + cost[a+1][b+1]){
  int x = a+1;
  int y = b;
  while(x < y){
    swap(seq[x],seq[y]);
    x++;
    y--;
  }
}
始点だけ固定されているケース

上に次の遷移を追加する。

int a = rand()%(N-2); // 0 <= a <= N-3
if(cost[a][a+1] > cost[a][N-1]){
  int x = a+1;
  int y = N-1;
  while(x < y){
    swap(seq[x],seq[y]);
    x++;
    y--;
  }
}
さいごに

もしかしたら良くない遷移かもしれない。
あと同様の遷移でもうまくやって軽くできるはず。

CodinGame SPRING CHALLENGE 2021に参加しました

はじめに

ボードゲームのAIを10日くらいで作って戦わせるコンテストに参加していました

www.codingame.com

全体38位、日本人としては6位と、非常に好成績を残すことができ満足しています

以下にコンテストの概要や、自分の戦略、反省などをまとめていきます

どんなボードゲーム？

盤面内で木を育成し、伐採することで勝利点を得るゲームです。

いなにわさんがルールの日本語訳をまとめてくださっているので、詳しくはこちらを参照してください。

inaniwa.hatenablog.com

以下はあるゲームのリプレイのURLです。ゲームの雰囲気がわかると思います https://www.codingame.com/replay/557676455

やったこと、考えたこと

  • 盤面の評価関数を作って貪欲
    • コンテスト2日目のBronzeリーグで真ん中あたりに収束
    • ゲームの進行度によって良い盤面が変化していくので、評価関数を作るのが非常に難しい
    • 評価関数が作れないとなると、貪欲をビームサーチに書き換えても良い結果は得られないと考え、別の方針を探す

  • ルールベースbot
    • 上位勢の対決を観戦し、このボードゲームで強そうな行動の条件を列挙した
    • complete > grow > seed > wait の優先度で、条件に見合う行動があれば出力
    • たぶんこの時点でGoldにすすめるくらいには強くなった

  • ルールベースbot改
    • 上のルールベースだと同じ種類の行動で条件を満たす行動が複数あった場合、どれが選ばれるかはランダムであった
    • 盤面の評価関数を作るのは難しいが、同じ種類の行動ならある程度優劣はつけやすいと考え、各行動について評価する関数を作った
    • 条件を満たし、優先度が一番高い行動を出力
    • 評価関数をある程度整備した時点でLegend解放後のGoldリーグで100位切るくらいの強さ

  • DUCT
  • ルールベースbot改 + DUCT
    • 既に作ったルールベースbot改くんを使ってrolloutやexpandで考える手を絞る
    • 各種類の行動について評価値上位2手ずつを合法手とする
    • それっぽいrolloutをしてくれるようになった

最終的な自分の戦略

ルールベースbot改 + DUCT が私の最終的な方針です。DUCT部分には特に工夫をしていないのでルールベースや各行動の評価関数について紹介します。

Complete

以下の3つの条件いずれかを満たすときのみcompleteを合法手に加えます。

  • サイズ3の木が4本以上
  • サイズ3の木が3本以上かつnutrientsが16以下
  • nutrientsが12以下

評価関数は

  • その木を伐採することで以降3日間で他の自分の木が得られるようになるsun値
  • その木が以降3日間で得られるsun値

を考慮します。

相手のサイズ2が成長しうるときはサイズ3の木として扱う、3日後より1日後のsun値を重く考える、のような工夫も入っています。

Grow

伐採が最終日に間に合わないGrowを合法手から外しています。

評価関数は

  • 木のサイズが大きい
  • 土壌が良い

ほど加点し、

  • 以降3日間に相手を妨害できるか

を参考にしています。Growの評価が一番良くわかりませんでした。

Seed

自分の種が既に盤面にあるとき、もしくは19日目以降はSeedを合法手に加えません。

Seedは自分の他の木と干渉しにくい場所ほど高評価としました。相手の木との干渉は考えていません。

Wait

終盤を除き、他に有効な手がないときのみ合法手に加えました。

その他

  • playoutは序盤で400回程度でした。
  • 次のターンに使い回せる部分の木を残す処理は行っていません。

反省

  • 上位の人は盤面の評価関数を頑張って作っていた
    • こっちのみが当たり解法だったら、爆死していた


  • MCTSについての理解が甘い
    • 今回はMCTSの内部についてほとんど変更を加えていない
    • もうちょっと柔軟に扱えるようになっておきたい

まとめ

次回もLegendいけるようにがんばります。

CODINGAME SPRING CHALLENGE 2020 に参加した

こんにちは！！！！！！！！！！！！！！！！！！！！！！

自分の思考の過程や気付きを書き残しておけば後々再利用できる気がしたのでブログを書くことにしました。 具体的な解法、方針の解説というより、もっとざっくりとした考え方のお気持ちが中心になります。

CodinGameって何さ

www.codingame.com

今回初参加だったので全体像は掴めていないのですが、ゲームAIを作成してその強さを競い合うコンテストサイトのよう。 ゲームAI？ 難しそうじゃない？ と思いましたが、標準入力からゲームの状態を取得し、標準出力からあらかじめ決められた行動コマンドを出力する、という形式なので楽に参入できた。

春休みくらいから気になってたのでバイトと研究の進捗を生贄にして時間を特殊召喚しました。

CODINGAME SPRING CHALLENGE 2020

www.codingame.com

今回のゲームは複数のパックマンを操作し、2Dグリッドの盤面上に設置されたエサを相手より多くゲットする、というもの (詳細は他の人がちゃんと書いてくれるでしょう)

ゲームの特徴として

  • 不完全情報ゲー
  • マルチエージェント
  • 対戦ゲーム

などが挙げられる。それぞれについて書いていく

不完全情報ゲー

敵パックや残っているエサの位置を全て取得できる訳ではなく、 毎ターンごとに自分のパックから見て上下左右の道の上にあるものしか情報は取得できない。 つまり、盤面上のどこに何があるかほとんどわからないということになる。

情報が足りないケースこそできる限り情報を使い尽くす必要がある、と痛感した。 すでに持っている情報から新しく情報を確定できる場合が多い。 貪欲、焼きなまし、ビームサーチ、何をやるにしても評価関数の正確性は重要なので些細な "確定埋め" の作業は思っている以上に恩恵が大きい(はず)(面倒なんだけどね...)。

盤面の評価がガバガバのうちにいろいろやってもいい結果が出ないのは、それはそう

マルチエージェント(？)

操作するパックが複数いるだけだからマルチエージェントは不適切かも？(各エージェントが得た情報が共有できず、それぞれが得た情報から個別に行動を決定してくのが"マルチエージェント"？)

とにかく、複数のキャラクターを同時操作するので協調した行動をが必須。同じような場所を探索するのは効率が悪いし、まして味方同士で衝突なんてことは絶対に避けなければならない。

今回の場合、各パックが進むべき経路を決める際に、

  • 他のパックの経路は無視して全てのパックの経路を個別に決定 -> 経路を少しずつ変えながら調整
  • パックの経路を順に決定(後から経路を決めるパックはすでに決定された他パックの経路の影響を受ける) -> 順番をいろいろ試す。

という方針が多かったっぽい。 順番の入れ替え、というのは自分が見落としがちな典型な気がする。

対戦ゲーム

相手が存在するというのは僕が普段やっているマラソンマッチと一番異なる点だと感じた。 相手の戦術を察知しメタっていく、というのはゲームAIコンペ特有の面白さなのかもしれないが、不慣れな僕はできるだけ相手に関与しないという方針をとった。 これはまあ良かったかも。戦術メタをしようとすると方針がルールベースに寄ってしまって自分の苦手な土俵になりそう。

あと、マラソンよりゲームの方が問題特有の性質が細かく色々なところに散らばっていて、それらをかき集めてバランスよく実装するのが大変そうだった (僕は問題特有の性質なんて気にするレベルのところまでいけませんでした)

一応、自分の解法

そんなに大したことやってないからツイート引用するだけでいい？いいよ。

ツリーにもうちょいいろいろ書いてあります。

いつもお気持ち評価関数書いて満足してる気がする。

懺悔とか

やっぱり文章書くの苦手だなあ......

他人が見ること一切考慮せずに箇条書きオンリーにして完全自分用にした方がいいかもしれない。

しかし、マラソンマッチとかは競プロのアルゴ界隈に比べてノウハウの共有、蓄積が進んでないという印象もうけるし多少なりとも貢献したいという気持ちもなくはないので......(葛藤)

あ、木曜日から始まるTopcoder Marathon Match 118 にも参加予定です。気分が乗ったらその感想もアップするかもしれません

はじめまして

こんにちは、しぶんぎ です。 

競技プログラミングの勉強をするときに何かしらアウトプットしたほうが身につくかな？と思いブログを開設してみました。

基本的に競プロ関連の記事を作成していくつもりです。