ネガマックス法（ゲーム探索問題のうち手番が対象なもの）

ネガマックス法とは、ミニマックス法のうち手番の対称性に注目して実装をより簡単にしたゲーム問題用のDPである。手番の対称性とは、AとBが対戦するときにA, Bが取れる行動が等しいことをいう。以下のような問題で用いることができる。

解法

再帰を使った例（メモ化も実装済み）

// 盤面の状態が state である状態から
// 最善手を打ったときに得られる得点の差の最大値を返す
// Gameは#[derive(Clone, Copy)]を実装してあることが条件である。
fn dfs(state: State, game: &Game, memo: &mut Memo, used: &mut Used) -> isize {
    // メモ化済み
    if used[state] {
        return memo[state];
    }
    // 終端条件
    if (stateが終端である) {
        return (終端での得点差); 
    } else {
        let mut val = std::isize::MIN;
        for next in (stateから一手で移動できる状態全体) {
            let add = stateからnextの一手で得られる得点;
            val = val.max(add - dfs(next, game, memo, used));
        }
        used[state] = true;
        memo[state] = val;
        return val;
    }
}

そのときの計算量はO(状態の数 x 状態からの遷移先の数の最大値)となる。また、これは配列で解くこともできる。グリッドなどでこの問題を解くときは配列で書いたほうが書きやすい場合が多い気がする。Rustの関数はletでクロージャーとして書くかmainの外に書くかしかないので、ゲームの状態も引数として渡すしかなく、どうしても引数が大きくなってしまうので大変だなあと思う。何かいい方法がある人は教えてください。