技術とか戦略とか

証券レガシーシステムを8年いじってから転職した普通の文系SEによるブログ。技術のみではなく趣味の戦略考察についても。

レトログレード解析とは-最終局面から順番に解析し簡単な問題を解く手法-

レトログレード解析(後退解析、バックトラック)とは、最終局面から順番に解析することで最善手を探る手法です。
状態の数がコンピュータで数え上げられる程度である場合に有効な手法であり、簡単な問題(ゲーム)であればこの手法で完全解析が可能です。
 
研究分野では、以下のように「どうぶつしょうぎ」(将棋を模した簡単なゲーム)の完全解析に使用されました。
どうぶつしょうぎ」の完全解析 - 田中哲朗研究室 - 東京大学

https://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/dobutsushogi/animal-private.pdf

 
手法の説明やコーディング例は以下のページにまとめられてます。
競技プログラミングにおけるゲーム問題まとめ [Nim,Grundy数,後退解析,ミニマックス法] - はまやんはまやんはまやん

https://www.hamayanhamayan.com/entry/2017/02/27/025050

 
前述のはまやんはまやんはまやん様の記事からもリンクされているのですが、後退解析のイメージ図は以下の通りです。
状態がループするゲームの解析(後退解析) - ペケンペイのブログ

https://pekempey.hatenablog.com/entry/2018/02/01/182034

 
ちなみに、コーディング例ではC言語のビット演算を多用しているので、私のような業務系システムのエンジニアが読むには少々苦しいものがあったりします。
しかし、ビット演算は基本情報処理技術者試験で勉強しているはずなので、頑張れば読めると思います。
ひと昔前はコーディング例をネット上で見つけることすらできなかったので、良い時代になりました。