« June 2005 | Main | August 2005 »

July 31, 2005

次の一手問題

もう8月だというのに(もう8月だから?)、レポートがやばいやばい。そんなときはついむらむらとヘンな妄想が浮かんでくるのである。

2chの将棋プログラミングスレかどこかで「将棋ソフトの評価に次の一手問題を使う」みたいなことが書いてあったのを思い出した。オセロでも同じことができるか?例えば-CORの-リバーシ次の一手なんていうページがある。こういうところにある問題を使って、どの程度当てられるかを見てみるのもおもしろいかもしれない。

問題点は、「果たして解答とされているものと統計評価関数の決定はどちらが信頼できるのか」というところだろうか。とはいうものの、これはそれなりにオセロに長けている人によって何らかの根拠を以て導かれた「解答」なのだから、それなりの信憑性(特に序盤)はあるのではないかと個人的には考えているが…。

あとはまあ、プログラムの評価用に使うなら問題と解答の組をもっと100問とか1000問とか欲しい、というところか。

今思いついたことだが、「次の一手問題の正解率」を適合度にして評価関数を遺伝的アルゴリズムで進化させれば、それほど莫大な計算量をかけずにそこそこの評価関数が作れるかも?3年生で何か変わったことをしたい人は挑戦してみてはどうだろうか。

まあでも、「最強」を目指すならやはりBuro論文の暗唱が一番ということには変わりないと思うけど……。

追記: xhl氏から村上先生の次の一手問題を紹介された。これはすごい。

| | Comments (0) | TrackBack (0)

July 28, 2005

VC++ v.s. g++

実はVC++とgccの速度比較をしたことがなかったことに気づいたので、ちょっと実験。テストは例によってオセロである。

実験に用いたコンパイラとコンパイルオプションは以下の通り。

  • Visual C++ 7.1…/Ox(最大限の最適化)にCPU「Pentium4またはAthlon」を指定
  • g++ 3.4.1(mingw)…-O3 -march=pentium4
  • g++ 3.3.3(cygwin)…-O3 -march=pentium4 (-mno-cygwinオプションなし)

以下に示す結果が得られた(単位は秒)。

テストVC++ 7.1g++ 3.4.1(mingw)g++ 3.3.3(cygwin)
FFO#4012.59411.07812.734
FFO#4126.92224.18826.892
FFO#4229.42126.54229.39
10手読みセルフ対局31.31225.76627.422

mingw版g++の速いこと速いこと。全てのテストにおいて他を圧倒する性能を見せた。少なくとも俺のコードに対しては、VC++よりもg++の方が最適なコードを吐いてくれるようだ。さらに、遅さが懸念されたcygwin版g++であるが、特に問題はなく、普通の速度で動作した。cygwin版g++で極端な速度低下が起きる現象の再現条件が全くわからない。cygwin版とmingw版の速度の差はバージョンの差もしくはメモリアロケーションまわりのAPI呼び出しにまつわるものだろうか。

| | Comments (1) | TrackBack (0)

July 20, 2005

攻殻機動隊 S.A.C. O.S.T.3

攻殻機動隊 STAND ALONE COMPLEX Original Sound Track 3を買ってきた。発売日は明日になっているが、フライング販売してるだろうとの予想の元CD屋に行ってみたら案の定あったので即購入。

個人的に聴きたかったのが"トルキア"。2nd GIGの後半でよく使われていたがこれまでのサントラには入っていなかったので、絶対入ってるはずと思って買ったら案の定入っていた。それ以外には日テレ版OPの"Chiristmas in the silent forest"とか。

攻殻S.A.C.3rdって作るのかな?

| | Comments (0) | TrackBack (0)

ソニーがデジタル一眼レフへ進出

DC Watchより。ソニーがデジタル一眼レフへの進出を決めたようだ。

それにしてもコニカミノルタ?何でまた……という感じもするが、それよりもニコンユーザーとして気になるのはニコンのデジタル一眼レフの行方である。ニコンユーザーの間では広く知られていることだが、ニコンのデジタル一眼レフのイメージセンサーはこれまでほとんどソニーが開発・供給してきた。そのソニーが独自にデジタル一眼レフを出し、しかもαマウント陣営ということになれば、ニコンのデジタル一眼への影響も懸念される。

個人的にはソニーのセンサにはあまりいい感情を抱いていないので、このあたりで富士のスーパーCCDハニカムの提供を受けてくれないだろうか…と思うのだが、世の中そこまで単純ではないだろうか。富士ならニコンFマウントのS3Proを出していることだし、両者の関係的にも悪くない話だと思うのだが。もっともスーパーCCDハニカム搭載のニコン製カメラが出たら誰もS3Proを買わなくなるので、富士にとっては大問題かもしれない。

ところで、D200の発表ま~だ~~?

| | Comments (0) | TrackBack (0)

July 19, 2005

ML演習最終課題

えーと、最初に断っておきますと別に俺が再履修してるというわけではございません。念のため。

今年のML演習最終課題は本当にオセロ大会らしい。かつてはProlog最終課題で行われていた恒例行事がMLで復活。半分ジョークだと思っていたのだがな(ぉ

当の3年生は課題効果(*)によってあまりやる気がないようだが、まあそういわずにぜひとも頑張って欲しいところである。ちなみに俺は出るかどうか未定……去年最終課題でリバーシを出したが、今回のルールに則ったものではないし、本気で勝負するには大幅な機能追加とチューニングを施さないといけなくてめんどいのだ。

さて、なんだかんだいいつつも実はこっそり優勝狙いを考えちゃったりしてる人に向けてアドバイス。とりあえずBuro論文は暗唱するくらい読む。1~2ヶ月という期間で最も効率よく強いプログラムを作るには、やはり先人に学ぶことが一番だろう。それから何よりも重要なのは評価関数。評価関数がよくないといかに深読みしても無駄だし、そもそもmove orderingがうまくできないのであまり深く読めない。

手順としては、ボード実装→評価関数学習開始→探索ルーチン実装→評価関数作成でとりあえず強いプログラムが完成、その後置換表を実装したりチューニングしたりってことになるだろう。

持ち時間30秒の試合は定石を持っているかどうかでかなり変わってくると思われる。ただ、有名定石はともかく、自動学習定石データベースの構築にはやはり非常に正確な評価関数が求められるので、何をさしおいても評価関数ということだ。

まあ、とりあえずは、ここに出てきた用語をぐぐることあたりからはじめるといいんじゃないでしょうか。頑張ってください。期待してます。

(*)課題効果…「いかに楽しいプログラミングも課題になると退屈で鬱な懲罰的修行と化す」という、おーくら氏によって提唱された理論。CPU実験は例外的にのめり込む。

| | Comments (0) | TrackBack (0)

July 16, 2005

夏はオセロの季節

地下では3年生によるリアルオセロが流行っているようだ。オセロって人間にも打てるものなんだねぇ(ぉ
オセロといえば、Unno氏も最近はりこんでるようなのでついつい釣られてみる。

まずは先日の高速化提案。軽く書いてみたがだめだった。全然速くならない。あの程度のループは余裕で予測できますということか。まあでも遅くもなってないので採用してみるか。

次に、Dothanの力。X40を買ってからオセロベンチしてないことを思い出したので、ちょっと動かしてみた。すると驚くべき結果が。

まず終盤探索性能(FFO #40)。これはNorthwood/3.0GHzで12.3sec、Dothan 1.4GHzで18.1sec。まあ妥当なところ。驚いたのは中盤探索性能。これはNorthwood/3.0GHzが800~900knpsに対し、なんとDothan 1.4GHzは1.0~1.2Mnps。つまり、クロック周波数半分以下のDothanの方が速い!

これは、終盤では(分岐予測をミスらなければ)純粋にクロックの争いになるのに対して、中盤では評価関数のために巨大なテーブルを引いたり、置換表を引いたりする必要があるため、2次キャッシュ容量の圧倒的な差(Northwood: 512KB、Dothan: 2MB)が効いてくるためと思われる。すごいなDothan。さらに性能を上げて来るというYonahが楽しみだ。

そんな俺の今の関心事は並列αβ。xhl氏の実験結果に感動。「並列αβは全然性能が出ない」という先入観を持っていた(これはxhl氏も同じようだ)が、予想に反してなかなかの性能が出ている。これまでは並列化するといっても動作環境の点であまり現実味のない話だったが、今後2~3年のうちにデュアルコアもしくはそれ以上のコア数が当たり前になると考えられ、並列化アルゴリズムがこれまでとは比較にならないほど重要になってくる。完全に分散した環境は大げさだと思うので、まずはデュアルコアを睨んでSMP環境への対応ということになるだろう。並列化αβと、スレッドセーフかつオーバーヘッドの小さな置換表、あたりが鍵か。

| | Comments (0) | TrackBack (0)

July 09, 2005

暗黒面に堕つ

公開初日に見に行くなんて……そんなつもりは毛頭なかったのだが、今朝起きた頃からむらむらとフォースの暗黒面の誘惑がやってきて、耐えられなくなったので「コンピュータ科学を学ぶ学生としては最先端のCG技術に直に触れ体感することが必要不可欠である」と理論武装して最寄りの映画館にふらっと向かってしまった。(スターウォーズのやってる)映画館ならなんでもよかった。今は反省している。

以下、ネタバレつつ雑多な感想。

Continue reading "暗黒面に堕つ"

| | Comments (3) | TrackBack (0)

久々にオセロ

ついむしゃくしゃして、ちょっと実験をしてしまった。

現在、探索アルゴリズムにはPVSを使っているのだが、これってNegaScoutと比べてどうなのよ?と疑問に思って実験。

結果として、何も変わらないということが判明。うーん。そもそもPVSってこれでいいのか?自信なくなってきた。

あと、ふと思いついたことをメモしとこう。
IndexBoardは遅い遅い言うが、悪あがきとして、石を打つ部分を機械展開するとどうなる?mobility tableから左右に何個石を返せるかを引いてくることができるので、あとはその結果に従って「下方向に3個返す関数」とか「右上に5個返す関数」を呼ぶ……本当に速くなるのか?

| | Comments (2) | TrackBack (1)

July 05, 2005

謎のアクセス制限

なぜか、大学からだとこのblogにアクセスできない。ココログトップとか、他の人のココログの記事にはアクセスできたんだけど、なんでだ?ladiemonはバイト先からもアクセスできないとか言っていたなぁ。

そんなにやばいこと書いたかね?

サーバーに接続できないのではなく、サーバーから403を食らうので大学側のフィルタリング等の話ではなくてココログ側の問題な気がする。本郷・湯島近辺からのアクセスをdenyするようになってるのか。なんだそりゃ。

| | Comments (2) | TrackBack (0)

July 04, 2005

Wiki公開

今更ながら、CPU実験の班のWiki及び関連資料を公開した。

Firexhl Wiki

主にこれからCPU実験に取り組むことになる3年生が見るとよいのではないかと思う。なお、各班の成果物は地下のマシンise0の/export/disk0/jikken/2004/以下にある(はず)なので、そこで見ることもできる。

| | Comments (0) | TrackBack (0)

July 02, 2005

ICPC2005国内予選

1年前の「/Oxの悲劇」から1年、オセロ、コンパイラ、CPUエミュレータと着実に実装経験を積み重ね、我々Team UFOはTeam UFO/Oxとなって再びここに戻ってきた。

競技中の我々をサポートするものは、かの飲料と、マシュマロである。

Continue reading "ICPC2005国内予選"

| | Comments (0) | TrackBack (0)

« June 2005 | Main | August 2005 »