ミニマックス法; Mini Max Algorithm
概要
ミニマックス法とは指定した探索深度までゲーム木をゲームの盤面の状態を取り得る棋譜によって展開し、自分の手番は評価値が最大になるよう、また相手の手番は評価値が最小になるよう、終端から1手目までノードを刈り込み棋譜を決定する手法である。
アルファベータ法のほうが高速で結果も同じになるため用いられることはない。
ソースコード
namespace GameTreeSearch {
/// <summary>ミニマックス法</summary>
/// <typeparam name="StateType">盤面状態クラス</typeparam>
/// <typeparam name="DecisionType">棋譜クラス</typeparam>
public static class MiniMaxMethod<StateType, DecisionType> where StateType : IState<DecisionType> where DecisionType : new() {
/// <summary>探索</summary>
/// <param name="root_state">ルートとなる状態</param>
/// <param name="max_depth">ゲーム木の深さ</param>
/// <param name="pass_decision">パス決定オブジェクト(有効な棋譜が存在しない場合に採用される)</param>
/// <returns>ゲーム木探索によって決定された棋譜</returns>
public static DecisionType Search(StateType root_state, int max_depth, DecisionType pass_decision) {
if(max_depth <= 0 || root_state.IsEndGame) {
return pass_decision;
}
Func<GameNode<StateType, DecisionType>, int, bool, double> minimax_method = null;
minimax_method = (node, depth, is_player) => {
if(depth >= max_depth || node.IsEndNode) {
return node.Evaluation;
}
if(is_player) {
GameNode<StateType, DecisionType> max_node = null;
double max_ev = double.NegativeInfinity;
foreach(var child_node in node.ChildNodes()) {
double ev = minimax_method(child_node, depth + 1, !is_player);
if(max_ev < ev) {
max_node = child_node;
max_ev = ev;
}
}
node.ChildNodeList.Clear();
if(max_node != null) {
node.ChildNodeList.Add(max_node);
}
return max_ev;
}
else {
GameNode<StateType, DecisionType> min_node = null;
double min_ev = double.PositiveInfinity;
foreach(var child_node in node.ChildNodes()) {
double ev = minimax_method(child_node, depth + 1, !is_player);
if(min_ev > ev) {
min_node = child_node;
min_ev = ev;
}
}
node.ChildNodeList.Clear();
if(min_node != null) {
node.ChildNodeList.Add(min_node);
}
return min_ev;
}
};
var root_node = new GameNode<StateType, DecisionType>(root_state, new DecisionType(), null);
minimax_method(root_node, 0, true);
if(root_node.ChildNodeList.Count > 0) {
return root_node.ChildNodeList[0].Decision;
}
else {
return pass_decision;
}
}
}
}
関連項目
ゲーム木
完全探索法
アルファベータ法
反復深化探索法
探索打ち切り可能な反復深化探索法
オセロAIの開発(実装例)