CodeVS に参加しました
CodeVS に参加しました。最後のほうあきらめて回さなかったので何とも言えないですが 50 位くらいでした。
この記事では, 最初に自分のやったこと, 次に初心者(100 位以内入れなかった, もしくは難しすぎて何すれば良いか全くわからなかった人)向けに「こうすれば考えやすいんじゃないの」的な実装方針, 最後に上位陣の解法でなるほどと思ったことを書きたいと思います。
考えたこと
一手でも valid な手が非常に多いため, 二手以上読むことが非常に困難
- おそらくたいていの AI はできたとしても一手詰みまで
- よくできた AI だとしても, 一手詰み＋α(相手が次に移動するところを予測して殺す, または次の相手の状態をかなり悪くする)と思われる
- 相手が根負けするのを待つ AI は(少なくとも予選では)かなり強いのではないか
- 予選の形式では, 「弱い相手に負けない」ことは重要なファクター
やったこと
まず今の状態が「危機的」かどうかを判定する
- 危機的かどうかは, 任意の次の状態が相手に一手詰みをさせられそうかで判断
- 一手詰みさせられるかは, 次の移動で生きられる場所が 3 個以上あるかで判断
- 危機的でない場合は, 「一手詰みさせられない移動の中で」「ソウルへの近さ, 犬への危機度」をあわせた評価関数でソウルを集める
- 危機的な場合は, 自分身を使いながら, 自由度の高いところへ移動する
実装方針
移動の中から最も良いものを選ぶために, 「評価関数を作り, その中から最も良いものを選ぶ」ということをやりたいですが, これが結構難しいです。
まず, このゲームのように「あるものから逃げながら別のあるものに近づく」ということを評価関数で動かしたい場合は, よく「影響マップ」というものが使われます。評価関数を作れなかった, という人は「影響マップ」でググるだけで結構いろいろ思いつくのではないでしょうか。
この方針でいくと, 犬への最短距離 をマイナス評価, ソウルへの最短距離でプラス評価, というようにすれば良い感じがします(自分が試した感じでは, 犬への最短距離は入れないほうが良い気がしますが)。
最も単純に「犬からできるだけ離れる, ソウルをできるだけ取る/取れなければ近づく」という方針を取ろうとしても, (犬からの距離は簡単に求められますが)岩があるせいでソウルからの距離を算出することが難しいです。
完璧な最短距離を求めるのは(多分)難しいですが, 概算を出すだけなら, よく知られたダイクストラ法で求めることもできます。
ソウルへの距離を求めるのが難しいのは, 岩があるせいです。一つしか岩がない場合は押せますが, 奥に岩がある場合は押せません。これを単純に考えると, 「進もうとしている方向に岩が集中的にあると押せない」となります。もうちょっとコード化すると, 「今いる場所および進もうとしている先 3 マスを見たときに, 行き止まりになる要素(岩, 壁, 犬)が 2 つ以上あればそっちへ行けない」というように考えれば, ある程度正確にソウルへの距離を求められるので, ソウルを素早く集められる AI になります。
下のコードは自分の書いた State の評価関数の一部です。
// ソウルへの近さを評価する // ダイクストラします vector<vector<edge> > G(H*W); for (int y = 1; y < H-1; y++) for (int x = 1; x < W-1; x++) { for (int k = 0; k < 4; k++) { int ny = y+dy[k], nx = x+dx[k]; if (field[ny][nx].isWall()) continue; int nny = y+2*dy[k], nnx = x+2*dx[k]; if (field[ny][nx].isObject() || field[ny][nx].containsDog) { if (!field[nny][nnx].isEmpty()) continue; if (field[nny][nnx].containsDog) continue; } // とりあえず (y, x) と (ny, nx) はつなげる if (field[y][x].isEmpty()) G[y*W+x].emplace_back(ny*W+nx, 1); if (field[nny][nnx].isWall()) continue; // (nny, nnx) は壁でないのでもう一個先を見ても範囲外ではない int nnny = y+3*dy[k], nnnx = x+3*dx[k]; int cnt = 0; if (!field[y][x].isEmpty() || field[y][x].containsDog) cnt++; if (!field[ny][nx].isEmpty() || field[ny][nx].containsDog) cnt++; if (!field[nny][nnx].isEmpty() || field[nny][nnx].containsDog) cnt++; if (!field[nnny][nnnx].isEmpty() || field[nnny][nnnx].containsDog) cnt++; // 進行方向に 2 つ以上の岩がなければ進めそう if (cnt < 2) { G[y*W+x].emplace_back(nny*W+nnx, 2); } } } vector<int> closeSoul(2); for (int i = 0; i < 2; i++) { Character ninja = ninjas[i]; auto d = dijkstra(H*W, G, ninja.y*W+ninja.x); vector<int> mini; for (Point soul : souls) { if (!field[soul.y][soul.x].containsSoul) continue; bool ng = false; for (int k = 0; k < 5; k++) { int ny = soul.y + dy[k]; int nx = soul.x + dx[k]; if (field[ny][nx].containsDog) ng = true; } if (ng) continue; mini.push_back(d[soul.y*W+soul.x]); } sort(mini.begin(), mini.end()); int mIndex = min<int>(3, mini.size()); for (int j = 0; j < mIndex; j++) closeSoul[i] += 1000/(mini[j]+1); }
なるほどと思ったこと
遷移について
どんな探索をするにせよ, valid な動きがたくさんある時は「それっぽい」動きを考えて計算量を減らすのが重要です。
今回の場合できたのは,
- 「動かない -> 動く」と「動く -> 動かない」は同じなので忍者の動きは(5*4)^2 に絞れる
- 術に関して,
- 超高速 -> 最初に動くマスは犬と重なるもののみ, 3 歩目は 1, 2 歩目のいずれかと同じ
- 雷 -> 忍者周辺のみ
- 分身 -> 端っこ, 現在の忍者の位置
数手深く読む場合について
なぜか一手読みでも結構時間がかかってしまったし, 数手先でもソウルの状況, 相手の忍術などで状況が大きく変わってしまうと思ってたので数手深く読むのはあんまり考えてなかったのですが, 上位陣のツイートを見ていて考えるべきだったなと思うこともありました。
- ソウルを早く手に入れていた場合, それを積分していくことで大きな評価にする
- 3 手まではしっかり読んで, あとは貪欲にするなどして深く読む
積分評価みたいな考えは全くなかったので今度から使える場面があったら使いたいですね。
あとこれは今回のだけではないですが,
- ビームサーチをする場合, 同一局面は必ず除去する
- 一回局面が一致してしまうと, 指数的に同じ状況が増え, それの評価が高かった場合ビームサーチと言いつつ貪欲とほとんど同じになってしまうので
評価関数について
今回のゲームでは相手からの攻撃をどう避けるか, というのも難しいポイントでした。これを評価関数のペナルティでマイナスさせると良い感じだったらしいです。
あと評価関数で感動したのが, 「生存率 * ソウル評価 を評価関数にする」というものでした。ソウル集めても死んだら意味ない, という思想ですが, こういう評価を線形和でやらずに掛け算でやる発想になるのがすごいです。
まとめ
楽しかったのでまた参加したいです。
