(別解) Pythonで川渡り問題「宣教師と人喰い」を解く 【遺伝的アルゴリズム】

## 執筆の動機
私の記事にコメントをくださった方の、過去記事（人気の投稿）を眺めていて、「宣教師と人喰い」問題を知りました。典型的な探索問題と言えそうですが、遺伝的アルゴリズムというヒューリスティクスな探索手法を適用するとどのような結果が得られるか、試してみたくなりました。

## 先行記事
Qiitaでこの問題を解いた記事は以下の4つあるようです。いずれも、遺伝的アルゴリズムは採用されていません。

- [宣教師と人喰い人問題を解く](https://qiita.com/lovablepleiad/items/9ba7b8f4de96654fc0dd)
- [Pythonで川渡り問題「宣教師と人喰い」を解く 【探索的（発見的）プログラム・再帰】](https://qiita.com/kansiho/items/6cded7436241681caf00)
- [宣教師と人食い人種の問題をGolangで再帰するクロージャ使って書いてみた。](https://qiita.com/jun68ykt/items/2b7d788d21a4cc5c9a56)
- [(別解) Pythonで川渡り問題「宣教師と人喰い」を解く 【探索的（発見的）プログラム・再帰】](https://qiita.com/shiracamus/items/ce536aaad95932dbbfb5)

よって、本記事は、「宣教師と人喰い」問題を遺伝的アルゴリズムで解く、Qiita初の試みということになります。

## 宣教師と人喰い問題とは
>3人の宣教師と3人の人喰いが川の左岸にいます。1隻の2人乗りボートを使って、右岸に渡るにはどうすればよいでしょうか。どちらの岸でも、人喰いの人数が宣教師の人数よりも多くなると、宣教師は喰われてしまいます。2人乗りボートにはもちろん1人だけ乗ることもできます。1人（宣教師でも人喰いでもよい）は乗らないと動かすことはできません。--@kansihoさんの[記事](https://qiita.com/kansiho/items/6cded7436241681caf00)より

## 遺伝的アルゴリズム
>遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉（組み換え）・突然変異などの操作を繰り返しながら解を探索します。適応度は適応度関数によって与えられます。--[Wikipedia](https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0#%E6%A6%82%E8%A6%81)より

### なぜ遺伝的アルゴリズムを採用するのか？
GIGO（gavage in gavage out）という言葉があります。ガラクタを入れれば、ガラクタが出てくるという意味です。データ分析の分野で、質の良いデータを揃えることの重要性を説くのに使われます。

他方、遺伝的アルゴリズムの特徴を表すなら、GIVO（gavage in value out）とでも言えるでしょう。ガラクタのような初期世代から開始し、進化の過程を経て、最適解へと収束する様は、見ていて爽快ですし、作っていてやり甲斐があるというものです。私は、以下記事の執筆を通じて、その快感を知りました。

- [ムダにエボリューショナルな"hello, world"の出力方法(Python)](https://qiita.com/tanuk1647/items/9802e001549ca1582eb3)

つまり、楽しいから、このアルゴリズムを採用したということです。

## 遺伝子の検討
川渡りを終えるまでの手数を高々20と仮定し、一回の乗船人数を宣教師2ビット、人喰い2ビットで表現します。解の候補を表す遺伝子を、80ビットのビット列で表現するわけです。

初期世代の遺伝子はランダムに生成しますので、乗船人数が2人を超える遺伝子、岸辺に宣教師が1人しかいないのに2人乗船させようとする遺伝子など、「非合法」な遺伝子が多数生成されます。しかし、遺伝子生成の段階で、それらは排除しません。なぜなら、進化の過程でふるいにかけられるためです。

ところで、ある局面に対する手は「宣教師：0、人喰い：0」〜「宣教師：3、人喰い：3」の16種類。それを20回繰り返すわけですから、探索空間の広さは16の20乗です。これは1024の8乗とイコールですので、10の24乗に近しい、広大な探索空間となります。このように広大な探索空間の中から、果たして解を見つけることができるのでしょうか。

——それができるのです。そこが、ヒューリスティクスな探索手法のおもしろいところです。

## 適応度関数の検討
適応度fを以下関数で表します。cは正の定数、hは川渡りを終える（成功 or 失敗）までの、合法手の数です。

```math
f = \begin{cases}
      1 & (if cleared) \\
      1 - \dfrac{1}{c^h} & (otherwise)
    \end{cases}
```

そして、川渡りの成功、失敗を、以下のとおりに定義します。

- 成功
  - 左岸の人数が0人である
- 失敗
  - 左岸か右岸で人数がマイナスあるいは3人を超えた
  - 乗船人数が2人を超えた
  - 宣教師が人喰いに喰われた
  - 同一局面が2回現れた（千日手）
  - 手数が20に達したが、川渡りが完了しなかった

「千日手」も失敗とみなします。そして、千日手を失敗とする条件下で、合法手を重ねるということは、それだけ解に近づいているだろう、という考えを表現したのが、先ほどの適応度関数です。逆に言うと、合法手を重ねつつ解を避けるのは不可能ではないか、と考えたのです。

## アルゴリズムの検討
[hello, world](https://qiita.com/tanuk1647/items/9802e001549ca1582eb3)を作ったときの設計を継承し、以下内容としました。

- 繁殖時、子供はビットごとに、両親いずれかの遺伝子を受け継ぐ。遺伝子の受け継ぎ後、突然変異が発生する。突然変異は、子供の各ビットごとに一定確率で値を反転させるものである。

- 個体の集団は、適応度が上位20%のエリートと、残り80%の非エリートに分かれる。エリート全員に繁殖の機会が与えられるが、その相手は非エリートである。これは、遺伝子の多様性を保つため、および、近親相姦のタブーを表現するためである。なお、雌雄の区別はないものとする。エリート1体が複数の子供を残す。

- 次世代に残る候補は、以下の中から、適応度の高い順に集団の上限サイズまで選ばれる。
  1. エリートのうち12/15の確率でランダムに選ばれた個体
  1. 子供
  1. 非エリートのうち3/15の確率でランダムに選ばれた個体

- 集団には「破局」が発生する。破局発生時は、現世代のごく一部が生き残り、現世代の遺伝情報を引き継がない新個体群と共に、次世代を構成する。これは、隕石の衝突などの大惨事を模したものである。

- 進化をつかさどる何かが状況を監視しており、集団の進化が停滞した際には、破局を引き起こし、さらなる進化を促す。

[パレートの法則](https://ja.wikipedia.org/wiki/%E3%83%91%E3%83%AC%E3%83%BC%E3%83%88%E3%81%AE%E6%B3%95%E5%89%87)を取り入れたところや、局所的最適解からの脱出を図る「破局」の仕組みを取り入れたところが、特徴と言えるでしょう。

## コーディング

書いたコードをいくつか抜粋します。全容は、[Github](https://github.com/tanuk1647/missionaries-cannibals-problem-with-ga)でどうぞ。

### Group
宣教師と人喰いの集団を表します。@shiracamusさんの[記事](https://qiita.com/shiracamus/items/ce536aaad95932dbbfb5)を参考にしたというのも事実ですし、美しく表現しようとしたらここに落ち着いたというのもまた事実です。ただのタプルで表すよりも、クラス化して、関連する演算をまとめることにより、コードの可読性が良くなるはずです。

```python
class Group():
    """Group of missionaries and cannibals"""
    def __init__(self, missionaries, cannibals):
        self.reset(missionaries, cannibals)
    
    def reset(self, missionaries, cannibals):
        self.missionaries = missionaries
        self.cannibals = cannibals
    
    def __str__(self):
        return  f'(m:{self.missionaries}, c:{self.cannibals})'
    
    def __add__(self, other):
        assert isinstance(other, Group)
        return Group(self.missionaries + other.missionaries,
                     self.cannibals + other.cannibals)
    
    def __sub__(self, other):
        assert isinstance(other, Group)
        return Group(self.missionaries - other.missionaries,
                     self.cannibals - other.cannibals)
    
    def is_valid(self):
        return 0 <= self.missionaries <= 3 and 0 <= self.cannibals <= 3
    
    def is_capacity_over(self):
        return not (1 <= (self.missionaries + self.cannibals) <= 2)
    
    def is_safe(self):
        return self.missionaries == 0 or self.missionaries >= self.cannibals
    
    def is_empty(self):
        return self.missionaries == self.cannibals == 0
```

### MCProblem
宣教師と人喰い問題のビジネスロジックを詰め込んだクラスです。辞書を使ってswitchしているのは、@hiratarichさんの[記事](https://qiita.com/hiratarich/items/839bcf7dff2921f3ef31#python%E3%81%AE%E7%AB%8B%E5%A0%B4%E3%81%8B%E3%82%89%E3%81%99%E3%82%8B%E3%81%A8switch%E6%96%87%E3%81%AF%E3%81%84%E3%82%89%E3%81%AA%E3%81%84)の真似事です。また、探索したノードの数を保持し、後から参照できるようにしています。

```python
class MCProblem():
    """Missionaries and cannibals problem"""
    _LEFT_BANK = 0
    _RIGHT_BANK = 1
    
    class Result(Enum):
        ILLEGAL_MOVE = auto()
        CAPACITY_OVER = auto()
        EATEN_BY_CANNIBALS = auto()
        REPETITION = auto()
        LEGAL_MOVE = auto()
        GAME_CLEAR = auto()
    
    def __init__(self):
        self.searched_nodes = 0
        self.reset()
    
    def reset(self):
        self._left_bank = Group(3, 3)
        self._right_bank = Group(0, 0)
        self._boat_position = self._LEFT_BANK
        self._records = [self._record()]
    
    def _record(self):
        return hash((str(self._left_bank),
                     str(self._right_bank), self._boat_position))
    
    _boat = {_LEFT_BANK : '=  ', _RIGHT_BANK: '  ='}
    
    def __str__(self):
        boat = self._boat[self._boat_position]
        left_bank = str(self._left_bank)
        right_bank = str(self._right_bank)
        return left_bank + boat + right_bank
    
    def _forward(self, passengers, verbose):
        self._left_bank -= passengers
        self._right_bank += passengers
        self._boat_position = self._RIGHT_BANK
        if verbose:
            print(f'    ==(m:{passengers.missionaries},'
                  f' c:{passengers.cannibals})=>')
    
    def _backward(self, passengers, verbose):
        self._left_bank += passengers
        self._right_bank -= passengers
        self._boat_position = self._LEFT_BANK
        if verbose:
            print(f'    <=(m:{passengers.missionaries},'
                  f' c:{passengers.cannibals})==')
    
    _cross_the_river = {_LEFT_BANK : _forward,
                        _RIGHT_BANK: _backward}
    
    def _move(self, passengers, verbose):
        self._cross_the_river[self._boat_position](self, passengers, verbose)
        
        if not (self._left_bank.is_valid() and self._right_bank.is_valid()):
            return self.Result.ILLEGAL_MOVE
        
        if passengers.is_capacity_over():
            return self.Result.CAPACITY_OVER
        
        if not (self._left_bank.is_safe() and self._right_bank.is_safe()):
            return self.Result.EATEN_BY_CANNIBALS
        
        if self._record() in self._records:
            return self.Result.REPETITION
        
        if self._left_bank.is_empty():
            return self.Result.GAME_CLEAR
        
        self._records.append(self._record())
        return self.Result.LEGAL_MOVE
    
    _countup = {Result.ILLEGAL_MOVE: 0, Result.CAPACITY_OVER: 0,
                Result.EATEN_BY_CANNIBALS: 0, Result.REPETITION: 0,
                Result.LEGAL_MOVE: 1, Result.GAME_CLEAR: 1}
    
    def moves(self, missionaries, cannibals, verbose=False):
        assert len(missionaries) == len(cannibals)
        self.reset()
        legal_moves = 0
        for i in range(len(missionaries)):
            if verbose: print(self)
            result = self._move(Group(missionaries[i], cannibals[i]), verbose)
            self.searched_nodes += 1
            legal_moves += self._countup[result]
            if result == self.Result.LEGAL_MOVE:
                continue
            break
        if verbose: print(self)
        return result, legal_moves
```

### Individual
個体を表すクラスです。適応度順でソート可能なように、[拡張比較(rich comparison)メソッド](https://docs.python.jp/3/reference/datamodel.html#object.__lt__)を実装しているのが特徴でしょうか。また、遺伝子をビット列で表現しているので、ビット操作が頻出しています。

```python
class Individual():
    """Individual that stands for the answer of the problem"""
    _GENE_SIZE = 80
    
    _MASK_UINT2 = 0b11
    _SHIFT_UINT2 = 2
    
    _MUTATE_PROBABILITY = 0.05
    
    def __init__(self, mc_problem, gene=None):
        if gene is None:
            self.gene = random.getrandbits(self._GENE_SIZE)
        else:
            assert 0 <= gene < 2 ** self._GENE_SIZE
            self.gene = gene
        self._mc_problem = mc_problem
        
        # at first, we are trying to parse a gene
        gene = self.gene
        
        self.missionaries = [0] * (self._GENE_SIZE // 4)
        self.cannibals = [0] * (self._GENE_SIZE // 4)
        
        for i in range(self._GENE_SIZE // 4):
            self.missionaries[i] = (gene & self._MASK_UINT2)
            gene = gene >> self._SHIFT_UINT2
        
        for i in range(self._GENE_SIZE // 4):
            self.cannibals[i] = (gene & self._MASK_UINT2)
            gene = gene >> self._SHIFT_UINT2
        
        # next, calculate the fitness
        self.calc_fitness()
    
    def _formula1(self):
        return 1. - (1. / 1.4 ** self.legal_moves)
    
    def _formula2(self):
        return 1.
    
    _fitness_from = {MCProblem.Result.ILLEGAL_MOVE      : _formula1,
                     MCProblem.Result.CAPACITY_OVER     : _formula1,
                     MCProblem.Result.EATEN_BY_CANNIBALS: _formula1,
                     MCProblem.Result.REPETITION        : _formula1,
                     MCProblem.Result.LEGAL_MOVE        : _formula1,
                     MCProblem.Result.GAME_CLEAR        : _formula2}
    
    def calc_fitness(self):
        self.result, self.legal_moves = \
        self._mc_problem.moves(self.missionaries, self.cannibals)
        self.fitness = self._fitness_from[self.result](self)
    
    def _is_valid_operand(self, other):
        return hasattr(other, 'fitness')
    
    def __eq__(self, other):
        if not self._is_valid_operand(other):
            return NotImplemented
        return self.fitness == other.fitness
    
    def __ne__(self, other):
        if not self._is_valid_operand(other):
            return NotImplemented
        return self.fitness != other.fitness
    
    def __lt__(self, other):
        if not self._is_valid_operand(other):
            return NotImplemented
        return self.fitness < other.fitness
    
    def __le__(self, other):
        if not self._is_valid_operand(other):
            return NotImplemented
        return self.fitness <= other.fitness
    
    def __gt__(self, other):
        if not self._is_valid_operand(other):
            return NotImplemented
        return self.fitness > other.fitness
    
    def __ge__(self, other):
        if not self._is_valid_operand(other):
            return NotImplemented
        return self.fitness >= other.fitness
    
    def __str__(self):
        return f'gene: {self.gene}'
    
    def mate(self, other, mc_problem):
        """Give birth to a child"""
        assert isinstance(other, Individual)
        
        child_gene = 0
        self_gene = self.gene
        other_gene = other.gene
        
        # inherits from parents
        mask_mate = random.getrandbits(self._GENE_SIZE)
        self_gene = self_gene & mask_mate
        other_gene = other_gene & ~mask_mate
        child_gene = self_gene | other_gene
        
        # genetic mutation
        mask_mutation = 0
        for _ in range(self._GENE_SIZE):
            mask_mutation = mask_mutation << 1
            if random.random() <= self._MUTATE_PROBABILITY:
                mask_mutation = mask_mutation | 0b1
        child_gene = child_gene ^ mask_mutation
        
        return Individual(mc_problem, child_gene)
```

### Population
個体の集団を表すクラスです。個体をリストで保持しているので、リスト操作が頻出しています。

```python
class Population():
    """Group of individuals"""
    _FERTILITY_RATE = 10
    _CATASTOROPHE_DAMAGE = 100
    
    def __init__(self, mc_problem, population_size):
        self._mc_problem = mc_problem
        self._population_size = population_size
        self.generation = [Individual(self._mc_problem)
                              for _ in range(self._population_size)]
        self.generation.sort(reverse=True)
        self.generation_number = 0
    
    def next_generation(self):
        self.generation_number += 1
        
        # divide individuals into elites and non-elites
        pareto = self._population_size // 5
        elites = self.generation[: pareto]
        non_elites = self.generation[pareto :]
        
        # all the elite to have a chance to marry non-elite
        children = []
        for parent1 in elites:
            parent2 = random.choice(non_elites)
            for _ in range(self._FERTILITY_RATE):
                children.append(parent1.mate(parent2, self._mc_problem))
        
        # choose individuals to survive
        elites = random.sample(elites, 12 * len(elites) // 15)
        non_elites = random.sample(non_elites, 3 * len(non_elites) // 15)
        self.generation = elites + children + non_elites
        self.generation.sort(reverse=True)
        self.generation = self.generation[: self._population_size]
        
        # logging the generation
        min_fitness = self.generation[-1].fitness
        max_fitness = self.generation[0].fitness
        mean_fitness = mean(i.fitness for i in self.generation)
        median_fitness = self.generation[self._population_size // 2].fitness
        
        return Aspect(min_fitness, max_fitness, mean_fitness, median_fitness)
    
    def catastrophe(self):
        """Some kind of natural disaster that would cause a wider evolution"""
        survivor_num = self._population_size // self._CATASTOROPHE_DAMAGE
        survivor = random.sample(self.generation, survivor_num)
        newcomer = [Individual(self._mc_problem)
                        for _ in range(self._population_size)]
        self.generation = survivor + newcomer
        self.generation.sort(reverse=True)
        self.generation = self.generation[: self._population_size]
```

### EvolutionController
進化をつかさどる何かです。メインループを回しながら、可視化の指示と、「破局」のチェックを行います。for文にelse節を付けられるのは、Pythonのおもしろいところですね。

```python
class EvolutionController():
    """Some existence that controlls the evolution"""
    def __init__(self, mc_problem, population_size=100, epochs=1000,
                 patience=30, verbose=0, graph=False):
        self._mc_problem = mc_problem
        self._population = Population(self._mc_problem, population_size)
        self._epochs = epochs
        self._patience = patience 
        self._memory = deque([], patience)
        self._graph = graph
        if self._graph: self._data4graph = Data4Graph()
        self._outmgr = OutputManager(verbose)
    
    def start(self):
        """Start the evolution"""
        for epoch in range(1, self._epochs + 1):
            aspect = self._population.next_generation()
            top1 = self._population.generation[0]
            if aspect.max == 1.:
                answer = (top1.missionaries[:top1.legal_moves],
                          top1.cannibals[:top1.legal_moves])
                self._outmgr.success(self._population.generation_number,
                                     aspect.max, top1.legal_moves,
                                     self._mc_problem.searched_nodes,
                                     str(top1), *answer)
                # print the answer
                self._mc_problem.reset()
                self._mc_problem.moves(*answer, verbose=True)
                
                if self._graph:
                    self._data4graph.append(aspect)
                    visualize(self._data4graph)
                break
            else:
                self._outmgr.continue_(self._population.generation_number,
                                       aspect.max, top1.legal_moves)
                if self._graph:
                    self._data4graph.append(aspect)
                
                # catastrophe check
                self._memory.append(aspect.max)
                if self._memory.count(self._memory[-1]) == self._patience:
                    self._outmgr.catastrophe()
                    self._population.catastrophe()
        else:
            self._outmgr.epoch_over(self._population.generation_number,
                                    aspect.max,
                                    self._population.generation[0].legal_moves)
            if self._graph:
                visualize(self._data4graph)
```

## 実行結果
### 初期世代
以下に、ランダムに生成した10個体が、どのような解を表しているかを示します。

```
(m:3, c:3)=  (m:0, c:0)
    ==(m:2, c:2)=>
(m:1, c:1)  =(m:2, c:2)
Result.CAPACITY_OVER
------------------
(m:3, c:3)=  (m:0, c:0)
    ==(m:2, c:2)=>
(m:1, c:1)  =(m:2, c:2)
Result.CAPACITY_OVER
------------------
(m:3, c:3)=  (m:0, c:0)
    ==(m:0, c:1)=>
(m:3, c:2)  =(m:0, c:1)
    <=(m:1, c:0)==
(m:4, c:2)=  (m:-1, c:1)
Result.ILLEGAL_MOVE
------------------
(m:3, c:3)=  (m:0, c:0)
    ==(m:0, c:1)=>
(m:3, c:2)  =(m:0, c:1)
    <=(m:0, c:1)==
(m:3, c:3)=  (m:0, c:0)
Result.REPETITION
------------------
(m:3, c:3)=  (m:0, c:0)
    ==(m:1, c:0)=>
(m:2, c:3)  =(m:1, c:0)
Result.EATEN_BY_CANNIBALS
------------------
(m:3, c:3)=  (m:0, c:0)
    ==(m:1, c:2)=>
(m:2, c:1)  =(m:1, c:2)
Result.CAPACITY_OVER
------------------
(m:3, c:3)=  (m:0, c:0)
    ==(m:1, c:1)=>
(m:2, c:2)  =(m:1, c:1)
    <=(m:3, c:1)==
(m:5, c:3)=  (m:-2, c:0)
Result.ILLEGAL_MOVE
------------------
(m:3, c:3)=  (m:0, c:0)
    ==(m:2, c:3)=>
(m:1, c:0)  =(m:2, c:3)
Result.CAPACITY_OVER
------------------
(m:3, c:3)=  (m:0, c:0)
    ==(m:2, c:2)=>
(m:1, c:1)  =(m:2, c:2)
Result.CAPACITY_OVER
------------------
(m:3, c:3)=  (m:0, c:0)
    ==(m:1, c:2)=>
(m:2, c:1)  =(m:1, c:2)
Result.CAPACITY_OVER
------------------
```

また、以下は、ランダムに生成した100個体の統計です。

![figure0](https://github.com/tanuk1647/mc-problem-with-ga/raw/master/figures/mc-problem-with-ga-0000.png)

![figure1](https://github.com/tanuk1647/mc-problem-with-ga/raw/master/figures/mc-problem-with-ga-0001.png)

「ガラクタ」ばかりであることが、わかります。このようなガラクタが、進化の過程を経て、価値あるものへと生まれ変わるのでしょうか。

### 進化の結果
ランダムに生成した100個体から開始し、51世代目で、正解を見つけることができました。10の24乗に近しい広大な探索空間から、39,261のノードを探索することで、正解を発見できています。

```
(introduction)bash-3.2$ python mc_problem_with_ga.py
51: 1.0(11)
searched_nodes: 39261
gene: 858311312441180971607557
m: [1, 1, 0, 0, 2, 1, 2, 0, 0, 0, 0]
c: [1, 0, 2, 1, 0, 1, 0, 1, 2, 1, 2]
(m:3, c:3)=  (m:0, c:0)
    ==(m:1, c:1)=>
(m:2, c:2)  =(m:1, c:1)
    <=(m:1, c:0)==
(m:3, c:2)=  (m:0, c:1)
    ==(m:0, c:2)=>
(m:3, c:0)  =(m:0, c:3)
    <=(m:0, c:1)==
(m:3, c:1)=  (m:0, c:2)
    ==(m:2, c:0)=>
(m:1, c:1)  =(m:2, c:2)
    <=(m:1, c:1)==
(m:2, c:2)=  (m:1, c:1)
    ==(m:2, c:0)=>
(m:0, c:2)  =(m:3, c:1)
    <=(m:0, c:1)==
(m:0, c:3)=  (m:3, c:0)
    ==(m:0, c:2)=>
(m:0, c:1)  =(m:3, c:2)
    <=(m:0, c:1)==
(m:0, c:2)=  (m:3, c:1)
    ==(m:0, c:2)=>
(m:0, c:0)  =(m:3, c:3)
```

![figure2](https://github.com/tanuk1647/mc-problem-with-ga/raw/master/figures/mc-problem-with-ga-0002.png)

### その他の正解
7回の試行で、4パターンの正解を見つけることができました。（残りの3回は既知のパターン。）

```
(introduction)bash-3.2$ python mc_problem_with_ga.py
39: 1.0(11)
searched_nodes: 27718
gene: 153275312797679522948608
m: [0, 0, 0, 0, 2, 1, 2, 0, 0, 1, 1]
c: [2, 1, 2, 1, 0, 1, 0, 1, 2, 0, 1]
(m:3, c:3)=  (m:0, c:0)
    ==(m:0, c:2)=>
(m:3, c:1)  =(m:0, c:2)
    <=(m:0, c:1)==
(m:3, c:2)=  (m:0, c:1)
    ==(m:0, c:2)=>
(m:3, c:0)  =(m:0, c:3)
    <=(m:0, c:1)==
(m:3, c:1)=  (m:0, c:2)
    ==(m:2, c:0)=>
(m:1, c:1)  =(m:2, c:2)
    <=(m:1, c:1)==
(m:2, c:2)=  (m:1, c:1)
    ==(m:2, c:0)=>
(m:0, c:2)  =(m:3, c:1)
    <=(m:0, c:1)==
(m:0, c:3)=  (m:3, c:0)
    ==(m:0, c:2)=>
(m:0, c:1)  =(m:3, c:2)
    <=(m:1, c:0)==
(m:1, c:1)=  (m:2, c:2)
    ==(m:1, c:1)=>
(m:0, c:0)  =(m:3, c:3)
```

```
(introduction)bash-3.2$ python mc_problem_with_ga.py
51: 1.0(11)
searched_nodes: 39570
gene: 496536938202681694234117
m: [1, 1, 0, 0, 2, 1, 2, 0, 0, 1, 1]
c: [1, 0, 2, 1, 0, 1, 0, 1, 2, 0, 1]
(m:3, c:3)=  (m:0, c:0)
    ==(m:1, c:1)=>
(m:2, c:2)  =(m:1, c:1)
    <=(m:1, c:0)==
(m:3, c:2)=  (m:0, c:1)
    ==(m:0, c:2)=>
(m:3, c:0)  =(m:0, c:3)
    <=(m:0, c:1)==
(m:3, c:1)=  (m:0, c:2)
    ==(m:2, c:0)=>
(m:1, c:1)  =(m:2, c:2)
    <=(m:1, c:1)==
(m:2, c:2)=  (m:1, c:1)
    ==(m:2, c:0)=>
(m:0, c:2)  =(m:3, c:1)
    <=(m:0, c:1)==
(m:0, c:3)=  (m:3, c:0)
    ==(m:0, c:2)=>
(m:0, c:1)  =(m:3, c:2)
    <=(m:1, c:0)==
(m:1, c:1)=  (m:2, c:2)
    ==(m:1, c:1)=>
(m:0, c:0)  =(m:3, c:3)
```

```
(introduction)bash-3.2$ python mc_problem_with_ga.py
76: 1.0(11)
searched_nodes: 57314
gene: 347871457183739615913472
m: [0, 0, 0, 0, 2, 1, 2, 0, 0, 0, 0]
c: [2, 1, 2, 1, 0, 1, 0, 1, 2, 1, 2]
(m:3, c:3)=  (m:0, c:0)
    ==(m:0, c:2)=>
(m:3, c:1)  =(m:0, c:2)
    <=(m:0, c:1)==
(m:3, c:2)=  (m:0, c:1)
    ==(m:0, c:2)=>
(m:3, c:0)  =(m:0, c:3)
    <=(m:0, c:1)==
(m:3, c:1)=  (m:0, c:2)
    ==(m:2, c:0)=>
(m:1, c:1)  =(m:2, c:2)
    <=(m:1, c:1)==
(m:2, c:2)=  (m:1, c:1)
    ==(m:2, c:0)=>
(m:0, c:2)  =(m:3, c:1)
    <=(m:0, c:1)==
(m:0, c:3)=  (m:3, c:0)
    ==(m:0, c:2)=>
(m:0, c:1)  =(m:3, c:2)
    <=(m:0, c:1)==
(m:0, c:2)=  (m:3, c:1)
    ==(m:0, c:2)=>
(m:0, c:0)  =(m:3, c:3)
```

初手と10手目で分岐し、次の手で合流していることがわかります。また、パターン3と4は、6手目を軸に前後に対称形となっているのが、とても美しいですね。

![figure3](https://github.com/tanuk1647/mc-problem-with-ga/raw/master/figures/mc-problem-with-ga-0003.png)

出力を最小限にすれば、一回あたりの実行時間は1.11秒程度ですので、必要なだけ回し続ければ、統計的に全パターンを洗い出せたと言えることでしょう。なお、[先行記事](https://qiita.com/shiracamus/items/ce536aaad95932dbbfb5)によると、この4パターンですべてのようです。

## まとめ
重要なのは、私自身がこの問題の解き方を知らない、ということです。簡単な洞察——合法手を重ねれば解に近づくだろうという考え——、および、合法手の定義を、適応度関数を通じて遺伝的アルゴリズムに教えただけなのです。それで解が得られるのですから、私の無能を補って余りある「人工知能」です。人工知能の可能性を示したと言えるでしょう。

## おまけ
とはいえ、自力で解かないまま終わるのも悔しいので、この問題の解き方を考えてみました。結論的には、以下のような図を描くと良いと思います。簡単のため、左岸の状態のみにしぼって考えます。座標(3, 3)から(0, 0)を目指すわけです。

![figure4](https://github.com/tanuk1647/mc-problem-with-ga/raw/master/figures/mc-problem-with-ga-0004.png)

青の×は左岸で、赤の×は右岸で宣教師が喰われてしまうので、NGです。また、奇数番（初手、3手目、5手目…）では左か下に、偶数番では右か上に動けます。一度に動けるのは1か2。番ちがい（奇数か偶数か）に限り、同一地点の訪問は1回のみ許されます。

このように問題を図解すると、意外と簡単に解けます。秋の夜長に、ぜひトライしてみてください！