■動機
PS1 の Zeus カルネージハート (以下 CH) というゲームがあって，過去この blog で取り上げたこともあるのでそっちを見てもらうとして，CH のプログラミングはチップを並べる事によって行うので，編集作業が大変．
で，これをプログラミング言語でソフト組めたらいいなぁとずっと思っていて，やってみることにした．目的はもう一つあって，AI に聞きながら，もしくはコード生成を丸投げしてどこまでのことができるのか試したくなった．
というわけで OKE Chip Compiler (okecc) プロジェクト開始．ちなみに Github で公開してます．
■AI の威力
okecc のやるべきことは 2つ．言語から CH のチップ群に変換する言語パーサと，チップを処理の流れに従って矛盾なく並べる配置処理．前者は過去経験があるので良いとして，後者をどうやったらいいのか見当もつかないので，AI に聞いてみる．
- MxN のグリッドにチップを並べる問題を解くアルゴリズム
- チップの接続関係はすでに定義されている
- チップは縦横斜めの 8方向に隣接したチップと接続できる
- それ以上離れている場合は NOP チップで接続する．
- MxN のグリッドに全チップを並べ，NOP 数を最小化することがゴール．
という問題を与えてみたところ，最初は巡回セールスマン問題とかずれた回答をしていたが，こちらが補足として CH の名を出したとたん AI の理解が急速に進み，CH の内容を正しく理解していることにびっくり．それでいくつかアルゴリズムの案をだしてきた．
- この問題をグラフ理論とみなして既知のアルゴリズムを適用: CH の離れたチップは NOP チップで接続する必要があり，要するに配線スペースが必要だが，既知のアルゴリズムではそれは考慮されない
- 機械学習: 教師データの準備が大変
- 焼きなまし法: AI のおすすめ．全数探索が不可能な問題はとりあえずこれだそうで．
ここでダメ元で「焼きなまし法のコードを出して」とお願いしたら，それなりに動くコードが出てきてまたびっくり．焼きなまし法はおぼろげな知識はあるが，正確なやり方は知らなかったので，実際に動くコードがあるのと無いとでは自分の理解が断然違う．AI が吐いた最初期のコードだけでもこれだけまともな配置を吐くことができて，このプロジェクトが成功する感触を得ることができた．
ちなみにこれ，SVG で出力したものを Web ブラウザで表示していて，SVG 出力のコードはは 100% AI が吐いてくれた．こういった，誰かがもうやっているであろうコードを吐くのは AI は得意そう．
■AI の限界
上の配置図は一見まともだが，黄色の箇所とか配置がおかしく，正解ではない．
ここで焼きなまし法の流れを簡単に説明すると，以下のようになっている．
- 今のチップ配置を元に次のチップ配置を生成する．ランダムに 1チップ選び，高確率で隣接するチップと入れ替えるか，低確率でランダムな場所とスワップする．
- チップ配置のスコアを計算する．接続するチップが離れていたら離れているマス数分のペナルティ，またそのチップ間のパスが他のチップ上を通過していたら大ペナルティ
- 前回のチップ配置からスコアが良化すれば新しいチップ配置を採用，スコアが悪くても確率で採用するが，解の探索が進むごとにその確率は少なくしていく．
で AI が吐いたコードは色々課題があって，
- 解けない配置にハマると，一度スコアが悪い状態を経ないと正解にはたどり着けないが，その頃には「スコアが悪くても確率で採用」の確率が低い
- そうなってしまう理由は，次のチップ配置の生成がランダム要素が強く，スコアが良化する配置が生まれにくい
という問題があることがわかった．そこの問題点を指摘して AI にコード吐かせてみたが，たいして効果が無かったり，的外れであったりと，この時点では AI はさほど有用ではなかった．
CH のチップ配置という誰もやったことがないことに対しては，どこにも参考となるコードがないから，AI もまともな回答はできないようだ．このあたりが AI の限界だなぁと悟った次第．
■結局力こそパワー
で結局「より良い配置を生みだしやすくする配置生成アルゴリズム」は人間の力で考えるしか無いが，アルゴリズムさえ考えて指示すれば，AI はちゃんとコードを吐いてくれる．
そうしたアルゴリズムを追加していった結果，チップ数が多い場合でも数十回に 1回ほど配置が成功するようになったので，後はマルチスレッド + 正解するまでループ，の力技で正解を探索するようにした．結局最後は CPU パワーがすべてを解決するw
今回 AI を活用してソフトを開発してみた感想としては，AI は「ネット上の膨大な知識を持っている社外工」だと感じた．
例えば最新 C++ の書き方を教えてくれたり，あと PS1 メモリカードイメージファイルから，特定のゲームのセーブデータを抜き出すコードなんかも一発で書いてくれた．
ただし誰もやったことがないことをアルゴリズムレベルまで落とし込むのはまだまだ人間の仕事で，そこら辺は考えてくれないところが社外工っぽい．あとまれに間違ったコードを吐いたりもするので，そこの W チェックが必要なのも，社外工と仕事やってる感覚と似てるなぁと思った．
