ベンソンのアルゴリズム（囲碁）

囲碁では、ベンソンアルゴリズム（デビッド・B・ベンソンにちなんで名付けられた）は、対戦相手が何ターン続けても捕獲されない、つまり無条件​​に生きている石を決定するために使用できます。[ 1 ]

アルゴリズム

一般性を損なうことなく、黒プレイヤーに対するベンソンのアルゴリズムを説明します。

X をすべての黒の鎖の集合とし、RをXの黒で囲まれたすべての領域の集合とします。ベンソンのアルゴリズムでは、どちらの鎖も領域も削除できなくなるまで、以下の2つのステップを繰り返し適用します。

  1. R内の 2 つ未満の重要な黒で囲まれた領域を持つすべての黒の連鎖をXから削除します。ここで、黒で囲まれた領域は、そのすべての空の交差点が連鎖の自由でもある場合、 X内の黒の連鎖にとって重要です。
  2. Rから、Xにない連鎖内の周囲の石を持つ黒で囲まれた領域をすべて削除します。

最終的な集合Xは、無条件に生きているすべての黒チェーンの集合である。[ 2 ]

適用範囲

2008年以降に開発された強力なコンピュータ囲碁プログラムのほとんどは、実際にはベンソンのアルゴリズムを使用していません。人間の戦略をシミュレートしようとする「知識ベース」の囲碁アプローチはあまり効果的ではないことが証明され、その後のアプローチでは、モンテカルロランダムプレイアウトなどのツールを用いて局面を「得点」することが一般的になりました。[ 3 ]囲碁の局面では、石や地をより確率的かつ段階的に得点することがしばしば求められます。つまり、相手が石を救うために無競争のプレイを許さない限り、石はおそらく死んでいる、競争されている、相手が一度も無競争のプレイを許さない限り生きている、相手がそのエリアで繰り返し無競争のプレイを許さない限り生きている、などといった状況です。無条件に生きているとしか認識しないシステムはあまり強力ではありません。なぜなら、高レベルのプレイでは、さらなるプレイによって保護されればグループの状態が安全になった後も、グループが完全に「完成」していない状態のまま放置されることが日常的に起こるからです（例えば、プレイヤーが捕獲を許した場合にのみ捕獲されます。その場合、おそらくより価値の高い目標と交換しているのでしょう）。より複雑な可能性の勾配を処理できるシステムは、スコアリングやポジションの理解に使用されるシステムの一部として、無条件に生きている石を「無料で」すでに理解しているでしょう。

参照

参考文献

  1. ^タパニ・ライコ (2005年5月5日)。「ベンソンのアルゴリズム」。2012 年3 月 21 日に取得。
  2. ^ 「先生の図書館：ベンソンの無条件の生命の定義」 。 2012年3月21日閲覧。
  3. ^ Steinmetz, ES, & Gini, MG (2015). 囲碁の初手におけるモンテカルロ探索を導くためのマイニングエキスパートプレイ [デジタル]. 国際人工知能合同会議, 第24回国際人工知能合同会議 (IJCAI 2015) (第24版) の議事録. 国際人工知能合同会議. https://www.ijcai.org/Proceedings/15/Papers/118.pdf
「 https://en.wikipedia.org/w/index.php?title=Benson%27s_algorithm_(Go)&oldid=1241243526」より取得