石取りゲーム: 回答例

では石取りゲームの回答例を出してみよう。

僕が最初に書いたC言語での回答例は次のようなカンジだ。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define A 0
#define B 4

typedef struct env_t {
　int stones;
　int player;
} Env_t;

char* Messages[] = {"石の数 (10以上) : ", "石の数: %d\n",\
　　　　　　　　　"プレイヤー%dの番です\n何個取る (1〜3個) ?",\
　　　　　　　　　"プレイヤー%dの勝ち\n"};

Env_t init(void) {
　Env_t env;
　char s[5];
　int num;
　while (true) {
　　printf("%s", Messages[0]);
　　scanf("%4s%*[^\n]", s);
　　getchar();
　　num = strtol(s, NULL, 10);
　　if (num > 9) {
　　　env.stones = num;
　　　env.player = 1;
　　　return env;
　　}
　}
}

int input(Env_t env, char* prompt) {
　char s[2];
　int num;
　while (true) {
　　printf(prompt, env.player);
　　scanf("%1s%*[^\n]", s);
　　getchar();
　　num = strtol(s, NULL, 10);
　　if ((num > A) && (num < B)) {
　　　return num;
　　}
　}
}

Env_t Eval(int num, Env_t env) {
　env.stones -= num;
　env.player = env.player == 1 ? 2 : 1;
　return env;
}

bool is_game_end(Env_t env) {
　return env.stones < 2 ? true : false;
}

int winner(Env_t env) {
　int player = env.player;
　if (env.stones == 0) {
　　return player;
　} else {
　　if (player == 1) {
　　　return 2;
　　} else {
　　　return 1;
　　}
　}
}

int main(void) {
　Env_t env = init();
　printf(Messages[1], env.stones);
　while (true) {
　　env = Eval(input(env, Messages[2]), env);
　　printf(Messages[1], env.stones);
　　if (is_game_end(env)) {
　　　printf(Messages[3], winner(env));
　　　return EXIT_SUCCESS;
　　}
　}
}

まぁ、C言語が分からない、って人もいるだろうから、上のコードは無視していいんだけど、一応「ひな型」と言うか、「完成形」はこうなる、と言う例示だ。

そして「プログラミングの筋道としては全く同じでもC言語の場合は面倒な記述要素が増える」と言う例でもある。

もう1つ、LispやPython等のモダンな言語だと、どう言う順番で関数を書いていこうと、何ら実行には影響がないんだけど、C言語の(古臭い)特徴として、関数の記述順序が悪いと実行出来ない、と言う事がある。

どういう事かと言うと、例えば関数A、関数B、・・・の順で定義していった際に関数Aが関数Bを利用してた場合エラーになる、と言う事だ(逆に、関数Bが関数Aを利用する場合は問題にならない)。

これはモダンなプログラミングに慣れてるとメンドイんだけど、一方、関数プロトタイプや関数同士が相互に利用し合わない前提だと、意外と「プログラムした人がプログラムを打って行く"順番"」が残りやすい形式でもあるんだ。アタマから順に考えていってる、と言う「発想の流れ」が(完全ではないにせよ)凄く読みやすい形式だ、と言う特徴がある。

もっともあまり複雑なプログラムじゃない限り、っつー但し書きが必要にはなるけれどね。

ブログの記事だったり、あるいはテキストなんかの場合、発想の「流れ」のまま記述するより「記事の読みやすさ」を重視して関数の解説時点で組み替える場合がある。僕もやってる。

だから星田さんがここで

RoRでもそうだったけど、関数を作っていく時って時系列だと先にでっち上げて・・感じのことが多いんですかね・・同時に頭の中で出来上がってるのか、本当に後で考え始めるのか。

って戸惑うのは良く分かる。要するに実際にプログラミングで組んでる際での「時系列」のままに教科書になったり、あるいはブログ記事になってる、って事はまずないんだ。

これが初心者が混乱するトコで、同時に、殆ど唯一「動画講座」が良かったりする例でもあるんだよな。一応、動画講座でも「シナリオ」っつーか「プログラミングの流れ」を動画作る前に考えてはいるだろうけど、リアルタイムに「どういう順番でプログラムを組み上げていくのか」分かったりするのはテキスト類じゃ得られないメリットかもな、とは思う(もっともズブの素人がそれを把握出来る、とも思えないけど)。

で、だ。

UNIX系プログラミングの真髄っつーか、金言は何度か紹介したかもしれないけど、これだ。

プログラムはフィルタを作るように作れ

この場合は、例えばRacketやPython組み込みのfilterを指すわけじゃあないんだけど、「データ処理を念頭に置いて作れ」って言う事(ついでに言うと、実は「元データは改変するな」と言う意味でもある)。

そして重要なのは、言い換えると「プログラムを書く前にデータ設計をまずはしっかりとしろ」って事を言ってるのね。「プログラムの前にデータだ」と。何故ならフィルタリングする前にデータが存在せんと、「どうフィルタリングするのか」と言うのは画餅になっちまうからだ。

そう、プログラミングでまず最初にしなきゃならないのは、「データ設計」なの。これが一番最初に来る。そして「そのデータを処理する(フィルタリングする、って言っても良い)プログラムを書く」のが二番手なのね。読み込みも出力も後回しでいい。これらが二本柱なんだ。

ニクラウス・ヴィルトと言うスイスの計算機学者がいる。プログラミング言語Pascalの開発者で、プログラミング教育にPascalを通じて多大な影響を与えた人なんだけれども。

実はこの人の作った、Pascal自体の影響力より、やっぱ「Pascalを使った教科書を書いた」事による影響がもっと大きい。

その教科書の名前を「アルゴリズム＋データ構造＝プログラム」と言う(笑)。これほど題名が核心に迫ってる例ってあんま無いんじゃないか(笑)。これだけで結論が分かっちゃう(笑)。

実は僕、この本読んだ事ねぇんだけど(笑)、題名見ただけで「全て分かった」気になっちゃう程良い題名だよな(笑)。ミステリで言うとタイトルが「犯人はヤス」ってなってるくらい「買う必要がない」本に見える(笑)。

この本、実際、コンピュータサイエンスの歴史的な名著に掲げられている本で、この本以降のアルゴリズム系の本ってある意味この本の「パクリ」なんだよな。それらが出てる理由は「Pascalが往年に比べるとマイナーになった」から。でも、これが出版された当時は「アルゴリズムを学ぶには何はともあれPascalを学ばないとならない」くらいになっちゃった本なの。そしてその結論は(読んだ事はねぇけど・笑)UNIXのプログラミングにおける金言「プログラムはフィルタを作るように作れ」と全く同じだ。多分。いや、断言出来る。

要するに

データ構造をまずは設計しろ
作成したデータ構造をプロセスするようなプログラムを書け

と言うのが二大方針で、まずはこの順番でプログラムを組んでいく。

そして2の途中で不具合が見つかったら1の設計を見直すわけだ。この繰り返し。

1. の「データ構造」がREPLで言うと「環境情報」だ。

んで、2の「作成したデータ構造をプロセスするようなプログラム」がREPLで言うとevalになる。

取り敢えず「環境情報」とevalの2つだけを組み上げる。そしてその2つの間で動作テストする。そこさえ乗り越えればREPLでルーピングする事自体は至極簡単になる。

特に、構造体を覚えたら「まずはデータ設計」と言う方針はより明確になる筈だ。

まずは石取りゲーム、ってお題の場合、「何がゲームに必要な情報か?」と考える。その結論がそのまま「必要なデータ構造」って事になる。そしてそれは多分、「石の数」と「何番目のプレイヤーか?」だ。

Racketで構造体を使うと、

(struct world (stones player) #:transparent)

になるだろう。これが「一番最初に」取り敢えずは書いてみるデータ構造だ。

なお、この時点で、「メッセージ分離方式」を目指すのなら出力メッセージは今すぐ使わないにせよ組み立てておいて良い。

(define *messages* '((init . "石の数 (10以上) :")
　　　　　　　　　(number-of-stones . "石の数: ~a~%")
　　　　　　　　　(prompt . "プレイヤー~aの番です~%何個取る (1〜3個) ?")
　　　　　　　　　(winner . "プレイヤー~aの勝ち~%")))

そして入力の最小値、最大値もデータとして定義しちゃって構わないだろう(※1)。

(define-values (*min* *max*) (values 0 4))

とにかく「最初はデータ」。その設計に注力しよう。

それが終われば、次はUNIXの知恵で言う「フィルタ」、ここではevalだ。このデータを「どうフィルタリングして結果を返す」のか。そこだけに注力して書く。

(define (world-go x env)
　(let ((stones (- (world-stones env) x))
　　　(player (if (= (world-player env) 1)
　　　　　　　　2
　　　　　　　　1)))
　　(world stones player)))

石取りゲームに於いては「石を何個取るか」なんで、既にある石の数から引数で受け取った数を引くこと、ってのがUNIXプログラミング流に言うと「フィルタ」部分その1。そして、「次は何番目のプレイヤーの行動なのか」と言う情報が「フィルタ」部分その2になる。2人で遊ぶゲームだとすれば、1番目のプレイヤーが現時点のプレイヤーなら次は2番目だし、2番目のプレイヤーの手番だったら次のプレイヤーは1番目、となる(※2)。

そしてその2つの「計算結果」を新しい環境値として返り値にする。

実はこれらデータ構造と関数だけ、で「動作テスト」は充分に行える、と言う事になる(※3)。何故ならこれらはある意味、プログラムにおける心臓部だから、だ。

> (world-go 3 (world 15 1))
(world 12 2)
> (world-go 2 (world 12 2))
(world 10 1)
>

当然こちらが考えた通りの値が返る。ぶっちゃけ、この時点でプログラムの90％は完成してる(※4)。

「データ構造を設計する事」「eval部を記述すること」さえ性交成功すれば、残りはハッキリ言って些事になる。

あとは好きな順番で書いていって良い。いや、ホント。データ構造を設計する事とevalを書くのが一番難しいんだ。

例えば1つの指針としてはRead->Eval->Print loopなんで、Read部から手を付ける、ってのもいいだろう。

(define (input env prompt)
　(display (format (cdr (assq 'prompt *message*)) (world-player env)))
　(let ((num (read)))
　　(if (and (number? num) (> num *min*) (< num *max*))
　　　num
　　　(input env prompt))))

ここでは再帰構造を使ってるけど、こだわらなくていい。

要するに入力としてある範囲での数値が欲しいんで、それ以外を入力した時に再び入力を促す為にこうしてるんだけど、例外をraiseで投げる、ってのもいいだろう(そしてその場合は、REPLでその投げられた例外をキャッチする、と言う事だ)。

> (input (world 15 1) (cdr (assq 'prompt *message*)))
プレイヤー1の番です
何個取る (1〜3個) ?4
プレイヤー1の番です
何個取る (1〜3個) ?0
プレイヤー1の番です
何個取る (1〜3個) ?3
3
>

要は入力された数値をそのままevalに手渡せばいいわけだ。

なお、古典的には、プロンプト出力もprint部に任せるべきなんじゃねーの?って人もいるだろうけど、ぶっちゃけ、Pythonのinputなんかの「プロンプトを引数として受け取ってそれだけは出力する」と言うのは便利だ。そしてその形式の方がシンプルになる可能性が高い。

だから入力を促すプロンプト「だけ」は入力関数に実装する方が個人的な好みになる。

次に出力関数だけど、今回は特に作らなくてもいいだろう。あまりにシンプルだから、だ。だからこの辺でREPLをまずはまとめよう。

REPLの書き方は色々あるんだけど(名前付きletを使うか、そうじゃないか、とか)要はやってる事はどの道ルーピングなんで、どう書いても良い。ちょっと弄ってるウチに「よりシンプルに」書ける事がある。その辺は正直言うと、プログラムの「仕様」に左右されると思う。

例えば今回は、直球勝負の末尾再帰で書けるタイプだと思う。次のようなカンジで。

(define (nim env)
　(display (format (cdr (assq 'number-of-stones *messages*))
　　　　　　　　(world-stones env)))
　(if (game-ends? env)
　　(display (format (cdr (assq 'winner *messages*)) (winner env)))
　　(nim (world-go (input env (cdr (assq 'prompt *messages*))) env))))

ここで出題に挙げられてる実行例を見ると、

石の数: -> プレイヤーxの番です -> 何個取る（1〜3個）?

と言う出力のルーピングになっている。

つまり、言い換えるとRead -> Eval -> Printループと言うより、Print -> Read -> Eval ループに見える、ってこった。「石の数:」と言う出力がenvの情報から出力されている以上、なんかその後にRead -> Eval(つまりenvの計算過程)が来ても良さそうで、それが再帰の引数になれば良さそうだ、とアタリが付けられるわけだ。

そして同時にこのケースが「補助関数を書くのを後回しにして良い」ケースだ。ゲームの終了判定を司る関数game-ends?と勝者表示に用いる関数winnerはまだ書いてない。大体、このテの関数は判定条件がメンド臭かったりするんで、REPL内に組み込むより外部にあった方が良かったりする。それは「修正を容易にするため」だ。

特に後者は実行テストをした際に一見バグっぽい挙動をする事があり得るんで、早々に外へと追い出した方が見通しは良いだろう(※5)。

ゲーム終了判定関数は、残りの石の数が1以下になった時ゲーム終了!なので、

(define (game-ends? env)
　(< (world-stones env) 2))

でオシマイ。基本的に述語なんで、#tか#fを返せば用は足りる。

一方、ゲームの勝者を決める関数はちと考え方がややこしいかもしんない。

基本的にこの「石取りゲーム」の仕様だと、残った石が1個で「それを取らなければならないヤツ」が負けになるんだ。

しかし、3個残ってる状態で3個取ったらその3個を取ったヤツが負けになる。逆に3個残ってる状態で2個取れば、次のヤツが負けになるわけだ。

要するに、その辺を考慮して「勝者を判定」しなければならないので、ゲームの終了判定関数よか遥かにややこしい。故に、REPLの外側で書いた方が実験しやすいし、またこの手直しでREPLが巻き込まれなくて済むようになる。

(define (winner env)
　(let ((player (world-player env)))
　　(if (zero? (world-stones env))
　　　player
　　　(if (= player 1)
　　　　2
　　　　1))))

これでREPL自体は完成だ。テストしてみよう。まずは最後のヤツが残った石を全部取るケース。

> (nim (world 15 1))
石の数: 15
プレイヤー1の番です
何個取る (1〜3個) ?3
石の数: 12
プレイヤー2の番です
何個取る (1〜3個) ?3
石の数: 9
プレイヤー1の番です
何個取る (1〜3個) ?3
石の数: 6
プレイヤー2の番です
何個取る (1〜3個) ?3
石の数: 3
プレイヤー1の番です
何個取る (1〜3個) ?3
石の数: 0
プレイヤー2の勝ち
>

もちろん、石取りゲームのルールがわかっていれば、こんなバカな事(最後に残った石を目一杯取る事)はしない。しかしレアケースなんだけど、これをやった時に勝者が狂っちゃう事は一応避けておくべきだろう(※6)。

> (nim (world 15 1))
石の数: 15
プレイヤー1の番です
何個取る (1〜3個) ?3
石の数: 12
プレイヤー2の番です
何個取る (1〜3個) ?3
石の数: 9
プレイヤー1の番です
何個取る (1〜3個) ?3
石の数: 6
プレイヤー2の番です
何個取る (1〜3個) ?3
石の数: 3
プレイヤー1の番です
何個取る (1〜3個) ?2
石の数: 1
プレイヤー1の勝ち
>

と、これで「石を1個残した方が勝ち」になった。

ここまで出来れば後は初期化プロセスだけ、だ。以前書いた通り、初期化プロセスはREPLとは独立した、要するに単体のプログラム(スクリプト)だ。今回のケースの場合、やるこたぁ、石の総数(10以上)を入力から受け取る事。オシマイ。そしてその部分で別のプロンプトを表示してる。

(define (init)
　(display (cdr (assq 'init *messages*)))
　　(let ((num (read)))
　　　(if (and (number? num) (> num 9))
　　　　(world num 1)
　　　　(init))))

ここでも、入力が数値じゃなかったり、あるいは数値が10以下だったら再帰して再び入力を促すようにしている。

これで一応完成ではある。問題の仕様には充分準じた。

コンピュータに敵をプレイさせたい場合は、1つの方法としては入力関数(input)もコンピュータが使うようにすればいいだろう。例えば次のようにして。

(define (input env prompt)
　(display (format (cdr (assq 'prompt *messages*)) (world-player env)))
　;;; ここを改造
　(let ((num (if (= (world-player env) 1)
　　　　　　　(read)
　　　　　　　(let ((result (add1 (random 3))))
　　　　　　　　　(display result) ;; read の仕様に合わせて、一旦出力して
　　　　　　　　　(newline) ;; 改行する
　　　　　　　　　result))))
　　　(if (and (number? num) (> num *min*) (< num *max*))
　　　　num
　　　　(input env prompt))))

とこれで出来上がりだ。

全ソースコードはここに置いておこう。

なお、乱数を使ってるが、石取りゲームは先手になった場合必勝法があり、その必勝法でコンピュータを先手にすると、後手のプレイヤーは絶対に勝てなくなる。

よって、コンピュータが後手で乱数で選択、の方が人には優しいだろう。

なお、Python版も基本的には全く同じ発想でプログラミングしている。

※1: 複数の、大した事のないデータを一気に定義したい場合はdefine-valuesを使って構わない。

※2: あまりこの石取りゲームでは意味がないが、仮に複数人数でプレイをする、と言う想定なら、データ設計から考え直した方がいい、と言う事だ。と言うか、改造する際のポイントがどこか、と見極めるのもデータ設計から見ていった方が良い。

ちなみに僕だったら、データとしては石の数、カウンター、循環リストの3つを用意して、カウンターは無限に増えていって、それで循環リストを参照する。

もちろん別のデータ設計法を考えても構わない。

※3: この「石取りゲーム」をREPLを使ったプログラミング例に挙げた理由はeval部を書くのが異様に簡単だから、だ。当然複雑になったevalだと書くのは大変になるわけだけれども、それを細かく分解して書く事自体はそこまで難しくはない。

とにかくどうデータをフィルタリングするのか、と言う事に注力すれば、eval自体を分解して書く事自体は難しくないし、それを完成させるのはスクリプトを書く程度の話となる。

取り敢えず、プログラムを書く「目的」が何なのか、と言うのは「しっかりしたデータがある」と言う前提さえあれば見えづらいモノにはならない。

※4: 当然、もっと短く

(define (world-go e env)
　(world (- (world-stones env) x)
　　　　(if (= (world-player env) 1)
　　　　　2
　　　　　1)))

と書いても良い。

※5: Schemeは仕様的に言うと「名前空間が1つしかない」ので、ANSI Common Lispと違い、このテの「補助関数」はREPL内部でのローカル関数にした方が好まれるかもしれない。

しかしながら、それは「最終的な開発プロセス」、つまりリファクタリングで行うべきだろう。最初は名前空間を汚して外部関数として書き、他の関数の補助関数として使い回ししない、とハッキリ分かった時点でコピペでREPL内部に入れてしまう、ってのが殆どのケースだと思う。

そしてそれが故に、ローカル関数専用の構文letrecを使うより、defineでローカル関数を書く方が好まれる、と言う事だ。コピペの結果だ。

ただし、今回の場合は、REPLが直接末尾再帰してるので、再帰する度にローカル関数を再生成するのはさすがに効率が悪いと思われる。もし、ローカル関数を使って補助関数をREPL用関数の内部に閉じ込めたい、となった場合、再帰を名前付きletで書き直して、ローカル関数の定義部分は再帰に巻き込まれないように切り離した方が良いだろう。

その場合は多分こういう定義になると思う。

(define (nim env)
　(define (winner env)
　　(let ((player (world-player env)))
　　　(if (zero? (world-stones env))
　　　　player
　　　　(if (= player 1)
　　　　　2
　　　　　1))))
　(define (game-ends? env)
　　(< (world-stones env) 2))
　(let loop ((env env))
　　(display (format (cdr (assq 'number-of-stones *messages*))
　　　　　　　　　(world-stones env)))
　　(if (game-ends? env)
　　　(display (format (cdr (assq 'winner *messages*)) (winner env)))
　　　(loop (world-go (input env (cdr (assq 'prompt *messages*))) env)))))