reverxii.tex: TeX でリバーシを遊ぶ（翻訳）

2018-12-10 (updated: 2021-12-25)  #TeX 

本稿は TeX & LaTeX Advent Calendar 2018 の10日目の記事です．9日目は aminophen さんでした．11日目は p_typo さんです．

最近は TeX 周辺のプログラミング環境もだいぶ拡張・整備されてきており，(La)TeX パッケージの開発においても必ずしも悪名高い TeX 言語を書かずに済むようになってきました．具体的には，今年のアドベントカレンダーの重点テーマにもなっている LuaTeX では汎用プログラミング言語 Lua を利用することができますし，LaTeX3 チームが開発する独自の言語 expl3 も TeX 言語よりは幾分高い可読性と便利な標準機能を有しています．また，そもそも TeX の外側で，より真っ当なプログラミングが可能であることをセールスポイントとする組版システムも着実な進歩を見せています．本稿の読者であれば，そのような例として SATySFi の存在をご存知のことでしょう．

そうした事情を鑑みると，「TeX 言語」が実用的に多用される時代は，本当に終わりが近づいているのかもしれません．

しかし，こういう流れが起こっているのは何も「TeX 言語の能力が低い」からではありません．むしろ，TeX 言語が使いにくいとされるのは，ある意味その圧倒的な自由度に起因するものです．高度に習熟した TeX プログラマの手にかかれば，かなり複雑な処理が必要なプログラムも TeX 言語で実装することが可能です．TeX 言語によって，そうした驚異的なプログラムを開発する行為は一般に “TeX 芸” と呼ばれ，昔から一部の変態的な TeX 愛好家によって親しまれてきました．TeX 言語が表舞台から遠ざかっていく中で，TeX 芸の文化も影を潜めてしまうのはある程度仕方のないことですが，完全に失われてしまうには惜しいものであると思います．

そうした TeX 芸の実例として有名なプログラムの1つに，Bruno Le Floch 氏（現在 LaTeX3 チームメンバー）による reverxii.tex があります．これは plain TeX で実行するとコンピュータ相手にリバーシ（オセロ）をプレイすることができるというもので，かつて ZR 氏によっても紹介されています．

このプログラムは TeX Live に含まれているため，TeX Live ユーザであれば，以下を実行すれば特にインストール等することなく遊ぶことができます．

$ tex "$(kpsewhich -var-value TEXMFDIST)/doc/plain/reverxii/reverxii.tex"

reverxii.tex はプログラムそのものもすごいのですが，TeX 芸プログラムとしては珍しいことに，作者によってその実装について詳細な解説が付けられています．この解説文書は，TeX Live ユーザであれば例によって Texdoc で呼び出すことが可能です．

$ texdoc reverxii

今回，TeX 芸の技術や面白さを後世に伝えたいという思いを込めて，この解説文書を日本語に翻訳してみました．

なおこの翻訳文書（若干の内容改変と追加の説明を含む）は reverxii プログラム・解説文書作者の Bruno 氏から直接許可を得てここに掲載しています．


reverxii.tex: TeX でリバーシを遊ぶ

  • Bruno Le Floch 著
  • 2011/12/28

アブストラクト

reverxii.tex はお好きな TeX エンジンを相手にリバーシをプレイするための938バイトの TeX プログラムです．リバーシをプレイするには，コマンドラインから plain TeX を dvi モードで起動し，reverxii.tex を読み込みます．これはつまり，ほとんどのディストリビューションではターミナルで tex reverxii.tex を実行するということです．このプログラムのドキュメントを生成するためには，同じファイルを LaTeX で処理します（例えば pdflatex reverxii.tex）．

コード

改行は取り除くことができるので，1行にした場合コードは938文字です．

\vsize5cm\hsize3cm\newlinechar`*\def~#1{\catcode`#113~}
~IJKLMNOPQRSTUVWXYZjqz@.[|](/+^'";:?,_)!*{ 13\def~#1#2{\let#1#2~}
\def+{\count1}+1=2}*\cr[\ifnum(\ifcase|\or/\else]\fiN\number@\advance
X\expandafter!\global?\message~\def.#1{@+1 1\countdef#1+1.}
.IJKLPQRSTUVWYZ.-1P1T2+44P+55P+45T+54T
~j{[0<Q[9>Q[0<J[9>J^/.]/.]/.]/.]}
~^{+NQNJ}~:#1{#11#12#13#14#15#16#17#18}~M#1{?{#1}#1}
~_#1#2{M#2:{\B#1}&M#2&M{*}}~\B#1#2{&M{(+#1#2  |-|0]}}
~q{?{Row and column? e.g. E6*}\read.to\EX\D\meaning\E  ;}
~\D#1->#2#3#4;{Q`#2@Q-`@J`#3@J-`0)(V?{Invalid move #2#3.}q]}
~){V0 (jS1z1z0z.S0z1z.S.z1z0z.]}~;{@R(P|-]}~z#1{{K#1Z1{Y1,}(Z,]}}
~,{@QS@JK[j=T(Y!^P!;2]O,/[j=P!VV(I(Y/!Z0]]]]}~\A#1{Q#1:\C}
~\C#1{J#1)[0<VO[V>WWVUQLJ]]}~"#1{(#1|0|1|2|2|2|2|1|0]}
~O{Z"Q\multiplyZ3@Z"J@V(Z9|1|6|1|1|2|6|2|4] }~'{M :{&M}&M{*}}
~~{PXTXTNP\halign{&## *M{*}'_1A_2B_3C_4D_5E_6F_7G_8H'}\vfil\break
I1W(W./0] :\AI0 [0<W[1=PQUJL/q])^P;1][.=W?{(RTie/ Player [0>R-/0]
wins by N[0>R-]R].}X\end]~}~

対人でゲームをプレイしたい場合は，コードの終わり近くにある 1=P を 0=P に書き換えてください．この変更によりコンピュータプレイヤーは0から1に変わり，無効化されます．

解説

いくつかのコメント

reverxii.tex という名前は，もちろん悪名高い xii.tex という叙事詩 Twelve days of Christmas を組版する，ほとんど誰も理解することのできない plain TeX コード（これも CTAN から入手できます）に由来しています．ただし私の場合，最も難解なコードを書くことよりも，最小のコードを書くことを目的にしています．具体的には，私は多くの文字をアクティブ化するほかは奇をてらったカテゴリーコードの割り当てをしていません．

私の目的は短いコードを書くことだったので，プレイヤーに提示されるメッセージは簡素なものですが，ゲームを理解し遊んでもらうのには十分であると思います．目標は短いコードを書くことではあるものの，一方でゲームの進行を記録し，組版するのが適切だと考えました：何と言っても，TeX は組版システムなのですから．この（棋譜を組版する）部分がおよそ38文字を要したので，全体のコードは900文字以上になってしまいました．

コードを短くするための技法の1つは，1度以上使用するすべてのプリミティブを1アクティブ文字にリネームすることです．また，情報を格納するカウンタには（\countdef 等で与えた “別名” ではなく）直接カウンタ番号でアクセスすることも有効です．

注意深い読者は残りの1文字コントロール・シークエンスをアクティブ文字にすることによって（実は $ が未使用のままです），さらに1文字削ることができることに気付いたかもしれません．しかし，それをやると私のエディタではシンタックス・ハイライトがおかしくなってしまうので，そうはしませんでした😊 もちろん，私は1文字コントロール・シークエンスには最も出現回数が少ないもの（それぞれ2回しか登場しません）を選びました．

それではコードを見ていきましょう！

まず，ページ寸法を設定します．これは PDF 出力のためには十分ではありません．

\vsize5cm
\hsize3cm

plain TeX は \typeout コマンドを提供していないので \message を使用する必要がありますが，そのためには新しい “改行文字” (new line char) を設定してやる必要があります．ここでは，適当に * を “改行文字” に選びました．のちほど * はアクティブ化され，\cr が \let されます．

\newlinechar`*

次に，最初のループで多くの文字をアクティブ化します．このループは後続の {} グループで終了します．終了点で空白文字をアクティブ化し，~ を次のループのために再定義しています．この時点で，入力ストリームにはまだ鬱陶しい 13~ が残ってしまっています．そこで，1から始まるレジスタ番号のカウンタへアクセスするための短縮表記 (+) を導入し，\count11を 213 に設定することで，先ほどの 13 を除去しました（このカウンタは後で使用します）．残したままの ~ は次のループを開始します．

\def~#1{\catcode`#113~}
~IJKLMNOPQRSTUVWXYZjqz@.[|](/+^'";:?,_)!*{ 13\def~#1#2{\let#1#2~}
\def+{\count1}+1=2}

この段階では ~ は引数を2つとり，1つ目を2つ目に \let し，それを繰り返すように定義されています．先述したように * は \cr になっているので，メッセージとアライメントの両方で改行に用いることができます．我々はなるべく一貫性のある命名規則を維持するように努めました：条件分岐の開始は左括弧，\or と \else は中置デリミタ，そして \fi は右括弧です．また他の何度も登場するプリミティブにも短縮形を与えました．2つ目のループは ~ を \def に再定義することで終了します．

*\cr
[\ifnum
(\ifcase
|\or
/\else
]\fi
N\number
@\advance
X\expandafter
!\global
?\message
~\def

さて今度はカウンタの割り当てを行いましょう．残念ながら \newcount は \outer 付きで定義されているので実用的でありません．我々はすでに +1（すなわち \count11）を213に設定しているので，213から始めてそれより大きな番号のカウンタを割り当てていきましょう．各ループでは +1 に1を足し，次の文字を +1 の保持する値のカウンタ番号に割り当て，そして繰り返します．いままでと同様，最終的に再帰マクロ . をカウンタに再定義することでループを終了します．最後に（入力ストリームに）残る . には-1を代入し，続いていくつかのカウンタに代入を行います：プレイヤー，対局相手，そして初期配置（つまり中央の2×2マスをクロスするように埋める）です．

.#1{@+1 1\countdef#1+1.}.IJKLPQRSTUVWYZ.-1P1T2+44P+55P+45T+54T

ここで各カウンタの用途についてまとめておきます：

  • P は現在のプレイヤー（1は -，2は 0 を表す）
  • T は対局相手
  • Q は行番号
  • J は列番号
  • S は行方向のステップサイズ
  • K は列方向のステップサイズ
  • R はスコア差で，0 側が勝っているときに正の数
  • V は位置 (Q, J) の石を計算するときに使用
  • W は AI による最善手の値を保持．プレイヤーにも手がないとき，ゲーム終了を判定する目的にも使用される
  • U は最善手の行番号
  • L は最善手の列番号
  • I と Y はブール値で，実際に石を返すのか，単に返る石の数を計算するだけなのかの制御をするために使用される
  • Z は一時カウンタで，ローカルにマスの情報などについて計算をするのに用いられる（例えば「角は重要」）ほか，グローバルには石を返すか否かを判定するためのブール値としても使われる

盤面はカウンタ 1<行番号><列番号> に保存されます．何もないマスは0，プレイヤー - の石のあるマスは1，プレイヤー 0 の石のあるマスは2にそれぞれ対応します．マクロ j は Q 行 J 列の値を取り出すもので，もし盤面の外を参照しようとした場合は . (-1) を返します．[ は \ifnum，/ は \else，] は \fi であることを思い出してください．もし Q 行 J 列が盤面の範囲に収まっていれば，\count1<行番号><列番号> として働く ^ によって値が取り出されます．ここで（展開の問題があるので）j と ^ は \ifnum 条件式の左辺でしか安全に使えないことと，^ は代入文の左辺として使用できることに注意してください．

~j{[0<Q[9>Q[0<J[9>J^/.]/.]/.]/.]}
~^{+NQNJ}

また，このプログラムではしばしば1から8の番号についてループを回す必要があるので，そのためのマクロも用意しておきます．

~:#1{#11#12#13#14#15#16#17#18}

次に，DVI とコンソールの両方に盤面を表示するためのマクロを考えます．M はその引数を \message と組版出力（入力ストリーム）に吐き出します．これは単純に1から8の数字を（少しスペースや改行を入れながら）単純に印字するだけの最初と最後の行では，ほぼ直接用いられます（' の定義）．マクロ _ は数字と対応するアルファベットの大文字を引数として受け取って，盤面の指定行を出力します．まず受け取った文字を盤の左側に置き，1から8までループしながら空白と，対応するカウンタレジスタにしたがって - または 0 のいずれかを出力していきます．この定義部分には2つの連続するスペースがあることに注意してください．1つ目のスペースがカウンタ番号の終了を明示し，2つ目が出力されます（plain TeX では，アクティブな空白文字は通常のスペースに展開されます）．

~M#1{?{#1}#1}
~'{M :{&M}&M{*}}
~_#1#2{M#2:{\B#1}&M#2&M{*}}
~\B#1#2{&M{(+#1#2  |-|0]}}

入力は q によって取り扱われます．このマクロはユーザが正しい入力，すなわち Q と J の値がそれぞれ1以上8以下の範囲に収まるまでユーザに入力を求めます．プロンプトとして入力例を含む小さな \message を表示します（この入力例は実際には最初の1回しか入力できないものですが，ユーザが入力形式を理解するのには十分なものだと思います）．入力を受け取った後の処理は LaTeX2e の \@onelevel@sanitize に似たものです．すなわち，ユーザ入力を格納する制御綴 \E の \meaning から最初の2文字を，それぞれ \D の引数 #2, #3 として取り出します（X は \expandafter であることを思い出してください）．取り出した2文字の文字コードをそれぞれ @（行）・0（列）と比較します．閉じ括弧 ) のところで，ここでの処理のほとんどが実行されます：ユーザ入力にしたがって石をマス (Q, J) に置いたとき1つの石もひっくり返らない場合，または石を置こうとしたマスが盤外の場合は V の値が0にセットされます．この計算の後，V が0であった場合，ユーザが入力した手は不正なので，ユーザにもう一度入力するように促します．

~q{?{Row and column? e.g. E6*}\read.to\EX\D\meaning\E  ;}
~\D#1->#2#3#4;{Q‘#2@Q-‘@J‘#3@J-‘0)(V?{Invalid move #2#3.}q]}

さて……ではどうやって V の値を計算すればよいでしょうか？ もしも j が0を返さない場合，それは既にそのマスが埋まっているか盤の外であることを意味するため，その手は無条件に不正と言えます．続いて入力されたマスから周囲8方向について，それぞれいくつの石が裏返せるかを数えます．方向は S と K の2つのカウンタで管理され，それぞれ-1, 0, 1のいずれかの値を取ります．はじめにブール値 Y を偽 (1) に設定した状態で , を呼び出すことにより，現在計算中の方向について石の反転が起こるかを（Z のグローバル値に基づいて）判定し，続いて Y を真 (0) に戻して再度 , を呼び出すことによって実際の反転を行います．, は反転を行うにあたって行・列の番号 Q, J を直接変更してしまうので，その呼び出しは必ずグループの中で行う必要があります．

~){V0 (jS1z1z0z.S0z1z.S.z1z0z.]}
~z#1{{K#1Z1{Y1,}(Z,]}}

マクロ , は再帰的で，各ステップで (Q, J) を方向 (S, K) に移動させていきます．そして，もし見ているマス (j) に置かれている石が対戦相手 (T) のものであったら (Y!^P!;2]O を実行し，繰り返します．ここでは何が行われているのでしょう？ ブール値 Y が真のときは現在のマスをグローバルにプレイヤーのものに切り替え，スコア差をやはりグローバルに2変更します（; の解説をご参照ください）．最後に，今考えているマスについて O の計算を実行します（O の解説をご覧ください）．

一方，もし見ているマス (j) がプレイヤー (P) の石であった場合，それは既に <石を置こうとしているマス><相手の石の並び><自分の石> の走査の終了点に至っているということです．すなわち，この時点で <石を置こうとしているマス> に実際に石を置いた場合，いくつの <相手の石の並び> が裏返るのかがカウントされた状態になっています．ここまでは，V へのすべての変更はローカルなので，, の呼び出し元を含むグループの終了点に至れば元の値に戻ります．ここまでこの方向への走査が正常に完了しているので，V の値がグループ外でも維持されるように \global V=V を実行します．最後に I が真で Y が偽のとき（すなわち，続いて実際に石の反転が行われるべきとき），ブール値 Z をグローバルに真に設定します (!Z0)．ここで Z が真になった場合は，Y を真に戻した上でもう一度 , を呼び出し，実際の石の反転を実行します．

~,{@QS@JK[j=T(Y!^P!;2]O,/[j=P!VV(I(Y/!Z0]]]]}

この解説では，説明の順序の関係で元の実装コードから O と " の定義位置を少し動かしました．これらの部分で，盤上のすべてのマスに次のような重みを与えています：

9 1 6 6 6 6 1 9
1 1 2 2 2 2 1 1
6 2 4 4 4 4 2 6
6 2 4 4 4 4 2 6
6 2 4 4 4 4 2 6
6 2 4 4 4 4 2 6
1 1 2 2 2 2 1 1
9 1 6 6 6 6 1 9

すべての重みは正の値なので，石を返すすべての手が最終的に正の評価値を得ます．AI にとっては，コーナー横のマスには負の重みを付けた方がよいですが，負の重みを許すにはかなりコードを変更しなければならないのでそうしませんでした．ここで私は列と行をそれぞれ3種類（0, 1, 2のいずれかの分類値で表される）に分類し，Q と J の値から分類値にマクロ " で変換します．そして，この分類値から0以上8以下の値を計算し，最終的にもう1つの \ifcase にかけてマスの重みを取得します．

~O{Z"Q\multiplyZ3@Z"J@V(Z9|1|6|1|1|2|6|2|4] }
~"#1{(#1|0|1|2|2|2|2|1|0]}

カウンタ R はスコア差を記録しており，石が返ったときは ;2，石が置かれたときは ;1 によって更新されます．このカウンタは現在計算中のプレイヤー P が 0 ならば正の値，プレイヤー - ならば負の値で \advance (@) します．

~;{@R(P|-]}

盤面を印字したあと，すべてのマスを走査して最も大きな重みをもつマスを探します．マクロ A が1行を走査するので，:\A によってすべての行を走査することができます．引数を行番号 Q に代入しつつ列についてループを回します．J に2つ目の引数を代入した後，\C は ) を呼び出します．) についてはすでに説明しましたが，石をそのマスに置いたときにいくつの石が返るかを（V に）返すものです．もし新たに計算した V が W より大きければ，W と最善の行 U および列 L を更新します．

~\A#1{Q#1:\C}
~\C#1{J#1)[0<VO[V>WWVUQLJ]]}

さて，~ はもはや \def として使う必要がなくなったので，これを main コマンドとして再利用します．

  1. はじめに，プレイヤーを入れ替えます：T の値を P に代入するわけですが，その前に P の値を展開し，P への代入後に T へ代入します．
  2. 次に，最後に空白を付加した繰り返し指定のプリアンブルを持つアライメント（表組み）を開始します．そして，出力を整形するために改行文字を標準出力に吐き出します（ここでは M よりも ? を使うべきかもしれません）．続いて，最初の1行を ' によって印字し，8行の盤面を _ によって描画し，最後に最下行を出力します．最後の行は ?{*}* によって終わるので，つまり最後のトークンは \cr です．したがって，アライメントを終了することができ，これをもって TeX はそのページの出力を行うことができます．
  3. 出力が終わったら，ここで次の手が存在するのかどうかを確認します．この確認フェーズでは実際に石を返したくはないので，ブール値 I を偽 (1) に設定します．また，最善スコア W を0にリセットしますが，W が元々0の場合は前のプレイヤーにとって手がなかったということを意味するので-1を代入します．そして各行についてループを回し，\A を用いて最善手（およびその評価値）を探索します．それが済んだらブール値 I を真に戻します．
  4. もし手順 3. で（最善）手が見つかっていたら（すなわち W > 0 なら），AI の場合はその手を使い，プレイヤーなら次の手の入力を促します．実際の手の実行には数多くのブール値の設定が必要ですが，それは ) がよしなにやってくれます．続いて ^ により現在（手）のマスにプレイヤーの石を配置し，スコアも1変更します．
  5. 最終的に，いずれのプレイヤーにも手がなくなった場合，ゲーム終了の宣言と最終スコアを提示して \end することで処理を終了します．そうでない場合は，上の手順を繰り返します．

もちろん，~ の定義が済んだらそれを呼び出します．さあ，リバーシをプレイしましょう！

~~{
  PXTXTNP
  \halign{&## *M{*}'_1A_2B_3C_4D_5E_6F_7G_8H'}\vfil\break
  I1W(W./0] :\AI0
  [0<W
    [1=PQUJL/q]
    )
    ^P;1
  ]
  [.=W
    ?{(RTie/ Player [0>R-/0] wins by N[0>R-]R].}
    X\end
  ]
  ~
}
~