6x6リバーシの神
絶対に勝てない6x6リバーシを作りました。あなたは黒番、AIが白番です。
絶対に勝てない6x6リバーシを作りました！ ぜひ挑戦してみてくださいhttps://t.co/Ul5n3q9jMp
— Yusuke Endoh (@mametter) December 30, 2021
これは何？
6x6の盤面のリバーシは後手必勝 *1 であることが知られています。 このAIは白番（後手）で完璧にプレイします。つまり黒番のあなたは絶対に勝てません。無力感を楽しんでください。
技術的な話
このAIはWebAssemblyになっているので、全部あなたのブラウザの上で動いてます。真のサーバーレスです。
AIのソースコードはRustで書きました。わりと堅実なゲーム木探索になってます。UIは普通にTypeScriptとthree.jsで実装しました。
作った順に説明します。
盤面の表現
なにはともあれ、盤面を表すデータ構造を作りました（src/bitboard.rs）。
ファイル名の通り、ビットボードです。
Rustのu64（64ビット整数）を2つ使って1つの盤面を表現します（1つが黒石の位置、もう1つが白石の位置）。
着手可能数のカウントなどすべて、ビット演算を駆使してやります。 石をひっくり返す処理は探索性能に直結するのでがんばってます。 36マスすべてに特化したコードをマクロで生成してます（src/bitboard/flip.rs）。 ただし、最終的にWASMにするので、アセンブリを書くようなことはしてません。
ちなみにビットボードを選んだ理由は、そうしないとRustの所有権や借用がすごく面倒くさそうだったからです。
ビットボードならu64が2つだけなので、雑にCopyトレイトを実装しても大丈夫。
終盤のアルゴリズム
最初に書いた探索アルゴリズムは、単純なネガマックス法です。 これはゲーム終盤（空きマスが11個以下）の探索に使っています。
終盤の探索は、凝ったアルゴリズムより、定数オーダの最適化がよく効くところです。 たとえば、空きマスを探すために全マスをチェックすると遅いです（終盤の場合、多くのマスはすでに石があるので無駄）。 そこで、終盤の探索に入る前にすべての空きマスの位置を列挙して連結リストでつなぎ、再帰のたびにこのリストをなめるようにしています。
残念ながら、Rustはリスト構造の扱いが極めて不得意な言語です *2 。
Rustでリストを作るには（型チェックを通すために）リファレンスカウントのセルを使うのが定番のようですが、今回はパフォーマンスが重要なのでunsafeを使いました。
こういうときはunsafeで良いという知見をもらっていたので。
Programming Rust 以下の記述が良かった。「コンテナはunsafe無しに効率的には書けないのでunsafeで良い」 まめさんの以下の記述への回答になっている。 https://t.co/r5iunzkpWH pic.twitter.com/e2bk3R5IFE
— Yu SUGAWARA (@gusmachine) May 10, 2017
中盤のアルゴリズム
次に、単純なネガマックス法で深く読むことはできないので、空きマスが12個以上あるときのためのもう少し賢いアルゴリズムを実装しました。 置換表付きMTD(f)＋評価関数によるムーブオーダリングという、とても昔ながらの方法です（src/search/midgame.rs）。
評価関数は、手動で作った特徴量（いわゆるedge2xのパターンと、着手可能数）を入力とし、勝ちそうか負けそうかを予測します。 これの学習のために、中盤の盤面を数十万ほどランダム生成し、それぞれに対して終盤探索のアルゴリズムを使って実際の勝敗を判定しました。 そして実際の勝敗を教師データとして焼きなまし法と最急降下法を適当に使って重みを決めました（src/learn.rs）。 学習した重みは浮動小数点数が3000個ちょっとなので、Rustの配列としてコードに直接埋め込んであります（data/weight.rs）。
あと、ビットボードのedge2xパターンから高速に係数を算出するために、完全ハッシュを用意しました。
補足 このヒューリスティックな評価関数はあくまでムーブオーダリング（良さそうな手から先に調べることで枝刈りを増やすテクニック）のために使っているだけです。メインの探索では、空きマスが11個のところまで読んだら終盤探索アルゴリズム自体を評価関数として使います。なので、全体としては近似解法ではなく完全探索になります。
序盤のアルゴリズム
6x6のリバーシは1993年に後手必勝であることが示されたそうです。 当時のワークステーションで数週間くらいかけて探索したらしいですが、そんな計算も現代では一瞬……かと思ったのですが、ここまでで作ったアルゴリズムで初期盤面からの探索をすると、1分強かかりました。ディープラーニングで評価関数作ってムーブオーダリングするともっと速くなるのかなあ？
これでリアルタイムに探索するのは厳しいので、序盤の16手をあらかじめ計算してしまうことにしました。 黒が任意の手を選ぶのに対し、白の手は1つだけ覚えればいいので、深さ8のツリーを作ります。 白は最善手（最も大きい石差で勝つ手）のうち、黒の着手可能数が小さくなる枝を選ぶようにすることで、なるべく覚える数を減らしました。 結果的に、およそ10万盤面程度を覚えることになりました。
ツリー部分は簡潔データ構造を使ったLOUDSという表現でエンコードし、およそ700キロバイトとなっています *3 。
そんなに大きくないので、include_bytes!マクロでバイナリデータを直接実行ファイルに埋め込みました。
これでAIは完成です。
ブラウザで動かす
ここまでは、Linuxでのネイティブ実行ファイルとして作ってました。 今回は探索をブラウザで動かす目標だったので、wasm-bindgenでブラウザ向けのAPIを用意し（src/api.rs）、wasm-packでWebAssembly（以下wasm）にしました。 emscriptenに比べるとびっくりするほど簡単にwasmができたのでびっくりしました。
ただ、動かして見るとpanicで落ちました。
「やっぱりwasm生成は完成度そんなに高くないのかなー」などと他人のせいにしつつ、何が起きているか調べてみると、usizeでオーバーフローが発生してました。
試してたネイティブビルドは64ビットなのでオーバーフローしないのですが、wasmは32ビットなのでオーバーフローが起きる。
要するに完全に自分のせいでした。完成度高いなあ。
直したら無事にwasmがWeb workerから動きました。 なお、panicは調べ始めてから数十分で直せたのに対し、wasm+Web workerのwebpackの設定に数時間ほど消費しました。webpack許せない。
UI部分
ここまでRustで開発してきたので、UIもyewで！ などと考えなくもなかったのですが、この時点でRustへのヘイトが溜まりすぎていたのでTypeScriptで書きました。 いやー、ちょっとmapしたいだけなのにiterだのcollectだの書かないといけないとか、雑なコード書くとunwrapだらけになるし……。
閑話休題。
かっこいいUIを作りたくなったので、three.jsを使うことにしました。 最初はReactで実装しようとしましたが、three.jsが状態のかたまりで相性最悪だった *4 ので、素で書きました。
雑感
完全解析されているゲームは、どうやっても勝てないところを実際に体験したいですよね。 6x6リバーシのパーフェクトプレイの棋譜は発見者のJoel Feinsteinが書いたニュースレターを始めいろいろなところで見かけますが、インタラクティブにできるものは見つからなかったので作りました。
あと、wasmで遊んでみたかったのも動機です。 6x6リバーシは全盤面をデータベースにするのは明らかに無理なので、ブラウザで現実的に動かせる速度とバイナリサイズを実現するにはwasmがよいかなと。 はやくWebアプリのフロントエンドが全部wasmで動く世界になるといいなあ。
まとめ
6x6のリバーシはやっぱり勝てませんでした。
アニメ「Sonny Boy」の『難解』プログラムの解説
『Sonny Boy』というアニメが放送されています。学校が異次元に漂流してしまい、超能力に目覚めた生徒たちがサバイバルしながら、さまざまな奇妙な現象の裏にあるルールを解き明かし、元の世界に変える方法を探す、というストーリーです。ルールが分かったあとで何度も見直したくなります。
さて今回、『Sonny Boy』に、プログラムを寄稿しました。プログラムでおもしろいCGを作ったとかではなく、プログラムの実行の様子そのものが『Sonny Boy』の5話の中で放送されました。
こういうプログラムです。
このプログラムがどういうものだったかを解説します。
どんなプログラム？
実行すると、「難解」という文字がほどけてなくなるアニメーションをします。
起動したらまず、プログラム自身が画面に表示されます。 しばらくしたら「難解」が左から右へほどけていきます。 その後上からヒモが降ってきて、"Solved" という単語になったあと、再度ほどけて終了。 実行時間5秒程度のちょっとしたデモアプリです。
手元で試してみたい人は、Rubyをインストールした上で、nankai.rbを保存しruby nankai.rbと起動します。
端末のサイズを 180 x 40 以上に広げて実行してください。
なお、プログラムはGitHubに置いてあります。
制作の背景
拙作のASCII Fluid（下記動画）が、Sonny Boyの監督の夏目真悟さんの目に止まったのがきっかけです。
「解ける（ほどける、とける）」というテーマで、数秒程度の難解なプログラムを自由に作ってほしい、と声をかけていただいたので、そのまま『難解』をほどくプログラムにしました。 作中に出てくる、『解く』という能力を示すデモになってます。 アニメで使ってもらうということで、わりと動きにこだわって作ってみたつもりです。
ちょっとだけ技術解説
アニメーションはハードコードしているのではなく、実際に「難解」の文字を分解することで表現しています。 「難解」を17領域くらいに分割し、それぞれの中でスパニングツリーを構成します。 その端っこを引っ張るような感じでアニメーションします。なので正確には一本のヒモではなく、何本かのヒモが絡まったような形になってます。
プログラム自身を表示するのは単にソースコードをファイル読み込みするのではなく、クワインという方法で実現しています。 端末でのアニメーションはエスケープシーケンスを使ってやってます。 エスケープシーケンスは無害化して出力されているので、エスケープシーケンスを含むコードを含めて再実行できるようになっています。
$ ruby nankai.rb > nankai.output $ ruby nankai.output
Rubyというプログラミング言語はとても実用的な言語ですが、こんな変わった使い方もできて、とても良い言語です。もしこういうプログラムに興味があったら、こんな感じのプログラムばっかり集めた本を書いているのでぜひ見てみてください（宣伝）。
まとめ
ということで、「難解」という文字が自発的に解けていくというプログラムでした。アニメ見てた方に「おっ」と思っていただけていたら嬉しいです。見てなかった方は、いろいろ配信があるので、5話だけと言わず、ぜひ1話から追っかけてください。
...
以下は、読まなくていいです。
おまけ
ここからはギークなプログラマ向けの、ちょっとしたおまけです。
このプログラムは「ほどいても」動作するようになってます。 どういうことかというと、左半分の「難」だけを切り出しても実行できるプログラムになっています。
q=%q!s =q[/#{ N=?\n}( #{Z=?\~
s}*)/, 1];E=3 3.chr; $><<t=~
(N*12+s+"q=%q#{E+q+E};eval# {Z*8}n= '#{n}'~
"+N*13+?#).gsub(/^.*/){(Z*( 35-s.si ze)+$&)
|c|d=d *90+(c -2)%91};d};b=116;c=0;i=D
`?oT`r #?jn%: _(7AF5]7lZ}|N,),slN15Ap8<
]];g=[];F=->x,m{g<<[t[x ],b>0?[0]*c+[x]*b+m:[0]*(c
map{|i|i+=x;s<=i&&i<s+n -170&&(i-s )%W<n%W
<<x;v <1&&v=D ["axC4?ap'5.bbU lui?h|b
".split(??)[(x%W+x/W)%8]];(d+=1;v/=2)while+v%2>0;z=
x+=d%8>3?z:-z;v/=2)whil e-x%W>1&&0<x&&x<8208;F[y,
8-'#'L> *B(B[(*-$XG|"E"H=$H:)$'$
,n=a;v=B.pop-34;v%3<2?( z=n%W; S[s+y=(
;y)]):(b+=200/r+=2;M[D[ "=,)_q >Z"]>>r
170]*19;b=0;T=(c+(0..8) .map{Z*51+(0..67).map{i/
%w{puts (["Usage:",:ruby,$0,100]
/q/)?$q[/^#{z}+/]+z+z+"R=ev al#{z*18}$q=#{z*35}%q{#$
1]:[]};n+z+?=+z+(m>1?f[2]:[ m])*(z +?x+z))
,n=0,m;6.ti mes{|i |c+=10;
[i]*684];b=52;t= T;M[6,(x-i%2)%W+4788]};s=
{|i|o=[Z* 170]*48*N; g.map{|c,m|x=m[i]||0;x>0&
ub(N,"\e[E ");slee p(0.01)};puts(s)#Unravel#
"q!;p 0/ 0.0;#";
これ実行すると、"NaN"が出力されます。ナンだけに。
$ ruby nan.rb NaN
もちろん、右半分の「解」も実行可能です。
p="><"
puts""+ p||$><<"____\n\s/\s/\n";(
"\u89D2";;x=(%~ );%#?_Y}_U1jojD(i0(DVA1aq
.ljust(170)};D=-> e{d=0;e. bytes{
["cGIY& ?dUptZ yGj5?= 1+wD5G
XzIUF<+ <L-MlD )"+t[2 513,21
-m.size)+m.reverse];t[x]= Z;[1,-1 ,-W,W].
&&t[i]>Z&&F[i,[i]+m]}};M=- >d,x{y=x; m=[];v=0;(m
*?_jJc? _v_&z 'NcJ{(Hn{?_O6m ?}3k7>?Q,
-(d%4) %172+ 1;~+%~ ##Y. #E2021
m]};W=171;B=%{36<-~;%w~ ;puts :Moo;'
OAs"3$*2$-2"*5s}.bytes; r=8;S= ->*a{s
v%3*17 0+1)* w=v/3, n-(S[s,v%3<1?n+w-z:w*W+z]
&6,s+B .pop- 34+v/3 *W])};S[2082,m=8378];c=[Z*
=2;i%2>0?%q@_R=eval$q=%q{z=?\ s;eval
*z)if[]==$*.map{|n|puts (n. match(
q}":(m=n.to_i;f=->x{m>1 ?m%x<1?(m/=x;[x]+f[x]):f[x+
)}}*"" }@[b+= 1]:Z}*""+Z*51}+c)*N;c=340;s
t=T+"" ;b=0;M [2,x=D["^lv(2A"[i]]+3302+26
"\e[F"* 47;504 .times
&o[x]=c };$><< s+o.gs
#!;eval n='eval q. gsub((
/[\s ]|~.*$/) ,"")#'
実行すると"><"が出力されます。ギリシャ文字のカイのイメージ。
$ ruby kai.rb ><
プログラムを横に分解してそれぞれ違う動きをさせるのはわりと難解だと思うので、腕に覚えのあるプログラマは解読してみてください。
ヒント：Rubyの「%記法」をうまく使って実現してます。 最初の2行と終わりの2行あたりに注目すると良いです。
おまけのおまけ
これで終わり？ まだ分解できますよね。そう、「角」と「刀」と「牛」。
p="><"
puts""+
"\u89D2";;x=(%~
.ljust(170)};D=->
["cGIY& ?dUptZ
XzIUF<+ <L-MlD
-m.size)+m.reverse];t[x]=
&&t[i]>Z&&F[i,[i]+m]}};M=-
*?_jJc? _v_&z 'NcJ{(
-(d%4) %172+ 1;~+%~
m]};W=171;B=%{36<-~;%w~
OAs"3$*2$-2"*5s}.bytes;
v%3*17 0+1)* w=v/3,
&6,s+B .pop- 34+v/3
=2;i%2>0?%q@_R=eval$q=%
*z)if[]==$*.map{|n|puts
q}":(m=n.to_i;f=->x{m>1
)}}*"" }@[b+=
t=T+"" ;b=0;M
"\e[F"* 47;504
&o[x]=c };$><<
#!;eval n='eval q.
/[\s ]|~.*$/)
「角」を実行すると角が出ます。
$ ruby tsuno.rb 角
次は「刀」。
p||$><<"____\n\s/\s/\n";(
);%#?_Y}_U1jojD(i0(DVA1aq
e{d=0;e. bytes{
yGj5?= 1+wD5G
)"+t[2 513,21
Z;[1,-1 ,-W,W].
>d,x{y=x; m=[];v=0;(m
Hn{?_O6m ?}3k7>?Q,
##Y.
「刀」を実行すると「刀」のアスキーアートっぽいものが出ます。
$ ruby katana.rb ____ / /
最後は「牛」。
#E2021
;puts :Moo;'
r=8;S= ->*a{s
n-(S[s,v%3<1?n+w-z:w*W+z]
*W])};S[2082,m=8378];c=[Z*
q{z=?\ s;eval
(n. match(
?m%x<1?(m/=x;[x]+f[x]):f[x+
1]:Z}*""+Z*51}+c)*N;c=340;s
[2,x=D["^lv(2A"[i]]+3302+26
.times
s+o.gs
gsub((
,"")#'
「牛」を実行すると鳴きます。
$ ruby ushi.rb Moo
それぞれのプログラムは単純なので、Rubyがわかれば普通に読めると思います。 実行に関係ない文字列がいかにSyntax Errorにならないようにするかがポイントです。
しかし、「解」や「難解」に合体させても動くようにするのは、かなり苦労しました。 その甲斐あって、なかなか香ばしいコードに仕上がったと思うので、ぜひ解読して欲しいです。
ヒント：pや~.*$/が分解次第で構文の解釈が変わります。ダブルミーニングなコード。
さらなるおまけ
最後に一瞬表示される "Solved" も実行可能になってます。
R=eval $q= %q{
z=?\s;eval %w{ put
s([" Usa ge: ",:
ruby ,$0 ,10
0]*z)if []==$*. map {|n |pu ts(n.ma tch(/q/)
?$q[ /^# {z} +/] +z+ z+" R=e val #{z *18
}$q =#{z *35} %q{# $q} ":( m=n .to_i;f=->x {m>1 ?m%
x<1?(m/=x; [x] +f[ x]) :f[ x+1 ]:[ ]}; n+z
+?=+z+ (m>1?f[ 2]: [m])* (z+?x+z) ))}}*""}
実行すると使い方が表示されます。
$ ruby solved.rb Usage: ruby solved.rb 100
この通りに実行してみます。
$ ruby solved.rb 100 100 = 2 x 2 x 5 x 5
100が素因数「分解」されました。コマンドライン引数の数字を次々に素因数分解していくプログラムになってます。
$ ruby solved.rb 1 2 3 4 5 6 7 8 9 10 1 = 1 2 = 2 3 = 3 4 = 2 x 2 5 = 5 6 = 2 x 3 7 = 7 8 = 2 x 2 x 2 9 = 3 x 3 10 = 2 x 5
最後のおまけ
もはや全然関係ないおまけですが、solved.rb は引数に "quine" を渡すと、自分自身を表示します。ここにもクワイン。
$ ruby solved.rb quine
R=eval $q= %q{
eval(%w{z= ?\s ;pu
ts([ "Us age :",
:rub y,$ 0,6
]*z)if[ ]==$*.m ap{ |n| put s(n.mat ch(/q/)?
$q[/ ^#{ z}+ /]+ z+z +"R =ev al# {z* 18}
$q= #{z* 35}% q{#$ q}" :(m =n. to_i;f=->x{ m>1? m%x
<1?(m/=x;[ x]+ f[x ]): f[x +1] :[] };n +z+
?=+z+( m>1?f[2 ]:[ m])*( z+?x+z)) )}}*"")}
ささやかなこだわりですが、左側に空白をいれたら出力も同じようにずれるようになってます。 アニメ中のように、画面真ん中あたりに表示されたのをコピペしてもちゃんとクワインになります。
$ cat solved2.rb
R=eval $q= %q{
eval(%w{z= ?\s ;pu
ts([ "Us age :",
:rub y,$ 0,6
]*z)if[ ]==$*.m ap{ |n| put s(n.mat ch(/q/)?
$q[/ ^#{ z}+ /]+ z+z +"R =ev al# {z* 18}
$q= #{z* 35}% q{#$ q}" :(m =n. to_i;f=->x{ m>1? m%x
<1?(m/=x;[ x]+ f[x ]): f[x +1] :[] };n +z+
?=+z+( m>1?f[2 ]:[ m])*( z+?x+z)) )}}*"")}
$ ruby solved2.rb quine
R=eval $q= %q{
eval(%w{z= ?\s ;pu
ts([ "Us age :",
:rub y,$ 0,6
]*z)if[ ]==$*.m ap{ |n| put s(n.mat ch(/q/)?
$q[/ ^#{ z}+ /]+ z+z +"R =ev al# {z* 18}
$q= #{z* 35}% q{#$ q}" :(m =n. to_i;f=->x{ m>1? m%x
<1?(m/=x;[ x]+ f[x ]): f[x +1] :[] };n +z+
?=+z+( m>1?f[2 ]:[ m])*( z+?x+z)) )}}*"")}
IOCCC日本語ネタバレ解説 中間報告
変態C言語プログラムコンテストであるIOCCCの全作品を日本語でネタバレ解説するサイトを書いてます。
年初にIOCCC 1984の解説から書き始めて、先程IOCCC 2000の解説を公開したところです。
数えてみると、ここまで165作品を解説したようです。どれも面白いものばかりですが、その中でも特におすすめの作品を個人的な好みでピックアップ紹介してみました。
Brian Westleyの作品
初期のIOCCCを支えたwestleyの作品群。多彩で超絶技巧で、とにかくすごいです。絶対に見てほしい！ので、まずは彼の作品だけまとめます。 ネタバレ解説を書き始めたのは、すごさのわりにあまり注目されていない彼の作品を紹介したかったのが動機のひとつです。
- IOCCC 1987 Best Layout 線対称なプログラム。実行すると回文が出る。
- IOCCC 1988 Best Layout 円の形のプログラムで、円周率を計算する。ちゃんと円の形に意味があるのがよい。
- IOCCC 1989 Most algorithms in one program ROT13しても文字列反転しても動くプログラム。コード形状のトリックが芸術の域。
- IOCCC 1990 Best Layout 演劇の英語脚本っぽいプログラム。これでちゃんと意味のある動きをするのだから衝撃的。
- IOCCC 1991 Grand Prize ○✕ゲームを組み込んだQuine。
- IOCCC 1992 Best Small Program 小さな円（地球）の形のプログラムで、世界地図が出る。指定した緯度経度にマークを置ける機能付き。
- IOCCC 1994 Worst Abuse of the C Preprocessor Cプリプロセッサでアドベンチャーゲームを実装。
- IOCCC 1996 Best One Liner たった92文字のコードで、様々な時計を表示するワンライナー。
気楽に楽しめる作品
個人的な好みでwestleyだけ贔屓しましたが、他にも面白いのがたくさんあります。 まずは、コードの形や実行結果がひと目で面白く、気楽に楽しめるものをピックアップ。
- IOCCC 1989 Best layout π、と見せかけてe
- IOCCC 1991 Best Output ターミナルで3D迷路。
- IOCCC 1994 Best Utility ターミナルでグラフ。
- IOCCC 1994 Most Well Rounded Obfuscation psで時計。
- IOCCC 1995 Best Layout 加算器の形をした加算器。
- IOCCC 1998 Best Object Orientation ターミナルで3Dオブジェクトのビューア。
- IOCCC 1998 Best of Show 飛行機の形をしたフライトシミュレータ。
- IOCCC 2000 Best Layout 「あく」「そく」「ざん」
- IOCCC 2000 Best Small Program 現在の月齢をわかりやすく表示する。
地味だけどよく見るとすごい作品
ちょっととっつきにくいけれど、個人的にかなり好きなもの。
- IOCCC 1988 Most useful Obfuscated C program わかりにくいC言語の型宣言を、英語で解説してくれる。
- IOCCC 1989 Best self-modifying program 自分自身を書き換えながら階乗を計算する。
- IOCCC 1990 Best of Show 微分方程式のソルバで、ソートで、フィボナッチ。
- IOCCC 1993 Best Abuse of the C Preprocessor ライフゲームのためのC言語埋め込みDSL。
- IOCCC 1994 Best Layout 入力を転置行列のように転置するプログラムで、自分自身も転置可能。
- IOCCC 1996 Best Obfuscated Character Set Utility 点字の形をした点字変換プログラム。
- IOCCC 1996 Best of Show セルフホスト可能なC言語サブセットコンパイラ。
縛りプレイな作品
C言語の機能を制約して書かれたプログラム。無意味な超絶技巧にIOCCCらしさを感じられます。
- IOCCC 1988 Best abuse of C constructs ほぼwhileとdecrementだけのプログラム。
- IOCCC 1998 Best Flow Control 条件分岐を使わずに条件分岐をするプログラム。
また、C言語ではなくCプリプロセッサで計算をするプログラムも結構あります。
ルールの悪用系の作品
「C言語プログラムとは何なのか」を考えさせられる哲学的な作品群。実にIOCCCならではです。
- IOCCC 1984 The Grand Prize
short main[]={...}; - IOCCC 1987 Best Abuse of the Rules
P; - IOCCC 1988 Best abuse of the rules
#include "/dev/tty" - IOCCC 1989 Strangest abuse of the rules
char*_="Hello, world.\n"; - IOCCC 1990 Strangest Abuse of the Rules
c - IOCCC 1993 Most Versatile Source
char*_=__FILE__; - IOCCC 1994 Worst Abuse of the Rules 世界最小Quine。
まとめ
20世紀のIOCCCから個人的なおすすめ作品ピックアップでした。 紹介しなかったやつもだいたい面白いので、ぜひ暇な土日などにでも眺めてみてほしいです。
20世紀のIOCCCは、古いC言語なので、動作確認やパッチ作成がやたら大変でした。 来週からは21世紀のIOCCCのネタバレを書いていきます。 動作確認は楽になりそうですが、そのかわり作品の数や難解さが増えるので、やっぱり大変そう。
WSL2 + subsystemctlの設定メモ
WSL2 + subsystemctlの設定メモ
WSL2のおかげでLinuxからWindowsに移住できました。WSL2はデフォルトでsystemdが動いていないので、genieを使うのが定番ですが、自分はsubsystemctlを使っています。subsystemctlの設定方法はあまり見かけないので、メモを残しておきます。
インストール
コンパイルからインストールまでのコマンドを一気に書きます。
sudo apt-get install cargo systemd-container binfmt-support git clone https://github.com/sorah/subsystemctl.git cd subsystemctl cargo build --release sudo install -m6755 -oroot -groot ./target/release/subsystemctl /usr/local/bin/subsystemctl sudo systemctl disable systemd-resolved sudo systemctl disable systemd-networkd
Windows Terminalの設定と起動
Windows Terminalの設定で、起動時に"subsystemctl shell --start --quiet"を呼ぶように設定しておきます。
{
"guid": "{XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX}",
"hidden": false,
"name": "Ubuntu",
"source": "Windows.Terminal.Wsl",
"commandline": "wsl -d Ubuntu subsystemctl shell --start --quiet",
...
},
起動時に次のように表示されたら成功。このメッセージはWSL2の初回起動時だけに表示されますが、気になるなら"RUST_LOG=error subsystemctl shell --start --quiet"とすれば消えます。
[2020-09-26T07:05:16Z INFO subsystemctl] Starting systemd mame@hostname:~$
subsystemctlのための.bashrcの設定
.bashrcに次の一文を足しておきます。
stty -echoprt
これをしないと、バックスペースを押したときに表示が妙なことになることがあります。subsystemctlというより、machinectl shellを通すとechoprtが有効になるようなのですが、systemd側の設定でこれを止める方法を知ってる人がいたら教えてほしいです。
それから、WSL2はデフォルトでWindowsのPATH設定をすべて引き継いでくれますが、subsystemctlを通すとそれが消えます。個人的にはデフォルトの状態はパスが多すぎて補完がよくわからなくなったので、必要なものだけパスを通すことにしました。特に使うものはaliasにしています。
alias explorer="/mnt/c/Windows/SysWOW64/explorer.exe" alias chrome="/mnt/c/Program\ Files\ \(x86\)/Google/Chrome/Application/chrome.exe" alias code="/mnt/c/Users/ユーザ名/AppData/Local/Programs/Microsoft\ VS\ Code/bin/code" alias mery="/mnt/c/Users/ユーザ名/AppData/Roaming/Mery/Mery.exe"
あとsubsystemctlにすると、起動時のディレクトリが"/mnt/c/Users/ユーザ名"ではなく"/home/ユーザ名"になります。これも自分は満足していますが、不満なら適宜変えるとよいと思います。
subsystemctlに関係ないですがついでに。WSL2で大きいファイルや大量のファイルにアクセスしていると、たまにPCが激重になります。ホストのメモリ枯渇が原因（この記事が詳しい）で、topでbuff/cacheが巨大化していたらそれです。次のコマンドで軽くなるので、これもaliasを設定してます。
alias wsl2_drop_caches='sudo sh -c "sync && echo 3 > /proc/sys/vm/drop_caches"'
追記：WSLgのための設定
/tmp/.X11-unix/X0のunix socketで通信するようなので、systemdがtmpfilesを消してしまわないようにする。
sudo systemctl mask systemd-tmpfiles-setup-dev sudo systemctl mask systemd-tmpfiles-setup sudo systemctl mask systemd-tmpfiles-clean
.bashrcでDISPLAY環境変数を定義しておく。
export DISPLAY=:0
これでxclockなど立ち上がる、はず。
IOCCC ネタバレ解説はじめました & IOCCC 2020 に入賞したよ
IOCCC の全作品のネタバレ解説を目指すサイトを作りました。
いまのところ、最初の 4 年分まで書いてます（IOCCC 1984 ～ IOCCC 1987）。週ペースで書き足していくつもりなのでご笑覧ください。
IOCCC は、「現存する世界最古のプログラミングコンテスト」と言われることもあります。つまり、現在も開催されているということです。今年の正月に、昨年の IOCCC 2020 の入賞作品が公開されました。自分のプログラムが 3 つ入賞したので、デモ動画と簡単な紹介を書いておきます。
endoh1 - Most explosive
端末でのマインスイーパーですが、推論でわかるようなところは大体勝手に進めてくれます。 そういうダルくてミスしやすい作業はコンピュータにやらせて、マインスイーパーの本質（勘で適当に開くところ）に集中できます。
このプログラムは IOCCC 2019 用に作っていたのですが、時差で締め切りを勘違いして投稿しそこねたやつなので、1 年寝かしてました。そのわりにはひねりがあまりないですが、それでも今回の中では一番よい出来かなと思っています。 アニメキャラ形状のプログラムで有名な omoikane さんがマップを作ってくれたのがとても嬉しかったです。IOCCC を知ったきっかけが omoikane さんの作品なので感慨深い。
ちなみにこれは 2007 年頃に Java Web Start で作ってたネタの焼き直しです。
endoh2 - Best perspective
スター・ウォーズのオープニング風にメッセージを流す ROT13 デコーダ。
フォントはベジエ曲線で表現したものをコード内に埋め込んでいます。monumental quine で作った経験を生かして一晩くらいで作りました。
スター・ウォーズのスクロールはずっとやりたいと思っていたネタでしたが、いまいち面白くする工夫を思いつかず、ずっと放置していました。結局 ROT13 を混ぜる程度になったけれど、気に入り度は普通。
endoh3 -- Most head-turning
散髪屋にある時計のように左右反転している時計を埋め込んだ Quine 。
本当に単純なプログラムなので、これが採択されたのはちょっと意外でした。まあ、「今年の Quine」みたいな扱いでしょうか。もっと頑張りたかったので、やや不満な出来。
審査員から「Unicode の文字を使ったもっと鏡文字っぽいバージョンが欲しい」と言われたので、prog.alt.c も作りました。動画のいちばん最後にデモしてるとおり、I ᨅ ℇ ᔨ ਟ ∂ ⎲ 8 ♇ OI II ᨅI を使ってます。これを作らせたくて採択されたのかも。
他の入賞作品
こちらからどうぞ。
そのうち日本語での解説も書くのでお楽しみに。
Rubyと型についてのポエム
matz はじめコミッターの型に対する姿勢にも疑問を持っています。
というご意見が自分に刺さった気がしたので、他の話題はともかくこの点に関してだけ、ポエムを書きます。
「Rubyに型が欲しい」というのは、「もっと速い馬が欲しい」だと思っています。意味を知らない人は ヘンリー・フォード もっと速い馬が欲しい で検索してください。
これは批判でも皮肉でもありません。みんなが馬の乗り方を知っている世界では、誰も乗り方を知らない自動車より、速い馬のほうが確実で合理的です。まして、自動車が本当に実現できるかどうかわからない段階では。なので、他言語で型注釈を書くことによるプログラミング体験が良いと思った人が、それをRubyでも享受したいと思うのは自然だと思います。実際、Steep や Sorbet は Ruby でそういうプログラミング体験を提供することを目指していて、すでにある程度実現できています。
ただ、みんなが本当にほしいのは、「バグを早期発見できるRuby」「IDEで補完やドキュメント表示ができるRuby」だと思っています *1 。型注釈はこれらの利点を実現するためのひとつの手段にすぎません。
Ruby 3 は公式で型注釈を入れないという判断をしました。これに関して、「型注釈を書かないと上記の利点が実現できないことは歴史が証明している。Ruby は歴史に学ばない」というような意見を聞いたこともあります。しかしほんの 10 年前には、「言語に静的型付けを後から導入するのは無理。型は言語の設計段階から考慮しないと入れられない。歴史が証明している」などと言われていたことをご存知でしょうか。漸進的型付けが大成功した現代では、言う人がいなくなった言説です *2 。
TypeProf は型注釈なしで同等の利点を実現できないかに挑戦する試みです。TypeProf は完成しても、既存の静的型付けのプログラミング体験とは違う体験になると思われるので、まさに「自動車」を目指しています。残念ながら、TypeProf はまだ完成品の自動車というには程遠く、まだエンジンができたかどうかという段階です。正直に言うと、TypeProf がどんな自動車になるのか（何にもなれないのか）は、自分でもまだよくわかっていません。でも、本格的に作り始めた2年前から見ると、予想よりだいぶ動くものになったので驚いています（ひいき目は認めます）。
TypeProf 何も知らない人のために参考リンク↓
「まともに使えるかどうかわからない自動車よりも、今すぐ使える速い馬が欲しい」というのは、完璧に正当な主張です。そういう人は、Steep や Sorbet をぜひトライしていただきたいです。まだいろんなライブラリに RBS が足らないので、RBS を書いて gem_rbs に pull request を送りまくってください。ライブラリの RBS が増えると Steep や Sorbet で解析できる範囲が増えますし、TypeProf の解析速度や精度も上がるので、とにかくありがたいです。
ということでポエムでした。こういうポエムは、ちゃんと自動車が作れてから言えたらカッコよかったんですけどね。なんか書きたくなった。なお、これは Ruby コミッタの総意などではなく、ぼくの個人的な意見です。
設定情報をエレガントに管理する方法（解決なし）
アプリケーションにはいろいろ設定があるものです。一般的な例では、production / development のようなモードや、ログレベルなど。プログラムを書くとき、こういうデータをどのように管理しますか？
大きく 2 種類の書き方があると思います。
どちらも一長一短があると思っています。
1. グローバル変数に入れる
たとえば、$config = { mode: :development } などとするだけ。
Rubyの場合、グローバル変数だけでなく、定数に入れたり、クラスメソッドにしたり、singletonライブラリを使ったり、スレッドローカルストレージを使ったりするのもこの分類に含めます。
長所
- 記述がとても簡潔
- 設定の追加が簡単
短所
- グローバル変数を使うことに罪悪感がある
- 1 つのプロセスで唯一の設定しか持てない
解説
とにかく簡単な方法。設定情報が必要なときはグローバル変数を読み出すだけなので、プログラムの記述は非常に簡潔。また、設定を追加したくなったときも自明。名前の衝突が気になるなら、$MyApp_configのように、アプリケーション名をprefixすると良さそう（ただし長くなるので、記述性は若干下がる）。
この方法を選びたくない最大の理由は、気持ちの問題だと思う。教育されたプログラマは「グローバル変数はダメ」と心に刷り込まれている。しかし設定情報をグローバル変数に入れることは、そこまで問題ではない気もする。グローバル変数がダメなのは、実行中にグローバル変数を書き換えることでモジュール間に暗黙的な依存が発生してしまうためだけれど、設定情報はアプリ初期化時以外に代入されることはないはずなので、意図しない依存は発生しないはず。
この方法の実用上の問題は、設定情報をプロセス内で1つしか持てないこと。つまり、同一プロセス内で異なる設定のアプリケーションインスタンスを複数作ることができない。大して問題ないと思うかもしれないが、テスト時などに様々な設定でのアプリケーションインスタンスを作りたくなったり、アプリケーションをライブラリとして使いたくなったりしたときに困る。
なお、定数やクラスメソッドなども本質的にはグローバル変数と変わらないので、プロセスの問題は解決しない *1 。スレッドローカルストレージを使っても、本質的な問題は変わらない *2 。
2. クラス生成時にコンストラクタに引き回す
たとえば次のように、クラスごとにインスタンス変数@configなどで保持する。設定情報が必要なクラスには必ず設定情報を渡す。
class MyApp::Foo
def initialize(config, ...)
@config = config
...
@bar = Bar.new(@config, ...)
...
end
end
長所
短所
- 記述が極めて冗長（ほとんどすべてのクラスに設定情報をたらい回しする必要がある）
- インスタンスを大量に生成する場合、速度やメモリ使用量がやや気になる（多くの場合は無視できるとは思う）
解説
教科書的に正しそうな方法。グローバル変数の類が一切ないので罪悪感がない。また、異なる設定のアプリケーションインスタンスを作ることもできる。
しかし、記述性は明らかにグローバル変数の方法より劣る。initializeは必ず@configを受け取る必要があり、newには必ず@configを渡す必要がある。
また、ASTのノードのクラスのように、インスタンスが大量生成される可能性があるクラスに毎回@configをもたせるのは、無駄が気にならなくもない。ほとんどの場合、すべての@configには同じオブジェクトへの参照が入るだけなので。（ただし、実際に問題になる可能性は高くないと思う）
近い将来にアプリケーションインスタンスを複数作る必要がない場合、この方法を選ぶメリットはないと思う。しかし、必要になってから書き換えるには、変更量は非常に多くてつらい。しかし、だからといって防衛的にこっちの方法を選んで記述性や実行効率を下げるのは、生産性を下げていると感じてしまう……。
なお、この方法のバリアントとして、「すべての設定情報を渡すのではなく、そのクラスが必要としている情報だけを渡す」というのがある。これはより「正しい」感じがするが、生産性はより最悪になる *3 。
どうなれば幸せか
上の 2 つはどちらを選んでも何か間違っているような気分になり、いつもモヤモヤしています。なにか言語機能が不足しているのではないかと思うのですが、どういう機能があれば綺麗に解決するのかもよくわかりません。
- 動的スコープな変数があればよいのでは？と思っていた時期もあったのですが、複数のアプリケーションインスタンスを相互に実行するような場合にはイマイチ使えなさそう。
- オブジェクトをグループ化する機能があればよさそうな気がしますが、記述性を下げずに所属グループを指定する方法を思いつかない。Ractor が近そうだけれど、Ractor はやはり別物なので多分転用はむずかしい（シェアされたオブジェクトの中で設定を参照すると曖昧とか）。
まとまらないまとめ
わかりやすそうなので「設定情報」で話しましたが、アプリケーション全体の管理を行う（半グローバルな）インスタンスも同様にすべての関係インスタンスに参照もたせたい気持ちになります。
この問題をエレガントに解決している言語の事例とか言語機能の論文とかあれば、教えてください。