コンピュータオセロ
 |
 | |
| NTest - 強豪オセロプログラム |
コンピュータオセロは、自ら指し手を選択してオセロの対局を行う能力を持つコンピュータ技術である。
ここでは、コンピュータオセロの技術的な情報について解説する。オセロとコンピュータとの関わり合い一般についての外延的な情報は、オセロとコンピュータを参照。
オセロプログラム
[編集]現在、インターネットから無料でダウンロード可能なNTestやSaio、Edax、Cassio、Ponty Stone、Herakles、WZebra、Logistelloといった多くのオセロプログラムが存在する。これらのプログラムは、最新のコンピュータ上で動作させた時、最強の人間のプレーヤーを容易に打ち負かすことができる。これは、手の結果はコンピュータと人間が共に予測できるが、コンピュータがそれらの予測に優れているためである[1]。
探索技術
[編集]コンピュータオセロプログラムはゲーム木を用いて全ての可能な手を探索する。理論上は、プログラムは全ての駒配置/節を調べ、ここでは1人のプレーヤーによるそれぞれの手は「プライ ply（層）」と呼ばれる。この探索は任意の最大探索深度まで、あるいはプログラムが最終「葉」配置に到達したと決定するまで続く。
ミニマックスやネガマックスと呼ばれるこのアプローチのばか正直な実装は、実際上の時間内で小さな深度しか探索することができない。そのため、より手を探索する速度を大きく増すための様々な手法が考案されている。これら、αβ枝刈り、Negascout、MTD-f、NegaC*に基づく[2]。
よい手の順番、置換表、選択的探索といったいくつかの経験則も探索木の大きさを減らすために用いられる[3]。
マルチプロセッサあるいはマルチコアを持つマシン上での探索を高速化するため、「並列探索」も実装される。ABDADA[4]あるいはAPHID[5]のように、オセロについて複数の実験がなされている。近年のプログラム上では、YBWC[6]がより好まれる手法のように見える。
評価技術
[編集]評価関数を作成するためには3つの異なる枠組みが存在する。
石-升表
[編集]異なる升は異なる価値を持つ - 角はよく、角の隣の升は悪い。対称性を無視すると、盤上には10の異なる位置があり、これらの個々の位置は3つの可能性について価値（黒、白、空白）が与えられる。より洗練された手法は、ゲームの異なる段階でそれぞれの位置が異なる価値を持つ。例えば、角は序盤や中盤の前半では終盤よりも重要である[7]。
可動性
[編集]ほとんどの人間のプレーヤーは、可動性（可能な手の数）を最大化し、境界の石（空白の角に隣接した石）を最小化することを目指す。プレーヤーの可動性と相手の可動性が計算され、プレーヤーの潜在的可動性と相手の潜在的可動性も同様に計算される[8]。これらの指標は非常に速く見つけることができ、強さを著しく上昇させる。ほとんどのプログラムは縁と角の配置に関する知識を有しており、中盤の前半での石の数を最小化しようと試みる（人間のプレーヤーでも使われる戦略）[7]。
パターン/パターン係数
[編集]可動性の最大化と境界（の石）の最小化は、局所的な配置へと分解することができる。通常の実装は、それぞれの行、列、対角、角の配置を別々に評価し、それぞれの価値を合計するため、多くの異なるパターンを評価しなければならない[7]。全ての配置についての価値を決定する過程は、強豪プレーヤー間でプレーされた試合の大きなデータベースを入手し、全ての試合からそれぞれのゲーム段階におけるそれぞれの配置についての統計を計算することによって行われる[7]。
勝者が対応する石の数だけボーナスを得るように重み付けされた石の数の差の指標が、最終的な石の数の差を予測するために最も一般的に用いられる[7]。
オープニングブック
[編集]オープニングブック（序盤定石のデータベース）は、まずいオープニングに反撃するよい方法と見なされている一般的なオープニングを与えることでコンピュータプログラムを助ける。全ての強力なプログラムはオープニングブックを使用し、それぞれの試合後に自動的に自身の定石データベースを更新する。試合データベース中の全ての試合の全てのポジションを調べ、データベースの試合で打たれていない最良の手を決定するため、以前に探索されたポジションを記録するための置換表が用いられる。これは、それらのポジションを再び探索する必要がないことを意味する[7]。個々のポジションについて深い探索を実行しなければならないためこれは多大な時間を必要とするが、一度実行してしまえば、定石データベースの更新は容易である。それぞれの試合をプレーした後、全ての新しいポジションが最良の偏差について探索される。
完全解析の手法
[編集]4×4盤
[編集]4×4盤オセロは非常に小さなゲーム木を持ち、全ての可能な局面（1千万近く）を生成するミニマックス法を用いる多くの単純なオセロプログラムによって1秒以内に解決される。結果は白（後手）の10石勝ちである[9]。
6×6盤
[編集]6×6盤オセロは、全ての可能な局面（3.6兆近く）を生成するミニマックス法を用いる多くの単純なオセロプログラムによって100時間以内に解決される。結果は白（後手）の4石勝ちである[10][11]。
8×8盤
[編集]8×8盤オセロのゲーム木のサイズは1054ノードと推定されており、合法的なポジションの数は1028と推定されている。数学的には未解決であるが、速い並列ハードウェア上あるいは分散コンピューティングを通じたプログラムによる徹底的な計算を行うことで解を見つけることは可能かもしれない[要出典]。
数多くの引き分けへの道筋が示されているが、このような道筋は完全に判明していない[12]。
一部の強豪プログラムは長年自身のデータベースを拡張してきた。斜め取り、縦取り、並び取りの23つの主要なオープニングに関しては、斜め取りと縦取りは引き分けの筋へ至る傾向にあり、一方で並び取りは黒（先手）の勝ちとなる。引き分け木は、縦取りの後よりも斜め取りの後の方が大きいようである[13]。並び取りは黒（先手）に非常に有利であり、完璧に打った場合は常に勝つことができる[14]。証明されてはいないが、実質的には双方のプレーヤーが完璧に打った場合は試合は常に引き分けとなる。オープニングブックを使用した標準的ゲームでは、トッププログラムの負ける確率は1%未満である[要出典]。
10×10盤
[編集]10×10盤では、先手（黒）がより勝ちやすい。10x10は中盤がより長い。コンピュータの解析では、両者が完璧に打ったとすると引き分けが最も起こりやすいことが示されている。ゲーム木の複雑さは非常に高く1090と推定されており、合法的なポジションの数は1044と推定されている[要出典]。
年表
[編集]- 1977年: Creative Computing誌がEd WrightによってFORTRANで書かれたオセロのバージョンを発表した[15][16]。なお、日本では8月7日に「第五回 全日本オセロ選手権大会」（日本オセロ連盟主催）にて人間vsコンピューターのオセロゲーム対決が行われている。コンピューター代表は電電公社（現・NTT）技術局の室谷正芳調査役が、同公社の大型コンピューターに「10の60乗の"手"を記憶した」というソフトウェアを組み込んだもの。対する人間代表は日本オセロ連盟の長谷川会長や、前年の同大会男子2位の強豪らが選ばれた。結果はコンピューターの20勝8敗[17]。
- 1978年: 任天堂レジャーシステムがアーケードゲーム「コンピューター・オセロ」をリリースした[18][19]。
- 1980年: Mike ReeveとDavid Levyによって書かれたオセロプログラムMoorが世界チャンピオン井上博との六番勝負で1勝を挙げた[18]。ノースウェスタン大学のPeter W. FreyがBYTE誌においてコンピュータと人間のオセロ戦略について議論し、CDC 6600上で動作するWriteのプログラムに容易に勝利するとFreyが主張するオセロゲームTRS-80について議論した[16]。カーネギーメロン大学のPaul RosenbloomはIAGOを開発し、ノースウェスタン大学で行われたコンピュータの大会で3位に入った[20]。
- 1981年: DEC KA10上で動作するIAGOが、カリフォルニア大学サンタクルーズ校でのSanta Cruz Open Othello Tournamentでその他19の対戦相手対して無敗で優勝した。Charles HeathのTRS 80ベースのゲームは2位であった。マイクロコンピュータ CPUベースエンジンが2位から7位を占め、メインフレームやミニコンピュータを上回った。Freyは、これがコンピュータオセロがより速い浮動小数点演算といった大型コンピュータの複数の利点から恩恵を受けていないためだと推測した[20]。
- 1980年代末: Kai-Fu LeeとSanjou MahajanはオセロプログラムBILLを作成した。BILLはIAGOと似ているが、ベイズ学習を組み込んでいる。BILLはIAGOを確実に負かした[18]。
- 1992年: Michael BuroはオセロプログラムLogistelloの開発を始めた。Logistelloの探索技術、評価関数、パターンの知識ベースは古いプログラムのものよりも優れていた。Logistelloは10万局以上自分自身と対戦することで仕上げられた[18]。
- 1997年: Logistelloは世界チャンピオン村上健との六番勝負で全勝した。実際には、それ以前からコンピュータオセロは人間を上回っており、1997年の時点で、Logistelloがいかなる人間よりも強いことは疑いようがなかった[18][21][22]。
- 1998年: Michela BuroはLogistelloの開発を中止した。オセロにおける研究的興味は幾分衰えたが、NtestやSaio、Edax、Cassio、WZebra、Heraklesを含むいくつかのプログラムの開発は続いた[18]。
- 2004年: Ntestが（Logistelloよりもかなり強い）最強プログラムとなった。
- 2005年: Ntest、Saio、Edax、Cyrano、WZebraがLogistelloよりもかなり強くなった。NtestとWZebraが引退した。
- 2011年: Saio、Edax、CyranoがLogistelloやその他のプログラムよりも高速になった。
- 2019年: 吉田拓真が開発した「最弱オセロ」が公開された[23][24][25]。従来のプログラムでは勝ちを目指すものであるが、この「最弱オセロ」は全くの正反対になっており人間が負けるのが難しくなっている。
脚注
[編集]- ^ 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.
- ^ 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
- ^ Solution of Othello 4 x 4 September 02, 2008
- ^ A free software for solving 4x4 and 6x6 othello
- ^ Perfect play in 6x6 Othello from two alternative starting positions November 17, 2004
- ^ Edax 4.0 Opening Book[リンク切れ] November 01, 2008
- ^ Strongest othello program in term of artificial intelligent[リンク切れ]
- ^ Saio's book[出典無効]
- ^ Wright, Ed (November–December 1977). “Othello”. Creative Computing: pp. 140–142 18 October 2013閲覧。
- ^ a b Frey, Peter W (July 1980). “Simulating Human Decision-Making on a Personal Computer”. BYTE: pp. 56 18 October 2013閲覧。
- ^ 毎日新聞朝刊 (7th August 1977). “今日は何の日？】8月7日＝世界初！人間とコンピューターがオセロ対決（1977年）／ 雑学ネタ帳”. pp. 昭和52年8月9日. 27 August 2023閲覧。
- ^ a b c d e f The History of Computer Games
- ^ “Game Machine” (PDF). ゲームマシン アーカイブ - Game Machine Archive. ゲームマシン 第98号. p. 18 (1978年6月15日). 2019年6月9日閲覧。 “コンピューター・オセロ テーブル型TVゲーム機発売した任天堂”
- ^ a b Frey, Peter W (July 1981). “The Santa Cruz Open / Othello Tournament for Computers”. BYTE: pp. 16 18 October 2013閲覧。
- ^ “人間VSコンピュータオセロ 衝撃の6戦全敗から20年、元世界チャンピオン村上健さんに聞いた「負けた後に見えてきたもの」 (2/3)”. ITmedia (2017年10月21日). 2020年3月22日閲覧。
- ^ “人間VSコンピュータオセロ 衝撃の6戦全敗から20年、元世界チャンピオン村上健さんに聞いた「負けた後に見えてきたもの」 (3/3)”. ITmedia (2017年10月21日). 2020年3月22日閲覧。
- ^ 「負けるのが難しい」…世界最弱のオセロAIを体験―開発者に誕生のきっかけを訊いた【特集】
- ^ 「負けられるなら負けてみてくれ！」 世界最弱のオセロAIが開発され、負けられないと話題に
- ^ 「世界最弱のオセロAI」が話題…一体何のために作ったの？開発者に聞いた
