囲碁 - 囲碁と数学 - わかりやすく解説 Weblio辞書

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

囲碁

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/14 05:07 UTC 版)

囲碁と数学

「en:Go and mathematics」も参照

囲碁の特徴として、盤面が広く、また着手可能な手が非常に多いため、出現しうる局面の総数やゲーム木のサイズがほかの二人零和有限確定完全情報ゲームに比べてもきわめて大きくなることが挙げられる。また、そのルールの単純性と複雑なゲーム性から、コンピュータの研究者たちの格好の研究材料となってきた。

合法な局面の総数

19路盤の着点の総数は 19² = 361目であり、ここに黒石、白石、空点をランダムに配置したとき、その組合せの総数は3³⁶¹、およそ1.7×10¹⁷²（173桁）となる。この中には着手禁止点に石があるなどの非合法な盤面が含まれるため、この値より囲碁の合法な局面数は小さくなる。合法な局面の総数の正確な値は2016年に求められ、約2.1×10¹⁷⁰（171桁）であることが明らかにされた^[31]。正確な値は下記のとおりである^[31]。

208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935 ≃ 2.1×10^170

これは将棋の10⁶⁸ - 10⁶⁹^[32]、チェスの10⁵⁰^[33]、シャンチー（象棋）の10⁴⁸^[34]、オセロの10²⁸^[33]、チェッカーの10²⁰^[33]などと比べても非常に大きい。

ほかの大きさの碁盤の総局面数も算出されており、13路盤では約3.7×10⁷⁹、9路盤では約1.0×10³⁸である^[31]。

ゲーム木のサイズ

ゲーム木の複雑性は、将棋で10²²⁶、チェスで10¹²³、シャンチーで10¹⁵⁰と見積もられるのに対し、囲碁では10⁴⁰⁰と見積もられている^[34]^{[注 6]}。

小路盤の解析

コンピュータによる探索を利用して19路盤より小さな碁盤における最善手順の研究もなされている。結果は持碁（2路盤）、黒勝ち（3路盤）、持碁（4路盤）、黒勝ち（5路盤）となることが2003年までに解明されている^[36]^{[注 7]}。5路盤のときは初手天元で黒25目勝ちとなる^[37]。5路盤の解析は『週刊碁』の連載（1993–1994）で趙治勲（名誉名人・二十五世本因坊）によって既に行われていたが、初手が隅から始まる場合の手順に見落としのあったことが判明した^[37]。6路盤や7路盤は黒勝ちと予想されている^[36]。

コンピュータ囲碁

「コンピュータ囲碁」も参照

チェスの世界では、1996年のガルリ・カスパロフとの対局で、初めて単一のゲームで世界チャンピオンにコンピュータが勝利した。また、1997年にはオセロの世界チャンピオンであった村上健がコンピュータとの6番勝負で6戦全敗し、2006年にはシャンチーのプログラムが大師との対局に勝利、2012年には引退した将棋棋士の米長邦雄がコンピュータに敗れた。こうしたほかのゲームにおけるコンピュータの躍進と比較すると、コンピュータ囲碁の棋力は伸び悩み、2000年代前半においてもアマチュアの有段者に及ばない程度の棋力であった。

コンピュータ囲碁がほかのゲームに比較して進歩が緩やかだったのは、前述の囲碁の総局面数の多さやゲーム木の複雑性も影響しているが、それだけではない。将棋やチェス、シャンチーより局面数の少ない9路盤においても、2005年まではコンピュータはアマチュア初段の域を出ることができていなかった^[33]。初めてコンピュータが9路盤でプロに公の舞台で勝ったのは2008年のエキシビジョンマッチでのMoGo対タラヌ・カタリン戦（1勝2敗）である^[33]が、プロ側が9路盤の対策を練った2012年の電気通信大のイベント、2014年の第1回囲碁電王戦ではいずれもコンピュータ側が全敗した^[38]^[39]。

こうしたコンピュータ囲碁の進歩の難しさの一因に、囲碁において評価関数を作るのが非常に難しい点が挙げられる^[33]。将棋やチェスでは駒の損得や局面の状態に応じた評価関数が作りやすく、オセロにおいても隅や辺の重要な部分のパターンで評価関数が作成されてきた^[33]。しかし囲碁にはそうした評価方法が存在せず、すべての石の価値が平等であり、オセロの隅のように大きな重みをもつ箇所も存在しない。「形のよさ」「厚み」「味のよさ」「石の軽さ」などが複雑に絡み合っており、評価関数を設定することで強いコンピュータを作るのは非常に困難であった^[33]。

しかし2006年、レミ・クーロンがモンテカルロ法を応用して作成したCrazy Stoneがひとつの転機となる^[40]。クーロンはこれを「モンテカルロ木探索」と名付けた。従来の評価関数を作成して着手を選択させる手法とは異なり、モンテカルロ木探索ではコンピュータにランダムな着手を繰り返させて多数の対局を行わさせ、さらにその中で有望な展開に多くの探索を繰り返させ、もっとも勝率が高くなる着手を決定させる^[33]。従来の手法よりモンテカルロ木探索は囲碁に適合し、ほかのプログラムもこぞってこれを採用した^[40]。コンピュータ囲碁の棋力は2006年から1年に1-2子ほどの速さで向上し、2012年ごろにはアマ六・七段程度の棋力にまで達したが、そこからは棋力の伸びが停滞した。2015年の段階でも、コンピュータがプロに勝つにはまだ10年以上かかるとクーロンや他の関係者は語っていた^[40]。

ところが、2016年にモンテカルロ木探索にディープラーニングとニューラルネットワークの技術を組み合わせたAlphaGoをGoogle DeepMind社が発表した。AlphaGoは数千万の棋譜による学習ののち、数百万の自己対戦を繰り返し強化された。ヨーロッパのプロ棋士である樊麾に2015年10月に勝利していたことが公表され、2016年3月に行われた韓国のトップ棋士である李世乭との五番勝負も4勝1敗で制した。2017年には中国のトップ棋士である柯潔とも三番勝負を行い、3連勝して人間との戦いから引退した。

「AlphaGo対李世ドル」および「AlphaGo対柯潔」も参照

AlphaGoの登場は、コンピュータがプロを上回るのはまだまだ先だろうと考えていた囲碁界に大きな衝撃を与えた。AlphaGoの技術を使用した囲碁AIはプロ棋士を凌駕する棋力を有するようになり、AlphaGoをはじめとする囲碁AIのさまざまな手法は従来の定石や布石に大きな影響を与え、新たな布石や定石の流行を生むようになった。形勢判断も従来の目算から数値による表現に変わりつつある^[41]。

脚注

注釈

^ 日本の公式戦で使用される囲碁のルールである「日本囲碁規約」の規定上は対局者が合意しないと、無限に続く可能性もあるため、有限なゲームとは分類されないが、事実上有限なゲームで、広くプレイされているゲームであるため、適切な停止条件を考慮した上で、二人零和有限確定完全情報ゲームとして研究されている。
^ 実際に「信長から名人の称号を受けた」かには異論もある。詳細は本因坊算砂を参照。
^ あくまでも、権利であるため、パスをして相手に手番を渡すことが認められる^[7]。
^ 「直前」のみならず、対局中のすべての同一局面の再現の禁止はスーパーコウルールと呼ばれる。日本ルールでは採用されていない。
^ 双方の石ともに打たれていない点のこと
^ ただし、数学的な解のある合法な局面数とは異なり、ゲーム木の総数には明確な定義がない。ゲーム木のサイズは合法手の数と多くの棋譜の平均手数から求められているが、平均手数が数手変わるだけで算出結果が何桁も変わるため、数学的にはあまり根拠がないという指摘がある^[35]。
^ ただし、これらの知見はその前からプロ棋士による研究などで既に得られており、コンピュータによって初めて明らかになったものではない。