数当てゲーム [1]
今回は「数当て」ゲームを作りましょう。ゲームの内容は、1 から 100 までの数字の中からコンピュータが選んだ数字を、私達が 7 回以内に当てるという単純なものです。コンピュータは当たりはずれだけではなく、大きいか小さいかを答えてくれますので、範囲を絞り込めば制限内で答えることができるというゲームです。
それでは、順番に処理内容を考えていきましょう。まず、コンピュータが数字を決めないことには、ゲームを始めることができません。コンピュータで適当な数字を選ぶためには、「乱数 (random numbers)」という方法を使います。
●乱数のお話
私たちが適当な数字を決める場合、サイコロを使えば 1 から 6 までの数字を簡単に決めることができます。たとえば、サイコロを振って出た目を記録したら、次のようになったとしましょう。
5, 2, 1, 2, 6, 3, 4, 3, 1, 5, .....
サイコロの目は、イカサマをしないかぎり、出る確率が 1 / 6 で規則性はまったくありません。したがって、数字の出る順番には規則性はなく、まったくでたらめになります。いま 2 が出たから次は 1 が出るとか、3, 4 と続いたから次は 5 が出るといったように、前に出た数字から次に出る数字を予測することはできないのです。このように、でたらめに並んだ数列を「乱数列 (random sequence)」といい、乱数列の中のひとつひとつの数字を「乱数」といいます。
コンピュータは、決められた手順 (プログラム) を高速に実行することは得意なのですが、まったくでたらめの数を作れといわれると、とたんに困ってしまいます。そこで、何かしらの数式をプログラムして、それを実行することで乱数を発生させます。厳密にいえば乱数ではありませんが、それを乱数としてみなして使うことにするのです。このような乱数を「疑似乱数 (pseudo-random numbers)」といいます。
●線形合同法
Scheme の仕様書 R5RS, R7RS-small には乱数の規定がありません。もちろん、Gauche には乱数を生成するライブラリが用意されていますが、ここでは「線形合同法」という簡単なアルゴリズムを使って乱数を生成することにしましょう。プログラムは次のようになります。
リスト : 線形合同法による乱数の生成 ;;; 種 (seed) (define *seed* 1) ;;; シードの設定 (define (srand x) (set! *seed* x)) ;;; 整数の一様乱数 (define (irand) (set! *seed* (modulo (+ (* 69069 *seed*) 1) #x100000000)) *seed*) ;;; 実数の一様乱数 (define (random) (* (/ 1.0 #x100000000) (irand)))
線形合同法の説明は拙作のページ Algorithms with Python の 乱数 をお読みください。
関数 irand は 0 以上 #xffffffff (32 bit) 以下の整数を返します。関数 random は 0 以上 1.0 未満の実数を返します。それでは、実際に乱数を 5 個作ってみましょう。
gosh[r7rs.user]> (irand) 69070 gosh[r7rs.user]> (irand) 475628535 gosh[r7rs.user]> (irand) 3277404108 gosh[r7rs.user]> (irand) 772999773 gosh[r7rs.user]> (irand) 3877832058
この乱数を使うためにはちょっとしたテクニックが必要になります。実は、プログラムを読み込んで irand を評価すると、必ずこの乱数列が生成されます。一般に、擬似乱数を生成する場合、種 (seed : シード) となる数値が必要になります。このプログラムは大域変数 *seed* にシードを保持しています。プログラムを読み込むと *seed* は 1 に初期化されるため、その直後に irand を評価すれば必ず同じ乱数列が生成されるというわけです。
異なる乱数列を生成するには、シードに違う値を設定すればいいのです。シードに値を設定する関数が srand です。ゲームを作る場合、とくに数当てゲームでは、プレイするたびに違う乱数列を発生させないと、当てる数字が同じになってしまうのでおもしろくありません。そこで、起動するたびに異なった値をシードに設定するようにします。
この設定に乱数を使うことはできません。そこで、よく使われるテクニックを紹介しましょう。それは、シードの設定に現在時刻を使う方法です。R7RS-small の time ライブラリ (scheme time) には、現在時刻を求める関数 current-second が用意されています。
gosh[r7rs.user]> (current-second) 1.598240318209634e9
current-second は国際原子時 (TAI) を基準とした現在の時刻を浮動小数点数で返します。なお、R7RS-small には現在時刻を文字列 (日付) に変換する関数がありません。日付 (時刻) の操作は他のライブラリ (SRFI-19 など) を使ったほうがよいでしょう。
分数や浮動小数点数を整数に変換するには、次に示す関数を使います。
- floor num
i <= num < i + 1 を満たす整数 i を求める。 - ceiling num
i - 1 < num1 <= i を満たす整数 i を求める。 - truncate num1 [num2]
小数点以下を切り捨てる。 - round num1 [num2]
近い方の整数に丸める。ちょうど 0.5 の場合には偶数方向に丸める。
これらの関数は引数に浮動小数点数を与えると、小数点数以下が 0 の浮動小数点数を返します。引数に分数を渡すと整数を返します。
gosh[r7rs.user]> (floor 3.5) 3.0 gosh[r7rs.user]> (ceiling 3.5) 4.0 gosh[r7rs.user]> (round 3.5) 4.0 gosh[r7rs.user]> (truncate 3.5) 3.0 gosh[r7rs.user]> (floor 7/2) 3
Scheme の場合、浮動小数点数を「不正確な数」といい、分数や整数を「正確な数」といいます。R7RS-small では、関数 exact で引数を正確な数に、関数 inexact で引数を不正確な数に変換することができます。
gosh[r7rs.user]> (exact 2) 2 gosh[r7rs.user]> (exact 2.0) 2 gosh[r7rs.user]> (exact 2.5) 5/2 gosh[r7rs.user]> (inexact 2) 2.0 gosh[r7rs.user]> (inexact 2.0) 2.0 gosh[r7rs.user]> (inexact 5/2) 2.5
current-second の値を整数に変換してシードに設定すると、起動するたびに異なる乱数列を発生させることができます。
gosh[r7rs.user]> (srand (exact (floor (current-second)))) 1598247892 gosh[r7rs.user]> (irand) 134210757 gosh[r7rs.user]> (irand) 1263350466 gosh[r7rs.user]> (irand) 1797750619 gosh[r7rs.user]> (irand) 1332976352 gosh[r7rs.user]> (irand) 424699233 gosh[r7rs.user]> (irand) 3219659694
この乱数列は、current-second の整数値が 1598247892 だった場合のものです。このように、シードの値を変更することで、異なる乱数列を生成することができます。逆にいえば、シードに同じ値を設定すれば、同じ乱数列を生成できるということです。乱数列を再現できることが擬似乱数の特徴です。
●1 から 100 までの乱数を生成する
数当てゲームは 1 から 100 までの数字を使います。irand は 0 から #xffffffff までの整数値を返すので、1 から 100 までの整数値を返す関数を作りましょう。次のリストを見てください。
リスト : 1 から n までの乱数を生成する (悪い例) (define (make-number-bad n) (+ (modulo (irand) n) 1))
irand の返り値と引数 n の剰余を求めると 0 以上 n - 1 以下の値になります。それに 1 を加算すれば 1 以上 n 以下の乱数を生成することができます。ところが、この方法には重大な欠点があります。実際に n の値を 8 にして乱数を生成したところ、次のようになりました。
7 8 5 6 3 4 1 2 7 8 5 6 3 4 1 2 7 8 5 6 3 4 1 2 ...
同じ乱数列 (7, 8, 5, 6, 3, 4, 1, 2) が繰り返し生成されています。また、奇数と偶数が交互に現れていることもわかります。実をいうと、線形合同法には大きな欠点があり、32 bit 整数の上位ビットはランダムになりますが、下位ビットはランダムではありません。単純に剰余を求めると下位ビットだけを使うことになり、生成される乱数はランダムではなく規則的なものになってしまうのです。
そこで、下位 16 ビットを捨てることにします。次のリストを見てください。
リスト : 1 から n までの乱数を生成する (define (make-number n) (+ (modulo (quotient (irand) #x10000) n) 1))
(quotient (irand) #x10000) で上位 16 ビットの値を取り出します。そして、その値と n の剰余を modulo で求めてから 1 を加算します。これで、1 以上 n 以下の乱数になります。*seed* = 1, n = 8 で試してみると、次のようになります。
2 2 2 4 4 5 4 8 8 8 1 4 7 5 3 5 ...
make-number-bad のように、規則的な数列にはなりません。*seed* = 1, n = 100 で乱数を生成すると、次のようになります。
2 58 10 96 72 17 64 92 16 76 65 44 67 25 95 13 ...
今回は単純なゲームなので、このような簡単な方法で十分でしょう。なお、実数の乱数を生成する random を使って、1 から 100 までの乱数を作ることもできます。興味のある方はプログラムを作ってみてください。
●データの入力
これで、コンピュータは自分で数字を決めることができます。今度は、私達が数字をコンピュータに入力して、正解なのかそれとも正解よりも大きいのか小さいのか、判断してもらわなくてはなりません。まず最初に、数字を入力する方法から説明しましょう。今回はオーソドックスにキーボードから数字を入力します。
Scheme (R7RS-small) には数値、リスト、文字列、シンボルなど S 式を入力する関数 read がライブラリ (scheme read) に用意されています。次の例を見てください。
gosh[r7rs.user]> (read) 100 <== キーボードからの入力 100 <== 関数 read の返り値 gosh[r7rs.user]> (read) (1 2 3 4 5) (1 2 3 4 5) gosh[r7rs.user]> (read) "abcdef" "abcdef" gosh[r7rs.user]> (read) abc abc
read は Scheme の文法にしたがって入力データを S 式に変換します。最初の入力 100 は整数型データとして変換されます。次の (1 2 3 4 5) はリストですね。"abcdef" は文字列として扱われます。最後の abc はシンボルに変換されます。それから、私達が S 式が入力するまで、read はずっと待っています。入力の最後にはリターンキーを押すことをお忘れなく。
ところで、read は入力待ちであることを示すプロンプトを出さないので、このままではちょっと不親切ですね。いま入力待ちであることを示すメッセージを出した方がいいでしょう。また、数当てゲームの場合、入力されたデータが整数値であって、その値が 1 から 100 の範囲であることを確認するべきです。そして、不適切なデータが入力された場合は、再入力できるようにした方が親切なプログラムになります。この処理を図に表すと次のようになります。
それでは、データを入力する関数を作りましょう。関数名は input-number とします。図を見ればおわかりのように、正常なデータが入力されるまで、処理を何回でも繰り返す必要があります。このような処理は再帰定義を使うと簡単にプログラムできます。次のリストを見てください。
リスト : 数字の入力
(define (input-number)
(display "please input integer (1 - 100)\n> ")
(let ((data (read)))
(cond
((not (integer? data))
(display data)
(display "is not integer\n")
(input-number))
((<= 1 data 100) data)
(else
(display "range error\n")
(input-number)))))
最初に、数値を入力するようにメッセージを出力します。次に、let で局所変数 data を定義します。data を初期化するところで read が評価され、キーボードから入力されたデータが data に代入されます。そのあとで入力データのチェック処理を行います。
データチェックには cond を使います。最初の条件部で、data が整数かチェックします。integer? は引数が整数型データなら #t を返す述語でしたね。その返り値を not で反転すれば、data が整数値でないときに条件部が成立することになります。display でエラーメッセージを画面に表示してから input-number を再帰呼び出しします。これで入力処理を繰り返すことができます。とても簡単ですね。
data が整数型データであれば、次の条件部で値をチェックします。data が 1 から 100 の間に収まっていれば、条件部が成立しますね。この場合は正常なデータなので data を返します。data の値が cond の返り値になり、それが input-number の返り値になります。このように、input-number を再帰呼び出ししなければ繰り返しから脱出することができます。
値が範囲内におさまっていない場合は、cond の else 節が実行されます。この場合は、エラーメッセージを出力して、input-number を再帰呼び出ししするだけです。
input-number が完成したら、正常に動作するか確認しましょう。次の例を見てください。
gosh[r7rs.user]> (input-number) please input number (1 - 100) > a a is not integer please input number (1 - 100) > 1.234 1.234 is not integer please input number (1 - 100) > "abcd" "abcd" is not integer please input number (1 - 100) > 0 range error please input number (1 - 100) > 101 range error please input number (1 - 100) > 100 100
作成した関数を簡単にテストできるのが Lisp / Scheme の長所です。テストするときは、エラーとなる条件に注意して行いましょう。input-number では、整数型データ以外はエラーとなる、0 や 101 は範囲エラーになるが、1 や 100 ならば正常なデータとして返すといったことを確認します。
●ゲーム本体の作成
これで入力処理は完成しました。次は、入力データと正解を比較するゲーム本体の処理を作ります。処理内容を図に示すと、次のようになります。
数当てゲームは 7 回以内に正解を当てなければいけません。回数の管理も再帰呼び出しを使うと簡単です。数を当てたならば繰り返しから脱出すればいいわけです。これをプログラムすると次のようになります。
リスト : 数当てゲーム
(define (game answer)
(let loop ((count 1))
(if (< 7 count)
(display "GameOver\n")
(let ((data (input-number)))
(cond
((= data answer)
(display "Congratulation\n"))
((< data answer)
(display "Number is greater than ")
(display data)
(newline)
(loop (+ count 1)))
(else
(display "Numbere is less than ")
(display data)
(newline)
(loop (+ count 1))))))))
関数 game はコンピュータが決めた数値を引数 answer に受け取ります。回数は名前付き let で管理します。単純な繰り返しなので名前は loop としました。7 回で数字を当てることができなかった場合は display でメッセージを表示します。この後、display の返り値がそのまま返されるので、繰り返しから脱出することができます。
次に、入力データを受け取ります。input-number と同様に、データを局所変数 data にセットします。あとは、cond で answer と data を比較します。data と answer が等しい場合は正解です。メッセージを出力して繰り返しから脱出します。
次は、data が answer よりも小さい場合です。メッセージを出力して loop を再帰呼び出しします。このとき、count を +1 することをお忘れなく。newline は改行を行う関数です。data が answer よりも大きい場合は else 節が実行されます。メッセージを表示して loop を再帰呼び出しするだけです。
最後に、ゲームを実行する関数 play を作ります。
リスト : ゲームの実行
(define (play)
(srand (exact (floor (current-second))))
(let loop ((answer (make-number 100)))
(game answer)
(display "Try Again? (y or n)\n> ")
(if (eq? 'y (read))
(loop (make-number 100)))))
まず、現在時刻でシードを初期化してから、ループに突入します。loop の引数には make-number で決めた数値を渡します。これを関数 game に渡してゲームを始めます。ゲームが終了したら、もう一度ゲームを行うかたずねます。ここで y が入力されたら、loop を再帰呼び出しして再びゲームを始めます。
y が入力されると、read は入力データをシンボル y に変換して返します。シンボル同士を比較する場合には、述語 eq? を使います。
●等値関係を調べる述語
eq? は 2 つの引数がまったく同じであるか調べる述語です。数値が等しいか調べる述語に = がありますが、eq? は 2 つのデータが存在するメモリアドレスを比較します。
Lisp / Scheme の場合、データはすべてメモリ領域の中に格納されています。したがって、同じメモリアドレスであれば同一のデータであることがわかります。同じ名前のシンボルは、Scheme 処理系の中でひとつしか存在しないので、eq? を使えば同じシンボルか判断できるのです。ところが、ほかのデータ型の場合は違います。たとえば、数値や文字列が同じ値でも eq? は #t を返さない場合があります。次の例を見てください。
gosh[r7rs.user]> (eq? 'a 'a) #t gosh[r7rs.user]> (eq? 1.0 1.0) #f gosh[r7rs.user]> (eq? "abc" "abc") #f
Lisp / Scheme は数や文字列のデータを作る場合、同じ値でも違うメモリ領域に実体を割り当てる場合があるため、同じ値を eq? で比較しても #t にならないことがあるのです。これはリストの場合も同様です。
gosh[r7rs.user]> (eq? '(a b c) '(a b c)) #f
リストの要素であるシンボルは同じなのですが、リストを構成するコンスセルのアドレスが違うのです。少々難しい話になってしまいましたね。理屈はともかく、シンボルを比較するときには eq? を使うことを覚えておいてください。
このほかにも、Scheme には S 式が同じ値か調べる述語 eqv? と equal? があります。eq?, eqv?, equal? の違いは、おおざっぱに言うと次のようになります。
- eq? は同一のオブジェクト (つまりメモリアドレスが等しい) 場合に真を返す。
- eqv? は eq? を満たしている、あるいは、同じ型で同じ値の数値や、同じ値の文字であれば真を返す。
- equal? は eqv? を満たしている、あるいは、要素が equal? を満たすリストやベクタ、内容が等しい文字列であれば真を返す。
等しいと判定される範囲が eq? < eqv? < equal? と広がっていきます。厳密な定義は Scheme の仕様書 R7RS-small または Gauche のリファレンスをお読みください。
eqv? と equal? の簡単な例を示します。
(eqv? 'a 'a) => #t (eqv? 'a 'b) => #f (eqv? 6.0 6.0) => #t (eqv? 6 6.0) => #f (eqv? '(a 1 2) '(a 1 2)) => #f (eqv? "abcdef" "abcdef") => #f (equal? 'a 'a) => #t (equal? 'a 'b) => #f (equal? 6.0 6.0) => #t (equal? 6 6.0) => #f (equal? '(a 1 2) '(a 1 2)) => #t (equal? '(a 1 2) '(a 1 2.0)) => #f (equal? "abcdef" "abcdef") => #t (equal? "ABCDEF" "abcdef") => #f
●ゲームの実行
これでゲームは完成しました。完成したプログラムは、ファイル kazu.scm に保存したとします。ファイルの最後に (play) を追加してください。このようにすると、Gauche は kazu.scm を読み込んだら play を直ぐに実行します。プロンプト gosh[r7rs.user]> が出てから (play) と打ち込む必要はありません。play が終了したら Gauche も終了します。
それでは実行してみましょう。
$ gosh kazu.scm please input integer (1 - 100) > 50 Numbere is less than 50 please input integer (1 - 100) > 25 Number is greater than 25 please input integer (1 - 100) > 38 Numbere is less than 38 please input integer (1 - 100) > 32 Number is greater than 32 please input integer (1 - 100) > 35 Number is greater than 35 please input integer (1 - 100) > 36 Congratulation Try Again? (y or n) n $
上の例では 6 回で当てることができました。実はこのゲーム、どんな数字でも 7 回以内に必ず当てることができる必勝法があります。上の実行例は、この必勝方法を使っています。
この方法は「二分探索」と呼ばれていて、全体を半分に分けて調べていきます。数当てゲームの場合、最初は 1 と 100 の中間である 50 を入力します。「もっと小さい数」であれば、答は 1 から 50 の間にあることがわかります。次は、1 と 50 の中間である 25 を入力します。「もっと大きな数」であれば、答は 25 から 50 の間にあることがわかります。
このように、中央の値を入力していくことで、100 個の候補が 50 個に減り、50 個の候補が 25 に減っていくのです。そして、最後に候補がひとつに絞られ、答が見つかります。実際に 100 を 2 で割ったいくと、次のようになります。
50, 25, 12.5, 6.25, 3.125, 1.5625, 0.78125 ...
このように、7 回目 [*1] で候補の数が 1 以下になる、つまり答が見つかることがわかります。もっとも、2 つに分けた中央値が答になることもあります。その場合は 7 回よりも少ない回数で答が見つかります。
[*1] 対数を使えば簡単に計算できます。log2 100 = 6.64 となるので最低 7 回であることがわかります。
●まとめ
今回はここまでです。簡単に復習しておきましょう。
- コンピュータで適当な数値を選ぶ場合は乱数を使う。
- 線形合同法は乱数を生成する簡単なアルゴリズムである。
- 線形合同法で生成される乱数 (整数) は、上位ビットはランダムになるが下位ビットはランダムではない。
- current-second は現在時刻を浮動小数点数で返す。
- 分数や浮動小数点数を整数に変換するには関数 floor, ceiling, truncate, round を使う。
- 関数 exact は不正確な数 (浮動小数点数) を正確な数 (整数 or 分数) に変換する。
- 正確な数を不正確な数に変換するには関数 inexact を使う。
- read は S 式を読み込む。
- 2 つの S 式が等しいか調べる述語には eq?, eqv?, equal? がある。
次回は、もうちょっと複雑な「数当て」ゲームを作りましょう。お楽しみに。
●プログラムリスト
;;;
;;; kazu.scm : 数当てゲーム
;;;
;;; Copyright (C) 2007-2020 Makoto Hiroi
;;;
(import (scheme base) (scheme read) (scheme write) (scheme time))
;;;
;;; 線形合同法による擬似乱数の生成
;;;
;;; 種 (seed)
(define *seed* 1)
;;; シードの設定
(define (srand x) (set! *seed* x))
;;; 整数の一様乱数
(define (irand)
(set! *seed* (modulo (+ (* 69069 *seed*) 1) #x100000000))
*seed*)
;;; 実数の一様乱数
(define (random) (* (/ 1.0 #x100000000) (irand)))
;;;
;;; 数当てゲーム
;;;
;;; 1 から 100 までの乱数を生成
(define (make-number n)
(+ (modulo (quotient (irand) #x10000) n) 1))
;;; 数字の入力
(define (input-number)
(display "please input integer (1 - 100)\n> ")
(let ((data (read)))
(cond
((not (integer? data))
(display data)
(display "is not integer\n")
(input-number))
((<= 1 data 100) data)
(else
(display "range error\n")
(input-number)))))
;;; 数当てゲーム
(define (game answer)
(let loop ((count 1))
(if (< 7 count)
(display "GameOver\n")
(let ((data (input-number)))
(cond
((= data answer)
(display "Congratulation\n"))
((< data answer)
(display "Number is greater than ")
(display data)
(newline)
(loop (+ count 1)))
(else
(display "Numbere is less than ")
(display data)
(newline)
(loop (+ count 1))))))))
;;; ゲームの実行
(define (play)
(srand (exact (floor (current-second))))
(let loop ((answer (make-number 100)))
(game answer)
(display "Try Again? (y or n)\n> ")
(if (eq? 'y (read))
(loop (make-number 100)))))
;;; 実行
(play)
●問題
次の関数を定義してください。
- 要素 x を n 個持つリストを生成する関数 my-make-list n x
- n 個の乱数 (0.0 以上 1.0 未満) を格納したリストを生成する関数 make-random-list n
- 乱数の生成には線形合同法の関数 random を使ってください。
- データを n 個読み込み、それをリストに格納して返す関数 read-data-list n
- 整数 n から m までを格納したリストを作る関数 iota n m
make-list は Scheme に定義されているので、名前を my-make-lst としました。iota は SRFI-1 に用意されていますが、仕様が異なるので注意してください。
●解答
gosh[r7rs.user]> (define (my-make-list n x) (if (zero? n) '() (cons x (my-make-list (- n 1) x)))) my-make-list gosh[r7rs.user]> (my-make-list 10 0) (0 0 0 0 0 0 0 0 0 0) gosh[r7rs.user]> (my-make-list 10 'a) (a a a a a a a a a a) gosh[r7rs.user]> (define (make-random-list n) (if (zero? n) '() (cons (random) (make-random-list (- n 1))))) make-random-list gosh[r7rs.user]> (make-random-list 10) (1.6081612557172775e-5 0.11074089794419706 0.7630801079794765 0.1799780346918851 0.9028781340457499 0.889840406132862 0.3870111908763647 0.4759426398668438 0.8821929632686079 0.1857799997087568) gosh[r7rs.user]> (define (read-data-list n) (if (zero? n) '() (cons (read) (read-data-list (- n 1))))) read-data-list gosh[r7rs.user]> (read-data-list 5) a b c d e (a b c d e) gosh[r7rs.user]> (define (iota n m) (if (> n m) '() (cons n (iota (+ n 1) m)))) iota gosh[r7rs.user]> (iota 1 10) (1 2 3 4 5 6 7 8 9 10) gosh[r7rs.user]> (iota 1 1) (1) gosh[r7rs.user]> (iota 1 0) ()