この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)
出典検索?: "コンピュータオセロ"
コンピュータオセロは、自ら指し手を選択してオセロの対局を行う能力を持つコンピュータ技術である。
ここでは、コンピュータオセロの技術的な情報について解説する。オセロとコンピュータとの関わり合い一般についての外延的な情報は、オセロとコンピュータを参照。 現在、インターネットから無料でダウンロード可能なNTest コンピュータオセロプログラムはゲーム木を用いて全ての可能な手を探索する。理論上は、プログラムは全ての駒配置/節を調べ、ここでは1人のプレーヤーによるそれぞれの手は「プライ ply(層)」と呼ばれる。この探索は任意の最大探索深度まで、あるいはプログラムが最終「葉」配置に到達したと決定するまで続く。 ミニマックスやネガマックスと呼ばれるこのアプローチのばか正直な実装は、実際上の時間内で小さな深度しか探索することができない。そのため、より手を探索する速度を大きく増すための様々な手法が考案されている。これら、αβ枝刈り、Negascout、MTD-f、NegaC*に基づく[2]。 よい手の順番、置換表
オセロプログラム
探索技術
マルチプロセッサあるいはマルチコアを持つマシン上での探索を高速化するため、「並列探索」も実装される。ABDADA[4]あるいはAPHID[5]のように、オセロについて複数の実験がなされている。近年のプログラム上では、YBWC[6]がより好まれる手法のように見える。 評価関数を作成するためには3つの異なる枠組みが存在する。 異なる升は異なる価値を持つ - 角はよく、角の隣の升は悪い。対称性を無視すると、盤上には10の異なる位置があり、これらの個々の位置は3つの可能性について価値(黒、白、空白)が与えられる。より洗練された手法は、ゲームの異なる段階でそれぞれの位置が異なる価値を持つ。例えば、角は序盤や中盤の前半では終盤よりも重要である[7]。 ほとんどの人間のプレーヤーは、可動性(可能な手の数)を最大化し、境界の石(空白の角に隣接した石)を最小化することを目指す。プレーヤーの可動性と相手の可動性が計算され、プレーヤーの潜在的可動性と相手の潜在的可動性も同様に計算される[8]。これらの指標は非常に速く見つけることができ、強さを著しく上昇させる。ほとんどのプログラムは縁と角の配置に関する知識を有しており、中盤の前半での石の数を最小化しようと試みる(人間のプレーヤーでも使われる戦略)[7]。 可動性の最大化と境界(の石)の最小化は、局所的な配置へと分解することができる。通常の実装は、それぞれの行、列、対角、角の配置を別々に評価し、それぞれの価値を合計するため、多くの異なるパターンを評価しなければならない[7]。全ての配置についての価値を決定する過程は、強豪プレーヤー間でプレーされた試合の大きなデータベースを入手し、全ての試合からそれぞれのゲーム段階におけるそれぞれの配置についての統計を計算することによって行われる[7]。 勝者が対応する石の数だけボーナスを得るように重み付けされた石の数の差の指標が、最終的な石の数の差を予測するために最も一般的に用いられる[7]。 オープニングブック(序盤定石のデータベース)は、まずいオープニングに反撃するよい方法と見なされている一般的なオープニングを与えることでコンピュータプログラムを助ける。全ての強力なプログラムはオープニングブックを使用し、それぞれの試合後に自動的に自身の定石データベースを更新する。試合データベース中の全ての試合の全てのポジションを調べ、データベースの試合で打たれていない最良の手を決定するため、以前に探索されたポジションを記録するための置換表 4×4盤オセロは非常に小さなゲーム木を持ち、全ての可能な局面(1千万近く)を生成するミニマックス法を用いる多くの単純なオセロプログラムによって1秒以内に解決される。結果は白(後手)の10石勝ちである[9]。 6×6盤オセロは、全ての可能な局面(3.6兆近く)を生成するミニマックス法を用いる多くの単純なオセロプログラムによって100時間以内に解決される。結果は白(後手)の4石勝ちである[10][11]。 8×8盤オセロのゲーム木のサイズは1054ノードと推定されており、合法的なポジションの数は1028と推定されている。数学的には未解決であるが、速い並列ハードウェア上あるいは分散コンピューティングを通じたプログラムによる徹底的な計算を行うことで解を見つけることは可能かもしれない[要出典]。 数多くの引き分けへの道筋が示されているが、このような道筋は完全に判明していない[12]。 一部の強豪プログラムは長年自身のデータベースを拡張してきた。斜め取り、縦取り、並び取りの23つの主要なオープニングに関しては、斜め取りと縦取りは引き分けの筋へ至る傾向にあり、一方で並び取りは黒(先手)の勝ちとなる。引き分け木は、縦取りの後よりも斜め取りの後の方が大きいようである[13]。並び取りは黒(先手)に非常に有利であり、完璧に打った場合は常に勝つことができる[14]。証明されてはいないが、実質的には双方のプレーヤーが完璧に打った場合は試合は常に引き分けとなる。オープニングブックを使用した標準的ゲームでは、トッププログラムの負ける確率は1%未満である[要出典]。 10×10盤では、先手(黒)がより勝ちやすい。10x10は中盤がより長い。コンピュータの解析では、両者が完璧に打ったとすると引き分けが最も起こりやすいことが示されている。ゲーム木の複雑さは非常に高く1090と推定されており、合法的なポジションの数は1044と推定されている[要出典]。
評価技術
石-升表
可動性
パターン/パターン係数
オープニングブック
完全解析の手法
4×4盤
6×6盤
8×8盤
10×10盤
年表
1977年: Creative Computing誌がEd WrightによってFORTRANで書かれたオセロのバージョンを発表した[15][16]。
Size:34 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef