GPx05

SNAP！によるゲームアルゴリズム（その3）

3目並べ（Tic-Tac-Toe）の思考ルーチンの高速化について

・ゲーム木と探索アルゴリズム

・コードの効率化

・メモ化（キャッシュ）の利用

探索した局面の結果（黒の勝ち・白の勝ち・引き分けあるいは勝敗不明）をデータブックに記録しておく。

手順の入れ替わりや回転・反転対称などで探索済みと同形の局面が探索中に現れた場合は、データブックに記載された値を利用する。

長手数の先読みのコストは高いので探索回数を減らすことで高速化が実現する。

問題点：キャッシュの有効性と利用コストのトレードオフ

メモ化の実行コストも発生するのでメモ化の利用範囲を調整する必要がある。メモ化の実行コストにより返って低速になる場合がある。

データブックに記載された局面の再利用率（キャッシュにヒットする）が高い状況で利用する。

・関数型プログラミングの例

解説動画で使用したSNAP!のコードをWebclassの資料としてアップロードした。
最終段階のコードも載せたのでPCやiPadから利用するとよい。

参考サイト：

高速化前に30秒かかった思考時間が2.3秒まで短縮される様子の動画。
高速化前は着手位置を限定して探索しているので実際は90秒程度。

今回の課題は用意していない。