【人工知能】チェッカーの完全解明について。

公開日: : 最終更新日:2018/06/05 ボードゲーム , ,

ボードゲームの1つである「チェッカー」が完全解明され、お互いに最善手を指し続けると絶対に引き分けになると2007年に報告されました。

チェッカー完全解明に至るまでの歴史や、関連資料をまとめてみました。

チェッカー(checker)とは?

チェッカーは、欧米ではメジャーなボードゲームで、チェスや将棋、囲碁のように「二人完全情報確定的ゼロ和ゲーム」であるが、チェスや将棋、囲碁と比べてると、そこまで複雑ではありません(それでも探索局面は 5*10^20 局面もあります)。詳しいルールについては、Wikipediaを参照してください。

Wikipedia:チェッカー

Chinock について

Chinock(チノック)とは、ジョナサン・スカエファー(Jonathan Schaeffer)を中心に開発され、人間の世界チャンピオンに勝つことを目標にした、チェッカーのコンピュータプログラムのことです。

Chinock は、わずか2年で強くなり、4年以内には人間の世界チャンピオンに勝てるようになると、当時、ジョナサン・スカエファーの「One Jump Ahead」には書かれています。

One Jump Ahead: Challenging Human Supremacy in Checkers

https://en.wikipedia.org/wiki/Jonathan_Schaeffer

当時、人間界の最強は、マリオン・ティンズリー(Marion Tinsley) という人でした。この人は、45年間にわずか7敗しかしていないという驚異的な強さでした。

https://en.wikipedia.org/wiki/Marion_Tinsley

そして、1992年に Tinsley と Chinock の戦いがロンドンで実現します。

この時は、Tinsley が4勝2敗(33引き分け)で Chinock に勝利します。

次に、1994年に 再びロンドンで再戦しました。

結果は、6戦して全て引き分でした。そして、Tinsley は高齢のため、この7カ月後に亡くなってしまいます。

Chinock に関する情報は、以下のページにあります。

https://webdocs.cs.ualberta.ca/~chinook/

ジョナサン・スカエファー(Jonathan Schaeffer)はその後、10年あまり研究を続けて、冒頭の「Checkers Is Solved」という論文を Science 誌に発表しました。

Checkers Is Solved とは?

2007年、「Checkers Is Solved」という論文が発表されました。日本でも話題になったようで、以下は日経新聞の記事の引用です。

市松模様の盤上で黒と赤などの丸い駒を斜めに動かし、相手の駒を飛び越して取り合うゲーム「チェッカー」を完全解明したと、カナダ・アルバータ大の研究チームが米科学誌サイエンス(電子版)に19日発表した。平均50台のコンピューターを18年動かし続けて得た結論は、最善手で差し続ければ必ず引き分けになるというもの。決して負けない対戦ソフトが可能になったが、より複雑なチェスや将棋の完全解明にはかなり時間がかかりそうだ。

こちらがサイエンス誌に投稿された論文です。無料で読めて、PDFをダウンロードできます。

http://science.sciencemag.org/content/317/5844/1518/tab-pdf

時間があれば読んでみたいと思います。英語ですが。。(汗)

あと、Jonathan Schaeffer と Tinsley の2人のが知り合って、チェッカーを解明するまでの物語「How Checkers Was Solved」が書かれているページが以下になります。

https://www.theatlantic.com/technology/archive/2017/07/marion-tinsley-checkers/534111/

こちらも、時間があれば読んでみたいと思います。英語ですが。。(汗)

そして、チェッカーが「お互いに最善手を指し続けると絶対に引き分けになる。」という結論に至った手法についてですが、あまり理解していないところがほとんどですが、ざっくりと概要を書きたいと思います。

まず、チェッカーのような「二人完全情報確定的ゼロ和ゲーム」と呼ばれるゲームは、ゲーム木によって指し手を探索していきます。全ての指し手を探索できれば、そのゲームの完全解明ができるのですが、多くのゲームが膨大な数となるので、全ての指し手の探索は不可能です。

そこで、通常、Minimax 法 を用いて、ある程度先の局面まで探索して、良さそうな手を選びます。そして、チェッカーにおりて完全解明をするということは、Minimax 法で AND/OR 探索になるということであることを意味します。ゲーム木の一種である AND/OR 木を解くために、共謀数と証明数という指標が用いられます。

共謀数(Conspiracy numbers)は、評価値の値が変わるためには、どれぐらいの葉局面を読まなければならないかというものです。チェッカーに限らず一般的に、ある解を候補として考えていて、それが安定しているか否かを確認するための指標になります。

Minimax法における共謀数に関する論文はこちらになります。

https://www.sciencedirect.com/science/article/pii/0004370288900197

証明数(Proof-number)は、ある局面を解くためには、どれぐらい読まなければいけないかというものです。これは、AND/OR 探索の場合では、評価値が「勝ち」「負け」「引き分け」のいずれかになるため、共謀数と等しくなります。

証明数に関する論文はこちらになります。

https://www.sciencedirect.com/science/article/pii/0004370294900043

というように、まとめると、チェッカーにおいて、「証明数」というものを使って、「AND/OR 探索」を解くことに成功した、ということじゃないかと思います(汗)。

関連記事

2016年11月20日|囲碁フォーカス講座|ストップ!車の後押し

今回は、NHKの囲碁フォーカス講座から2016年11月20日に放送された、三村智保講師による「磨け初

記事を読む

囲碁|棋譜再生ソフト「MultiGo」をインストールしてみた

NHKの囲碁講座の内容や詰め碁をブログに載せるために、棋譜再生のための囲碁盤ソフトを探していたところ

記事を読む

【人工知能】コンピュータチェスの歴史をまとめてみた。

コンピュータチェスは、1997年に DEEP BLUE がグランドマスターのカスパロフを破ったことは

記事を読む

【ゲーム木探索】コンピュータにボードゲームをプレイさせる方法。

チェス・将棋・囲碁までもがコンピュータ(人工知能)が人間を超えてしまいました。 では、コンピュ

記事を読む

2017年6月11日|囲碁フォーカス講座|ハサみたい?~小目

囲碁フォーカス講座「初段へのスタート、小山竜吾、囲碁ワールドで基礎力アップ」の2017年6月11日の

記事を読む

【ボードゲーム】X目並べは先手必勝!?

ゲームにおける「Fairness」という考え方があります。 これは、ある程度スキルがあるプレイ

記事を読む

【Game Refinement Theory】ゲームの面白さを数値化する研究について。

ゲームの面白さを数値化するような研究について紹介したいと思います。 ゲーム理論(game th

記事を読む

【藤井聡太】将棋界に若き天才が登場!新たな時代の幕開けか!?

将棋界は、長らく羽生さんの時代が続いていました。しかし、若手棋士の台頭によりタイトルを連続して奪取さ

記事を読む

2017年6月4日|囲碁フォーカス講座|ハサみたい?~星

囲碁フォーカス講座「初段へのスタート、小山竜吾、囲碁ワールドで基礎力アップ」の内容です。 6月

記事を読む

Message

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

【Python】pip3 で「cannot import name ‘main’」エラーが出たときの対処法。

Python でライブラリをインストールする際に、pipを使います。

【mecab-python3】parseToNode で surface が正しく取得できないときの対処法。

python3 で mecab-python3 を使うと、parseT

【Python】形態素解析器 Mecab を Linux(Ubuntu)で使ってみた。

Linux の Ubuntu OS に、形態素解析器 Mecab をイ

【Python】NLTK(自然言語処理ライブラリ)を使ってみた。

Python の自然言語処理ライブラリである NLTK を Linux

【Python】OpenCV を使って顔画像を検出してみた。

OpenCV のインストール Numpy のインストール [c

→もっと見る

PAGE TOP ↑