天声人語にモノ申す

テーマ:

朝日新聞、天声人語2005年10月30日(日曜日)付 を読んだ。苦言でも嫌味でも、ましてや突っ込みでもないのだが、何か微妙に疑問を感じたので一言書く。


チェスではわずか50年でIBM製の人工知能が破ってしまった。


この表現はかなり怪しく、大きな誤解を招きかねない。アレは真の意味での「人工知能」とは言わないし、HsuらもArtificial Intelligenceだとは思ってない筈。それと、


詰めの局面ではもう人知を超えた。


CSAの瀧澤会長が本当にこんな過激なことを仰ったのだろうか。恐ろしくて確認してないのだが、「人知を超えつつある」くらいでないと、ちょーっと問題ではなかろうか、と思っている。なぜなら、今の計算機の解図能力は「完全に人知をナメた詰ましかた」をすることが未だによくあるからだ。また、先日の王者戦では「詰があるのに詰ましてない局面」もある。熟練者なら、寧ろ詰みがありそうだと感じる局面、手数で言えば高々21手詰。これはマシンの性能と持時間の問題だけの話ではあるが、そのようなことでは人間様に示しがつかない。


羽生善治四冠でさえ、対局後の詰みの確認にはソフトを使う。


事実だとは思うが、なにも羽生四冠の名前を出す事もないと思うのだが>朝日。それはともかく、谷川ですら使う、というくらいまで行かない限りは、まだまだ改善の余地がある、ということだ。いや、既に使ってたりして…。
AD

仮想合2手延長探索

テーマ:

詰将棋のルール にちょっと興味深い図(2005/10/27)があったので、謎電といくつかの市販将棋プログラムで試験的に解いてみた。ソースは2ちゃんねるからのようである。


結論から書くと、謎電では▲39角の1手詰となる。但し、警告を出すようにしている。なお、とある市販プログラムで解くと、ヘンな動作を起こさせたりするので、計数将棋学的には結構面白い図かも知れない。


謎電では柿木のアルゴリズムの変形で仮想合2手延長探索を行っている。例えばこの図の場合、▲39角に▽28合とし、その合駒を直に取って王手を掛ける手についてのみ2手延長して探索する、というものである。反復深化4回目、つまりは7手先まで読んだ時点で、仮想合で詰むことが判り、どのような駒種であっても(その駒を使わずに)詰と判断し、特にこの場合2手目は合駒しか手がないので解の組立を中断して「▲39角までの1手」が返るようになっている。


注意しなければならないのは、仮想合処理を実装する際は「連続王手の千日手」の誤った判定を行わないようにするのがポイントになる。「取った駒を直に相手に返す」という処理とほぼ同じ動作になるので、これを言葉通りに処理すると、不詰扱いになりかねないからだ。


具体的には、▲39角▽28合▲同角▽27玉▲39角▽28合▲同飛▽17玉に▲29飛の局面が、置換表を参照した時に完全同一局面で不詰(連続王手の千日手と等価扱い)に判定してしまうとちょっと拙い。詰方基準で駒得同一盤面として詰扱いにする方がまだマシだ、という意味である。


しかしこの図は1手詰というわけではなく、不完全作として扱われるようだ。恐らく、無駄合か否かの判定基準は「1回の合で2手延命しているだけかどうか」であって、「その駒を使わずに詰ますことが出来るかどうか」ではない、ということだと思われる。この図に限って言えば、確かに▽28合は4手以上の延命になっている。


(追補) 余談だが、謎電では玉方に持駒がない時、あるいは持駒の駒種が1つしかない時は、仮想合生成・探索を行わないようにしている。
(私信) TETSU様 なるほど、そのあたりが意見の分かれるところなんですね。コメントありがとうございました。こういう局面を計算機で解かせた時に、人間に対してどのようなワーニングを出すかがポイントだと思ってるのですが、今の謎電は「解不定」と表示しているだけです。
AD

最近、FPGAネタを遠慮してたのだが、ちょっと単発的に書くことにする。なお、タイトル[*1]と本文は何ら関係がない、、、かもしれません。


FPGAというのは、PLDの進化形態の一つである。但し、進化の最終形ではないとは思う。昔からPAL/GALといった数百ゲート以下の回路をプログラミング出来るICはあった。これらは、簡単に言えば、単純なANDアレイ/ORアレイが多数用意されていて、それを結線するだけ、というものだ。アーキテクチャの進化と共にCPLDと呼ばれるようになり、それが大規模化してFPGAと呼ばれるようになった。なにやら難しいものに見えるかもしれないが、中身はLUTとFFと線材が多数用意されているだけのものだし、極論を言えば、ただのスイッチの塊でしかない。そもそも半導体とは、導体←→非導体と状態が遷移する(外から制御できる)物質・素子のことで、結局スイッチなのである。


さて、本来FPGAはASICのプロトタイピング(エミュレーション)が目的で作られたもので、個人で開発環境を用意できるようなものではなかった。しかしこのデバイスが意外と便利であることが判り、需要が増えると共にコストが下がって色んなことに応用されるようになった。DeepBlueの資料の中にもFPGAという言葉が使われているように、その時代から存在していたのである。


日本では、あのKasparov-DeepBlue戦が終った直後に、詰将棋・指将棋の探索をFPGAで出来るんじゃないか(あるいは出来る時代が来るのではないか)という発想を持った人間は既に何人も居た。電子立国日本を支えていた技術屋でなくとも、ハードを知っている人間なら誰でも容易に想像できたことなのである。ASICで出来るのならFPGAで出来ないわけがない、という単純な理由だ。


しかしながら、いかんせん当時のFPGAは規模が小さく、数万、大きくても十数万ゲート[*2]の規模でしかなかった。DeepBlueの「チェスチップ」が約75万ASICゲートであることは判っていて、将棋の探索に適用した場合ならどれくらいの規模になるか正しく見積れなかったとしても、「十年もあれば十分だろう」ということだけは皆予測出来ていたのである。これは、速度、規模、コストの全ての解決に掛かる時間、という意味である。


「十年もあれば十分」。つまりは2007年となるのだが、恐らく2005年の今日でも出来なくはない筈だ。ただ指将棋探索で、それをやった人間がいないだけの話だと思う。この2007年の目標に向けて、というわけでもないのだが、私は2003年(初代Cyclone/Stratixが出てきた時)に、仕事絡みでAlteraのセミナに行くことがあり、開発キットが半値で手に入る(当時\140k→\70k)と知って買ったのが事の始まりだ。そういうこともあって、その後コンピュータ将棋の進歩4を読んだ時に、「やられた~」と思った(笑)


因みに私が買ったのは、Nios II 開発キット Cyclone エディション [*3]である。これは以前紹介したようなPCIバスを介してCPU-FPGA間通信を行うのでなくイーサを経由する。当時、ネットワーク並列分散システムを想定していて、これを多数HUBに繋ぐつもりだったのだが、実際に試験してみるとレスポンスがかなり悪く、つまりは相当考えが甘くこの選択はちょっと失敗したなと思った。


しかしながら、開発環境の学習を含めて、ふと思いついたアイデアの実験や、機能単位の試作・検証を行う分には問題なかった。とはいえ、これは既に一世代古く、性能的に(規模的にも速度的にも)不満があるので他人にはお奨めできない。そろそろ私もPCI開発の方へ切り替えようと考えている。のだが、StratixII版がなかなか出て来ないのでもう少し様子を見るつもり。場合によっては、更にもう一世代後のキットにしようか悩むところではある。

-- 続く --


[*1] (c)1995 手塚理

[*2] 因みに、純粋にユーザがプログラミング可能なゲート数と、そこへブロック型メモリ等を含めた場合のシステムゲート数では1桁異なるので注意が必要。なお、前者は「(ユーザブル)ASICゲート数」と呼び、正味で表現される。昔は後者の約1桁大きい数字を大々的に表示していたのだが最近は自粛しているようである。例えばCycloneII EP2C35のASICゲート数は50~60万ゲート程度だが、メモリや乗算器(Embedded multiplier(s))を含めると300万ゲート近くになる。実際には、用意されているメモリ資源や乗算器を全て使い切るようなことはないので、典型的には(実質的最大は)200万ゲートを割るのが普通。

[*3] このキットで使われているFPGAは、EP1C20で20,000LE品。従ってChrillyの(現Hydraの)探索コア1個分がギリギリ実現できる規模である。なので指将棋の探索用で使うのは厳しい。

AD

秘密基地

テーマ:

昨日、ブログの形をした秘密基地を発見した。どこからもリンクが貼られてないので、きっと秘密基地だ。しかし、とあるキーワードで検索をかけると、おもいっきし上位だった。つまりアクセス数が、はっきり言って「最先端計数将棋学」をはるかに上回っているということだ。なんてことだ。それに今まで気が付かなかったとは。自分の調査能力にほとほと呆れてしまった。とりあえず内緒だが、いずれバレると思う。っていうか、既にほとんどバレてるんじゃないかと思う。ので、今は公表しない。武士の情け(笑)


さて。先日の王者戦の棋譜が公開されたので、全部並べてみた。で、印象として第15回選手権と比べると、いくらか緩い手(あるいは悪手)が目立っているような気がした。これは選手権で使われたマシンと比べると、少なからず王者戦の方がスペックダウンしている、あるいは王者戦の持時間規定に合わせたチューニングが充分出来なかった、ということなのかも知れない。


一通り謎電で終盤分析してみたのだが、やはり何か甘い手が多いような感じなのだ。それをいちいちここで指摘するのもなんだかなあ、という気がするので、一旦保留とした。もし、「いや、チビシク批判してれ」という要望がありましたら、メイルでもください。他人に厳しく、地球環境に優しい謎電の作者が、懇切丁寧にムチを打ちます(強気)


(追補) 「どこからもリンクが貼られてない」と書いたが、再度細かく調べてみると、貼られていた…。それに気が付かない方がおかしい。いやー、すみません。本当に気が付かなかったんですよ、マジで。

王者決定戦2005

テーマ:

今回、残念ながら観戦することができなかった。ので、後日棋譜が公開された後、面白い将棋を見つけだして紹介しょうと思う。結果については、詰将棋おもちゃ箱 の中のコンピュータ将棋(将棋ソフト) をご覧ください。


さて、エキシビションで現名人との角落戦が行われたことで、ちょっと思い出したことがある。私の記憶が定かであれば、生前の升田幸三の計算機将棋に対する感想。


「プロの六段まではいくだろうな」


この言葉は、名人に角落の手合まで計算機は到達できるだろう[*1]、という直観的印象を述べられたものだと思う。今回の結果は計算機の負けだったが、その手合で名人との対局が実現するまでに至ったという意味では、やや達成しつつあると言える。それとは別件だが、次のように仰っていたことも思い出した。


「米長君、笑えるうちに笑っておきなさい、いずれ泣く日が来るのだから」


升田幸三は、棋界で最も先を読める棋士だったのではないだろうか。


[*1] これは善意の解釈で、恐らく「計算機が名人に平手で勝つことは無理」という暗のニュアンスが含まれていると思われる。しかしながら、当時のプログラムの棋力からでは、現状は想像もつかないものだと考えられるので、やはり升田の直観力は半端ではないと言える。

先の「消費時間の怪」の記事を書いた後で、「一度詰を見つけた後なら、原理的に即見つけられないわけがない」という素朴な確信がよぎった。そう、あくまで素朴な確信だ。いや、計算機将棋の神様の御告げかもしれない:-)


例えば根局面で合法手が唯一つならノータイムでその手を指すように殆どのプログラムがそうなっているのではないかと思う。そういう局面はよく出てくるので実装しておいて損はないアイデアだ。その類の小さなギミック。詰があることを見つけたら、それ以降の自手番では置換表上の情報をそのままにして(ありていに言えば初期化せず)、普通に探索を行う[*1]。それだけで問題なく即刻[*2]指せるようになった。詰の主探索部では置換表にヒットしてしまって(詰があるものとして全く探索せず)スキップするが、手順組立部で最低でも解の初手を返せるようになっていたので改造は簡単だった。


この手法を用いても一局の将棋の中で稼げる時間は僅かでしかないことは判っているが、1秒を笑うものは1秒に泣きかねないので、とりあえず満足。このことは王者戦も近いし、計算機将棋開発者の皆には秘密だ[*3]


[*1] 但し、セルフプレイではないものとする。

[*2] 選手権のルールでは、思考時間1秒としてカウントされる。

[*3] 選手権と王者戦では規定が異なり、まず意味がないギミック。

専門棋士 v.s. 計算機棋士

テーマ:

世間で話題になっているらしく、先ほど米長邦雄ホームページの「まじめな私」の中にある「コンピュータ将棋とプロ棋士」の項を読んでみたのだが…。以下、個人的感想を独り言として述べる。


○将棋というゲームの難解さ

「チェス、象棋、囲碁との比較をしてもらう」のなら、探索の難易度という意味では囲碁が頂点。(一般的な)チェス系ゲームの範囲の中なら、日本の将棋が世界一難解であるとは思う。


○次には予算です

国から研究費を貰わねばならないような国家プロジェクトではない。はっきり言って、国から金を引き出そうとする事業にロクなものはない。それこそ税金の無駄遣い。国の借金をこれ以上増やさないように。飽くまで興行[*1]なのだから、スポンサから賞金が出る、という程度で充分。


○いよいよ本番です
日本中、世界中の科学技術を相手にする、というのは大袈裟。我々は核融合炉の開発をやっているわけではない。また、20年間で100億円くらいというのは、あまりにも皮算用。対局場を東京ドームにして10万人呼ぶのなら、1局1億円というのは的を得た数字にはなるが、竜王・名人相手でもそれだけの観客を動員するのは難しい。TVの放映権で1億円ならボリ過ぎ。付け加えて、これから20年間、つまりは2025年まで専門棋士側が勝ち続けるというのは、見積もりが甘過ぎる。トップクラスの開発者が本気で取り組めば、あと5年。ノンビリやってても10年。技術の進歩とはそういうもの。10年前と今の計算機将棋の棋譜を並べて比べれば判ること。


それよりなにより先ずは、専門棋士トップバッター神吉、解説内藤、実況古館、でお願いします(笑)


[*1] 誤解を招きかねない表現なので補足する。人間同士、あるいは計算機同士の将棋はスポーツと同様、競技といえるが、人間と計算機の対局は、純粋にショウorイベントだ、という意味である。一言でいえば、異種格闘技戦とさほど変わらない。特に盤外のルール(例えば持時間等)で、万人が(あるいは当事者がお互いに)フェアだと納得出来る規定を作るのは殆ど不可能だからだ。Kasparov-DeepBlue戦で揉めた筈だが、終盤DBをDeepBlueは使えたが、Kasparovに使うことを許さないルールがフェアかどうか、といった類の問題も出てくる。これは一例に過ぎず、どうやってもアンフェアな部分を排除できないのである。2日制の将棋では夜中にコンピュータの電源を切ってくれという話が出れば、ならば1日制でなければフェアじゃない話になるようなこと。キリがないので、以下省略。
(追補) そういえば例のETV特集の中で、柿木さんが「NHK杯にコンピュータ将棋枠を」という、画期的な提案をされていたのを思い出した。アレが編集でカットされず放送されていたということはあり得ない話ではないってことだ。柿木企画、今なら軽く+10%の視聴率をかせげますぜ。天下のNHKの底力を見せて頂きたい。

あなたは何秒で解けますか

テーマ:

計算機将棋プログラムが、その詰解図能力を世間に誇示しだしたのは、10年くらい前からではないかと思う。左図は、週刊将棋上での森田将棋の宣伝で、ちょっとウロ覚えなのだが「あなたは何秒で解けますか?森田将棋なら2秒です」という旨のキャッチコピーが使われていた詰物だ。

この「2秒」で解ける時のマシンスペックがどれくらいのものなのか不明だが、当時、森田将棋の詰解図性能はピカイチで、DOSベース(仮想86)で動いていた謎電で初代Pentium/90MHzを使って解いた時、探索効率が悪く10秒を切ることが出来なかった記録が残っている[*1]

今にしてみれば、この体験から、謎電の詰探索性能改善計画がスタートした気がする。「あなたは何秒で解けますか」が、「あなたのプログラムは何秒で解けますか」に読めたからだ。但し、その初速は遅く、加速も鈍かった。
左図は、'99/08にNHK・ETV特集で出て来た詰物、柿木将棋が約30秒で解いたと紹介されていた。当時、これも手元にあったMMXPentium/200MHzを使って、やっとWin32への移植が終ったばかりの謎電で試してみたら「およそ450万局面の探索で約40秒掛かった。柿木将棋といい勝負になってきたかなー」と書かれたメモが今も残っている[*2]

この詰物は、詰め上がりが○の形になるのがミソで、場合によってはそれを判断できなければ(あるいは玉方応手の探索順が悪ければ)、作意解を得られない。謎電では、そのような認識処理を行ってないので、詰ますことは出来ても正解を得ることは出来ない。

また左図は、青野照市九段作。永世名人Ⅲプレステ版で19'05"、ドリキャス版なら1'47"で解けるという話である。家庭用ゲーム機と一般のPCの性能とでは全然比べようもないが、同様に当時の謎電でMMXPentium/266MHzを用いた時、3秒程度で解けた[*3](但し、その時の謎電は最後の8手を作意ではない手順で詰ませていたので参考にならない)。「ヨッシャ、永世名人に勝ったー、はっはっはっ」と思っていたが、選手権の直接対決で永世名人に謎電が勝った試しはない(笑)

なお、この頃までの謎電は、置換表というものを実装してなかった。詰・不詰の結論を、完全にツリー管理で行うという、非常に涙ぐましく原始的なことはやってた。当然、置換表を用いた時の効率と比べれば全く比較にならない。


さて最後の左図。これは既にPN系詰探索が猛威を振いつつある時代に、近代将棋'00/02(p.38)で紹介されていた実戦図。「▲谷川は14分で詰ましたが、400MHzのCPU+RAM128MBで3時間以上掛かった」らしい。プログラム名も判らないしアバウトな表現になっているが、実際記事内では詳細を伏せてある。

現謎電(Barton/3000+,置換表1GB)で解くと39手詰、置換表がオーバフロをバリバリ起こし出して300秒位掛かるので、相当難しい実戦詰であることは確かだ。しかしながら、これくらいは古典的な探索手法のままでもサクっと詰ませたいと思うところである。でなければ、図巧8番の作意解を純粋に探索で得ようなんてのは夢のまた夢になってしまうからだ。

攻方最短・受方最長手順解(理想的には作意解)を求めるアルゴリズムを極めてみるのも面白いと思うのだが、詰解図はPN系がほぼ主流になってしまった。と言いつつ、現在最強のPN系詰探索ならどれくらいのコストで解けるのか興味あるところではある。


[*1] 現謎電では、63[ms]で解く(Barton/3000+)。

[*2] 現謎電では、2498[ms]で解ける(Barton/3000+)が、指将棋では今でも柿木将棋と勝負にならない、為念。

[*3] 現謎電では、86[ms]で解く(Barton/3000+)。

別冊MultiCore (号外)

テーマ:

既に一週間ほど前の記事ですが、Opteron 280(2.4GHz)が出てたようです。


2Way対応では最上位のOpteron 280が発売


価格的には、\160k台と非常に高価です。800番だと\200k超えるのでしょうかねえ。因みに64X2/4800+(これも2.4GHz)は、まだ\100kを切らない状況の模様。Dual2.6GHz品が出るのを待とうかどうしようか悩むところ。

以下、余談。DDR SDRAM PC3200の1GB品が\10k前後になってるのを知ってちょっと吃驚。私がPC2700の512MB品を買った3年前は1枚\25k位したのですが。メモリは価格変動が激しいことは判ってますが、うーむ、既に1/5以下ですか。

機械仕掛けの将棋指し

テーマ:

一般に良く知られているのは、こっちの「機械仕掛けの将棋指し 」ではないかと思う。このフレーズが個人的に気にいってたので、念の為 Google で調べてみたらもう一つあった。今まで全然気付かなかったが、こっちの方が初々しくて断然面白い。


機械仕掛けの将棋指し


この中の次の文章は興味深い。


「柿木義一さんは普通の会社に勤めるかたわら趣味で将棋プログラムを作っている人で、

身分としては私と同じアマチュアである。」


そういえば、そういう時代があったんですね。更に、


「これから先は理想論、いわば私の大ボラと聞き流してもらってかまわない。
8年後。これを読んでいるあなた、もしあなたがプロでない限り、あなたはコンピュータに破れます。」


なるほど、確かに。最先端的な話ではなくなるが、予測というよりそういう理想や哲学が、既にその時代からあったからこそ今があるわけで、約12年?前の話として非常に楽しめた。


「ちなみに今の夢はさらにずうずうしくなって名人をぶっ倒すことになってはいるが。」


そこまでは未だ考えてないんですが、それよりなにより先ずSPEARを直接対決でブッ倒さないと。次回選手権の目標は、そのあたりにしたい[*1]と思います。


[*1] と思いつつ、既にかれこれ10年ですよ、10年!!(泣)