Google
 

English|日本語

  

The Shodan Go Bet

私は生まれつき、どうしようもなく楽天家だ。それでも、ずいぶん気を付けて、軽はずみなことはしないようにしているのだが、時々ついつい悪い癖が出てしまう。1997年のある日にも、ついつい口からするりとお金を賭ける話を出してしまった。私がどうしてそんなことを言い出してしまったのか、まず、そこから話を始めよう。

  



Go Bet II     The Bet Is Back!

At the end of 2010 John Tromp, in London, triumphed and I was forced to hand over the $1000. Now it is time to see if the bots have improved in the past 12 months, as John will play another match with a computer program.

The match is online, on KGS, this time. Best of 5 (instead of best of 7), and using 90 minutes each, with byo-yomi of 25 stones every 10 minutes. Chinese rules and 7.5pt komi are the same as last time.

Yamato, the author of Zen, was reluctant to take part a year ago, unsure of the outcome (*). Well, this year he has agreed. A sign the machines have improved... or over-confidence?

By the way, there is no money being wagered this time. At least, not by me!

Playing Schedule

New York TimeJapan TimeResult
Game 1Fri, Jan 13th, 8pmSat, Jan 14th, 10amWon by John, as white. SGF
A weak opening by Zen, but John failed to take advantage of this, and Zen seemed to be leading for much of the game. Black 61 and 67 (on the left) were weak, but Zen seemed to lose the game with some poor moves from move 120 onwards. Ingo Althöfer used Many Faces to make charts of winning percentages and expected territory; the former, at least, seems to match the expert view of the game.
Game 2Sat, Jan 14th, 8pmSun, Jan 15th, 10amWon by Zen, as white. SGF
The game was close, perhaps favouring white (Zen), but was decided when black's group at the bottom was killed (with white 126, if I've understood the experts). The white 120/122 combination was praised; Zen's earlier move at 74 in that area was not. Charts of winning percentages and expected territory as analyzed by Many Faces (thanks to Ingo again).
Game 3Sun, Jan 15th, 8pmMon, Jan 16th, 10am
Game 4Mon, Jan 16th, 8pmTue, Jan 17th, 10am
Game 5Wed, Jan 18th, 8pmThu, Jan 19th, 10am
KGS Account Name for Zen: Zen19N
KGS Account Name for John Tromp: tromp
The match will be played in the Computer Room on KGS.

Hardware

The hardware Zen runs on for this match will be operated by Hideki Kato, and will be a dual 6-core Xeon X5680 (over-clocked to 4.2Ghz).

With the over-clocking, this hardware is slightly more than twice as fast as the Amazon EC2 instance used for the London go bet. (Six to seven times faster than the notebook used for the first two games in that match.) A doubling in 12 months is a bit ahead of Moore's Law; but we were underpowered last year, relative to what I had hoped to use.

This hardware cost was about 350,000 yen (which is about US$4375 at current exchange rates).

The Zen cluster used in tournaments (zen19D, zen19S) adds two more machines (another 12 cores, giving 24 cores in total). Hideki Kato estimates it to be about one half to one stone stronger than the 12-core machine (Zen19N) by itself.

Trivia

John claims not to be worried about starting the match on Friday The Thirteenth, as he was born on one!

*: Also restrained by the contract with the publisher of Zen. Not a problem this time because Team DeepZen will be operating Zen.

初段になるのはいつか?

1997年を思い返してみよう。クローン羊のドリーが産まれ、香港は中国に返還され、ハリーポッターが生まれ、マザーテレサとダイアナ妃が亡くなられた。消費税は5%に上がり、サッカー日本代表がアジア予選を突破して、初めてのワールドカップ出場資格を得た。
そして、この年の5月。チェスのチャンピオン、カスパロフがDeep Blueというコンピュータに負けた。人間の最高の知性はコンピュータに凌駕されてしまった。

Deep Blue
Deep Blue

少々誇張して語れば、コンピュータチェスを作っていた人達は、その仕事が終わったと感じ、人工知能の新しい「目標」として、囲碁をはじめようとしていた。囲碁は、2500年の歴史のあるゲームで、コンピュータにとって、チェスよりも遥かに難しいゲームだと認識されていた。チェスと比較して、囲碁は終局までの手数は長いし、それぞれの局面で選択できる手は遥かに多い。そのため、Deep Blueで成功した、力任せで虱潰しに探索する手法は通じないからだ。

『初段』とは、
 アマチュアの本当に
 強いレベルの人

第三回FOST杯コンピュータ囲碁大会が1997年9月に東京で行われた。そのときに優勝を争ったプログラムのレベルは、大体10級前後…初段から見て、10ランク劣るレベルだった。『初段』とは、アマチュアの本当に強いレベルの人を言う。格闘技なら、黒帯を意味する。囲碁を始めたばかりの人なら、大体25-30級位であろう。 ほとんどの人が、真剣に数ヶ月取り組めば、10級程度になる。対照的に、多くの熱心なプレイヤーも初段に達することは出来ない。言い換えれば、この時点では、囲碁に真剣に取り組んでいる人ならば最強のプログラムを倒すのは簡単だった。だけれども、囲碁プログラムが初段に達したら?それは、囲碁のプレイヤーにとって、脅威的な相手となるだろう。

この1997年の大会の際に、私は囲碁のプログラマーや大会参加者/関係者に、囲碁プログラムはいつ「初段」のレベルに達すると考えているかアンケートをとってみた。 囲碁は、複数の国で行われていて、それぞれの国で段・級のレベルが多少異なるため、「国際的な初段」のレベルとして、 大体、日本でなら3段、アメリカでなら2段、ヨーロッパでなら1段を「国際的な初段」として定義してみた。 私は、いろいろな人から返事をもらい、1999年から2050年までの範囲の回答(ずいぶん幅がある答えだ!)をもらい、 computer-go メーリングリストにその結果を送った。(アンケートの結果は、このメールとアンケート結果の一覧を見て欲しい)


John TrompJohn Tromp(ジョン・トロンプ)は、そのメールにこんな返信をくれた。
みんな特に賭けるものがないから、楽観的な予想をしているんじゃないのかと私は疑ってる。もし、1000ドルを賭けようと言っても、同じ答えになるのかな?私(オランダで1級)は、2011年以前に、10ゲームの試合をやって、私自身が負かされるかどうか賭けてもいい。

私はその賭けにのった[1][7]。大体、コンピュータ囲碁のプログラムが永遠に進歩しないなんてあり得ないと思うだろう?

私は、私自身の作成したプログラムや、市販されているプログラム以外で彼に挑戦してもいいという条件をつけて貰うように彼に要求した。Johnは、それに加えて「対戦場所に持ってくることが出来るのならば」どんなハードウェアを使っても良いという条件を付け加えた。(私が「賭けを受け入れた」内容とそれに対するJohnの返答は、このメールを見て欲しい。)

Darren Cook

暗黒の数年間

そこからの数年間、コンピュータ囲碁プログラムはほとんど進歩しなかった。もちろん、ムーアの法則[2]は、有効に働いていた。コンピュータは順調に速くなっていった。だけれども、コンピュータが速くなっていくことの影響は、プログラムが速く動くようになっただけで…つまるところ、プログラムは、コンピュータの速さをうまく使えていなかった。このころの最強のプログラムの中身は、エキスパートシステム[3]と同様で、囲碁プログラムは人間の考え方の真似をすることで強くしようとしていた。人間の考え方の真似をするプログラムを作成するのは難しいので、新しい考え方をプログラムに追加するのも難しく、時間のかかる作業だ。しかも、ある考え方とある考え方との間で矛盾があり、その矛盾の間でバランスを取るのが非常に難しいこともある。

コンピュータの速さを
  うまく使えていなかった

ずっと変わらない私の信念は、『囲碁プログラムを強くするのに必要なのは、コンピュータの計算力を活かす「力任せ」の方法を見つけること』だ。 私の勘では、巨大なパターンのデータベースを作成すること…数百万、数億のパターンを含んだパターンのデータベースを作ることで、可能だと思っていた。「パターン」と言うのは、「石の並び方」のことになる。 だけど、私の実験では、その方向でのプログラムはあんまりうまくいかなかった。正確に序中盤の評価を行うためには、とても深く幅の細い探索が必要で、それは相変わらず困難だった。パターンとヒューリスティクス[4]で何とかなると思っていたのだけれども。 その方法は、相変わらずあんまりうまく行っていない。[5]

そんなわけで、私は希望を捨ててはいなかったけれど、Johnが賭けの金額をもっと大きくしようと言って来た時には、丁寧にお断りさせてもらった。

最新のニュース

2010年6月: このShodan Go Betに対しての対局は今年の12月末、ロンドンで開催することに決めました。「2010年以内」という締切りはぎりぎりだ!

British Go Association(英国囲碁協会)のお世話になって、London Open Go Tournament(ロンドン囲碁オープン)の開催地で行います. 対局詳細(英語)に参考してください。来られたら、教えてください!

このページの読者の投票によると、最初は際どい勝負だそうだったけど、最近皆さんはJohnは有利じゃないかとおっしゃっています。現在は私は皆さんの78。5%と違う意見をもっています。まだ五分五分だと思います。でも、皆さんの30。3%に応援は本当にありがとうございます。一方いつコンピュータが世界最強の囲碁プレイヤーを倒すことができる意見は全然一致していません。まだ投票していない方はしたにスクロールして意見を教えてください。



MCTS:かすかな希望

2006年の初頭、MCTS(モンテカルロ木探索[6])が強い9路盤の囲碁プログラムに使われ始めた。そのアイデアは、クレージーなものに見えた。アイデアはこうだ。コンピュータは、とにかく終局まで乱数を使って打っていく。沢山その回数を重ねて、一番勝ちやすい手を選べばいい、というものだ。私は、未だにこの方法は気狂いじみていると思うのだが、とにかく、その方法で強いプログラムが出来て、実際に動いているという事実からは逃げられない。

アルゴリズムはスケーラビリティがある…新しい
  コンピュータの計算力を使い切ることが出来る

2008年の秋には、世界中の最強クラスのプログラムは、9路盤でも、19路盤でも、MCTSアルゴリズムを使ったものになっていた。プログラムの強さは、ちょっとした伸び、なんていう物ではなく、飛躍的な伸びを見せた。おそらく、5級位一気に強くなった。もっと重要なことは、MCTSアルゴリズムは、スケーラビリティがあるということだ。コンピュータが速くなれば、その計算力を有効に使うことが出来る。そう、新たにプログラムを書かなくても、コンピュータが速くなれば、プログラムは勝手に強くなっていく。

MCTSアルゴリズムを使った最強クラスのプログラム、MoGoは、巨大なクラスターを使って、ハンデ付きのゲームで高段のプロに勝った。(この時に使われたクラスターの性能は、15TFlops…1秒間に15兆回の浮動小数点演算を行うことが出来る…もので、八段のプロ棋士に9子置かせてもらうハンデをもらい、55分の思考時間を使うことで勝つことが出来た。)また別のプログラム、CrazyStoneは、7子のハンデで8コアのコンピュータを使い、プロ4段に勝った。(訳者注:8コアのコンピュータなら、50万円程度で買うことが出来るし、持ち運ぶことも出来なくはない。) これらの結果から、コンピュータは、ほぼ初段のレベルに達したといえる。

終わりに

突然、賭けは、五分五分という感じになったように見える。それとも、私がまた楽観的になってるだけなのかな? Johnは、今やヨーロッパでの2段になっており、もうしばらく経てば3段になる。そして、コンピュータ碁のことを理解しているし、その弱点や強みも良く分かっている。 MoGoが初段レベルでプレイするには、今のところ巨大なクラスターが必要だし、賭けでは、ハードウェアは勝負の場所に持ち込まないといけないことになっている。 (と言っても、Crazy StoneやMany Faces of GoやZenなどのプログラムなら、ほぼ同じ強さを持って運べないことはないサイズのハードウェアで実現しているから、多分巨大なクラスターが必要になることはあまり問題にならないだろう。)

さて、あなたはどう思う?あなたの意見をここに投票して下さい。(結果を見て、コメントを付ける事も出来ます)
("Too Close To Call"は五分五分という意味です)

 


それから、元の調査のもう半分、コンピュータが世界最強の囲碁プレイヤーを倒す日がいつ来ると思うかにも意見を下さい。(チェスで1997年5月に、DeepBlueがカスパロフを倒した日のように。)
先のものと同じく、結果を見てコメントを付ける事も出来ます。




More...

Related Links and references

Competition Details

脚注

[1]: ちなみに、メーリングリストの過去ログをみると、どうやら楽天的だったのは、私だけじゃないみたい。 John Clarkeは、"うん、賭ける! 君のお金をただで持って行く犯罪みたいな行為だけどね。 私はそのリストには乗っていない、ただの賭博士だけど、その頃までには強いプログラムができているのは間違いないから。"と言っている。だけど、どうも真剣に賭けに乗ったようには私には思えないのだけれど。

[2]: http://ja.wikipedia.org/wiki/ムーアの法則

[3]: http://ja.wikipedia.org/wiki/エキスパートシステム

[4]: http://ja.wikipedia.org/wiki/ヒューリスティクス

[5]: 後から考えたのだけれど、私の間違いは、「唯一つの正しい道」を探索で見つけようとしたことだと思う。 MCTSは、同じように、深く細い探索を行うというアイデアを使っているけれど、そこには何も道標らしい道標はない。その代わりに、何回も何回も乱数を使った探索を行うことで、正しい答えを見つける。

[6]: この頃には、UCTと呼ばれていた。UCTとは、Upper Confidence bounds applied to Treesの略で、UCBという方法をゲーム木の探索へ応用したもの。今では、UCBを使わないプログラムもあるため、MCTS(モンテカルロ木探索)というもっと概念を広げて一般的にした言葉が使われている。

[7]: 訳者注:全体に渡り、「賭け」と翻訳していますが、日本国内の法律では「賭博」は禁止されています。DarrenとJohnは、Darrenの故郷イギリスや、Johnにとって都合の良い場所、おそらくEU圏内で勝負をすることになるでしょう。

謝辞

コメントをくれた人、投票してくれたすべての人に感謝を。池泰弘さんはこのページを翻訳してくれました。 デザインについて意見を頂いたPaul Dickinson さんと Eduardo Galvaniさんと、 この内容について意見をくれた沢山の人に感謝を。(もし、まだ何か分からない点があれば、私まで連絡を下さい。)


 

著者について

Darren CookDarren Cook(クック・ダレン)は、フリーランスのソフトウェア開発者/研究者です。イギリス人ですが、もう長い間東京に住んで東京で働いています。

熱心な関心を持つ研究は、コンピュータ碁と機械翻訳にあります。 コンテキストによって強化されたパターン認識で、これらの問題は解決できるという信念を持っており、今もそれを証明するために研究を続けています。 ここ数年、コンピュータ囲碁に関する研究としては、9路盤における序盤戦の研究を主にやっておりました。 (不幸にも、19路盤で行われる、この賭けについてそれは役に立つものではありませんでしたが…。まぁしかし、誰しも自分の好奇心には従ってみるべきです。)

ソフトウェア開発者としては、主に大規模なデータ処理に関することに関わって来ました。 たとえば、証券の取引に関する解析や、大規模データベースにおける矛盾の発見と修正、顧客情報の収集や処理を行うウェブサイトの構築などです。主にPHP,C++,ActionScriptで仕事を行っています。また、オープンソースの信奉者でもあり、いくつかのオープンソースのプロジェクトを実行してもいます。(その一つに、MLSN…「多言語間でのセマンティクスネットワーク」があります。)

実際のDarrenのスキルや経験は、http://dcook.org/work/を見て下さい。 もし、連絡を取りたい場合には、darren@dcook.orgまでメールをお願いします。 (その際には、SPAMとして処理されないように、"computer go"や"go bet"という文字列を入れてくれると助かります。)

訳者について

池 泰弘池泰弘さんはこのページを翻訳してくれました。
株式会社ワイビート
池's ページ
うさぴょんソフトウェア製作所


1971年東京生まれ
1993年筑波大学第三学群情報学類卒
同年(株)富士通ソーシアルサイエンスラボラトリ入社
2005年 病気のため退社。フリーランスとなる。
2007年より、(株)ワイビート取締役。

現在は、フリーランスのプログラマーとして主にJava/JavaScript/C++/PHP/XHTML/CSSによるWebサイトの構築やメンテナンスを手がける。その他、バイオインフォマティクスなど「まだあまり人の手の付いてないところ」を愛する。

実益を兼ねた趣味は、将棋/囲碁のプログラミング。将棋の思考は、既にいくつかをOEMで提供している。 囲碁では、MCTSを使いながら、『日本ルール』の難しさに泣いている。


© Copyright 2009, 2010 Darren Cook <darren@dcook.org>

Go board and Deep Blue images from Wikipedia.

Revision History
2009-05-26: First public release (English)
2009-06-17: Japanese translation first release
2010-06-20: Announce venue; minor tweaks.


このページから得られる広告収入は、Darrenのコンピュータ囲碁に関する活動とオープンソース開発に使われます。面白そうな広告があれば、クリックして下さると幸いです。