Seiichi Yonezawa — How creativity is helped by failure

(単純な)AIについて考える

GWも目前に迫っていますが、実は今日観光旅行から無事戻ってきました。旅行最終日の今日たまたまこのような川渡り問題というものを見つけました。

「3人の宣教師と、3人の先住民が川岸にいる。2人まで乗れるボートがあり、ボートをこげるのはある先住民1人と宣教師1人だけである。どちらかの岸で先住民が宣教師より多くなってしまうと、先住民が宣教師を襲ってしまう。無事全員で渡り切るにはどうすればよいかを出力しなさい。」

普段Webのことばかり考えている私ですが、もっぱらアルゴリズムに関わるようなプログラミングは普段する機会もありません^1。しかし今ちょうど読んでいる本や、興味関心がだんだんAIにも向きつつあって、このような問題を解いてみようと思いました。……さて、いざ解こうと思ってみてもなかなかイメージが掴めません。というのも、単純にwhileループで正解までイテレーションを続けていくことはわかるのですが、ではこの問題の場合だと最初に宣教師と先住民を乗せたとして、先住民の数が多くなってしまった場合は新しいパターンを試行しなければなりません。頭の中で普段行なっているような試行方法ですが、コンピュータは人間のように融通が効きません。ただし、方法さえ教えてあげれば答えがみつかるまでの努力は厭わないのが健気なところです。なんとかしてこのコンピュータと無知なる私がどうやってこのような問題に取り組んでいけばよいでしょうか。

まずは問題に取り組むにあたって、今回はRubyを選びました。そして、問題に取り組む前に次のようなコードを用意してみます。

names = ['alice', 'bob', 'claire', 'david', 'eli', 'felix', 'gary']
verbs = ['ate', 'bought', 'cut', 'drawn', 'earned', 'fixed', 'got']
nouns = ['apple', 'banana', 'cherry pie', 'desk', 'frog', 'guiter']

よくコンピュータの例でアリスとボブという例えを耳にしますが、実はアルファベット順だということに最近気づきました。微妙にアレンジを加えていますが、それぞれ文章をつなげるとalice ate appleから始まり、gary got guiterまでのパターンがあります。途中でEから始まる名詞がないことに気づきましたが、可変長に対応させられるようにそのままにしてみました。

さて、このような例であれば特定のフレーズと等しくなるまで試行を続けるコードがかけるような気がします。

names = ['alice', 'bob', 'claire', 'david', 'eli', 'felix', 'gary']
verbs = ['ate', 'bought', 'cut', 'drawn', 'earned', 'fixed', 'got']
nouns = ['apple', 'banana', 'cherry pie', 'desk', 'frog', 'guiter']

i = 0

loop do
  phrases = [
    names[i % 7],
    verbs[i / 7 % 7],
    nouns[i / 7 / 7]
  ]

  break if phrases.join(' ') == 'claire cut cherry pie'

  i += 1
end

p i #=> 114

これで、あらかじめ与えられている文字列に対する組み合わせを探すことができるようになりました。現時点ではfelix ate deskみたいな不自然な組み合わせも出てきてしまったり、食べ物の時はaおよびanをつけ、それ以外はhisあるいはherをつけるなどのルールを加えたいなどの要望が出てくるかもしれません。上の橋渡し問題でも、例えばボートにのせた後は移動するといった行動の順序があるように派生をさせる必要が出てくると思います。ただ、今日は時間の都合上これ以上は続けられないので続編として近いうちに解法も考えていこうと思っています。