コンピュータオセロ

コンピュータオセロは、オセロの試合を行う能力のあるコンピュータハードウェアおよびコンピュータソフトウェアを包含するコンピュータ技術を意味する。 現在、インターネットから無料でダウンロード可能なNTestやSaio、Edax、Cassio、Ponty Stone、Herakles、WZebra、Logistelloといった多くのオセロプログラムが存在する。これらのプログラムは、最新のコンピュータ上で動作させた時、最強の人間のプレーヤーを容易に打ち負かすことができる。これは、手の結果はコンピュータと人間が共に予測できるが、コンピュータがそれらの予測に優れているためである。 コンピュータオセロプログラムはゲーム木を用いて全ての可能な手を探索する。理論上は、プログラムは全ての駒配置/節を調べ、ここでは1人のプレーヤーによるそれぞれの手は「プライ ply（層）」と呼ばれる。この探索は任意の最大探索深度まで、あるいはプログラムが最終「葉」配置に到達したと決定するまで続く。 ミニマックスあるいはネガマックスと呼ばれるこのアプローチのばか正直な実装は、実際上の時間内で小さな深度しか探索することができない。そのため、より手を探索する速度を大きく増すための様々な手法が考案されている。これら、αβ枝刈り、Negascout、MTD-f、NegaC*に基づく。αβアルゴリズムは、どのみち使われることのない場合を枝刈りすることによってMinimax探索ルーティンを高速化するための手法である。 よい手の順番、置換表、選択的探索といったいくつかの経験則も探索木の大きさを減らすために用いられる。 マルチプロセッサあるいはマルチコアを持つマシン上での探索を高速化するため、「並列探索」も実装される。ABDADAあるいはAPHIDのように、オセロについて複数の実験がなされている。近年のプログラム上では、YBWCがより好まれる手法のように見える。 評価関数を作成するためには3つの異なる枠組みが存在する。 異なる升は異なる価値を持つ - 角はよく、角の隣の升は悪い。対称性を無視すると、盤上には10の異なる位置があり、これらの個々の位置は3つの可能性について価値（黒、白、空白）が与えられる。より洗練された手法は、ゲームの異なる段階でそれぞれの位置が異なる価値を持つ。例えば、角は序盤や中盤の前半では終盤よりも重要である。 ほとんどの人間のプレーヤーは、可動性（可能な手の数）を最大化し、境界の石（空白の角に隣接した石）を最小化することを目指す。プレーヤーの可動性と相手の可動性が計算され、プレーヤーの潜在的可動性と相手の潜在的可動性も同様に計算される。これらの指標は非常に速く見つけることができ、強さを著しく上昇させる。ほとんどのプログラムは縁と角の配置に関する知識を有しており、中盤の前半での石の数を最小化しようと試みる（人間のプレーヤーでも使われる戦略）。 可動性の最大化と境界（の石）の最小化は、局所的な配置へと分解することができる。通常の実装は、それぞれの行、列、対角、角の配置を別々に評価し、それぞれの価値を合計するため、多くの異なるパターンを評価しなければならない。全ての配置についての価値を決定する過程は、強豪プレーヤー間でプレーされた試合の大きなデータベースを入手し、全ての試合からそれぞれのゲーム段階におけるそれぞれの配置についての統計を計算することによって行われる。 勝者が対応する石の数だけボーナスを得るように重み付けされた石の数の差の指標が、最終的な石の数の差を予測するために最も一般的に用いられる。 オープニングブック（序盤定石のデータベース）は、まずいオープニングに反撃するよい方法と見なされている一般的なオープニングを与えることでコンピュータプログラムを助ける。全ての強力なプログラムはオープニングブックを使用し、それぞれの試合後に自動的に自身の定石データベースを更新する。試合データベース中の全ての試合の全てのポジションを調べ、データベースの試合で打たれていない最良の手を決定するため、以前に探索されたポジションを記録するための置換表が用いられる。これは、それらのポジションを再び探索する必要がないことを意味する。個々のポジションについて深い探索を実行しなければならないためこれは多大な時間を必要とするが、一度実行してしまえば、定石データベースの更新は容易である。それぞれの試合をプレーした後、全ての新しいポジションが最良の偏差について探索される。 オセロは4×4および6×6について完全解析されており、完璧に打った場合は後手（白）必勝である。数学的には未解決であるが、標準的な8×8盤についても同様に実質的に解決されている。コンピュータによる解析では、数多くの引き分けへの道筋が示されているが、このような道筋は完全に判明していない。 4×4盤オセロは非常に小さなゲーム木を持ち、全ての可能な局面（1千万近く）を生成するミニマックス法を用いる多くの単純なオセロプログラムによって1秒以内に解決される。結果は白（後手）の8石勝ちである。 6×6盤オセロは、全ての可能な局面（3.6兆近く）を生成するミニマックス法を用いる多くの単純なオセロプログラムによって100時間以内に解決される。結果は白（後手）の4石勝ちである。 8×8盤オセロのゲーム木のサイズは1054ノードと推定されており、合法的なポジションの数は1028と推定されている。数学的には未解決であるが、速い並列ハードウェア上あるいは分散コンピューティングを通じたプログラムによる徹底的な計算を行うことで解を見つけることは可能かもしれない[要出典]。 一部の強豪プログラムは長年自身のデータベースを拡張してきた。対角、垂直、平行の23つの主要なオープニングに関しては、対角オープニングと垂直オープニングは引き分けの筋へ至る傾向にあり、一方で平行オープニングは黒（先手）の勝ちとなる。引き分け木は、垂直オープニングの後よりも対角オープニングの後の方が大きいようである。平行オープニングは黒（先手）に非常に有利であり、完璧に打った場合は常に勝つことができる。証明されてはいないが、実質的には双方のプレーヤーが完璧に打った場合は試合は常に引き分けとなる。オープニングブックを使用した標準的ゲームでは、トッププログラムの負ける確率は1%未満である。 10×10盤では、先手（黒）がより勝ちやすい。10x10は中盤がより長い。コンピュータの解析では、両者が完璧に打ったとすると引き分けが最も起こりやすいことが示されている。ゲーム木の複雑さは非常に高く1090と推定されており、合法的なポジションの数は1044と推定されている[要出典]。 1977年: Creative Computing誌がEd WrightによってFORTRANで書かれたオセロのバージョンを発表した。 1978年: 任天堂がアーケードゲーム「コンピューターオセロ」をリリースした。 1980年: Mike ReeveとDavid Levyによって書かれたオセロプログラムMoorが世界チャンピオン井上博との六番勝負で1勝を挙げた。ノースウェスタン大学のPeter W. FreyがBYTE誌においてコンピュータと人間のオセロ戦略について議論し、CDC 6600上で動作するWriteのプログラムに容易に勝利するとFreyが主張するオセロゲームTRS-80について議論した。カーネギーメロン大学のPaul RosenbloomはIAGOを開発し、ノースウェスタン大学で行われたコンピュータの大会で3位に入った。 1981年: DEC KA10上で動作するIAGOが、カリフォルニア大学サンタクルーズ校でのSanta Cruz Open Othello Tournamentでその他19の対戦相手対して無敗で優勝した。Charles HeathのTRS 80ベースのゲームは2位であった。マイクロコンピュータ CPUベースエンジンが2位から7位を占め、メインフレームやミニコンピュータを上回った。Freyは、これがコンピュータオセロがより速い浮動小数点演算といった大型コンピュータの複数の利点から恩恵を受けていないためだと推測した。 1980年代末: Kai-Fu LeeとSanjou MahajanはオセロプログラムBILLを作成した。BILLはIAGOと似ているが、ベイズ学習を組み込んでいる。BILLはIAGOを確実に負かした。 1992年: Michael BuroはオセロプログラムLogistelloの開発を始めた。Logistelloの探索技術、評価関数、パターンの知識ベースは古いプログラムのものよりも優れていた。Logistelloは10万局以上自分自身と対戦することで仕上げられた。 1997年: Logistelloは世界チャンピオン村上健との六番勝負で全勝した。オセロプログラムが人間よりも強いことはほとんど疑問視されていなかったが、コンピュータが現役世界チャンピオンと対戦したのは17年振りであった。1997年の対局後、Logistelloがいかなる人間のプレーヤーよりもかなり強いことはもはや疑いようがなかった。 1998年: Michela BuroはLogistelloの開発を中止した。オセロにおける研究的興味は幾分衰えたが、NtestやSaio、Edax、Cassio、WZebra、Heraklesを含むいくつかのプログラムの開発は続いた。 2004年: Ntestが（Logistelloよりもかなり強い）最強プログラムとなった。 2005年: Ntest、Saio、Edax、Cyrano、WZebraがLogistelloよりもかなり強くなった。NtestとWZebraが引退した。 2011年: Saio、Edax、CyranoがLogistelloやその他のプログラムよりも高速になった。 ^ http://www.dcs.gla.ac.uk/~daw/masters-projects/dissertations/Colquhoun.2008.pdf ^ Jean-Christophe Weill (1992). The NegaC* Search. ICCA Journal, Vol. 15, No. 1, pp. 3-7. ^ Buro, M. (1997年). “Experiments with Multi-ProbCut and a New High-Quality Evaluation Function for Othello”. Games in AI Research: 77-96. http://www.cs.ualberta.ca/~mburo/ps/improve.pdf.  ^ Jean-Christophe Weill (1996). The ABDADA Distributed Minimax Search Algorithm. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted ICCA Journal Vol. 19, No. 1 ^ Mark Brockington (1997). KEYANO Unplugged - The Construction of an Othello Program. Technical Report TR-97-05, Department of Computing Science, University of Alberta. ^ Rainer Feldmann, Peter Mysliwietz, Burkhard Monien (1991). A Fully Distributed Chess Program. Advances in Computer Chess 6 ^ a b c d e f Writing an Othello program April 02, 2007 ^ How Ntest Works March 02, 2005 ^ a b Solution of Othello 4 x 4 September 02, 2008 ^ Perfect play in 6x6 Othello from two alternative starting positions November 17, 2004 ^ Edax 4.0 Opening Book November 01, 2008 ^ A free software for solving 4x4 and 6x6 othello ^ Strongest othello program in term of artificial intelligent ^ Saio's book ^ Wright, Ed (November–December 1977). “Othello”. Creative Computing: pp. 140–142. http://www.atariarchives.org/bcc3/showpage.php?page=258 2013年10月18日閲覧。  ^ a b Frey, Peter W (1980年7月). “Simulating Human Decision-Making on a Personal Computer”. BYTE: pp. 56. http://archive.org/stream/byte-magazine-1980-07/1980_07_BYTE_05-07_Computers_and_Education#page/n57/mode/2up 2013年10月18日閲覧。  ^ a b c d e f The History of Computer Games ^ a b Frey, Peter W (1981年7月). “The Santa Cruz Open / Othello Tournament for Computers”. BYTE: pp. 16. http://archive.org/stream/byte-magazine-1981-07/1981_07_BYTE_06-07_Energy_Conservation#page/n27/mode/2up 2013年10月18日閲覧。  コンピュータ囲碁 コンピュータ将棋 コンピュータチェス コンピュータオリンピアード 4 x 4 Othello 6 x 6 Othello List of Othello programs Chess programming