2018-05-03

One-Liner Game of Life

先々週くらいにアメリカのピッツバーグというところで、RailsConfというRailsのカンファレンスが行なわれていました。
日本でもデカ外人として知られているJonanが何人かのRubyistをつかまえて、交代でペアプログラミングをしてその動画を配信するという遊びをしていました。

https://www.twitch.tv/videos/251736888

私は夜中だというのにtwitterでたまたま見つけてしまって観ていました。
課題はConway's Geme of Lifeで日本だとライフゲームと呼ばれているやつです。プログラミング初心者の課題としてはとても良い課題です。
Jonanたちは設計を重視しているのか、きちんとクラスを定義してとても分りやすく綺麗なコードを書いていきます。(あとでビデオの最初のほうを観てみたら、テストファーストでやっているようでした。)
こういった小さな課題に対してきちんとプラクティスを適用してやってみるというのは、体験としてよいですね。コンテンツとしても面白いです。

夜中に一人で見ていると、けまらしさというか、楽しそうだなーといううらやましさとかあって、参加してみたくなりました。
こっちはひとりです。目先を変えていかなくては、コンテンツとしても、体験としても面白くなくなります。
そういうわけで、ワンライナーで書いてみました。(gist)

s=30;Array.new((s+2)*(s+2),0).tap{|g|(s*s).times{|i|[100,133,163,164,165].each{|i|g[i]=1}};100.times{s.times{|y|puts s.times.map{|x|g[x+s+3+y*(s+2)]==1??*:?.}.join};(s*s).times.map{|i|i+=i/s*2;[0,1,2,3,5,6,7,8].map{|x|g[i+x%3+x/3*2+x/3*s]}.sum.yield_self{|x|x==3?1:x==2?g[i+s+3]:0}}.tap{|n|(s*s).times{|i|g[i+s+3+i/s*2]=n[i]}};sleep(0.1);print"\e[#{s}A"}}

このプログラムでは30x30のフィールドをグライダーのパターンが斜めに飛びます。ライフゲームではこのようにパターンによって規則的な動きをするものがあります。

このプログラムで工夫した点は境界の処理です。
ゲームは各セルの周りのセルの状態によって進行します。つまり、各セルの周りのセルを見る必要がありますが、縁のセルに対しては境界値の処理が必要になります。
ナイーブに書くなら、境界を越えていないか条件判定するところですが、このような条件判定は長くなる傾向があります。
ここでは、ゲームの盤の周辺に1つ分余計に盤のデータを作ります。(余計にとった縁のデータは0で埋めておきます。)
そして、ゲームを進行したり、盤面を表示するときには縁を除いた真の盤面だけに対して処理をします。
盤面はもともと1次元の配列で取っているのでセルへのアクセスは行、列に対して1次元に変換する計算が必要になりますので、この計算を縁を考慮したものに変えればよいだけです。

実はこの方式は画像処理のコンボリューション計算でもよく使われる手法です。(ライフゲーム自体がコンボリューション計算の一種と言えます。)
コンボリューションといえば、最近話題のディープラーニングでも画像の認識問題によくCNN(Convolutional Neural Network)が使われます。
ライフゲームのようなベーシックな課題の中にも、高度な応用技術と共通のテクニックが使われたりすることがあります。面白いですね。