Loading article…
 | |
| NTest - 強力なオセロプログラム |
コンピュータオセロとは、オセロゲームをプレイできるコンピュータハードウェアとコンピュータソフトウェアを含むコンピュータアーキテクチャを指します。これは、 Microsoft Windows 1.0からXPまで含まれており、そこでは単にリバーシとして知られています。[引用が必要]
可用性
NTest、Saio、Edax、Cassio、Pointy Stone、Herakles、WZebra、Logistelloなど、インターネットから無料でダウンロードできるオセロプログラムは数多くあります。これらのプログラムを最新のコンピュータで実行すると、人間の最高のプレイヤーが簡単に負けてしまうゲームをプレイできます。これは、動きの結果はコンピュータと人間の両方にとって予測可能ですが、コンピュータの方がそれを探索するのに優れているためです。[1]
検索テクニック
コンピュータ オセロ プログラムは、ゲーム ツリーを使用して、可能な合法的な動きを検索します。理論的には、すべての位置/ノードを調べます。各プレーヤーの動きは「プライ」と呼ばれます。この検索は、特定の最大検索深度に達するまで、またはプログラムが最終的な「リーフ」位置に到達したと判断するまで続行されます。
このアプローチの単純な実装は、ミニマックスまたはネガマックスとして知られており、実用的な時間内に小さな深さまでしか探索できないため、良い動きの探索速度を大幅に向上させるさまざまな方法が考案されています。これらは、アルファベータ剪定、ネガスカウト、MTD(f)、およびネガC*に基づいています。[2]アルファベータアルゴリズムは、とにかく使用されないケースを剪定することで、ミニマックス探索ルーチンを高速化する方法です。この方法は、ツリーの他のすべてのレベルが最大化し、他のすべてのレベルが最小化するという事実を利用しています。[3]
探索木のサイズを縮小するために、適切な移動順序、転置表、選択的探索などのいくつかのヒューリスティックも使用される。[4]
複数のプロセッサまたはコアを持つマシンでの検索を高速化するために、「並列検索」を実装することができます。ABDADA [5]や APHID [6]など、オセロ ゲームでいくつかの実験が行われてきました。最近のプログラムでは、YBWC [7]が推奨されるアプローチのようです。
マルチプロブカット
Multi-ProbCut は、探索木のアルファベータ剪定で使用されるヒューリスティックです。 [8] ProbCut ヒューリスティックは、より深いスコアとより浅いスコアの間の線形回帰を使用して、探索木のより深いレベルでの評価スコアを推定します。Multi-ProbCut は、このアプローチを探索木の複数のレベルに拡張します。線形回帰自体は以前のツリー検索を通じて学習されるため、ヒューリスティックは一種の動的探索制御になります。[9]これは、より深いレベルとより浅いレベルの評価スコアの間に強い相関関係があるオセロなどのゲームで特に役立ちます。[10] [11]
評価手法
評価関数を作成するための 3 つの異なるパラダイムがあります。
円盤型テーブル
異なるマスには異なる価値があり、角は良いマスで、角に隣接するマスは悪いマスです。対称性を無視すると、ボード上には10の異なる位置があり、それぞれに3つの可能性（黒ディスク、白ディスク、空）のそれぞれに価値が与えられます。より洗練されたアプローチは、ゲームのさまざまな段階で各位置に異なる価値を与えることです。たとえば、角はエンドゲームよりもオープニングと中盤の初期に重要です。[12]
モビリティベース
人間のプレイヤーのほとんどは、機動性（移動可能な回数）を最大化し、フロンティアディスク（空きマスに隣接するディスク）を最小化しようとします。プレイヤーの機動性と対戦相手の機動性が計算され、プレイヤーの潜在的機動性と対戦相手の潜在的機動性も計算されます。[13]これらの尺度は非常に迅速に見つけることができ、プレイの強さを大幅に向上させます。ほとんどのプログラムはエッジとコーナーの構成を認識しており、人間のプレイヤーが使用するもう1つの戦略である、ゲーム中盤の早い段階でディスクの数を最小限に抑えようとします。[12]
パターンベース/パターン係数
移動度最大化とフロンティア最小化は、加算可能なローカル構成に分解できます。通常の実装では、各行、列、対角線、コーナーの構成を個別に評価し、値を加算しますが、多くの異なるパターンを評価する必要があります。[12]すべての構成の値を決定するプロセスは、強力なプレーヤー間でプレイされたゲームの大規模なデータベースを取得し、すべてのゲームの各ゲームステージの各構成の統計を計算することによって行われます。[12]
最終的なディスク差を予測するための最も一般的な選択肢は、勝者がディスクの数に応じたボーナスを得る加重ディスク差測定を使用するものである。[12]
オープニングブック
オープニングブックは、悪いオープニングに対抗する良い方法と考えられている一般的なオープニングを提供することで、コンピュータプログラムを助けます。すべての強力なプログラムはオープニングブックを使用しており、各ゲームの後にブックを自動的に更新します。ゲームデータベース内のすべてのゲームのすべてのポジションを調べて、どのデータベースゲームでもプレイされていない最善の動きを決定するために、トランスポジションテーブルを使用して、以前に検索されたポジションを記録します。つまり、それらのポジションを再度検索する必要はありません。[12]各ポジションに対してディープサーチを実行する必要があるため、これには時間がかかりますが、一度これを実行してしまえば、ブックの更新は簡単です。各ゲームがプレイされた後、すべての新しいポジションで最良の偏差が検索されます。
その他の最適化
より高速なハードウェアと追加のプロセッサにより、より深い層の探索など、オセロをプレイするプログラムの機能が向上します。
オセロを解く
ゲーム中、プレイヤーは交互に動きます。人間のプレイヤーは黒のカウンターを使用し、コンピュータは白のカウンターを使用します。人間のプレイヤーがゲームを開始します。[1]オセロは4×4と6×6のボードで強力に解かれ、2番目のプレイヤー（白）が完璧なプレイで勝ちます。[14] [15]
オセロ 4 × 4
オセロ4x4のゲームツリーは非常に小さく、ミニマックス法（約1000万通り）を使った多くのシンプルなオセロプログラムによって1秒未満で解かれています。その結果、白が+8の差（3-11）で勝ちます。[14]
オセロ 6 × 6
オセロ6x6は、ミニマックス法（約3.6兆）を使った多くのシンプルなオセロプログラムによって100時間未満で解かれました。その結果、ハイトが+4の差（16-20）で勝利した。[16]
オセロ 8 × 8
オセロの8x8ゲームツリーのサイズは10 54ノードと推定され、合法的なポジションの数は10 28未満と推定されています。2023年10月現在、プレプリントではゲームが解決され、最適な結果は引き分けであると主張しています。[17] [18]計算結果も共有されており、公開されている書籍としては最大級のものです。[19]
いくつかのトッププログラムは、何年も前からブックを拡張してきました。その結果、多くのラインは実際にはどちらかの側にとって引き分けまたは勝ちになっています。対角、垂直、平行の3つの主要なオープニングに関しては、対角と垂直の両方のオープニングがラインの引き分けにつながり、平行オープニングは黒の勝ちであるように見えます。また、ドローツリーは、垂直オープニングの後よりも対角オープニングの後の方が大きく見えます。[20] [検証に失敗しました]平行オープニングは黒プレーヤーにとって大きな利点があり、黒は完璧なプレイで常に勝つことができます。[21] [検証に失敗しました]
コンピュータオセロのマイルストーン
- 1977年：サイエンティフィック・アメリカン誌は、 BCPLでNJD・ジェイコブスが書いたオセロ/リバーシプログラムに関する最古の出版物を出版した。[22] BYTEは10月に「オセロ、新しい古代ゲーム」をBASIC入力プログラムとして出版した。[23]
- 1977年：クリエイティブコンピューティング社はエド・ライトがFORTRANで書いたオセロのバージョンを出版した。[24] [25]
- 1978年：任天堂がビデオゲーム 「コンピュータオセロ」をアーケードで発売。[26]
- 1980年：オセロプログラム「The Moor」 （マイク・リーブとデビッド・レヴィ作）が世界チャンピオンの井上弘との6ゲームマッチで1勝した。[27]ノースウェスタン大学のピーター・W・フレイはBYTEでコンピュータと人間のオセロ戦略について論じ、TRS-80オセロゲームについて論じた。フレイによれば、このゲームはCDC 6600で動作するライトのバージョンを簡単に打ち負かしたという。[25]カーネギーメロン大学のポール・ローゼンブルームはIAGOを開発し、ノースウェスタン大学のコンピュータトーナメントで3位になった。[28] IAGOがThe Moorと対戦したとき、IAGOは駒を永久に捕獲し、相手の機動力を制限する点で優れていた。[27]
- 1981年: DEC KA10で動作していたIAGOが、カリフォルニア大学サンタクルーズ校で開催されたサンタクルーズオープンオセロトーナメントで、唯一無敗の記録で他の19人の出場者を抑えて優勝した。チャールズ・ヒースのTRS 80ベースのゲームは2位となった。マイクロコンピュータのCPUベースのエンジンは、メインフレームやミニコンピュータを抑えて2位から7位を獲得した。これは、コンピュータオセロが、より高速な浮動小数点演算など、大型コンピュータの利点のいくつかを享受していないためだとフレイは推測した。[28]
- 1980年代後半：カイフー・リーとサンジョイ・マハジャンは、IAGOに似ているがベイズ学習を取り入れたオセロプログラムBILLを作成した。BILLは確実にIAGOに勝った。 [27]
- 1992年：マイケル・ビューロがオセロプログラムLogistelloの開発を開始。Logistelloの探索技術、評価関数、パターンの知識ベースは、以前のプログラムよりも優れていた。Logistelloは10万回以上の自己対戦によりゲームを完成させた。[27]
- 1997年：ロジステロは世界チャンピオンの村上健との6ゲームマッチで全勝した。オセロプログラムが人間より強いことにはそれほど疑問の余地はなかったが、コンピュータと現世界チャンピオンの最後の試合は17年ぶりだった。1997年の試合後、ロジステロがどの人間プレイヤーよりも明らかに優れていることに疑問の余地はなくなった。[29] [27]
- 1998年：マイケル・ビューロがLogistelloを引退。オセロの研究への関心はやや薄れたが、Ntest、Saio、Edax、Cassio、Zebra、Heraklesなどのプログラムは開発が続けられた。[27]
- 2004年：NtestはLogistelloを大幅に上回る最強のプログラムになりました。
- 2005 : Ntest、Saio、Edax、Cyrano、Zebra が Logistello よりも大幅に強くなりました。 NtestとZebraは引退した。
- 2011 : Saio、Edax、Cyrano は、Logistello や他のプログラムよりもはるかに高速になりました。
- 2022 :エダックスに強くインスパイアされた強力なエンジンとしてエガロウシッドが登場します。
- 2023年：オセロはわずかに改良されたEdaxを使用して解かれ、Egaroucidは自己プレイデータを公開した。[30]
トップオセロ/リバーシプログラムのリスト
- NTest (Ntest) Chris Welty 著
- Edax (Edax Archived 2013-04-06 at the Wayback Machine ) リチャード・デローム
- マイケル・ブロによる「Logistello (Logistello)」
参照
注記
- ^ ab "Dcs.gla.ac.uk" (PDF) 。 2011年1月3日時点のオリジナル(PDF)よりアーカイブ。
- ^ Jean-Christophe Weill (1992). NegaC*検索。ICCAジャーナル、第15巻、第1号、pp.3-7。
- ^ アルマント、ヘンドラワン;サントソ、ジョアン。ジョバンニ、ダニエル。クルニアワン、ファリス。ユディアント、リッキー。グナワン、スティーブン (2012 年 10 月)。 「オセロゲームのための進化的ニューラルネットワーク」。Procedia - 社会および行動科学。57 : 419–425。土井：10.1016/j.sbspro.2012.09.1206。
- ^ Buro, M.、「オセロのマルチプロブカットと新しい高品質評価関数の実験」、Games in AI Research、HJ van den Herik、H. Iida（編）、ISBN 90-621-6416-1、2000年
- ^ Jean-Christophe Weill (1996)。ABDADA 分散ミニマックス検索アルゴリズム。1996 ACM コンピュータサイエンス会議の議事録、pp. 131-138。ACM、ニューヨーク、NY、ICCA ジャーナル Vol. 19、No. 1 に再掲載
- ^ Mark Brockington (1997)。KEYANO Unplugged - オセロプログラムの構築。技術レポート TR-97-05、アルバータ大学コンピューティング科学部。
- ^ ライナー・フェルドマン、ピーター・ミスリヴィッツ、ブルクハルト・モニエン (1991)。完全分散型チェス プログラム。コンピューターチェス 6 の進歩
- ^ Buro, Michael (1997). 「オセロにおけるマルチプロブカットと新しい高品質評価関数の実験」. Games in AI Research . 34 (4): 77–96.
- ^ ブリトコ、ヴァディム;ルストレク、ミティア。シェーファー、ジョナサン。ビョルンソン、イングヴィ。スヴェリルのシグムンダルソン（2008年6月1日）。 「リアルタイムヒューリスティック検索における動的制御」。人工知能研究ジャーナル。32 : 419–452。土井：10.1613/jair.2497。
- ^ Fürnkranz, Johannes (2001). ゲームをプレイすることを学ぶマシン | ガイドブック。Nova Science Publishers, Inc.6080 Jericho Tpke. Suite 207 Commack, NYUnited States: Nova Science Publishers, Inc. pp. 11–59. ISBN 978-1-59033-021-0。
{{cite book}}: CS1 メンテナンス: 場所 (リンク) - ^ Heinz, Ernst A. (2013). コンピュータチェスにおけるスケーラブルな検索: 高い検索深度でのアルゴリズムの強化と実験。Springer Science & Business Media。p. 32。ISBN 978-3-322-90178-1。
- ^ abcdef Gunnar Andersson (2007). 「オセロプログラムの作成」. radagast.se . 2023年2月12日閲覧。
- ^ Ntest の仕組み 2011-11-09 にWayback Machineにアーカイブ2005 年 3 月 2 日
- ^ ab オセロ 4 × 4 の解法 2011-07-07 にWayback Machineでアーカイブ2008 年 9 月 2 日
- ^ 6x6 オセロにおける 2 つの代替開始位置からの完璧なプレイ 2009 年 11 月 1 日にアーカイブ、Wayback Machineで2004 年 11 月 17 日
- ^ F. Pittner (2006年7月). 「Tothelloホームページ」www.tothello.com . 2023年2月12日閲覧。
- ^ 「オセロは解決された」（PDF） 。 2023年11月4日閲覧。
- ^ 滝沢、ヒロキ。 「リバーシスクリプト」。ギットハブ。2023 年11 月 4 日に取得。
- ^ 「オセロのポジションのゲームの分析」。2023年11月4日閲覧。
- ^ 「人工知能の観点から見た最強のオセロプログラム」。2007年1月9日時点のオリジナルよりアーカイブ。2010年4月5日閲覧。
- ^ 「SaioAppプロジェクト – 最強のオセロエンジン」。2023年2月12日閲覧。
- ^ ガードナー、マーティン。数学的レクリエーション。サイエンティフィック・アメリカン、1977年4月。
- ^ Duda, Richard O (1977年10月). 「オセロ、新しい古代ゲーム」. BYTE . pp. 60–62.
- ^ エド・ライト（1977年11月～12月）。「オセロ」。クリエイティブ・コンピューティング。pp. 140～142。2013年10月18日閲覧。
- ^ ab Frey, Peter W (1980 年 7 月)。「パーソナル コンピューターでの人間の意思決定のシミュレーション」。BYTE。p . 56。2013年10 月 18 日閲覧。
- ^ 「コンピュータオセロ - 任天堂のビデオゲーム」。
- ^ abcdef 「コンピュータゲームの歴史」(PDF)。2011年1月24日時点のオリジナル(PDF)よりアーカイブ。
- ^ ab Frey, Peter W (1981 年 7 月)。「The Santa Cruz Open / Othello Tournament for Computers」。BYTE。p . 16。2013年10 月 18 日閲覧。
- ^ Michael Buro (1997年8月20日). 「オセロ マッチ オブ ザ イヤー」. skatgame.net . 2023年2月12日閲覧。
- ^ 山名、拓人。 「エガルーシッドの自演転写」。オセロAIエガルーシッド。2023 年11 月 5 日に取得。
外部リンク
無料辞書『ウィクショナリー』で「コンピューターオセロ」を調べてください。
- 4×4 オセロ
- 6 × 6 オセロ
- チェスプログラミング
- コンピュータと対戦してオンラインでオセロをプレイ