ゲーム・パズルゲーム木; Game Tree
概要
ゲーム木とは将棋や囲碁、オセロなどの確定完全情報ゲームにおいて、ゲームの盤面の状態を取り得る棋譜によって展開したものである。
確定完全情報ゲームは以下の条件を満たすゲームのことを言う。
・確定:確率的要素はなく盤面の状態と棋譜によって次の盤面の状態が定まる。
・完全情報:ゲームに参加するプレイヤーが盤面の状態を完全に把握できる。
ゲーム木を用いてゲームを有利に進められる棋譜を決定するために必要なものは以下になる。
・盤面状態を一意に表現するデータ構造
・棋譜を一意に表現するデータ構造
・ある盤面状態がプレイヤーにとってどれだけ有利かを評価する評価法
・盤面状態から次の取り得る棋譜を列挙する処理
・盤面状態と棋譜から次の盤面状態を生成する処理
・ゲーム木の探索手法
このうちゲーム木の探索手法以外はゲームの種類によって異なる。 ゲーム木の探索手法には完全探索法、ミニマックス法、アルファベータ法、反復深化探索法などがあり、より効率的にゲーム木を探索できる手法を選ぶ。これらについては他の記事で取り上げている。 また、盤面状態の評価法の設計はゲームをどう進めれば有利に運ぶのか知識が必要になる。または機械学習に任せる方法もある。残りの要素はゲームのルールによって定まる。
つまりゲームのAIの強さは、盤面状態の評価法の質とゲーム木の探索速度によってのみ決まる。
当サイトでは盤面状態インターフェースの実装クラスと棋譜クラスを作るだけで、ゲーム木を用いた棋譜決定プロセスが実現できるようにソースコードを掲載している。
実装例については オセロAIの開発 を参考のこと
ソースコード
ゲーム木の探索手法アルゴリズムを扱うのに必要な盤面状態インターフェース
namespace GameTreeSearch {
/// <summary>ゲーム状態インターフェイス</summary>
/// <typeparam name="DecisionType">棋譜クラス</typeparam>
public interface IState<DecisionType> where DecisionType : new() {
/// <summary>評価値</summary>
double Evaluation { get; }
/// <summary>ゲームセットか否か</summary>
bool IsEndGame { get; }
/// <summary>次の取り得る棋譜をコレクションとして返す</summary>
IEnumerable<DecisionType> NextDecisions();
/// <summary>次のゲーム状態を生成する</summary>
/// <param name="decision">棋譜</param>
IState<DecisionType> NextState(DecisionType decision);
}
}
ゲーム木の探索手法アルゴリズムで用いるゲーム木ノードクラス
namespace GameTreeSearch {
/// <summary>ゲーム木ノード</summary>
/// <typeparam name="StateType">盤面状態クラス</typeparam>
/// <typeparam name="DecisionType">棋譜クラス</typeparam>
public class GameNode<StateType, DecisionType> where StateType : IState<DecisionType> where DecisionType : new() {
private double evaluation;
/// <summary>コンストラクタ</summary>
/// <param name="state">盤面状態</param>
/// <param name="decision">この盤面状態にした棋譜</param>
/// <param name="parent_node">親ノード</param>
public GameNode(StateType state, DecisionType decision, GameNode<StateType, DecisionType> parent_node) {
this.evaluation = double.NaN;
this.State = state;
this.Decision = decision;
this.ParentNode = parent_node;
this.ChildNodeList = new List<GameNode<StateType, DecisionType>>();
}
/// <summary>子ノードをコレクションとして返す</summary>
public IEnumerable<GameNode<StateType, DecisionType>> ChildNodes() {
foreach(var decision in State.NextDecisions()) {
var child_node = new GameNode<StateType, DecisionType>((StateType)State.NextState(decision), decision, this);
ChildNodeList.Add(child_node);
yield return child_node;
}
}
/// <summary>子ノードを展開</summary>
public void ExpandChildNodes() {
foreach(var decision in State.NextDecisions()) {
var child_node = new GameNode<StateType, DecisionType>((StateType)State.NextState(decision), decision, this);
ChildNodeList.Add(child_node);
}
}
/// <summary>子ノード昇順ソート</summary>
/// <param name="is_evaluate">未評価の子ノードの評価を行うか</param>
public void AscendingSortChildNodes(bool is_evaluate) {
if(ChildsCount > 1) {
if(is_evaluate) {
ChildNodeList.Sort((a, b) => (a.Evaluation < b.Evaluation) ? -1 : ((a.Evaluation <= b.Evaluation) ? 0 : +1));
}
else {
ChildNodeList.Sort((a, b) => {
if(a.IsEvaluated && b.IsEvaluated) {
return (a.evaluation < b.evaluation) ? -1 : ((a.evaluation > b.evaluation) ? +1 : 0);
}
return (!a.IsEvaluated && !b.IsEvaluated) ? 0 : (a.IsEvaluated ? -1 : +1);
});
}
}
}
/// <summary>子ノード降順ソート</summary>
/// <param name="is_evaluate">未評価の子ノードの評価を行うか</param>
public void DescendingSortChildNodes(bool is_evaluate) {
if(ChildsCount > 1) {
if(is_evaluate) {
ChildNodeList.Sort((a, b) => (a.Evaluation > b.Evaluation) ? -1 : ((a.Evaluation >= b.Evaluation) ? 0 : +1));
}
else {
ChildNodeList.Sort((a, b) => {
if(a.IsEvaluated && b.IsEvaluated) {
return (a.evaluation > b.evaluation) ? -1 : ((a.evaluation < b.evaluation) ? +1 : 0);
}
return (!a.IsEvaluated && !b.IsEvaluated) ? 0 : (a.IsEvaluated ? -1 : +1);
});
}
}
}
/// <summary>盤面状態</summary>
public StateType State { get; set; }
/// <summary>この状態にした棋譜</summary>
public DecisionType Decision { get; set; }
/// <summary>親ノード</summary>
public GameNode<StateType, DecisionType> ParentNode { get; }
/// <summary>子ノードリスト</summary>
public List<GameNode<StateType, DecisionType>> ChildNodeList { get; }
/// <summary>子ノードの数</summary>
public int ChildsCount {
get {
return ChildNodeList.Count;
}
}
/// <summary>評価値</summary>
public double Evaluation {
get {
return IsEvaluated ? evaluation : (evaluation = State.Evaluation);
}
set {
evaluation = value;
}
}
/// <summary>子ノードの先頭の評価値か、子ノードが存在しない時は自身の評価値</summary>
public double EvaluationFirstChildOrSelf {
get {
return ChildsCount > 0 ? ChildNodeList[0].evaluation : evaluation;
}
}
/// <summary>評価済みか否か</summary>
public bool IsEvaluated {
get {
return !double.IsNaN(evaluation);
}
set {
evaluation = value ? State.Evaluation : double.NaN;
}
}
/// <summary>末端ノードか否か</summary>
public bool IsEndNode {
get {
return ChildNodeList.Count <= 0 && State.IsEndGame;
}
}
/// <summary>文字列出力</summary>
public override string ToString() {
return IsEvaluated ? $"EV = {evaluation}" : "UnEvaluated";
}
}
}
関連項目
完全探索法
ミニマックス法
アルファベータ法
反復深化探索法
探索打ち切り可能な反復深化探索法
オセロAIの開発(実装例)
