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

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

では、コンピュータはボードゲームをどのようにプレイしているのか、基本的な概要を調べてみました。

二人完全情報確定的ゼロ和ゲーム

将棋などのボードゲームは、「二人完全情報確定的ゼロ和ゲーム」というゲームに分類されます。
なにやら長くて難しい名称ですね(笑)
ちなみに、オセロ・チェス・囲碁も同じ仲間に分類されます。

それでは、「二人完全情報確定的ゼロ和ゲーム」に当てはまる条件は何なのでしょうか?
単語を分割して1つずつ説明していきます。

二人」は、二人で対戦するゲームであるということです。

完全情報」は、相手の情報も全て見えるということです。
例えば、トランプは相手のカードが見えないのでこの条件には当てはまりません。

確定的」は、偶然性が一切入らないということです。
例えば、サイコロを振るゲームだと、偶然性が入ってしまいこの条件に当てはまりません。

ゼロ和」は、足してゼロになるゲームであるということです。
自分が勝てば、相手が負け、
相手が勝てば、自分が負けとなるゲームです。

で、以下の手法は、この「二人完全情報確定的ゼロ和ゲーム」にしか適応することができない手法です。

ゲーム木探索

ゲーム木とは、以下のような樹形図のことです。

初手がルートとすると、
1手指すごとにどんどん枝分かれしていきます。
そして、ずっと伸ばしていくと、必ず最後のノードにいきつきます。
それを葉といいます。

コンピュータは、このゲーム木を探索していき、指し手を決めていきます。

最終局面まで読みきることができれば、そのボードゲームの必勝法を求めることができますが、
その局面まで着手可能な指しては、

  • オセロの場合は、10の60乗
  • チェスの場合は、10の120乗(将棋と違って持ち駒が使えないため少ない)
  • 将棋の場合は、10の220乗
  • 囲碁の場合は、10の360乗(将棋より升目が多い19×19路ある)

あるため、読み切るのは不可能で、スーパーコンピュータを使っても宇宙の歴史より長い時間がかかってしまうそうです。

Minimax 法

よほど単純なゲームでない限り、最終局面までの読み切りは不可能なので、コンピュータに「ある程度の局面まで読んで、その時点での最善手を指す。」ということをさせます。

その際に指し手を決めるルールが Minimax 法です。

もう少し詳しくいうと、ゲーム木において、「あるところまで探索してその局面に点数を付け、分の手番で評価値を最大化し、相手の手番で自分の評価値を最小化するような手順を選択していく。」ということになります。

局面に点数を付けるときに使われるのが、局面評価関数と呼ばれるもので、将棋の大局観に相当します。

この Minimax の考え方を考案したのが、「CLAUDE E. SHANNON」や「Von Neumann」です。

それぞれの論文です。

・「Programming a Computer for Playing Chess

https://link.springer.com/chapter/10.1007/978-1-4757-1968-0_1

・「Game Theory and Von Neumann’s Minimax Theorem

http://cdm16120.contentdm.oclc.org/cdm/ref/collection/p16120coll7/id/5

αβアルゴリズム

単純にMinimax法を使って探索していくと膨大な数の局面になってしまいます。

ある局面の平均着手可能手は、チェスだと35、将棋だと80、囲碁だと250程度だといわれており、数手先の探索でさえ膨大な探索空間になってしまいます。

そこで、Minimax法 で不要な探索を減らして、効率的に探索を行うために、D. E. Knuthらにより考案された手法が αβアルゴリズムです。探索を減らすというのは、具体的には「不要な葉ノードの局面評価関数の呼び出しを減らす。」ということです。

ちなみに、αβアルゴリズムを使って効率的に探索を行うとMinimax法と比較して探索数がその平方根くらい少なくできることが知られています。

論文です。

・「An analysis of alpha-beta pruning

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

 

関連記事

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

【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 ↑