コンピュータ囲碁

コンピュータ囲碁は、伝統的なボードゲームである囲碁をプレイするコンピュータプログラムの作成に特化した人工知能（AI）の分野です。この分野は2つの時代に分かれています。2015年より前、その時代におけるプログラムは弱いものでした。1980年代と1990年代の最高の努力によって生み出されたAIは初心者でも負けるほどのもので、2000年代初期のAIはせいぜい中級レベルでした。プロは、AIに有利な10以上のハンディキャップを与えられたとしても、これらのプログラムを倒すことができました。チェッカーやチェスのAIとして優れたパフォーマンスを発揮したアルファベータミニマックスなどのアルゴリズムの多くは、囲碁の19x19の盤上では分岐の可能性が多すぎるため、崩壊しました。当時の技術とハードウェアでは、人間のプロ品質のプログラムを作成することは不可能でした。一部のAI研究者は、人間のようなAIを作成しない限り、この問題は解決できないと推測していました。

モンテカルロ木探索を囲碁アルゴリズムに適用したことで、 2000年代後半には目覚ましい進歩が見られ、プログラムはついに低段レベル、つまり上級アマチュアのレベルに到達できるようになりました。高段のアマチュアやプロは依然としてこれらのプログラムの弱点を突いてコンスタントに勝つことができましたが、コンピュータのパフォーマンスは中級者（一桁級）のレベルを超えて進歩していました。長い間達成不可能だと考えられていた、ハンディキャップなしで最高の人間のプレイヤーに勝つという、達成されていない魅力的な目標は、新たな関心を一気に呼び起こしました。鍵となる洞察は、機械学習とディープラーニングの応用であることが判明しました。AI 研究に特化したGoogleの買収企業DeepMindは、2015年にAlphaGoを開発し、2016年に世界に発表しました。AlphaGo は、2016年にハンディキャップなしの試合でプロの李世ドル九段を破り、その後2017年には、当時2年間世界ランキング1位を維持していた柯潔を破りました。 1995年にチェッカーが、1997年にチェスが機械に敗北したのと同じように、2016年から2017年にかけて、コンピュータプログラムはついに人類史上最高の囲碁チャンピオンに勝利した。DeepMindはAlphaGoを一般向けにリリースしなかったが、DeepMindがAlphaGoとその変種について説明した学術誌の記事に基づいて、それ以来さまざまなプログラムが構築されてきた。

プロの囲碁プレイヤーは、このゲームには直感、創造力、戦略的思考が必要だと考えています。^{[1] [2]囲碁は}人工知能（AI）の分野では長い間難しい課題と考えられており、チェスよりもかなり難しいと言われています。 [3]この分野の多くの人は、囲碁はチェスよりも人間の思考を模倣する要素を必要とすると考えていました。 [ ^{4 ]}数学者IJグッドは1965年に次のように書いています。^[5]

コンピューターで囲碁？ – コンピューターが、単に合法的なゲームではなく、合理的な囲碁ゲームをプレイするようにプログラムするには、優れた戦略の原則を形式化するか、学習プログラムを設計する必要があります。原則はチェスよりも定性的で神秘的であり、判断に大きく依存します。したがって、コンピューターが合理的な囲碁ゲームをプレイするようにプログラムするのは、チェスよりもさらに難しいと思います。

2015年以前は、最高の囲碁プログラムでもアマチュア段位レベルにしか達しませんでした。^{[6] [7]} 9×9の小さな盤上では、コンピュータの方が成績が良く、一部のプログラムはプロのプレイヤーとの9×9のゲームでほんの一部に勝つことができました。AlphaGo以前は、コンピュータが囲碁でトップクラスの人間に勝つことは決してないと主張する研究者もいました。^[8]

最初の囲碁プログラムは、 1968年にアルバート・リンゼイ・ゾブリストによってパターン認識に関する論文の一部として書かれました。^[9]このプログラムでは、領域を推定する影響関数とコを検出するゾブリストハッシュ法が導入されました。

1981年4月、ジョナサン・K・ミレンはバイト誌に、KIM-1マイクロコンピュータの1K RAMに収まる15x15の碁盤を使った囲碁プログラム「Wally」についての記事を掲載した。 ^[10] ブルース・F・ウェブスターは1984年11月に同誌に、 MacFORTHソースを含むアップル・マッキントッシュ用に書いた囲碁プログラムについての記事を掲載した。 ^[11] 囲碁のプログラムは弱く、1983年の記事では、せいぜい初心者の格付けである20級に相当し、小さい盤でしかプレイできないことが多かったと推定されている。[ ¹² ]ハードウェアが大幅に改良された後、2003年にはインターネット囲碁サーバー（IGS）で19x19サイズの盤 でプレイしたAIの強さは20～15級程度だった。^[13]

1998年、非常に強いプレイヤーが25～30石のハンディキャップを与えながらコンピュータプログラムに勝つことができた。これは人間のプレイヤーならまず受けないほどの大きなハンディキャップである。1994年の世界コンピュータ囲碁選手権では、優勝したプログラムであるGo Intellectが15石のハンディキャップを受けながら若手プレイヤーに3試合すべて負けたというケースもあった。^[14]一般的に、プログラムの弱点を理解してそれを利用したプレイヤーは、大きなハンディキャップがあっても勝つことができた。^[15]

2006 年 (2007 年に論文を発表)、レミ・クーロンはモンテ カルロ木探索と呼ばれる新しいアルゴリズムを作成しました。^[16] このアルゴリズムでは、通常どおり、移動ごとに分岐する可能性のある将来のゲーム ツリーが作成されます。ただし、コンピューターは、ランダム プレイアウトを繰り返してツリーの終端リーフを「スコアリング」します (他の問題に対するモンテ カルロ戦略と同様)。利点は、このようなランダム プレイアウトを非常に迅速に実行できることです。ランダム プレイアウトはポジションの実際の価値に対応しないという直感的な反論は、予想されたほどこの手順にとって致命的ではないことが判明しました。アルゴリズムの「木探索」側は、探索する適切な将来のゲーム ツリーを見つけるのに十分に修正されました。この方法に基づく MoGo や Fuego などのプログラムは、以前の古典的な AI よりも優れたパフォーマンスを示しました。最高のプログラムは、探索できる可能性が少ない小さな 9x9 ボードで特に優れたパフォーマンスを発揮しました。 2009 年には、 19x19 盤上の KGS 囲碁サーバーで低段位レベルに到達し、それを維持できる最初のプログラムが登場しました。

2010年、フィンランドで開催された2010年ヨーロッパ囲碁大会で、MogoTWは19路盤でCatalin Taranu （5人）と対戦した。MogoTWは7石のハンデキャップを受けて勝利した。^[17]

2011年、ZenはKGSサーバーで1手15秒の対局で5段に到達した。このランクに到達したアカウントは、26コアマシンで稼働するZenのクラスターバージョンを使用している。^[18]

2012年、ゼンは5石ハンディキャップで竹宮正樹（9p）を11ポイントで破り、続いて4石ハンディキャップで20ポイントの勝利を収めました。^[19]

2013年、クレイジーストーンは19×19のゲームで石田善雄（9p）を4石ハンディキャップで破った。 ^[20]

2014年のコードセントリック囲碁チャレンジは、クレイジーストーンとフランツ＝ヨゼフ・ディックハット（6d）の間で、19x19の対局で5戦先取の互角の試合が行われた。これより強いプレイヤーが囲碁プログラムと対等な条件で真剣勝負をすることに同意したことはこれまでなかった。フランツ＝ヨゼフ・ディックハットが勝利したが、クレイジーストーンは1.5ポイント差で初戦を勝利した。^[21]

Google DeepMindが開発したAlphaGoは、以前の囲碁プログラムと比較してコンピュータの強さにおいて大きな進歩を遂げた。ディープラーニングとモンテカルロ木探索を組み合わせた技術を採用した。^{[22] 2015年10月、AlphaGoはトーナメント形式でヨーロッパ囲碁チャンピオンの}ファン・フイを5回中5回 破った。 ^[23] 2016年3月、AlphaGoは5試合のうち最初の3試合でイ・セドルに勝利した。 ^[24] 9段の名人がハンディキャップなしでコンピュータとプロの対局を行ったのはこれが初めてだった。 ^[25]イは4試合目に勝利し、この勝利を「非常に貴重」なものと表現した。^[26] AlphaGoは2日後に最終戦に勝利した。^{[27] [28]} この勝利により、AlphaGoはフルサイズの盤上でハンディキャップなしで9段の人間のプロに勝利した最初のプログラムとなった。

2017年5月、AlphaGoはFuture of Go Summitでの3局勝負で、当時世界ランキング1位だった柯潔を破った^{[29] [30]}。^[31]

2017年10月、DeepMindは、自己対戦のみでトレーニングされたAlphaGoの新バージョンを公開した。このバージョンは、これまでのすべてのバージョンを上回り、100試合中89試合で柯潔バージョンに勝利した。^[32]

AlphaGoの基本原理がNature誌に発表されて以来、他のチームも高レベルのプログラムを作成できるようになりました。それ以来、囲碁AIの作業は主に、他のすべてよりもはるかに強力であることが証明されたAlphaGoの構築に使用された技術をエミュレートすることで構成されてきました。2017年までに、ZenとTencentのプロジェクトFine Artの両方が、非常に高レベルのプロを時々打ち負かすことができました。オープンソースのLeela Zeroエンジンも作成されました。

長い間、コンピュータ囲碁はコンピュータチェスとは根本的に異なる問題を提起するというのが広く信じられていた意見だった。多くの人は、強い囲碁プログラムは、汎用的な人工知能技術の根本的な進歩の結果として、遠い将来にのみ達成できるものだと考えていた。問題が実現可能だと考える人たちは、人間の専門家に対抗するにはドメイン知識が必要だと信じていた。そのため、この時期のコンピュータ囲碁開発の大部分は、人間のような専門知識を表現し、これをローカルサーチと組み合わせて戦術的な性質の質問に答える方法に重点が置かれていた。その結果、多くの特定の状況にうまく対処するプログラムは生まれたが、ゲーム全体の処理には非常に顕著な弱点があった。また、これらの古典的なプログラムは、利用可能なコンピューティング能力の増加からほとんど何も得られなかった。この分野の進歩は概して遅かった。

ボードのサイズ

強力なプログラムを作成するのが難しい主な理由の 1 つとして、ボードのサイズが大きいこと (19×19、交差点が 361 個) が挙げられます。ボードのサイズが大きいと、大幅な検索拡張やプルーニングヒューリスティック なしでは、アルファベータ検索でディープ ルックアヘッドを実現できなくなります。

2002年、MIGOS（MIni GO Solver）と呼ばれるコンピュータプログラムが5×5の囲碁を完全に解きました。黒が勝ち、盤上全体を獲得しました。^[33]

移動オプションの数

チェスとの比較を続けると、囲碁の動きはゲームのルールによってそれほど制限されません。チェスの最初の動きでは、プレイヤーは 20 の選択肢を持っています。囲碁のプレイヤーは、対称性を考慮して 55 の異なる合法的な動きから始めます。対称性が崩れるとこの数は急速に増加し、すぐに盤上の 361 のポイントのほぼすべてを評価する必要があります。

評価関数

ゲームで最も基本的なタスクの 1 つは、盤上の位置を評価することです。つまり、どちら側が有利で、その差はどの程度かということです。チェスでは、木における将来の位置の多くは、一方の側が直接勝利することになり、盤には単純な資材カウントにおける評価のための合理的なヒューリスティックと、ポーン構造などの特定の位置要因があります。一方がクイーンを何の利益もなく失った将来は、明らかにもう一方の側が有利です。このようなタイプの位置評価ルールは、囲碁に効率的に適用できません。囲碁の位置の価値は、グループが生きているかどうか、どの石を互いに接続できるか、強い位置がどの程度の影響力を持つか、または弱い位置がどの程度攻撃されるかに関するヒューリスティックを決定するための複雑な分析に依存します。置かれた石はすぐには影響を与えないかもしれませんが、多くの動きの後、盤上の他の領域が形を整えるにつれて、後から振り返ってみると非常に重要になる可能性があります。

盤面の状態を適切に評価しないと、AI は誤って有利だと思い込んで実際には有利ではないポジションに向かって行動することになります。

生と死

囲碁プレイヤーにとっての主な関心事の 1 つは、どのグループの石を生かしておくことができ、どのグループを捕獲できるかということです。この一般的な種類の問題は、生死判別問題として知られています。知識ベースの AI システムは、盤上のグループの生死状態を理解しようとすることがあります。最も直接的なアプローチは、問題の石に影響を与える可能性のある動きについてツリー検索を実行し、メインのプレイ ラインの終了時に石の状態を記録することです。ただし、時間とメモリの制約があるため、どの動きが石のグループの「生」に影響を与えるかを完全に正確に判断することは通常不可能です。これは、考慮すべき動きを選択するために何らかのヒューリスティックを適用する必要があることを意味します。最終的な影響は、特定のプログラムでは、プレイ速度と生死の読み取り能力の間にトレードオフがあるということです。

すべての囲碁プログラムが取り組まなければならない問題は、ゲームの現在の状態をどのように表現するかということです。盤面を表現する最も直接的な方法は、1 次元または 2 次元配列として表現することです。配列の要素は盤面上の点を表し、白石、黒石、または空の交差点に対応する値を取ることができます。捕獲された石の数、誰の番か、およびコ ルールによりどの交差点が違法であるかを保存するには、追加のデータが必要です。一般的に、機械学習プログラムはこの最も単純な形式で停止し、有機 AI が盤面の意味を独自に理解できるようにします。おそらく、モンテ カルロ プレイアウトを使用して、プレーヤーにとって盤面が良いか悪いかを「スコア」するだけです。ただし、人間の戦略を直接モデル化しようとした「古典的な」AI プログラムは、ゲームの状態を表現する際に、死んでいると思われる石、無条件に生きている石、相互に生きている セキ状態の石などのデータを重ねるなど、さらに進む可能性があります。

歴史的に、シンボリック人工知能技術は囲碁 AI の問題に取り組むために使用されてきました。 ニューラル ネットワークは、それ以前の数十年間では実現不可能なほど高価だった膨大な計算能力を必要としたため、2000 年代に代替アプローチとして試され始めました。これらのアプローチは、囲碁のゲームが持つ高い分岐係数やその他の多くの難しさの問題を軽減しようとします。

プログラムが行う必要がある唯一の選択は、次の石をどこに置くかです。しかし、1 つの石が盤全体に及ぼす影響は多岐にわたるため、またさまざまな石のグループが互いに複雑な相互作用を及ぼす可能性があるため、この決定は困難です。この問題に対処するために、さまざまなアーキテクチャが生まれています。一般的な手法と設計哲学には次のものがあります。

• 何らかの形のツリー検索、
• パターンマッチングと知識ベースシステム、
• モンテカルロ法の応用、
• 機械学習の活用。

ゲームプレイソフトウェアを作成するための従来の AI手法の1 つは、ミニマックス 木探索を使用することです。これは、特定のポイントまで盤上のすべての仮想的な動きを実行し、評価関数を使用して現在のプレーヤーのその位置の価値を推定することを伴います。最良の仮想的な盤につながる動きが選択され、このプロセスが各ターン繰り返されます。木探索はコンピュータチェスでは非常に効果的でしたが、コンピュータ囲碁プログラムではあまり成功していません。これは、囲碁盤に対して効果的な評価関数を作成することが従来困難であったことと、各側が実行できる可能性のある動きの数が多いために分岐係数が高くなるためです。これにより、この手法の計算コストが非常に高くなります。このため、探索木を広範に使用する多くのプログラムは、完全な 19×19 の盤ではなく、より小さな 9×9 の盤でしかプレイできません。

速度とメモリの両方の観点から、探索木のパフォーマンスを大幅に向上できる手法がいくつかあります。アルファベータ剪定、主変異探索、MTD(f)などの剪定手法は、強度を損なうことなく有効な分岐係数を減らすことができます。生死などの戦術的な領域では、囲碁は特に転置表などのキャッシュ手法に適しています。これらは、特に反復深化アプローチと組み合わせると、繰り返しの労力を減らすことができます。フルサイズの囲碁盤を転置表にすばやく格納するには、数学的に要約するためのハッシュ手法が通常必要です。 ゾブリストハッシュは、衝突率が低く、ゼロから計算するのではなく、2つのXORだけで各移動ごとに反復更新できるため、囲碁プログラムで非常に人気があります。これらのパフォーマンス向上手法を使用しても、フルサイズの盤上の完全な木検索は依然として法外に遅いです。相手がすでに強い手を考慮しない、捕獲されそうな石のグループの隣の手は常に考慮するなどの選択的拡張や、ドメイン固有の剪定テクニックを大量に使用することで、検索を高速化できます。ただし、これらのオプションは両方とも、ゲームの流れを変える重要な手を考慮しないという重大なリスクをもたらします。

コンピュータ競技の結果は、少数の適切な動きを選択するためのパターン マッチング技術と、高速な局所的戦術検索 (上記で説明) を組み合わせることで、かつては競争力のあるプログラムを作成するのに十分であったことを示しています。たとえば、GNU Go は2008 年まで競争力がありました。

人間の初心者は、名人による昔のゲームの記録から学ぶことが多い。1990年代のAIの研究では、AIに人間のような囲碁の知識のヒューリスティックを「教える」試みがよく行われた。1996年、ティム・クリンガーとデビッド・メクナーは、最高のAIの初心者レベルの強さを認め、「囲碁の知識を表現し維持するためのより優れたツールがあれば、より強力な囲碁プログラムを開発できると信じている」と主張した。^[34] 彼らは、石の一般的な配置とその位置を認識することと、局所的な戦いに集中することという2つの方法を提案した。2001年、ある論文は「囲碁プログラムは依然として知識の質と量の両方が不足している」と結論付け、これを修正することで囲碁AIのパフォーマンスが向上するとしている。^[35]

理論的には、専門知識を利用することで囲碁ソフトウェアは改善されるだろう。強力なプレーのための何百ものガイドラインや経験則が、ハイレベルのアマチュアとプロの両方によって策定されている。プログラマーの仕事は、これらのヒューリスティックをコンピューターコードに形式化し、パターンマッチングとパターン認識アルゴリズムを使用して、これらのルールがいつ適用されるかを認識することである。また、これらのヒューリスティックを「スコアリング」できることも重要であり、矛盾するアドバイスが出されたときに、システムがどちらのヒューリスティックがより重要で状況に適切であるかを判断する方法を持つようにする。比較的成功した結果のほとんどは、プログラマーの囲碁のスキルと囲碁に関する個人的な推測から生まれたものであり、正式な数学的主張から生まれたものではない。彼らは、コンピューターに囲碁のプレー方法を模倣させようとしている。2001年頃の競争力のあるプログラムには、定石など、ゲームのさまざまな側面と戦略を扱う50〜100のモジュールが含まれていた。^[35]

専門家の知識に大きく依存するプログラムの例としては、Handtalk (後に Goemate として知られる)、The Many Faces of Go、Go Intellect、Go++ などがあり、いずれも世界最高の囲碁プログラムとみなされたことがある。しかし、これらの方法は最終的に収穫逓減の法則に陥り、フルサイズの盤上ではせいぜい中級レベルを超えることはなかった。特に問題だったのは、ゲーム全体の戦略だった。専門家システムがパターンを認識し、局所的な小競り合いのプレイ方法を知っていたとしても、将来的に迫りくるより深い戦略上の問題を見逃す可能性がある。その結果、プログラムの強さは部分の総和よりも小さくなる。個々の動きは戦術的には良いかもしれないが、プログラムは騙されて操作され、引き換えに多くのものを譲り渡してしまい、全体として負けてしまう可能性がある。2001 年の調査では、「たった 1 つの悪い動きで良いゲームが台無しになることがある。ゲーム全体でのプログラムのパフォーマンスは、マスター レベルよりはるかに低くなる可能性がある」と述べられている。^[35]

手作業でコード化された知識と検索を使用する代わりに、モンテカルロ法を使用する方法があります。これは、可能性のある動きのリストを生成し、各動きに対して、結果として得られる盤上で何千ものゲームをランダムにプレイすることによって行われます。現在のプレーヤーにとって最良のランダムゲームのセットにつながる動きが、最良の動きとして選択されます。誤りの可能性がある知識ベースのシステムは必要ありません。ただし、評価に使用される動きはランダムに生成されるため、特定の対戦相手の反応を除いては優れている動きが、誤って良い動きと評価される可能性があります。この結果、全体的な戦略的意味では強力であっても、戦術的には不完全なプログラムが生成されます。^[要出典]この問題は、動きの生成にドメイン知識を追加し、ランダムな進化に加えてより深いレベルの検索の深さを追加することで軽減できます。モンテカルロ手法を使用するプログラムとしては、Fuego、^[36]、 The Many Faces of Go v12、^[37]、 Leela、^[38]、 MoGo、^[39]、 Crazy Stone、MyGoFriend、^[40]、Zenなどがあります。

2006年、新しい探索手法である木に適用された上側信頼境界（UCT）^[41]が開発され、多くの9路盤モンテカルロ囲碁プログラムに適用され、優れた結果が出ました。UCTは、これまでに収集されたプレイアウトの結果を使用して、より成功するプレイラインに沿って探索を導きますが、代替ラインの探索も可能にします。UCT手法と、より大きな19路盤でのプレイのための他の多くの最適化により、MoGoは最強の研究プログラムの1つになりました。19路盤囲碁へのUCT手法の初期の成功した適用には、MoGo、Crazy Stone、Mangoなどがあります。^[42] MoGoは2007年のコンピュータオリンピックで優勝 し、はるかに複雑でない9路盤囲碁で、郭娟プロ5段とのブリッツゲーム3回のうち1回に勝利しました。The Many Faces of Go ^[43

モンテカルロベースの囲碁エンジンは、人間のプレイヤーよりも、局地的な戦いを続けるよりも、盤上の他の場所への手である手抜きをプレイする傾向が強いという評判がある。これは、これらのプログラムが登場した当初は、しばしば弱点とみなされていた。 ^[44] とはいえ、この傾向はAlphaGoのプレイスタイルにも引き継がれ、優勢な結果を残してきたため、これは「弱点」というよりは「癖」なのかもしれない。^[45]

知識ベース システムのスキル レベルは、プログラマーと関連するドメイン エキスパートの知識と密接に関連しています。この制限により、真に強力な AI をプログラムすることが困難になっています。別の方法として、機械学習技術を使用します。この方法では、プログラマーがプログラムする必要があるのは、ポジションの価値を分析するルールと簡単なスコアリング アルゴリズムだけです。理論上は、ソフトウェアが独自のパターン、ヒューリスティック、戦略を自動的に生成します。

これは通常、ニューラルネットワークまたは遺伝的アルゴリズムに、プロのゲームの大規模なデータベースをレビューするか、自分自身または他の人やプログラムと対戦して多くのゲームをプレイさせることによって行われます。これらのアルゴリズムは、このデータを活用してパフォーマンスを向上させることができます。機械学習技術は、主に他の技術に依存するプログラムの特定のパラメータを調整するために、それほど野心的ではないコンテキストで使用することもできます。たとえば、Crazy Stoneは、 Eloレーティングシステムの一般化を使用して、数百のサンプルゲームから移動生成パターンを学習します。^[46]

このアプローチの最も有名な例は AlphaGo で、これは以前の AI よりもはるかに効果的であることが証明されました。最初のバージョンでは、何百万もの既存のポジションを分析して、さらに分析する価値があると優先順位を付ける可能性のある動きを決定するレイヤーと、最初のレイヤーから提案された可能性のある動きを使用して独自の勝利の可能性を最適化しようとする別のレイヤーがありました。AlphaGo は、モンテカルロ木探索を使用して、結果として得られたポジションを評価しました。AlphaGo の後のバージョンである AlphaGoZero は、既存の囲碁ゲームからの学習を避け、代わりに繰り返しプレイすることからのみ学習しました。ニューラル ネットを使用した他の初期のプログラムには、NeuroGo と WinHonte があります。

コンピュータ囲碁の研究成果は、認知科学、パターン認識、機械学習などの他の類似分野にも応用されている。^[47] 応用数学の一分野である組合せゲーム理論は、コンピュータ囲碁に関連するトピックである。^[35]

ジョン・H・コンウェイは、囲碁の終盤の解析に超実数を適用することを提案した。このアイデアは、エルウィン・R・バーレカンプとデイビッド・ウルフの著書『数学的囲碁』でさらに発展した。^[48] 囲碁の終盤は、ほぼ埋められた任意の盤上で絶対的な最善手を計算しなければならない場合、 PSPACE困難であることが証明されている。三枚コ、四枚コ、糖蜜コ、月光命などの複雑な状況では、この問題は困難になる。^[49] （実際には、強力なモンテカルロアルゴリズムは通常の囲碁の終盤の状況を十分に処理でき、最も複雑なクラスの生死に関わる終盤の問題が高レベルのゲームで発生する可能性は低い。）^[50]

さまざまな難しい組み合わせ問題（NP困難な問題）は、十分に大きな盤上で囲碁のような問題に変換できます。しかし、チェスやマインスイーパなどの他の抽象的なボードゲームでも、任意のサイズの盤に適切に一般化すれば同じことが言えます。NP完全問題は、一般的に、適切にプログラムされたコンピュータよりも支援を受けていない人間の方が簡単に解ける傾向はありません。たとえば、部分集合和問題の例を解くのは、支援を受けていない人間はコンピュータよりもはるかに苦手です。^{[51] [52]}

• Google DeepMindの機械学習プログラムであるAlphaGoは、ハンディキャップなしの対局で人間の9段の囲碁プレイヤーに勝利した最初のコンピュータプログラムである。
• BaduGI、イ・ジュヨンの番組^[53]
• Crazy Stone、レミ・クーロン著（日本では最強の囲碁として販売）
• Darkforest、Facebookより
• テンセントによるファインアート
• オープンソースのモンテカルロプログラムであるFuego ^[36]
• Goban、Sen:teによるMacintosh用囲碁プログラム（無料のGoban Extensionsが必要）^[54]
• GNU Go、オープンソースの古典的な囲碁プログラム
• KataGo、David Wu 著。
• リーラ、一般向けの最初のモンテカルロプログラム^[38]
• Leela Zeroは、AlphaGo Zero論文^[38]で説明されているシステムの再実装である。
• デビッド・フォトランド著『囲碁のさまざまな側面』（日本ではAI囲碁として販売）^[37]
• MyGoFriend、フランク・カーガーによるプログラム^[40]
• シルヴァン・ジェリーによるMoGo。多くの人々による並行バージョン。^{[55] [39]}
• Pachi、Petr Baudiš によるオープンソースのモンテカルロ プログラム^[56]
• スマートゲームフォーマットの発明者アンダース・キエルルフによるスマート囲碁^[57]
• ステーンヴレーター、エリック・ファン・デル・ヴェルフ作^[58]
• Zen、ヤマトこと尾島洋司著（日本では「天長の囲碁」として販売）。加藤秀樹による対訳版。^[59]

コンピュータオリンピックでの囲碁イベントを含め、囲碁コンピュータプログラム間では毎年いくつかの大会が開催されています。プログラム間の定期的であまり公式ではない大会は、KGS囲碁サーバー^[60]（毎月）とコンピュータ囲碁サーバー^[61] （継続的）で行われていました。

コンピュータの囲碁エンジン同士が対戦できるようにするプログラムは多数ありますが、ほとんどの場合、Go Text Protocol (GTP) を介して通信します。

最初のコンピュータ囲碁大会はAcornsoftがスポンサーとなり、^[62]最初の定期的な大会はUSENIXがスポンサーとなった。これらは1984年から1988年まで開催された。これらの大会では、ブルース・ウィルコックスによる最初の競技囲碁プログラムであるNemesisや、後にCosmosやThe Many Faces of Goへと発展するデビッド・フォトランドによるG2.5が発表された。

コンピュータ囲碁研究の初期の推進力の一つは、イング賞であった。これは台湾の銀行家イング・チャンキがスポンサーとなり、1985年から2000年にかけて毎年世界コンピュータ囲碁大会（イングカップ）で提供されていた比較的大きな賞金であった。このトーナメントの優勝者は、短い対局でハンディキャップ付きの若いプレイヤーに挑戦することができた。もしコンピュータが対局に勝てば賞金が授与され、新しい賞が発表された。それは、より低いハンディキャップのプレイヤーに勝った場合に与えられる、より高額の賞金であった。イング賞の一連の賞は、1) 2000年、または2) プログラムがハンディキャップなしで初段のプロに勝って40,000,000台湾ドルを獲得した時、のいずれかで期限が切れるように設定されていた。最後の優勝者は1997年のHandtalkで、11石のハンディキャップ対局で11～13歳のアマチュア2～6段3人に勝利して25万台湾ドルを獲得した。 2000年に賞品が期限切れになった時点で、未請求の賞金は9ストーンハンディキャップマッチの優勝賞金40万台湾ドルであった。^[63]

他の多くの大規模な地域囲碁トーナメント (「大会」) には、コンピュータ囲碁イベントが付随していました。ヨーロッパ囲碁大会は 1987 年以来コンピュータ トーナメントを後援しており、USENIX イベントは米国/北米コンピュータ囲碁選手権へと発展し、1988 年から 2000 年まで米国囲碁大会で毎年開催されました。

日本は 1995 年にコンピュータ囲碁の大会を後援し始めました。FOST カップは 1995 年から 1999 年まで毎年東京で開催されました。この大会は岐阜チャレンジに取って代わられ、2003 年から 2006 年まで毎年岐阜県大垣市で開催されました。コンピュータ囲碁 UEC カップは2007 年から毎年開催されています。

2 台のコンピュータが互いに囲碁をプレイする場合、2 人の人間がプレイするのと同じようにゲームを扱い、実際の人間による介入を避けるのが理想です。しかし、これはゲーム終了時のスコアリングでは難しい場合があります。主な問題は、標準化されたGo Text Protocol (GTP) を使用して通信する囲碁プレイ ソフトウェアが、石の生死状態に関して必ずしも一致しないという点です。

2 つの異なるプログラムが「話し合い」、衝突を解決する一般的な方法はありませんが、この問題は、盤上の 石の状態に異議がなくなるまで (ペナルティなしで) プレイを続けることを義務付ける中国囲碁、トロンプ・テイラー、またはアメリカ囲碁協会(AGA) のルールを使用することで、大部分回避できます。実際には、KGS 囲碁サーバーなどでは、サーバーは 2 つのクライアント プログラムに特別な GTP コマンドを送信して、特定のグループの状態に疑問がなくなる (すべてのデッド ストーンが捕獲される) まで石を配置し続けるように指示することで、紛争を仲裁できます。CGOS 囲碁サーバーでは、通常、ゲームがスコアリング フェーズに達する前にプログラムが投了しますが、完全なプレイを必要とするトロンプ・テイラー ルールの修正バージョンをサポートしています。

これらのルール セットは、日本のルールではゲーム終了時に (両方のプレーヤーがパスしたとき) 勝ちの立場にあったプログラムが、解決フェーズでのプレイの悪さのために理論的には負ける可能性があることを意味しますが、これは非常に可能性が低く、すべてのエリア ルール セットではゲームの通常の一部と見なされます。

上記のシステムの主な欠点は、一部のルール セット(伝統的な日本のルールなど) では、プレイヤーが余分な動きをした場合にペナルティが課せられ、2 台のコンピューターで追加のプレイアウトを使用できなくなることです。ただし、ほとんどの最新の囲碁プログラムは、人間に対して日本のルールをサポートしています。

歴史的に、この問題を解決する別の方法は、最終的なボードを専門家の人間が判定することでした。しかし、これでは結果に主観が入り込み、プログラムが認識したものを専門家が見逃してしまうリスクがあります。

• コンピューターチェス
• コンピューターオセロ
• コンピュータ将棋
• テキストプロトコル

• 囲碁をプレイするニューラルネットワークの共進化、Alex Lubberts と Risto Miikkulainen 著、2001 年
• コンピュータゲームのプレイ：理論と実践、MA Brauner編（The Ellis Horwood Series in Artificial Intelligence）、Halstead Press、1983年。コンピュータ囲碁に関する記事集。アメリカ囲碁ジャーナル、第18巻第4号、6ページ。[ISSN 0148-0243]
• コンピューター囲碁への機械学習アプローチ、Jeffrey Bagdis、2007 年。
• ユビキタスインターフェースデザインにおけるミニマリズム Wren, C. および Reynolds, C. (2004) Personal and Ubiquitous Computing、8(5)、370～374 ページ。コンピュータ囲碁ビジョンシステムが動作しているビデオでは、インタラクションと、ユーザーが定石と布石を探索している様子が映し出されています。
• モンテカルロ囲碁、Markus Enzenberger 氏による講演、コンピュータ囲碁セミナー、アルバータ大学、2004 年 4 月
• モンテカルロ囲碁、B. Bouzy と B. Helmstetter 著、Scientific Literature Digital Library より
• 囲碁における生死の静的分析、ケン・チェンとジシン・チェン著、1999年2月20日
• Mogoの基礎となる技術を解説した記事

Wikibooksには、コンピュータ囲碁に関する本があります。

• コンピュータ囲碁イベントの広範なリスト
• David A. Mechner 著の All systems Go (1998) では、プロの囲碁プレイヤーJanice Kim が25 石のハンディキャップを与えてプログラム Handtalk に勝利したゲームについて説明しています。
• Sensei's Library のコンピュータ囲碁とコンピュータ囲碁プログラミングのページ
• コンピュータ囲碁の参考文献
• もう一つのコンピュータ囲碁参考文献
• コンピュータ囲碁メーリングリスト
• Ideosphere に掲載されたコンピュータ囲碁に関する記事では、囲碁プログラムが世界最高のプレイヤーになるかどうかの現在の推定値が示されています。
• 囲碁エンジンとグラフィカルクライアントやインターネットサーバーをインターフェースするために一般的に使用される囲碁テキストプロトコルに関する情報
• K Go Server (KGS) 上のコンピュータ囲碁ルームでは、オンラインでのディスカッションや「ボット」の実行ができます。
• 代表的なコンピュータ囲碁ゲーム2つ、1999年に行われた2つのコンピュータ囲碁ゲームについての記事。1つは2人のコンピュータプレイヤーによるゲーム、もう1つは29石のハンディキャップによる人間とコンピュータのゲームである。
• 「What A Way to Go」は、Microsoft Research でのコンピューター囲碁プレイヤーの構築に関する取り組みについて説明しています。
• IEEE Spectrum誌 (2007 年 10 月)に掲載された Feng-hsiung Hsu 著「Cracking Go」– 人間のプレイヤーよりも強い囲碁マシンを構築できる理由
• コンピュータ囲碁データセット、1,645,958 ゲームの SGF データセット