コンピュータ囲碁

出典: フリー百科事典『ウィキペディア（Wikipedia）』

これはこのページの過去の版です。ミッドランドライダー (会話 | 投稿記録) による 2012年4月4日 (水) 03:01 （個人設定で未設定ならUTC）時点の版 (→‎歴史)であり、現在の版とは大きく異なる場合があります。


囲碁

コンピュータ囲碁（コンピュータいご）とは、人工知能研究の一分野で、ボードゲームの囲碁を打てるコンピュータプログラムを作ることを目的とした試みのことを指す。

2000年代前半、日本棋院から段級位認定されたことを売りにするアプリケーションがあったが、重要な場面での手抜きなどコンピュータ囲碁特有の弱点が有り実際には級上位レベルであった。（アマ初段を認定されたアプリケーションに手談対局4、最高峰3、最強の囲碁2003、銀星囲碁3がある）。数十年の研究にもかかわらずアマチュア級位者の実力を脱することがなく、これらのプログラムが人間の初段と互先で戦って勝つのはほぼ不可能という評価をされてきた。しかし、2000年代後半に入ってモンテカルロ法を導入することにより、アマチュア段位者のレベルに向上したとされる。

歴史

コンピュータ囲碁の研究はアメリカで始まった（1962年Remusによるコンピュータ囲碁の論文「囲碁の好手、悪手に関する研究」）。最初に19路盤で動作するプログラムを書いたのは1969年のアメリカのZobristで、この時の棋力は38級程度（囲碁のルールを覚えた程度の棋力）であった。

70年代に入って、置かれた石の周辺に発生する影響力を関数として扱う手法や、石の生死を判定するアルゴリズムなどが生まれた。1979年には、攻撃と防御の基本的戦略と、完全につながった石を「連」、つながってはいないがひと塊の石として認識できる石の集まりを「群」として扱う階層パターンを持った囲碁プログラムInterim.2が15級程度の棋力を発揮した[1]。

1984年に、初めてのコンピュータ囲碁大会USENIXが開催される。翌1985年、台湾の応昌期が設立したING杯（1985-2000）は2000年までに互先で人間の名人に勝てば4000万台湾ドル（約1億4千万円）の賞金を出したことで有名になった。80年代のソフトでは、アメリカの「Nemesis」「Go Intellect」、台湾の「Dragon」、オランダの「Goliath」などが有力で、日本の第五世代コンピュータでも人工知能応用ソフトとして「碁世代」が開発された。また、この頃から、商用囲碁ソフトが販売されるようになった。

90年代になると中国の「Handtalk」、「Silver Igo」などが人間のアマチュア上級者並みの棋力に到達した。また、日本での大会としては、FOST杯（1995-1999）、世界コンピュータ囲碁大会 岐阜チャレンジ（2003-2006）などが開催された。

初期のコンピュータ囲碁のアルゴリズムは、人間の思考に近い手法を採用していた。まず、石の繋がり・地の大きさ・石の強さ（目の有無）などからある局面の状況を評価する静的評価関数をつくる。次に、評価関数の結果を元に石の活きを目指す・相手の石を殺す・勢力を拡大するなどさまざまな目的の候補着手を導く。もしくは、定石・布石・手筋などのデータベースを参照する知識ベースの手法により候補となる着手を作成する。各着手についてその後、数手進めた局面を評価関数によって評価する（ゲーム木探索）。到達局面での評価を元にミニマックス法により互いの対局者が最善手を選択した場合の現局面における各候補着手の優劣の評価を行い着手を決定する。その際、アルファベータ法を採用し、有望ではない着手の先読みを途中で打ち切り、有望な手を深く読む工夫を施した。

1993年、ランダムな候補手で終局まで対局をシミュレーションし（プレイアウトという）、その中で最も勝率の高い着手を選ぶというモンテカルロ法を応用したアルゴリズムを持つ囲碁プログラムが登場した。当初は、コンピュータの性能が低かったことと、単純にランダムな着手によってプレイアウトを行ったため従来の手法を持ったプログラムより弱かった（原始モンテカルロ碁）。2000年代後半になって、ゲーム木探索とモンテカルロ法を融合し、勝率の高い着手により多くのプレイアウトを割り当てプレイアウト回数が基準値を超えたら一手進んだ局面でプレイアウトを行う「モンテカルロ木探索」を実装した囲碁プログラム「Crazy Stone」が登場し、パソコンの計算能力の向上もあいまって格段の棋力向上を果たした。2006年、「Crazy Stone」がコンピュータオリンピアードの9路碁部門で優勝すると、急速にその手法が広がり他の多くのソフトウェアも同様のアルゴリズムを採用した。

2007年に開催された第1回UEC杯コンピュータ囲碁大会で優勝した「Crazy Stone」は、エキシビジョンマッチでプロ棋士の青葉かおりに八子をもらって勝った。翌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年10月には、第15回コンピュータオリンピアードの優勝プログラムである台湾の『ERICA』と藤沢里菜初段の対局が六子局で行われ、結果は藤沢の中押し勝ちとなった。ERICAは序盤に悪手を連発したものの、中盤からは独特の手を打ち、藤沢は「最初は順調だったが、途中から定石にない手を時々打たれて難しくなった」と対局を振り返った[4]。

2011年12月には、第５回ＵＥＣ杯コンピュータ囲碁大会のエキシビションとして、優勝した「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]

課題

チェス、将棋では、それぞれの駒の価値が異なるため駒の交換による損得を評価したり、王将･キングというターゲットがはっきりしているため王将･キングの守りが薄いか堅いかを評価するなど比較的有効な評価関数を作ることが可能であったが、囲碁では石自体に軽重がなく置かれた場所や形により要石になったりカス石になったりするためチェスや将棋ほど有効な評価関数を作ることは出来なかった。オセロでは、隅を取ることが非常に重要であるため隅を占めることを高く評価する評価関数が有効だが、囲碁では、盤面が広くここを占めれば明らかに有利という評価が難しい。さらに、将棋に比べ囲碁は最善手と次善手の差が少なく理詰めで着手を導きやすい将棋とくらべ感覚的な部分が多分にあることもコンピュータプログラム（アルゴリズム）との親和性が低い一因である。

将棋･チェス･オセロの定跡と囲碁の定石では、終局までの手数に占める定石・定跡の手数の割合が将棋・チェス･オセロのほうが高く、勝敗に対する影響度も定石に比べ定跡のほうが高いため、データベースの充実による棋力上昇は将棋・チェス・オセロのほうが効果的である。終局に向かうにつれ着手可能点が減り最終的には読みきり可能な点で等しいオセロと囲碁でも、オセロの場合は定石が終わり終局まで読みきれる終盤に至るまでの間（中盤）が囲碁と比べ圧倒的に短い。将棋・チェス・オセロ・囲碁の盤面の広さは、囲碁が一番広く[注釈 1]、しらみつぶしに着手を評価する場合も囲碁が一番困難である。このような理由により、悲観的な見方だと21世紀中に名人に勝てるコンピュータソフトは現れないだろうと言われていた。限られた範囲内の死活を問う詰碁ではしらみつぶしに着手を探ることでプロ級の評価が挙がるプログラムもあるが、実践の死活は詰碁になっている部分から石が長く連なっている場合も多く、その先で一眼できる可能性があったり他の生きた石と連絡が残っている場合があり、しらみつぶしで調べるには手数が膨大で不可能である。このためあらゆる手を読まなければならない複雑な中盤になると途端に弱くなる。特に厚みをどう評価するかは人間のプロにも非常な難題であり、これをプログラムに組み込むことはきわめて難しい。

しかし囲碁は将棋などに比べて最善手と次善手、三番手の差が小さく一本道の攻防が少ないという特徴から、ランダムなプレイを多数回行って勝率を調べることで形勢を評価することが可能であり、その性質を利用したモンテカルロ碁の登場により、2009年にはこの段階でアマチュアの最上位者やプロ目前の奨励会員三段と同等の棋力と評価されていたコンピュータ将棋よりも先に、プロ最上位者に勝つのではないかとする見解も現れた[8]。またモンテカルロ碁では従来の評価関数を用いるアルゴリズムに比べてソフト開発者の棋力がそれほど必要ない[注釈 2]ために、研究者の裾野の広がりが期待できる。

モンテカルロ碁は、終局までをシミュレーションし勝率の高い着手を選択するため計算力が棋力に大きな影響を与えるため、プレイステーション3を8台使用するソフト「不動碁」が現れるなど、計算機の廉価化も棋力向上の要素となっている。また、アルゴリズムの改良により木探索の効率化も図られている。具体的には、石の配置等からよさそうな手を判断し優先的もしくは限定的にプレイアウトを行う方法、終局図に至る手順を考慮せずすべての着手を1手目とみなすことにより1回のプレイアウトで数十倍のプレイアウト結果を得たと仮定してプレイアウト回数を稼ぐ方法などがある。モンテカルロ碁の弱点として、死活など長い一本道の末に決定的な結果が訪れるような手順を見つけにくい点がある。単純なランダム着手によるプレイアウトでは弱いが、着手点を絞るためには手の評価を行わねばならず正確な評価をしようとするほどリソースを消費しプレイアウトの数を減らさずを得ないという矛盾が生じる。現在は、着手を絞る方法をいかに簡素で効果的にするか、もしくは、プレイアウトの数を稼ぎいかに有効な手に深くモンテカルロ木探索を延ばすかというアプローチでモンテカルロ碁の研究が進んでいる。

コンピュータ囲碁棋戦

囲碁プログラム

Zen
KCC Igo（Silver Igo）
Go++（Go4++）
Crazy Stone
The Many Faces of Go
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）

注釈

  1. ^ 終局までに現れるパターンは、チェッカーで10の20～30乗通り、オセロで10の28～60乗通り、チェスで10の50～120乗通り、将棋で10の71～220乗通り、囲碁は10の171～360乗通り程度とされている。ただし、9路盤の囲碁はチェスより場合の数は少ない。
  2. ^ 将棋のBonanzaなどの例外はあるが、通常は戦法などについての知識が必要となる。

脚注

  1. ^ 人工知能概論14ページ
  2. ^ 「メイエン事件簿」第30回 かんぱいモンテカルロ 2008年9月8日
  3. ^ 囲碁ソフト『天頂の囲碁』とプロ棋士の王九段が公開対局 マイコミジャーナル2009年8月11日
  4. ^ 囲碁ソフトと藤沢初段が対戦－金沢でコンピューターチェス世界選手権 金沢経済新聞 2010年10月6日 2011年5月12日閲覧
  5. ^ Ｚｅｎ、日本勢初優勝　ＵＥＣ杯コンピュータ囲碁 朝日新聞2011年12月13日　2011年12月25日閲覧
  6. ^ 囲碁コンピューターvs人間コンピューター ニコニコインフォ 2012年2月24日 2012年3月18日閲覧
  7. ^ 囲碁ソフトがトッププロの棋士に勝利 NHK NEWS web 2012年3月17日、2012年3月18日閲覧
  8. ^ でるかコンピューター名人 囲碁に確率重視の「モンテカルロ法」朝日新聞2009年4月8日 2009年4月9日閲覧

参考文献

関連項目

外部リンク

「https://ja.wikipedia.org/w/index.php?title=コンピュータ囲碁&oldid=41936583」から取得