コンピュータオセロ

コンピュータオセロ

NTest - 強豪きょうごうオセロプログラム

コンピュータオセロは、自みずから指さし手てを選択せんたくしてオセロの対局たいきょくを行おこなう能力のうりょくを持もつコンピュータ技術ぎじゅつである。

ここでは、コンピュータオセロの技術ぎじゅつ的てきな情報じょうほうについて解説かいせつする。オセロとコンピュータとの関かかわり合あい一般いっぱんについての外延がいえん的てきな情報じょうほうは、オセロとコンピュータを参照さんしょう。

オセロプログラム

現在げんざい、インターネットから無料むりょうでダウンロード可能かのうなNTestやSaio、Edax、Cassio、Ponty Stone、Herakles、WZebra、Logistelloといった多おおくのオセロプログラムが存在そんざいする。これらのプログラムは、最新さいしんのコンピュータ上うえで動作どうささせた時とき、最強さいきょうの人間にんげんのプレーヤーを容易よういに打うち負まかすことができる。これは、手ての結果けっかはコンピュータと人間にんげんが共ともに予測よそくできるが、コンピュータがそれらの予測よそくに優すぐれているためである。

探索たんさく技術ぎじゅつ

コンピュータオセロプログラムはゲーム木きを用もちいて全すべての可能かのうな手てを探索たんさくする。理論りろん上じょうは、プログラムは全すべての駒こま配置はいち/節ふしを調しらべ、ここでは1人ひとりのプレーヤーによるそれぞれの手ては「プライ ply（層そう）」と呼よばれる。この探索たんさくは任意にんいの最大さいだい探索たんさく深度しんどまで、あるいはプログラムが最終さいしゅう「葉は」配置はいちに到達とうたつしたと決定けっていするまで続つづく。

ミニマックスやネガマックスと呼よばれるこのアプローチのばか正直しょうじきな実装じっそうは、実際じっさい上じょうの時間じかん内ないで小ちいさな深度しんどしか探索たんさくすることができない。そのため、より手てを探索たんさくする速度そくどを大おおきく増ますための様々さまざまな手法しゅほうが考案こうあんされている。これら、αあるふぁβべーた枝えだ刈がり、Negascout、MTD-f、NegaC*に基もとづく。

よい手ての順番じゅんばん、置換ちかん表ひょう、選択せんたく的てき探索たんさくといったいくつかの経験けいけん則そくも探索たんさく木きの大おおきさを減へらすために用もちいられる。

マルチプロセッサあるいはマルチコアを持もつマシン上じょうでの探索たんさくを高速こうそく化かするため、「並列へいれつ探索たんさく」も実装じっそうされる。ABDADAあるいはAPHIDのように、オセロについて複数ふくすうの実験じっけんがなされている。近年きんねんのプログラム上じょうでは、YBWCがより好このまれる手法しゅほうのように見みえる。

評価ひょうか技術ぎじゅつ

評価ひょうか関数かんすうを作成さくせいするためには3つの異ことなる枠組わくぐみが存在そんざいする。

石いし-升ます表ひょう

異ことなる升ますは異ことなる価値かちを持もつ - 角かくはよく、角かくの隣となりの升ますは悪わるい。対称たいしょう性せいを無視むしすると、盤上ばんじょうには10の異ことなる位置いちがあり、これらの個々ここの位置いちは3つの可能かのう性せいについて価値かち（黒くろ、白しろ、空白くうはく）が与あたえられる。より洗練せんれんされた手法しゅほうは、ゲームの異ことなる段階だんかいでそれぞれの位置いちが異ことなる価値かちを持もつ。例たとえば、角かくは序盤じょばんや中盤ちゅうばんの前半ぜんはんでは終盤しゅうばんよりも重要じゅうようである。

可動かどう性せい

ほとんどの人間にんげんのプレーヤーは、可動かどう性せい（可能かのうな手ての数かず）を最大さいだい化かし、境界きょうかいの石いし（空白くうはくの角かくに隣接りんせつした石いし）を最小さいしょう化かすることを目指めざす。プレーヤーの可動かどう性せいと相手あいての可動かどう性せいが計算けいさんされ、プレーヤーの潜在せんざい的てき可動かどう性せいと相手あいての潜在せんざい的てき可動かどう性せいも同様どうように計算けいさんされる。これらの指標しひょうは非常ひじょうに速はやく見みつけることができ、強つよさを著いちじるしく上昇じょうしょうさせる。ほとんどのプログラムは縁えんと角かくの配置はいちに関かんする知識ちしきを有ゆうしており、中盤ちゅうばんの前半ぜんはんでの石いしの数かずを最小さいしょう化かしようと試こころみる（人間にんげんのプレーヤーでも使つかわれる戦略せんりゃく）。

パターン/パターン係数けいすう

可動かどう性せいの最大さいだい化かと境界きょうかい（の石いし）の最小さいしょう化かは、局所きょくしょ的てきな配置はいちへと分解ぶんかいすることができる。通常つうじょうの実装じっそうは、それぞれの行くだり、列れつ、対たい角かく、角かくの配置はいちを別々べつべつに評価ひょうかし、それぞれの価値かちを合計ごうけいするため、多おおくの異ことなるパターンを評価ひょうかしなければならない。全すべての配置はいちについての価値かちを決定けっていする過程かていは、強豪きょうごうプレーヤー間あいだでプレーされた試合しあいの大おおきなデータベースを入手にゅうしゅし、全すべての試合しあいからそれぞれのゲーム段階だんかいにおけるそれぞれの配置はいちについての統計とうけいを計算けいさんすることによって行おこなわれる。

勝者しょうしゃが対応たいおうする石いしの数かずだけボーナスを得えるように重おもみ付づけされた石いしの数かずの差さの指標しひょうが、最終さいしゅう的てきな石いしの数かずの差さを予測よそくするために最もっとも一般いっぱん的てきに用もちいられる。

オープニングブック

オープニングブック（序盤じょばん定石じょうせきのデータベース）は、まずいオープニングに反撃はんげきするよい方法ほうほうと見みなされている一般いっぱん的てきなオープニングを与あたえることでコンピュータプログラムを助たすける。全すべての強力きょうりょくなプログラムはオープニングブックを使用しようし、それぞれの試合しあい後ごに自動的じどうてきに自身じしんの定石じょうせきデータベースを更新こうしんする。試合しあいデータベース中ちゅうの全すべての試合しあいの全すべてのポジションを調しらべ、データベースの試合しあいで打うたれていない最良さいりょうの手てを決定けっていするため、以前いぜんに探索たんさくされたポジションを記録きろくするための置換ちかん表ひょうが用もちいられる。これは、それらのポジションを再ふたたび探索たんさくする必要ひつようがないことを意味いみする。個々ここのポジションについて深ふかい探索たんさくを実行じっこうしなければならないためこれは多大ただいな時間じかんを必要ひつようとするが、一度いちど実行じっこうしてしまえば、定石じょうせきデータベースの更新こうしんは容易よういである。それぞれの試合しあいをプレーした後のち、全すべての新あたらしいポジションが最良さいりょうの偏差へんさについて探索たんさくされる。

完全かんぜん解析かいせきの手法しゅほう

4×4盤ばん

4×4盤ばんオセロは非常ひじょうに小ちいさなゲーム木きを持もち、全すべての可能かのうな局面きょくめん（1千せん万まん近ちかく）を生成せいせいするミニマックス法ほうを用もちいる多おおくの単純たんじゅんなオセロプログラムによって1秒びょう以内いないに解決かいけつされる。結果けっかは白しろ（後手ごて）の10石せき勝がちである。

6×6盤ばん

6×6盤ばんオセロは、全すべての可能かのうな局面きょくめん（3.6兆ちょう近ちかく）を生成せいせいするミニマックス法ほうを用もちいる多おおくの単純たんじゅんなオセロプログラムによって100時間じかん以内いないに解決かいけつされる。結果けっかは白しろ（後手ごて）の4石せき勝がちである。

8×8盤ばん

8×8盤ばんオセロのゲーム木きのサイズは10⁵⁴ノードと推定すいていされており、合法ごうほう的てきなポジションの数かずは10²⁸と推定すいていされている。数学すうがく的てきには未解決みかいけつであるが、速はやい並列へいれつハードウェア上じょうあるいは分散ぶんさんコンピューティングを通つうじたプログラムによる徹底的てっていてきな計算けいさんを行おこなうことで解かいを見みつけることは可能かのうかもしれない。

数すう多おおくの引ひき分わけへの道筋みちすじが示しめされているが、このような道筋みちすじは完全かんぜんに判明はんめいしていない。

一部いちぶの強豪きょうごうプログラムは長年ながねん自身じしんのデータベースを拡張かくちょうしてきた。斜ななめ取とり、縦たて取とり、並ならび取とりの23つの主要しゅようなオープニングに関かんしては、斜ななめ取とりと縦たて取とりは引ひき分わけの筋すじへ至いたる傾向けいこうにあり、一方いっぽうで並ならび取とりは黒くろ（先手せんて）の勝かちとなる。引ひき分わけ木きは、縦たて取とりの後のちよりも斜ななめ取とりの後のちの方ほうが大おおきいようである。並ならび取とりは黒くろ（先手せんて）に非常ひじょうに有利ゆうりであり、完璧かんぺきに打うった場合ばあいは常つねに勝かつことができる。証明しょうめいされてはいないが、実質じっしつ的てきには双方そうほうのプレーヤーが完璧かんぺきに打うった場合ばあいは試合しあいは常つねに引ひき分わけとなる。オープニングブックを使用しようした標準ひょうじゅん的てきゲームでは、トッププログラムの負まける確かく率りつは1%未満みまんである。

10×10盤ばん

10×10盤ばんでは、先手せんて（黒くろ）がより勝かちやすい。10x10は中盤ちゅうばんがより長ながい。コンピュータの解析かいせきでは、両者りょうしゃが完璧かんぺきに打うったとすると引ひき分わけが最もっとも起おこりやすいことが示しめされている。ゲーム木きの複雑ふくざつさは非常ひじょうに高たかく10⁹⁰と推定すいていされており、合法ごうほう的てきなポジションの数かずは10⁴⁴と推定すいていされている。

年表ねんぴょう

• 1977年ねん: Creative Computing誌しがEd WrightによってFORTRANで書かかれたオセロのバージョンを発表はっぴょうした。なお、日本にっぽんでは8月がつ7日にちに「第だい五ご回かい 全日本ぜんにほんオセロ選手権せんしゅけん大会たいかい」（日本にっぽんオセロ連盟れんめい主催しゅさい）にて人間にんげんvsコンピューターのオセロゲーム対決たいけつが行おこなわれている。コンピューター代表だいひょうは電電でんでん公社こうしゃ（現げん・NTT）技術ぎじゅつ局きょくの室谷むろたに正芳まさよし調査ちょうさ役やくが、同どう公社こうしゃの大型おおがたコンピューターに「10の60乗じょうの"手しゅ"を記憶きおくした」というソフトウェアを組くみ込こんだもの。対たいする人間にんげん代表だいひょうは日本にっぽんオセロ連盟れんめいの長谷川はせがわ会長かいちょうや、前年ぜんねんの同どう大会たいかい男子だんし2位いの強豪きょうごうらが選えらばれた。結果けっかはコンピューターの20勝しょう8敗はい。
• 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は世界せかいチャンピオン村上むらかみ健けんとの六ろく番ばん勝負しょうぶで全勝ぜんしょうした。実際じっさいには、それ以前いぜんからコンピュータオセロは人間にんげんを上回うわまわっており、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やその他たのプログラムよりも高速こうそくになった。
• 2019年ねん: 吉田よしだ拓たく真しんが開発かいはつした「最さい弱じゃくオセロ」が公開こうかいされた。従来じゅうらいのプログラムでは勝かちを目指めざすものであるが、この「最さい弱じゃくオセロ」は全まったくの正せい反対はんたいになっており人間にんげんが負まけるのが難むずかしくなっている。

関連かんれん項目こうもく

• コンピュータ囲碁いご
• コンピュータ将棋しょうぎ
• コンピュータチェス
• コンピュータオリンピアード
• ビットボード

外部がいぶリンク

• 4 x 4 Othello
• 6 x 6 Othello
• List of Othello programs
• Chess programming
• 最さい弱じゃくオセロ