読者です 読者をやめる 読者になる 読者になる

がりらぼ

WindowsRuntimeの応援ブログ

C#で問題の状態空間表現をしてみる

問題状態空間表現とは

人工知能ネタです。 問題状態空間表現とは、そもそも人工知能を適用する以前に、人工知能を適用する問題をどのように表現(モデリング)するかというところです。

よく用いられるのが水差し問題と8パズルですが、8パズルは長いので水差し問題を状態空間表現してみたいと思います。

4ガロンと3ガロンの2つの水差しと,水を入れるためのポンプが与えられています。4ガロンの水差しに正確に2ガロンの水をいれるにはどうすればいいでしょうか。水差しにはメモリがついていません。 共立出版 荒屋真二著 人工知能概論(第2版)より

ようするに、「4ガロン入るバケツと3ガロン入るバケツをどのように操作したら正確に4ガロンのバケツに2ガロン入れることができるか」ということです。

普通に考えたら結構難しいです。たぶん。 そこをコンピュータに解かせるのが人工知能の分野の話。

問題状態空間表現は、この問題を

  • 初期状態

  • 終了状態

  • ルール

の3つで表します。

初期状態は4ガロン入るバケツをx、3ガロン入るバケツをyとすると (x,y)=(0,0) のように表現できます。(最初バケツに水は入っていないので)

終了状態は (x,y)=(2,0) と表現できます。(4ガロンのバケツに2ガロンいれる)

ルールとは、現在の状態に適用させて新たな状態を作り出すものです。 例えば、

(x,y|x+y<=3∧x>0)->(0,x+y)

ならば、4ガロンバケツと3ガロンバケツの合計値が3ガロン以下でありかつ4ガロンバケツが0以上であるならば4ガロンバケツを0にして3ガロンバケツを4ガロンバケツと3ガロンバケツの合計値にする。 ということです。 つまり、このような条件に対する操作をして、どんどん状態を遷移していきます。

今回用いるルールは以下の8つです。

(x,y|x<4)->(4,y)
(x,y|y<3)->(x,3)
(x,y|x>0)->(0,y)
(x,y|y>0)->(x,0)
(x,y|x+y>=4∧x<4)->(4,x+y-4)
(x,y|x+y>=3∧y<3)->(x+y-3,3)
(x,y|x+y<=4∧y>0)->(x+y,0)
(x,y|x+y<=3∧x>0)->(0,x+y)

これらのルールを適用できるように問題状態空間表現を実装していきます。

状態をつくる

まず1つの状態を考えます。 この場合でいうと、4ガロンのバケツに入っている水と3ガロンのバケツに入っている水です。 この問題での状態は2つの値しか持ちませんが、ほかの問題になるともっとたくさんの値を1つの状態が保持することになるので C#のDictionaryを使って実装します。

//状態
public class State
{
    //状態を表現する値のリスト
    public IDictionary<string,int> ValueList { get; set; }
    public State()
    {
        ValueList = new Dictionary<string,int>();
    }
}

ルールをつくる

次に1つのルールクラスを作ります。 ルールは「条件」と「アクション」が必要になるので、 C#のFuncとActionデリゲードをつかって、外部からルールの条件を設定できるようにしましょう。

Applyメソッドでルールを適用して、条件がtrueならアクションを実行するようにします。

//状態を変えるルール
public class Rule
{
    //現在の状態に適用される条件
    public Func<State, bool> CurrentCondition { get; set; }
    //条件に一致したときに実行されるアクション
    public Action<State> NewAction { get; set; }
    public Rule(Func<State, bool> currentCondition, Action<State> newAction)
    {
        this.CurrentCondition = currentCondition;
        this.NewAction = newAction;
    }

    //条件を適用させる
    public void Apply(State state)
    {
        //条件がtrueなら
        if (CurrentCondition(state))
        {
            //アクション実行
            NewAction(state);
        }
    }
}

問題を作る

続いて問題をクラス化します。 この場合の問題とは、水差し問題などのことです。

問題は先ほども言いましたが、「初期状態」、「終了状態」、「ルール」の3つを持つのでフィールドとしてそれを作ります。

Executeメソッドでルールをすべて適用します。 本来人工知能ならば、このExecuteメソッド内を変更して、どのように実行知能にルールを適用させるのかを変更しますが、今回は人工知能を作っていないのですべてのルールを適当に適用します。

public class Problem
{
    //初期状態
    public State BeginState { get; set; }

    //現在の状態
    public State CurrentState { get; set; }
    //終了状態
    public State EndState { get; set; }
    //ルールのリスト
    public IList<Rule> RuleList { get; set; }

    public Problem(State beginState,State endState,IList<Rule> ruleList)
    {
        this.BeginState = beginState;
        this.EndState = endState;
        this.RuleList = ruleList;
        //初期状態をディープコピー
        this.CurrentState = new State();
        foreach (var i in beginState.ValueList)
        {
            this.CurrentState.ValueList.Add(i);
        }
    }

    //条件を実行
    public State Execute(Rule rule)
    {   
        //ルール適用
        rule.Apply(CurrentState);
        
        return CurrentState;
    }
}


Main関数

最後にアプリケーションのエントリポイントから、問題解決を実行します。 最初に、初期状態とゴール状態を設定し、8つのルールを設定します。

すべて設定できたら、問題解決を実行し、結果を出力します。

class Program
{
    static void Main(string[] args)
    {
        //最初の状態
        State beginState = new State();
        beginState.ValueList.Add("x",0);
        beginState.ValueList.Add("y",0);

        //ゴール状態
        State endState = new State();
        endState.ValueList.Add("x",2);
        endState.ValueList.Add("y",0);

        //ルール
        //(x,y|x<4)->(4,y)
        Rule rule1 = new Rule((state)=>state.ValueList["x"]<4,(state)=>state.ValueList["x"]=4);
        //(x,y|y<3)->(x,3)
        Rule rule2 = new Rule((state) => state.ValueList["y"] < 3, (state) => state.ValueList["y"] = 3);
        //(x,y|x>0)->(0,y)
        Rule rule3 = new Rule((state) => state.ValueList["x"] > 0, (state) => state.ValueList["x"] = 0);
        //(x,y|y>0)->(x,0)
        Rule rule4 = new Rule((state) => state.ValueList["y"] > 0, (state) => state.ValueList["y"] = 0);
        //(x,y|x+y>=4∧x<4)->(4,x+y-4)
        Rule rule5 = new Rule((state) => (state.ValueList["x"]+state.ValueList["y"]) >= 4&&state.ValueList["x"]<4, (state) =>{
            int x = state.ValueList["x"];
            int y = state.ValueList["y"];
            state.ValueList["x"] = 4;
            state.ValueList["y"] = x+y-4;
        });
        //(x,y|x+y>=3∧y<3)->(x+y-3,3)
        Rule rule6 = new Rule((state) => (state.ValueList["x"] + state.ValueList["y"]) >= 3 && state.ValueList["y"] < 3, (state) =>
        {
            int x = state.ValueList["x"];
            int y = state.ValueList["y"];
            state.ValueList["x"] = x+y-3;
            state.ValueList["y"] = 3;
        });
        //(x,y|x+y<=4∧y>0)->(x+y,0)
        Rule rule7 = new Rule((state) => (state.ValueList["x"] + state.ValueList["y"]) <= 4 && state.ValueList["y"] > 0, (state) =>
        {
            int x = state.ValueList["x"];
            int y = state.ValueList["y"];
            state.ValueList["x"] = x+y;
            state.ValueList["y"] = 0;
        });
        //(x,y|x+y<=3∧x>0)->(0,x+y)
        Rule rule8 = new Rule((state) => (state.ValueList["x"] + state.ValueList["y"]) <= 3 && state.ValueList["x"] > 0, (state) =>
        {
            int x = state.ValueList["x"];
            int y = state.ValueList["y"];
            state.ValueList["x"] = 0;
            state.ValueList["y"] = x + y;
        });
        //ルールのリスト
        var ruleList=new List<Rule>{
            rule1,rule2,rule3,rule4,rule5,rule6,rule7,rule8
        };

        //水差し問題を作る
        Problem waterProblem = new Problem(beginState, endState, ruleList);
        //テキトーにルールを適用して実行
        foreach (Rule rule in waterProblem.RuleList)
        {
            State state = waterProblem.Execute(rule);
            //出力
            Console.WriteLine("Current State x={0},y={1}", waterProblem.CurrentState.ValueList["x"], waterProblem.CurrentState.ValueList["y"]);
            Console.WriteLine("↓");
        }
        

        //出力
        Console.WriteLine("Current End State x={0},y={1}", waterProblem.CurrentState.ValueList["x"], waterProblem.CurrentState.ValueList["y"]);
        
        Console.WriteLine("Goal End State x={0},y={1}",endState.ValueList["x"],endState.ValueList["y"]);

        
    }
}


結果

実行結果です。全然ゴール状態に近づいていませんね。 なぜならば、今回はルールをすべて機械的に適用させただけなのでただの人工無能です。 このルールの適用順を考えるのが人工知能です。 今回は人工知能をつくる以前の問題をプログラムで表現したという感じです。

f:id:garicchi:20140525202417p:plain