2005年12月26日

石を取り除く処理 (7)

ここまでは特に活死判定方法について考察し、判定開始〜活死判定終了までの処理を設計して来た。最後は「死んでいる石をリセットする仕掛け」を作れば盤上から「石を取り除く」ことが出来るわけだが、それと同時に死んでいる石のカウントも必要だと思われる。それも含めて考えることにする。

続きを読む
posted by Masa at 02:04| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月24日

石を取り除く処理 (6)

ユニットが動作中か否かの監視を実現する方法は、簡単に言えば「活死判定ユニットのssoが、ある時間経過して変化したか否か」を全ユニットについて検査する、ということである。ユニットの中の何れか1つでも変化があれば動作中、全く変化がなければ「結論が出た」と判定するわけだ。ここでいう「ある時間」とは「基準クロックのサイクル時間」という意味になる。

続きを読む
posted by Masa at 02:57| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月19日

石を取り除く処理 (5)

この手の回路はかなり特殊で、実質的クリティカルパスが内部データによって異なるような設計は一般に殆ど行わない。先に示したユニットを何の工夫もなく使えばトンでもなく遅くなり実用的ではなくなる。先ずその理由を考えてみることにする。

続きを読む
posted by Masa at 00:15| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月18日

石を取り除く処理 (4)

先の図の中から何れか黒石1つを取れば、そこに空点が生まれることになる。となれば、その交点ユニットのsoはOFFからONに変化し、そのことで活死判定ユニットのssoもONに変化する。その信号が上下左右の4つのユニットに対して送られることになるが、白石に対してどのようにその情報が伝搬するかをここでは考察する。

続きを読む
posted by Masa at 12:25| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月17日

石を取り除く処理 (3)

実際に先の回路を格子状に接続してみる。なお、生きているか否かを判定するユニットを今後「活死判定ユニット」と呼ぶことにする。ここでは簡単な「シングル処理」のユニットを用い、図が複雑にならないように、意味のある信号名のみ表示しているので注意。

続きを読む
posted by Masa at 00:29| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月12日

石を取り除く処理 (2)

結論を先に書くと、生きていることを報せる相手の交点は同色の石でなければならない、ということだ。そのことが先の回路では考慮されていない。このままでは、ある任意の色の石に空点が接続されているか否かの判断を正確に行うことは出来ないので、その対処を入れてみたのが下図。ここでは2つの案がある。

続きを読む
posted by Masa at 00:28| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月11日

石を取り除く処理 (1)

p.30の「3.4石を取り除く処理」は、7頁に渡り4項に分かれて解説されている。それだけ重要な処理だということで、ここは気合を入れてデザインする必要があると思われる。ざっとこの節を読んでみて感じたのは、FPGAに組み込むならハードならではのアルゴリズムに置き替えなければ意味がない、ということだ。ソフトでは関数の再帰呼び出しによって石が生きてるか否かを単純に判断できる。しかしここに書かれてある通りのことをそのままハードで行うことは、実現が難しいというより寧ろ複雑になるし、それ程速くはならない。
ハードが得意とする、てかFPGAを使うことの意味は「分散化・多並列化とデータフロ化」による処理の高速化で、再帰的手続きそのものを分散化・多並列化・データフロ化してもこの場合意味がなく、そもそもハード処理には向かない。そこで発想の転換が必要になる。
ここでは交点数と同じ数の分散並列化とデータフロ化によって(再帰処理なしで)石が生きていることを検出する方法を何回かに分けて考えることにする。余談だが「分散化」と「並列化」は似て非なるものである。但し、今回は並列化するために分散化している。念の為、言葉の定義を示す。

・並列化:複数の処理を同時に進行させる事により、効率の向上をはかる手法のこと。
・分散化:複雑・大規模な処理を複数に分割して処理し、その結果を結合して実現する手法のこと。

まず単純に考えてみる。ある石が生きているか否かの判定の基本は「四方に空点が1つでもあるか否か」である。それだけを考慮し設計した交点毎の回路が下図である。

続きを読む
posted by Masa at 00:01| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月10日

対局の流れ

本の中では一見フロチャート風で書かれているが、ここではSDで書き直してみることにした。純粋なソフト屋では見慣れてないか全く書かないかも知れないが、ファームorハード屋の場合は必須のドキュメントと言える。特にFSMを設計する場合最低でもこれを書かずに作り始める奴はいない。慎重な技術屋なら更にマトリクス(状態遷移表)を書く。

続きを読む
posted by Masa at 02:02| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月09日

碁盤の表示

p.26の3.2碁盤の表示に進む。表示とは、機械側が持つデータを人間に表し示すことだ。ソフト的には二次元配列変数board[y][x]で(x,y)位置のデータを管理し、それを何かしら目に見える形で出力すれば良いだけの話。ハード的には、最初にその内容をread(あるいはそこへ任意のデータをwrite)する為の仕掛け、つまりはアドレッシングが予め必要なので、先ずその処理をここでは考えてみる。

GPRは結局2ビット幅のメモリの、その1つと見立てることが出来る。9路盤なら2ビット幅×81のRAMとして機能出来れば良い。となれば、GPRの「住所」を決定するためのアドレスデコーダが必要になる。で、具体的に9路盤用でデザインしてみたのが下図である。

続きを読む
posted by Masa at 00:03| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月08日

碁盤の初期化

以上で、ここをご覧になる訪問者は、もー完全なハードのエキスパートであるものとして次に進む。

p.25の碁盤の初期化を行う関数。これをハード的に行うのは極めて簡単だ。先の回路図のclrn(負論理なので注意)を一旦(ON状態から)OFFにすれば初期化終了(clrnは通常ONでレジスタの中身をクリアしたい場合、一時的にOFFにする)。9路盤なら81組の、19路盤なら361組のGPRを一瞬にして初期化出来る(つまりは盤全体が完全に石なし状態となる)。
posted by Masa at 01:43| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月06日

待ってましたの第3章

第3章 碁盤プログラムの作成
やっとプログラムの話が出て来ました。トップクラスの囲碁プログラマが推奨する囲碁プログラムの作り方は? 楽しみです。ここは「節」単位で噛み締めてみる。
3.1 碁盤の表現(データ構造)
考え方としては空点と色(敵味方)の識別ができれば良いわけで2ビットで表現できるわけですが。ここではbit0を白、bit1を黒として、その色の石がある時ONということで。更に盤外表現でどちらもON。これはソフトならではの常套手法で囲碁の場合は特に合理的。ハードに置き換える場合は不要といえば不要な概念。結局交点を管理する「交点ユニット」が3種類必要。端と壁と完全な盤内(盤外を傍に持たない交点)用の3種。但しこの場合、回路記述自体は1つで充分の筈。

続きを読む
posted by Masa at 21:52| Comment(0) | 計算機囲碁 | 更新情報をチェックする

さて、第2章

第2章 囲碁プログラムの設計
p.22より引用「チェスプログラムや将棋プログラムのような先読みをするプログラム(中略)この方式が将来、主流になると予想される」
ええっ?将来!? いやあ、今現在が主流なのかと思ってました。ってことは今の主流は「探索」というものを行ってないってことなんですかね、その方が驚きですが。
で余談ですが、さっき彩の最新バージョン(5.54?)を試してみました。これは探索やってますね。9路強い。考えずに打ってると私の方が負けます。19路も考えずに打ったらいい勝負になる。おっかしいなあ、てか10年前にとある囲碁プログラムを試した時は10局やって10回勝てたんですが、しかも大差で。当時あまりに弱いんでアホらしくなって興味が失せたんですが。やっぱ技術の進歩ってのは恐ろしいなあと思いましたね、ええ。
posted by Masa at 00:25| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月05日

やっと届いた

先日発注した本が今日(正確には昨日の昼間)に届いた。で、早速バッと全体を斜め読みしてみる。やや初心者向けのような気もするが、今まで囲碁プログラムを書いたことのない私にはピッタリかもしれない。というわけで、これから少しずつ読んで、その感想を日誌的にこのブログに記録しようかと思う。
第1章 コンピュータと囲碁
p.7から引用「チェスや将棋では、駒の損得という比較的重要でかつ簡単に計算可能な基準があるが、囲碁の場合には、それに匹敵するほどはっきりした基準はない」
ええっ?そうなの!? と思った。いやあ、そういう感覚はなかったなあ。Chrillyもそうだと思う。つまり「囲碁をナメてた」かも知れない。まだ良く理解してないのだが。
http://www32.ocn.ne.jp/~yss/igo.htmlに拠れば、「囲碁のプログラムは何であんなに遅いんだ!俺がさくっとFPGAで囲碁のプログラムをハードウェア化して1年以内に9路盤で初段のプログラムを作ってやるぜ!ビールを50リッター賭けるぞ!」だそうだが、Chrillyの負け? 既に1年経ってるしなあ。
posted by Masa at 00:04| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月04日

どれくらい不思議か

例えば、"囲碁 FPGA" でググってみると、このブログが先頭に来る。これは予想すらしなかった。インタネット上で公開されているアーティクルの中で最上位。こんなことは生まれて初めてである。これを不思議と言わずして何を不思議というのだ。それくらい囲碁探索にFPGAを使うというのは、飛躍した発想なのだろうか。
posted by Masa at 00:21| Comment(0) | ブログ | 更新情報をチェックする

2005年12月03日

しかし不思議だ

元々ハード探索はBelleが原点だ。標準ロジックデバイスを約1700個使ってチェスのハード探索を行った。そこからHsuが単にワンチップ化を考え、そのアイデアをIBMにぶつけて実現したのが俗にいうチェスチップで、その並列探索の最終形がDeepBlueII。
で、チェスを単に囲碁や将棋に置き換えることは思いつきそうなものだし、今現在FPGAで動いて話題になってても良さそうなものだ。将棋(あくまで指将棋)は明らかに大変だから囲碁でなくても五目並べ(あるいは連珠)でもオセロでもいい。でもそんな話は聞いた事がない。何故作らないのだろう。いや既に存在していても世に公表されてないだけの話なのかも知れない。囲碁でやってるとしたらChrillyくらいかもしれないが。
posted by Masa at 00:13| Comment(0) | ブログ | 更新情報をチェックする

2005年12月02日

例の本を発注した

例の本とは、ズバリ「コンピュータ囲碁の入門」。
以前、http://www32.ocn.ne.jp/~yss/howtogo.htmlを読んだりはしてました。が、あまり真剣に囲碁の研究はやってなかったので、これくらいは読んでおかないと、というわけで。
このことは山下さん(特に名を出す)には秘密だ(笑)
posted by Masa at 01:00| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月01日

ブログのタイトルを変更しました

うっかり、4、5ヵ月忘れてしまってました。記録を見ると相当のアクセスがあったようで、何の更新もしてないのに、アクセスしてくださったみなさん、ありがとうございます。
本来このブログは、本家が落ちた時の連絡用で作ったのですが、あっちが安定してるので役割を終らせて別のことをやろうかと思います。但しあまり更新はできないと思いますが、思いついたら何か書くという程度で。
posted by Masa at 00:27| Comment(0) | ブログ | 更新情報をチェックする

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。