ジャンケン勝敗判定マシーンを OR と INVERT だけで
ダニエル・ヒリスの「思考する機械コンピュータ」にでてくる、
ジャンケンの勝敗判定マシンを OR と INVERT だけの論理回路で設計してみました。
そもそものきっかけがヒリス本に、
OR回路 と INVERT回路 だけで AND回路 が作れるということと、
逆に AND と INVERT で OR を作ることができるというのがあって、
しかもその形の対比がきれいな相似形であったことに感動したからです。
それで、トップダウンで各機能を分割しながら設計していったんですけど、
全体を作ってから、ボトムアップで冗長な部分を最適化していったら、
意外とすっきりとしたものになってさらに感動しました。
- 作者: ダニエルヒリス,W.Daniel Hillis,倉骨彰
- 出版社/メーカー: 草思社
- 発売日: 2000/10/01
- メディア: 単行本
- 購入: 5人 クリック: 62回
- この商品を含むブログ (28件) を見る
以下はそのプロセスです。
とりあえず下記の感じで表記しています。
+---+ | | モジュール +---+ |> INVERT回路(not) | |OR OR回路 |
装置の概要としてはこういう感じです。
+----------+
a1 -----| o v w |
| |----- out1
a2 -----| |
| |
b1 -----| |
| |----- out2
b2 -----| |
+----------+
A と B がグーチョキパーのいずれかの情報を入力すると、その勝敗が出力されます。
４ビットを入力して２ビットを出力します。
ovwというのはグーチョキパーの手の形です。
それぞれのデータは以下のように定義しています。
| a1 | a2 | |
|---|---|---|
| 0 | 0 | 未確定 |
| 1 | 0 | グー o |
| 0 | 1 | チョキ v |
| 1 | 1 | パー w |
| out1 | out2 | |
|---|---|---|
| 0 | 0 | 未確定 |
| 1 | 0 | A の勝ち |
| 0 | 1 | B の勝ち |
| 1 | 1 | あいこ |
あいこの状態がヒリス本とはちょっと違っており、
0 0 の場合は、どちらかが未確定で勝敗が決まらない状態を表します。
ovw の中身はこんな感じ、
ovw +---------------------------+ | +----------+ | a1 -----| a1 -----| judge | | | | | | | a2 -----| | | a2 -----| | |-----|----- out1 | b1 -----| | | | | | | | b2 -----| | | | +----------+ | | | | +----------+ | | b1 -----| judge | | | | | | | b2 -----| | | b1 -----| | |-----|----- out2 | a1 -----| | | | | | | b2 -----| a2 -----| | | | +----------+ | +---------------------------+
２つの judge というモジュールでそれぞれの真偽値を計算します。
同じモジュールですが、入力がテレコになっています。
続いて judge の中身は、
judge
+-------------------------------------------+
| +----------+ |
a1 -----| a1 -----| !lose? | |
| | | |
| a2 -----| | |
a2 -----| | |-----+ |
| b1 -----| | | |
| | | | |
| b2 -----| | | +---+ |
| +----------+ +-----| | |
| |AND|-----|----- out
| +----------+ +-----| | |
| a1 -----| fa? | | +---+ |
| | | | |
| a2 -----| | | |
b1 -----| | |-----+ |
| b1 -----| | |
| | | |
b2 -----| b2 -----| | |
| +----------+ |
+-------------------------------------------+
!lose? というモジュールで「負けではない状態」を判断、
「負けではない状態」とは「勝ち、あいこ、どちらかが未確定」です。
fa? というモジュールでは、お互いが手を出しているか(勝敗判定可能か？)どうかを判断します。
それらを AND で結んで、「勝ちかあいこ」の状態であれば真を出力します。
次 fa? の中身、お互いに1ビットでも立っていればよいのでこういう感じになります。
fa?
+------------------------------+
a1 -----|-----| |
| |OR|-----+ +---+ |
a2 -----|-----| +-----| | |
| |AND|-----|----- out
b1 -----|-----| +-----| | |
| |OR|-----+ +---+ |
b2 -----|-----| |
+------------------------------+
!lose? の中身は一見複雑ですが、実は単純です。
!lose?
+-------------------------------------------------------------+
| +--+ |
| a1 -----| | |
a1 -----| |o?|-----+ |
| a2 -----| | | +---+ |
| +--+ +-----| | |
| |AND|----- |> -----+ |
| +--+ +-----| | | |
| b1 -----| | | +---+ | |
a2 -----| |w?|-----+ | |
| b2 -----| | | |
| +--+ | |
| | |
| | |
| +--+ | |
| a1 -----| | | |
| |v?|-----+ | +----+ |
| a2 -----| | | +---+ +-----| | |
| +--+ +-----| | | | |
| |AND|----- |> -----------|3AND|-----|-----
| +--+ +-----| | | | |
| b1 -----| | | +---+ +-----| | |
| |o?|-----+ | +----+ |
| b2 -----| | | |
| +--+ | |
| | |
| | |
| +--+ | |
| a1 -----| | | |
b1 -----| |w?|-----+ | |
| a2 -----| | | +---+ | |
| +--+ +-----| | | |
| |AND|----- |> -----+ |
| +--+ +-----| | |
| b1 -----| | | +---+ |
b2 -----| |v?|-----+ |
| b2 -----| | |
| +--+ |
+-------------------------------------------------------------+
負けていない状態を判断すればよいので、
グーのとき相手がパーでない、チョキのとき相手がグーでない、パーのとき相手がチョキでない、という条件を
すべて満たしているかどうかを判断しています。
3ANDというのは３つの入力がすべて真なら真を出力します。
3AND
+-------------------------------+
| +---+ |
in1 -----|-----| | |
| |AND|-----+ |
in2 -----|-----| | | |
| +---+ | +---+ |
| +-----| | |
| |AND|-----|----- out
in3 -----|---------------------| | |
| +---+ |
+-------------------------------+
グー、チョキ、パーの判断は下記の通り。
o?
+------------------------+
| +---+ |
in1 -----|--------------| | |
| |AND|-----|----- out
in2 -----|----- |> -----| | |
| +---+ |
+------------------------+
v?
+------------------------+
| +---+ |
in1 -----|----- |> -----| | |
| |AND|-----|----- out
in2 -----|--------------| | |
| +---+ |
+------------------------+
w?
+------------------------+
| +---+ |
in1 -----|----- |> -----| | |
| |AND|-----|----- out
in2 -----|----- |> -----| | |
| +---+ |
+------------------------+
最後に、 OR と INVERT だけで実装するので、ANDも以下のように定義します。
AND
+--------------------------------+
| |
in1 -----|----- |> -----| |
| |OR|----- |> -----|----- out
in2 -----|----- |> -----| |
| |
+--------------------------------+
あとは、これらを組み合わせると完成しますが、
ちょっと気をつけなければいけないところがあって、例えば 3AND を OR と INVERT だけで表記すると、、
3AND*
+-----------------------------------------------------------------+
| |
in1 -----|----- |> -----| |
| |OR|----- |> -----+ |
in2 -----|----- |> -----| | |
| +----- |> -----| |
| |OR|----- |> -----|----- out
in3 -----|-------------------------------------- |> -----| |
| |
+-----------------------------------------------------------------+
というようになり、 INVERT が２つ並んでいます。
賛成の反対の反対は賛成なんで、これは無駄です。
ANDモジュールは前後に INVERT があるため、
ANDが並んでいるような箇所は無駄がありそうなんで、そういうのを除去していきます。
そうやって整理するとこういう状態になります。
いきなり縦書きになっていますが、それが僕には書きやすかったからです。
!o? (グー以外)や nor( 0 0 なら 1 )とか否定ばかりで分かりにくいかも知れませんが、
nor というのは実は AND の入力部分の INVERT を除去した形で、
そういう風にみると、結構すっきりして見えると思います。
あとはこれをそのままプログラムにしてしまえば完成です。
(define (ovw a1 a2 b1 b2) (define (OR a b) (or a b)) (define (INVERT a) (not a)) (define (nor a b) (INVERT (OR a b))) (define (fa? a1 a2 b1 b2) (OR (nor a1 a2) (nor b1 b2))) (define (!lose? a1 a2 b1 b2) (define (!o? a b) (OR (INVERT a) b)) (define (!v? a b) (OR a (INVERT b))) (define (!w? a b) (OR (INVERT a) (INVERT b))) (OR (OR (nor (!o? a1 a2) (!w? b1 b2)) (nor (!v? a1 a2) (!o? b1 b2))) (nor (!w? a1 a2) (!v? b1 b2)))) (define (judge a1 a2 b1 b2) (nor (!lose? a1 a2 b1 b2) (fa? a1 a2 b1 b2))) (list (judge a1 a2 b1 b2) (judge b1 b2 a1 a2)))
入力が4ビットなんで、16通りのテストが作れます。
;; ovw_test.scm (use gauche.test) (test-start "ovw.scm") (load "./ovw") (test* "ovw#00 - -" '(#f #f) (ovw #f #f #f #f)) (test* "ovw#01 - v" '(#f #f) (ovw #f #f #f #t)) (test* "ovw#02 - o" '(#f #f) (ovw #f #f #t #f)) (test* "ovw#03 v w" '(#t #f) (ovw #f #t #t #t)) (test* "ovw#04 v -" '(#f #f) (ovw #f #t #f #f)) (test* "ovw#05 v v" '(#t #t) (ovw #f #t #f #t)) (test* "ovw#06 v o" '(#f #t) (ovw #f #t #t #f)) (test* "ovw#07 v w" '(#t #f) (ovw #f #t #t #t)) (test* "ovw#08 o -" '(#f #f) (ovw #t #f #f #f)) (test* "ovw#09 o v" '(#t #f) (ovw #t #f #f #t)) (test* "ovw#10 o o" '(#t #t) (ovw #t #f #t #f)) (test* "ovw#11 o w" '(#f #t) (ovw #t #f #t #t)) (test* "ovw#12 w -" '(#f #f) (ovw #t #t #f #f)) (test* "ovw#13 w v" '(#f #t) (ovw #t #t #f #t)) (test* "ovw#14 w o" '(#t #f) (ovw #t #t #t #f)) (test* "ovw#15 w w" '(#t #t) (ovw #t #t #t #t))
ちゃんとテストも通りました。
Testing ovw.scm ... test ovw#00 - -, expects (#f #f) ==> ok test ovw#01 - v, expects (#f #f) ==> ok test ovw#02 - o, expects (#f #f) ==> ok test ovw#03 v w, expects (#t #f) ==> ok test ovw#04 v -, expects (#f #f) ==> ok test ovw#05 v v, expects (#t #t) ==> ok test ovw#06 v o, expects (#f #t) ==> ok test ovw#07 v w, expects (#t #f) ==> ok test ovw#08 o -, expects (#f #f) ==> ok test ovw#09 o v, expects (#t #f) ==> ok test ovw#10 o o, expects (#t #t) ==> ok test ovw#11 o w, expects (#f #t) ==> ok test ovw#12 w -, expects (#f #f) ==> ok test ovw#13 w v, expects (#f #t) ==> ok test ovw#14 w o, expects (#t #f) ==> ok test ovw#15 w w, expects (#t #t) ==> ok
これをもとにして電子回路かなんかをつくって
夏休みの宿題にしたらヒーローになれるかもしれません。
