今回は、ゲーム木探索の下準備をします。実務上の泥臭い話で、AI的な話は出てこないので適当に読み飛ばしてください。
現在ゲーム木探索のもっとも単純な手法として、原始モンテカルロ法（次回以降に説明）の実装を進めています。処理が非常に重いため実験コストの見積もりと有意義な実験条件の設定を考える必要が生じました。今回は実験コストの見積もりについてです。次回、有意義な実験条件の設定について書きます。
実験コストの見積もり
前回、ランダムプレイヤーのバトル1回で20～30msかかると書きましたが、ターン数などを含めた測定を行いました。またプロファイリングでボトルネックを探してみましたが見つからなかったという話をします。
環境はIntel Core i5-7600K CPU @ 3.80GHz, Windows 10, node v14.15.1です。シミュレータのリビジョンは4cecf1117aade118e4bb64768951e87bf5a75029です。
ランダムに生成したパーティ同士の対戦を1000回行い、所要時間などを測定しました。交代を選ぶ確率は0.1としました。その結果、18014msかかり、20428ターン、44296回の行動選択（1プレイヤーが1回選択したら1インクリメントされる。ターン開始時には2インクリメントされ、片方だけ倒れた際の交代先選択では1インクリメントされる）がなされました。おおむね、1ターン1ms、1バトル当たり20ターンかかり、両方のプレイヤーが思考する場合は44回の思考が発生するとして計算時間を見積もる必要がありそうです。
測定前にnodeをv10.16.3からv14.15.1にアップグレードしたのですが、約10%の高速化になりました。
一応、node.js標準機能でプロファイリングを行ってみました。
結果の一部を表示します。
[Summary]:
ticks total nonlib name
209 18.3% 98.1% JavaScript
0 0.0% 0.0% C++
21 1.8% 9.9% GC
926 81.3% Shared libraries
4 0.4% Unaccounted
[C++ entry points]:
ticks cpp total name
[Bottom up (heavy) profile]:
Note: percentage shows a share of a particular caller in the total
amount of its parent calls.
Callers occupying less than 1.0% are not shown.
ticks parent name
878 77.1% C:\Program Files\nodejs\node.exe
320 36.4% C:\Program Files\nodejs\node.exe
144 45.0% LazyCompile: *findPokemonEventHandlers D:\dev\pokeai\pokeai\Pokemon-Showdown\.sim-dist\battle.js:787:26
144 100.0% LazyCompile: *findEventHandlers D:\dev\pokeai\pokeai\Pokemon-Showdown\.sim-dist\battle.js:742:19
142 98.6% LazyCompile: *runEvent D:\dev\pokeai\pokeai\Pokemon-Showdown\.sim-dist\battle.js:556:10
25 17.6% LazyCompile: *tryMoveHit D:\dev\pokeai\pokeai\Pokemon-Showdown\data\mods\gen2\scripts.js:148:12
14 9.9% LazyCompile: *useMoveInner D:\dev\pokeai\pokeai\Pokemon-Showdown\data\mods\gen3\scripts.js:22:14
読み方は詳しく理解できていないのですが、一定時間ごとにどの処理が実行されているかがサンプリングされるようです。node.exe内の処理を実行中に取られたサンプルが878個で、そのうち144個がLazyCompile: *findPokemonEventHandlersの処理中だったようです。所要時間の大きい順にソートされているにもかかわらず最大所要時間の関数が全体の16%しか時間を消費していないということで、負荷の大部分を占める特定の処理があるわけではないようです。よって、その処理をC言語で作成したライブラリで置き換えて高速化ということはできなさそうでした。当面は1ターン1msかかるという前提で実験計画を立てる必要があります。
