コンピュータ囲碁
テンプレート:囲碁 コンピュータ囲碁(コンピュータいご)とは、人工知能研究の一分野で、ボードゲームの囲碁を打てるコンピュータプログラムを作ることを目的とした試みのことを指す。
2000年代前半、日本棋院から段級位認定されたことを売りにするアプリケーションがあったが、重要な場面での手抜きなどコンピュータ囲碁特有の弱点が有り実際には級上位レベルであった。(アマ初段を認定されたアプリケーションに手談対局4、最高峰3、最強の囲碁2003、銀星囲碁3がある)。数十年の研究にもかかわらずアマチュア級位者の実力を脱することがなく、これらのプログラムが人間の初段と互先で戦って勝つのはほぼ不可能という評価をされてきた。しかし、2000年代後半に入ってモンテカルロ法を導入することにより、アマチュア段位者のレベルに向上したとされる。
目次
歴史
- 1960年代 … 38級程度
- 1970年代 … 15級程度
- 2000年代後半 … アマ三~四段程度
- 2010年代前半 … アマ四~六段程度
1970年代以前
コンピュータ囲碁の研究はアメリカで始まった(1962年Remusによるコンピュータ囲碁の論文「囲碁の好手、悪手に関する研究」)。最初に19路盤で動作するプログラムを書いたのは1969年のアメリカのZobristで、この時の棋力は38級程度(囲碁のルールを覚えた程度の棋力)であった。
70年代に入って、置かれた石の周辺に発生する影響力を関数として扱う手法や、石の生死を判定するアルゴリズムなどが生まれた。1979年には、攻撃と防御の基本的戦略と、完全につながった石を「連」、つながってはいないがひと塊の石として認識できる石の集まりを「群」として扱う階層パターンを持った囲碁プログラムInterim.2が15級程度の棋力を発揮した[1]。
1980年代
1984年に、初めてのコンピュータ囲碁大会USENIXが開催される。翌1985年、台湾の応昌期が設立したING杯(1985-2000)は2000年までに互先で人間の名人に勝てば4000万台湾ドル(約1億4千万円)の賞金を出したことで有名になった。
80年代のソフトでは、アメリカの「Nemesis」「Go Intellect」、台湾の「Dragon」、オランダの「Goliath」などが有力で、日本の第五世代コンピュータでも人工知能応用ソフトとして「碁世代」が開発された。また、この頃から、商用囲碁ソフトが販売されるようになった。
1990年代
90年代になると中国の「Handtalk」、「Silver Igo」などが人間のアマチュア上級者並みの棋力に到達した。また、日本での大会としては、FOST杯(1995-1999)、世界コンピュータ囲碁大会 岐阜チャレンジ(2003-2006)などが開催された。
初期のコンピュータ囲碁のアルゴリズムは、人間の思考に近い手法を採用していた。まず、石の繋がり・地の大きさ・石の強さ(目の有無)などからある局面の状況を評価する静的評価関数をつくる。次に、評価関数の結果を元に石の活きを目指す・相手の石を殺す・勢力を拡大するなどさまざまな目的の候補着手を導く。もしくは、定石・布石・手筋などのデータベースを参照する知識ベースの手法により候補となる着手を作成する。各着手についてその後、数手進めた局面を評価関数によって評価する(ゲーム木探索)。到達局面での評価を元にミニマックス法により互いの対局者が最善手を選択した場合の現局面における各候補着手の優劣の評価を行い着手を決定する。その際、アルファベータ法を採用し、有望ではない着手の先読みを途中で打ち切り、有望な手を深く読む工夫を施した。
1993年、ランダムな候補手で終局まで対局をシミュレーションし(プレイアウトという)、その中で最も勝率の高い着手を選ぶというモンテカルロ法を応用したアルゴリズムを持つ囲碁プログラムが登場した。当初は、コンピュータの性能が低かったことと、単純にランダムな着手によってプレイアウトを行ったため従来の手法を持ったプログラムより弱かった(原始モンテカルロ碁)。
2000年代
2000年代後半になって、ゲーム木探索とモンテカルロ法を融合し、勝率の高い着手により多くのプレイアウトを割り当てプレイアウト回数が基準値を超えたら一手進んだ局面でプレイアウトを行う「モンテカルロ木探索」を実装した囲碁プログラム「Crazy Stone」が登場し、パソコンの計算能力の向上もあいまって格段の棋力向上を果たした。2006年、「Crazy Stone」が第11回コンピュータオリンピアードの9路碁部門で優勝すると、急速にその手法が広がり他の多くのソフトウェアも同様のアルゴリズムを採用した。
2007年に開催された第1回UEC杯コンピュータ囲碁大会で優勝した「Crazy Stone」(2011年から『最強の囲碁』として市販)は、エキシビジョンマッチでプロ棋士の青葉かおり四段(以下、段位・称号は対局当時のもの)に八子をもらって勝った。翌2008年第2回大会優勝時には青葉に七子で勝ち、同年8月には情報処理学会のイベント「第7回情報科学技術フォーラム」でトッププロの王銘琬九段と対局し、19路盤の8子局で中押し勝ち、9路盤の黒番互先で1目勝ちをおさめた。王はこの対局を振り返って、「十九路盤の棋力を判定するならアマ三段ぐらいだが、まだ底知れない力を秘めている」「プロレベルまで、十年以内で来るのではないか」と評価している[2]。また、2008年3月には、パリ囲碁トーナメントのエキシビジョンで、モンテカルロ碁の「MoGo」がタラヌ・カタリン五段と対戦し19路盤では9子のハンデをもらって敗れたが、ハンデなしの9路盤で3局対戦し1局に勝利した。
2009年8月には、同年5月に開催された「第14回コンピュータオリンピアード」の優勝プログラム「Zen」(『天頂の囲碁』として市販)が、王銘琬から9路盤黒番コミ2目半で勝利した[3]。Zenも実力をアマチュア三~四段と評価されており、王は「従来の囲碁ソフトは読み切れる局面で力を発揮したが、このソフトは読み切れないような難しい局面において力を発揮する」と評価した。
2010年代
2010年10月には、第15回コンピュータオリンピアードの優勝プログラムである台湾の『ERICA』と藤沢里菜初段の対局が六子局で行われ、結果は藤沢の中押し勝ちとなった。ERICAは序盤に悪手を連発したものの、中盤からは独特の手を打ち、藤沢は「最初は順調だったが、途中から定石にない手を時々打たれて難しくなった」と対局を振り返った[4]。
2011年12月には、第5回UEC杯コンピュータ囲碁大会のエキシビションとして、優勝した「Zen」と鄭銘瑝九段、準優勝の「ERICA」と小林千寿五段の対局が持ち時間30分の六子局で打たれ、ERICAは敗れたがZenは中押し勝ちした。鄭はZenについて「アマチュア四段以上はある」とその実力を評価した[5]。
2012年2月25日には、ライブストリーミングサイト「ニコニコ生放送」の企画で、Zenと二十四世本因坊秀芳(石田芳夫九段)の13路盤対局が、Zenの黒番コミなしで打たれ、結果は石田の中押し勝ちとなった[6]。石田はZenの実力について、19路盤なら5子差程度ではないかと語った。
2012年3月17日には、電気通信大学のイベントで、Zenと大橋拓文五段との9路盤対局、同じくZenと武宮正樹九段との19路盤対局が行われた。大橋との対局は持ち時間20分、コミ7目で黒と白を入れ替えての2局打たれ、ZENの黒番では大橋の中押し勝ち、白番ではZenの5目勝ちとなった。武宮との対局は持ち時間30分、一局目が5子局、二局目が一局目の結果を受けての一番手直りで打たれ、一局目はZenの11目勝ち、4子局となった二局目はZenの20目勝ちとなった[7]。
2012年11月25日には、電気通信大学のイベントで、Zenと蘇耀国八段、大橋拓文五段、一力遼二段の3名が9路盤で対局した。対局はプロ一人がそれぞれ黒と白を1局ずつ持って計6局、黒番コミ7目の持碁有りで打たれ、プロの6戦6勝となった。盤面の小さな9路盤はコンピュータに有利な舞台ではあったが、プロ側は事前研究を重ね、また、一力が劣勢から逆転した第1局の勝利からもヒントを得て全勝を果たした[8]。
2013年からは「電聖戦」が開催されることとなった[9]。これはその年のUEC杯コンピュータ囲碁大会で決勝に進んだ2つのプログラムが、日本棋院のプロ棋士とハンデ付きで戦うというものである。第1回大会では石田芳夫が4子局で戦い、Zenには中押し勝ちしたもののCrazy Stoneには3目負けした。石田はCrazy Stoneを「アマ六段くらいの力は十分ある。ただ、プロレベルにはまだまだ」と評した。大会実行委員長の伊藤毅志は「プロレベルになるのは約10年後」と語った[10]。
2014年2月11日には、コンピュータ将棋と人間が対局する棋戦「電王戦」を主催するドワンゴが、囲碁版となる「囲碁電王戦」を電気通信大学の後援で開催した。第1回では、張豊猷八段と平田智也三段がZenを相手に9路盤でそれぞれ黒と白を1局ずつ持ち、合計4局が互先先番コミ6目半、持ち時間20分・秒読み30秒で打たれ、人間側の4戦4勝となった。Zenの開発者である加藤英樹は「プロ棋士にもミスがあったが、チャンスを生かすことができなかった。これまではコンピューターが打つ手の意外性で人間と戦ってきたが、研究を重ねられて通用しなくなってきたようだ。ソフトに改良を加え、来年こそは勝ちたい」と語り、張は「コンピューターの打ち方を学んでいたからこそ勝てたが、小さい碁盤ではプロとコンピューターは、ほとんど互角だと思う」と感想を話した[11]。また、第1回電王戦では世界アマチュア囲碁選手権戦 日本代表決定戦連覇の実績を持つ江村棋弘とZenの13路盤対決、政界きっての打ち手とされる小沢一郎アマ6段とZenの19路盤対決も行われており、13路盤対決は白黒を入れ替えて2局行われたがいずれも江村の勝利、1局のみ行われた19路盤対決ではZenの勝利となっている。 同年7月26日、ニコニコ囲碁サークルにおいて、小沢一郎同様政界の強豪である与謝野馨アマ7段とZenの対局が行われ、Zenが勝利している。
モンテカルロ法の限界から(後述)ここ1年程度はプログラムの進歩も頭打ちとなっており、2014年3月の第2回電聖戦では、依田紀基九段がCrazy Stone(UEC杯準優勝)、Zen(UEC杯優勝)と4子局(下手半目コミ出し)を打ち、Crazy Stoneに2目半負,Zenに中押し勝ちと,第1回とほぼ同じ結果に終わった[12]。
課題
- 評価関数が作りづらいこと
- チェス、将棋では、それぞれの駒の価値が異なるため駒の交換による損得を評価したり、王将・キングというターゲットがはっきりしているため王将・キングの守りが薄いか堅いかを評価するなど比較的有効な評価関数を作ることが可能であったが、囲碁では石自体に軽重がなく置かれた場所や形により要石になったりカス石になったりするためチェスや将棋ほど有効な評価関数を作ることは出来なかった。
- オセロでは、隅を取ることが非常に重要であるため隅を占めることを高く評価する評価関数が有効だが、囲碁では、盤面が広くここを占めれば明らかに有利という評価が難しい。
- 感覚的な部分が多いこと
- 将棋に比べ、囲碁は最善手と次善手の差が少なく、理詰めで着手を導きやすい将棋とくらべ感覚的な部分が多分にあることも、コンピュータプログラム(アルゴリズム)との親和性が低い一因である。
- データベースが膨大であること
- 将棋・チェス・オセロの定跡と囲碁の定石では、終局までの手数に占める定石・定跡の手数の割合が将棋・チェス・オセロのほうが高く、勝敗に対する影響度も定石に比べ定跡のほうが高いため、データベースの充実による棋力上昇は将棋・チェス・オセロのほうが効果的である。終局に向かうにつれ着手可能点が減り最終的には読みきり可能な点で等しいオセロと囲碁でも、オセロの場合は定石が終わり終局まで読みきれる終盤に至るまでの間(中盤)が囲碁と比べ圧倒的に短い。
- 盤面が広いこと
- 将棋・チェス・オセロ・囲碁の盤面の広さは、囲碁が一番広く[注釈 1]、しらみつぶしに着手を評価する場合も囲碁が一番困難である。
このような理由により、悲観的な見方だと21世紀中に名人に勝てるコンピュータソフトは現れないだろうと言われていた。限られた範囲内の死活を問う詰碁ではしらみつぶしに着手を探ることでプロ級の評価が挙がるプログラムもあるが、実践の死活は詰碁になっている部分から石が長く連なっている場合も多く、その先で一眼できる可能性があったり他の生きた石と連絡が残っている場合があり、しらみつぶしで調べるには手数が膨大で不可能である。このためあらゆる手を読まなければならない複雑な中盤になると途端に弱くなる。特に厚みをどう評価するかは人間のプロにも非常な難題であり、これをプログラムに組み込むことはきわめて難しい。
モンテカルロ碁の登場
しかし囲碁は、将棋などに比べて最善手と次善手、三番手の差が小さく一本道の攻防が少ないという特徴から、ランダムなプレイを多数回行って勝率を調べることで形勢を評価することが可能であり、その性質を利用したモンテカルロ碁の登場により、2009年にはこの段階でアマチュアの最上位者やプロ目前の奨励会員三段と同等の棋力と評価されていたコンピュータ将棋よりも先に、プロ最上位者に勝つのではないかとする見解も現れた[13]。またモンテカルロ碁では従来の評価関数を用いるアルゴリズムに比べてソフト開発者の棋力がそれほど必要ない[注釈 2]ために、研究者の裾野の広がりが期待できる。
モンテカルロ碁は、終局までをシミュレーションし勝率の高い着手を選択するため計算力が棋力に大きな影響を与えるため、プレイステーション3を8台使用するソフト「不動碁」が現れるなど、計算機の廉価化も棋力向上の要素となっている。また、アルゴリズムの改良により木探索の効率化も図られている。具体的には、石の配置等からよさそうな手を判断し優先的もしくは限定的にプレイアウトを行う方法、終局図に至る手順を考慮せずすべての着手を1手目とみなすことにより1回のプレイアウトで数十倍のプレイアウト結果を得たと仮定してプレイアウト回数を稼ぐ方法などがある。
モンテカルロ碁の弱点として、死活など長い一本道の末に決定的な結果が訪れるような手順を見つけにくい点がある。単純なランダム着手によるプレイアウトでは弱いが、着手点を絞るためには手の評価を行わねばならず正確な評価をしようとするほどリソースを消費しプレイアウトの数を減らさざるを得ないという矛盾が生じる。 目算が苦手であるなどの問題点[14]も明らかとなっている。
こうした問題点は2014年2月の段階でも解決されておらず、将棋でコンピュータがプロ棋士を次々と下している(将棋電王戦に関する記述を参照)中で、19路盤の囲碁における棋士の優位は全く揺らいでいない。 このため、モンテカルロ法も限界に近付いており、新手法の発見がなければプロ棋士の優位を揺るがすのは難しいとする開発者サイドの見方もある。[15]
現在は、着手を絞る方法をいかに簡素で効果的にするか、もしくは、プレイアウトの数を稼ぎいかに有効な手に深くモンテカルロ木探索を延ばすかというアプローチでモンテカルロ碁の研究が進んでいる。
コンピュータ囲碁棋戦
- コンピュータオリンピアード(囲碁部門は1989年より開催)
- ING杯(1985-2000)
- FOST杯(1995-1999)
- 世界コンピュータ囲碁大会 岐阜チャレンジ(2003-2006)
- UEC杯コンピュータ囲碁大会(2007-)
- CGFオープン(2001-)
- KGSコンピュータ囲碁トーナメント
- 21世紀杯
- 天宇杯
- SG杯
- European Go Congress
- FJK2000 コンピュータ囲碁大会
囲碁プログラム
- Zen
- KCC Igo(Korea Computer Center)
- 世界最強 銀星囲碁
- ファミリー囲碁
- バリュー囲碁
- おやじの挑戦 囲碁の奥義
- Go++(Go4++)
- 最強の囲碁(~2010)
- Crazy Stone
- 最強の囲碁(2011~)
- The Many Faces of Go
- AI囲碁
- igowin
- Goemate(HandTalk)
- HARUKA
- Wulu
- Katsunari(勝也)
- やさしい囲碁指導対局
- 若葉
- 至高の囲碁 永聖
- お気軽囲碁対局
- 囲碁世界~IV
- 達観の囲碁
- 囲碁大全
- 初段くん
- Aya(彩)
- 囲碁世界V
- 剛腕王 孟帝
- 囲碁大全コンプリート
- MASAYAN
- 囲碁初段
- Go Intellect
- 道策
- 囲碁塾
- Goliath
- 対局囲碁 ゴライアス
- GREAT 5
- GNU Go
- MoGo
- Erica
- Fungo
- Martha
- GORO
- caren(カレンのささやき)
- Leela
- Steenvreter
- 不動碁(GGGo、GGMCGo)
- 思考錯碁
- Yogo
- Smart Go
- GoLois
- Indigo
- Explorer
- NeuroGo
- Go Star
- Topgoer
- GMS
- Northan Star(Polar Star)
- GoAhead
- Dariush
- Star of Poland
- Jimmy
- 碁世代(GO Generation)
- EGO(Nemesis)
注釈
脚注
参考文献
- 『週刊碁』2009年1月12日号
- Playing with Shannon: a forum about computer go programming
- 囲碁における正確な着手予測のためのファジーパターンマッチング
- コンピュータ囲碁の歴史と将来の展望(勝也作者による解説)
- コンピュータ囲碁研究の現状と展望
- コンピュータ囲碁(<特集>ゲームとコンピュータ)(Aya開発者によるコンピュータ囲碁の解説)
- モンテカルロ法で囲碁、将棋(Aya開発者によるモンテカルロ碁の解説)
- コンピュータ囲碁における モンテカルロ法 ~理論編~
- コンピュータ囲碁における モンテカルロ法 ~実践編~
- モンテカルロ木探索 : コンピュータ囲碁に革命を起こした新手法
関連項目
外部リンク
- ↑ 人工知能概論14ページ
- ↑ 「メイエン事件簿」第30回 かんぱいモンテカルロ 2008年9月8日
- ↑ 囲碁ソフト『天頂の囲碁』とプロ棋士の王九段が公開対局 マイコミジャーナル2009年8月11日
- ↑ 囲碁ソフトと藤沢初段が対戦-金沢でコンピューターチェス世界選手権 金沢経済新聞 2010年10月6日 2011年5月12日閲覧
- ↑ Zen、日本勢初優勝 UEC杯コンピュータ囲碁 朝日新聞2011年12月13日 2011年12月25日閲覧
- ↑ 囲碁コンピューターvs人間コンピューター ニコニコインフォ 2012年2月24日 2012年3月18日閲覧
- ↑ 囲碁ソフトがトッププロの棋士に勝利 NHK NEWS web 2012年3月17日、2012年3月18日閲覧
- ↑ コンピューターにプロ全勝 九路盤、巧みにミス誘う 朝日新聞デジタル 2012年11月27日 2014年1月2日閲覧
- ↑ 第1回電聖戦
- ↑ ルポ:第1回電聖戦 囲碁ソフトが3目勝ち 仏大学教員開発の「クレージー・ストーン」 毎日新聞 2013年3月25日、2013年3月31日閲覧
- ↑ 「囲碁電王戦」プロ棋士が圧勝 NHK NEWS WEB 2014年2月11日、2014年2月13日閲覧
- ↑ 第2回電聖戦より。なお、手合割の決定に際し、運営委員会は「今年のUEC杯のコンピュータ同士の対戦から、顕著な進歩が見られなかった」としている。
- ↑ でるかコンピューター名人 囲碁に確率重視の「モンテカルロ法」 朝日新聞2009年4月8日 2009年4月9日閲覧
- ↑ 第一回囲碁電王戦初日 たかお日記 2014年2月11日 2014年3月19日閲覧
- ↑ プロ棋士やあの小沢一郎氏が参戦!!将棋電王戦の囲碁版『第1回囲碁電王戦』開催 週アスPLUS 2014年3月19日閲覧
引用エラー: 「注釈」という名前のグループの <ref>
タグがありますが、対応する <references group="注釈"/>
タグが見つからない、または閉じる </ref>
タグがありません