TOP

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

公開日： 2018/06/05 : 最終更新日：2018/06/05 ボードゲームチェッカー, 完全解明, 引き分け

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

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

Contents

チェッカー（checker）とは？

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

Wikipedia：チェッカー

Chinock について

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

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

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

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

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

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

この時は、Tinsley が４勝２敗（３３引き分け）で Chinock に勝利します。

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

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

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

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

ジョナサン・スカエファー（Jonathan Schaeffer）はその後、１０年あまり研究を続けて、冒頭の「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 探索」を解くことに成功した、ということじゃないかと思います（汗）。