宣教師と人食い人種の問題をGolangで再帰するクロージャ使って書いてみた。

1.背景

　いま、プログラミング言語 Go を読んでいて、これの「5.6節 無名関数」でクロージャを
再帰させるコード例が出ていたのを見て、ふと、
「これと同じように、クロージャ使って、『宣教師と人食い人種問題』を再帰で解くのをGoで書いてみよう」
と思い立って書いてみました。
　今回書いたソースコードは、https://github.com/jun68ykt/m-and-c に上げてあります。

2.「宣教師と人食い人種」問題とは

2.1　初めて聞く人のために

「宣教師と人食い人種」問題を初めて聞く人のために説明すると、以下の(1)から(3)で設定される問題です。

　　(1) 川岸の片側に宣教師が3人と人食い人種が3人いて、2人まで乗れるボートがある。
　　

　　(2) 宣教師も人食い人種もともにボートを漕ぐことができて、何往復かすることで6人全員が
　　 　向こう岸に渡りたい。（川に入って歩いたり泳いだりして渡るのはナシで。）

　　　以下の図はこの様子を描いたもので、Mは宣教師（Missionary)、C は人食い人種（Cannibal）を表す。

　　　　なお上記の図で、矢印の先に「ボートを使って何往復かして、全員が向こう岸に行きたい。」と書いて
　　　あるけれども、「何往復」というのは間違いで、正しくは「ボートを使って何回か行き来して、全員が
　　　向こう岸に行きたい。」です。なぜなら最後に片道一回が必ずあるからです。

　　　 　以下、説明の便宜上、最初に6人がいる方の岸を、上の図にそって左岸といい、
　　　渡って行きたいほうの岸を右岸という。
　
　　(3) 何回かボートを往復（＋最後の片道一回）させて、彼らは右岸に渡ろうとするが、
　　　注意しなければならないのは、

　　 　左岸、右岸どちらにおいても、もし、人食い人種の人数のほうが宣教師の人数よりも多くなると、
　　 　宣教師は人食い人種に食われてしまう

　　　ということ。

　　　　例えば、上記(2)の初期状態から、宣教師2名がボートに乗って右岸に行こうとすると、
　　　左岸において、宣教師が1人、人食い人種が3人の状況になり、左岸で一人残された宣教師は
　　　人食い人種に食われてしまう。以下の図では、左岸の宣教師が、3人の人食い人種に襲われて
　　　食われてしまうことを表している。

　　　もうひとつの例として、以下のような状態の場合を考える。

　　　

　　　このときに、もし次に右岸から人食い人種が1人だけでボートに乗って、左岸に行ったとする。

　　　　すると、ボートが左岸に着いて、乗っていた人食い人種が岸に降りたとき、左岸では
　　　人食い人種が2人、宣教師が1人になり、人食い人種のほうが多いので宣教師が襲われる。

　　　　このように、ボートに乗った宣教師も人食い人種も、川を渡りきったら、いったんは
　　　全員がボートから降りて、降りた状態での人数によって、人食い人種が宣教師を襲うか
　　　どうかを判定するものとする。（つまり、ボートに2人乗って降りるのは1人だけに
　　　しておく、ということはできない。そういうルール）

　【問題】
　　上記 (1)〜(3) で設定された状況とルールにそって、何回かボートを行き来させれば、全員が
　無事に右岸に渡れるだろうか？渡れるならば、毎回のボートの行き来で、宣教師が何人、
　人食い人種が何人乗ればよいのかを示せ。

・・・というのが、この問題になります。

2.2　補足

　なお、この問題は、WikipediaのMissionaries_and_cannibals_problem に、

a well-known toy problem in artificial intelligence

と書いてあるとおり、人工知能の勉強をしていると、どこかしらで目にするクイズだったりします。
　かくいう私も、第5世代コンピュータプロジェクト ※1 の終焉期に、システム科学を専攻する学生として Prolog の勉強をしていて、それ関係の書籍 ※2に出ていて知りました。

3. Golang で解いてみます。

　それでは、Golang で解を求めるアルゴリズムを書いていきます。

3.1　川岸の状態を表す構造体

　宣教師の人数を m 、人食い人種の人数を c として、以下の構造体 RiverSideを定義します。

type RiverSide struct {
    m, c int
}

3.2　両岸の状態と、ボートがどちらにあるかを表す構造体

　全体の状況を表す構造体 State を以下のように定義します。

type State struct {
    left, right RiverSide
    boat string // "left" or "right"
}

フィールド変数が何を表すかというと、

• left と right は、それぞれ左岸、右岸を表します。
• boatは文字列で、ボートが左岸にあるとき "left" 、右岸にあるとき"right"になるものとします。

3.3　初期状態と目標状態

　上記の State構造体のインスタンスとして、初期状態と目標(Goal）状態を構造体リテラルで
書くと、以下のようになります。

初期状態

var initialState State = State{
    left:  RiverSide{3, 3},
    right: RiverSide{0, 0},
    boat:  "left",
}

目標状態

var goalState State = State{
    left:  RiverSide{0, 0},
    right: RiverSide{3, 3},
    boat:  "right",
}

3.4　オペレータ

　　この手の問題をAI分野では探索問題といい、探索問題において、ある状態から別の状態に
　変化させる手段のことをオペレータ（作用素）といいます。👉「探索問題 オペレータ」でググる。
　　では、この問題においてオペレータは何かといえば、ボートによる、宣教師または人食い人種の
　一回（片道）の移動です。この一回の移動を特徴づけるのは、そこに宣教師が何人、人食い人種が
　何人乗っているのかという人数ですので、オペレータを表す構造体 Operator を以下のように定義
　します。

オペレータ

type Operator struct {
    m, c int
}

　　次に、実際に選択可能なオペレータの集合を考えます。
　　この問題では、ボートには2人までしか乗ることができず、また、誰も乗らなければ移動はできないので、
　以下のように、選択可能なオペレータの集合は5個の要素を持つことになります。

　選択可能なオペレータの集合　＝
　｛ 宣教師2人がボートに乗る, 
　　 宣教師1人だけでボートに乗る, 
　　 宣教師1人と人食い人種1人がボートに乗る, 
　　 人食い人種1人だけでボートに乗る,  
　　 人食い人種2人でボートに乗る }

　　上記の集合をどうプログラムで書くかですが、Goでは、(Pythonのsetのような）集合を表す型が標準で
　用意されていないので、Operatorの配列で表すことにして、以下の Operatorsを定義します。

選択可能なオペレータの配列

var Operators = [5]Operator{
    {2, 0},
    {1, 0},
    {1, 1},
    {0, 1},
    {0, 2},
}

3.5　状態が妥当であるかの検証

　「どちらの岸でも、人食い人種の人数が宣教師の人数を上回ると、人食い人種が宣教師を
　食べてしまうので、このような状態は避けなければならない」
　というルールは、状態の妥当性を検証するバリデータとして、以下のように実装しました。

状態の妥当性を検証する関数

func valid(state State) bool {
    switch {
    case state.left.m < 0 || state.left.c < 0 || state.right.m < 0 || state.right.c < 0:
        return false
    case state.left.m > 0 && state.left.c > state.left.m:
        return false
    case state.right.m > 0 && state.right.c > state.right.m:
        return false
    default:
        return true
    }
}

　　上記には3つの caseがありますが、2つ目と3つ目の caseで、
　「人食い人種が宣教師を食べてしまう状況が発生するときは、falseを返す」
　ようにしています。
　　1つ目のcaseは、いかなる状態でも、両岸の宣教師、人食い人種を表す m と c は負数に
　なってはならないという自明な制約を表しています。

3.6　状態遷移関数

　下準備の最後に重要なのは、この状態遷移関数です。これによって、この問題は有限オートマトン を
構成することになるといえます。
　ここでは、現在の状態 currentState とオペレータ op を引数として、遷移先の状態を表す nextStateと、遷移が成功したことを示す bool値の okを返す関数を、以下のように定義しました。

状態遷移関数

func stateTransition(currentState State, op Operator) (nextState State, ok bool) {

    var from, to *RiverSide

    if currentState.boat == "left" {
        from, to = &currentState.left, &currentState.right
        nextState.boat = "right"
        nextState.right = RiverSide{ to.m + op.m, to.c + op.c }
        nextState.left = RiverSide{ from.m - op.m, from.c - op.c }
    } else {
        from, to = &currentState.right, &currentState.left
        nextState.boat = "left"
        nextState.left = RiverSide{ to.m + op.m, to.c + op.c }
        nextState.right = RiverSide{ from.m - op.m, from.c - op.c }
    }

    ok = valid(nextState)

    return
}

3.7　解を得るアルゴリズムを書く

　3.6 までに書いた構造体や関数を使って、解を得るアルゴリズムを書いていきます。
なお、これから示すコードは、

func main() {

}

の中に書いていくものとします。
　

3.7.1　得られた解を保存しておくオペレータのスライス

　以下のように、空のスライスを用意しておきます。

solution := []Operator{}

　

3.7.2　探索時に一度たどった状態を記録しておくマップ

　Stateをキーとして boolを値とするマップで、一度たどったStateを記録するものとします。

history := map[State]bool{ initialState: true }

　
　　Go の構造体は、そのすべてのフィールドが比較可能であれば、その構造体自体も比較可能です。これに沿えば、先に定義したRiverSideは比較可能であり、したがってStateも比較可能なので、（JAVAの equals()メソッドのような同値メソッドを別途作らなくても）そのままマップのキーに使える。これはなかなかイイ。
　

3.7.3　与えられた状態から目標状態に到達する解を探す関数

　これを書くのが、冒頭の 1.背景 に書いた、そもそもの動機でした。
色々な書き方があると思いますが、以下のようにしてみました。

探索関数（クロージャ）

    var solve func(currentState State) bool

    solve = func(currentState State) bool {

        // もし、currentStateが目標状態と等しいなら、trueを返す。
        if currentState == goalState {
            return true
        }

        // 深さ優先探索(Depth-first search)で目標状態に至る解を探す。
        for _, op := range Operators {
            if nextState, ok := stateTransition(currentState, op); ok {
                if !history[nextState] {
                    history[nextState] = true
                    solution = append(solution, op)
                    if solve(nextState) {
                        return true
                    } else {
                        solution = solution[0 : len(solution)-1]
                    }
                }
            }
        }
        return false
    }

　　　ところで、上記の

    var solve func(currentState State) bool

    solve = func(currentState State) bool {
        // 関数本体・・・
    }
　　　　　　

　のところは、なんとなく冗長に思えて、一行で

    var solve = func(currentState State) bool {
        // 関数本体・・・
    }

　と書けたら、ちょっとうれしいのだけれど、このように書いて実行すると、

undefined: solve

　と叱られますね。

3.7.4　結果の出力

　もし、solve が問題を解くことができたら、解となるOperatorの列を保存してある
solutionを表示するようにします。

    if solve(initialState) {
        fmt.Printf("%+v\n", solution)
    }

4. 実行結果と解になっていることの確認

　以下は、上記のコードをGoファイル main.goに保存して、実行してみたところです。

$ go version
go version go1.9.2 darwin/amd64
$ go run main.go
[{m:1 c:1} {m:1 c:0} {m:0 c:2} {m:0 c:1} {m:2 c:0} {m:1 c:1} {m:2 c:0} {m:0 c:1} {m:0 c:2} {m:1 c:0} {m:1 c:1}]

　解として表示された、Operator のスライス　[{m:1 c:1} ・・・ ]　が本当に正解になっているかは、
手作業で絵を描いていけば確認できます。
　あるいは、Wikipedia Missionaries_and_cannibals_problem 　のページ中ほどの右側に出ている、解を図示したものと、上記のOperatorのスライス内容とが同じになっていることでも確認できます。
（図のキャプションには、Graphic of solution to Jealous Husbands River Crossing Problem とありますが
実質、同じことを問う問題です。）

5. ソースコード

　
　　今回書いたソースコードは、以下

　https://github.com/jun68ykt/m-and-c

　に上げておきましたので、この手の問題がお好きな方はご自由に手を入れて頂き、
　たとえば
　「深さ優先探索ではなく、幅優先探索にしてやんよ」
　みたいな感じで遊んでみてください。

脚注

※1：第5世代コンピュータ
　このプロジェクトがどういうもので、予算規模はどのくらいで、結果としてどういう経緯をたどったのかについては、池田信夫氏のブログエントリ「第5世代コンピュータ」の解説が分かりやすい。

※2：それ関係の書籍
　うろ覚えだが、その本はDEC-10 Prologの開発者R・コワルスキによる Logic for Problem Solvingの訳本「論理による問題の解法」培風館(1987/3/1) だった気がする。あ、いや。違うかもしれない。この本に出ていたのは、15パズルか、あるいはハノイの塔だったかもしれない。忘れた。なにせ、この本を修論のための副読本として読んだのは、四半世紀あまり昔の話だ。