Typical DP Contest B. ゲーム - れどこだ目指すよ！　(；`・ω・）

2人が2つの「石が積まれた山」から交互に好きな方を選んで取っていく。
石には数字が書かれており、取った石の数値の合計が最終得点となる。
両者が最善を尽くしたとき、先手の得られる最終得点を答える。

ゲーム木の探索(先読み)。
ゲームの状態(木の各ノード)は、「それぞれの山に石がどれだけ残っているか」になる。

先手のターンの場合は、山Aから取った場合と山Bから取った場合で得られる最大得点の方、
後手のターンの場合は、後手が山Aからとるか山Bから取るかを考えて、先手の得られる最大得点が低くなる方、
を選択するとき最善行動になる。
各ノードの計算をメモ化すれば、よい。

「両者が最善を尽くしたとき」というのがちょっと難しい気がする。
ゲームの先読みするとき、以下の推論が行える。

合理的な選択を2人がする場合、完全情報ゼロ和ゲームとして、「min-max戦略」が最適になる。

と考えて行動する事で、最終的に最適な行動がとれる。
これ以外の行動を相手が取った場合は、上記の推論で得られるよりも高い価値が最終的に得られるはず。

別のいい方であれば、現局面における評価値は、「先手が得られる最大得点」として、

になる。