探索木・ゲーム木

Image from Gyazo

ゲーム木

これまでは8パズルやハノイの塔など1人のプレイヤーが解く問題を対象にしていました. ここでは,プレイヤーとコンピュータが対戦するオセロや将棋などの対戦形式のゲームについて考えましょう.

人間とコンピュータとの対戦

対戦形式のゲームは,従来から人工知能の研究テーマとして取り組まれています. これまでに,人間(プロ棋士)とコンピュターとの対戦がメディアにも取り上げられています. 1997年には,IBMのDeep Blueが当時のチェスのチャンピオンに勝利しました, 2013年には,山本一成氏が開発したPonanzaがプロ棋士に勝利したことが注目されました. さらに,2016年には,ディープラーニングを取り入れたDeepMindのAlphaGoがプロ棋士に勝利しました. このように,対戦形式のゲームでは,既にコンピュータ(AI)が人間を超えるようになっています.

ゲーム 状況
オセロ 1980年 ムーアが世界チャンピオンの井上博に勝利
チェス 1997年 IBMのDeepBlueが世界チャンピオンのガルリ・カスパロフに勝利
将棋 2013年 山本一成が開発したPonanzaがプロ棋士の佐藤慎一に勝利
囲碁 2016年 DeepMindのAlphaGoがプロ棋士のイ・セドルに勝利

ゲーム木を利用した解の導出

対戦形式のゲームでは,プレイヤーの選択と,コンピュータの選択が交互に繰り返されます. このため,これまでの探索木では,適切な解を導出することができません. このような場合, ゲーム木(Game Tree) と呼ばれる手法が用いられます.

ゲーム木は次のような木構造で表されます. 木のルート(根)であるAはゲームの初期状態(盤面)であり,先手(黒)が手を打つ場面です. 先手が手を打つとBまたはCに遷移します. BCは後手(白)が手を打つ場面です. 同様に,後手が手を打つと,BからDEF,また,CからGHI,のいずれかに遷移します. DからIは先手が手を打つ場面です. 最終的には,後手が手を打つ場面であるJからVに遷移します.

JからVの状態(盤面)には,先手がどれぐらい有利かを表す評価が与えられます (評価を決める評価関数はゲームによって異なり,開発者が最も頭を悩ませる部分です). 例えば,Jは3,Kは2,Lは7となっています. 先手にとっては,A - B - D - Lと遷移すると,最も評価の高い 7 になりますが, 後手は先手の評価を下げようと手を打つため,実際はLに到達することはできません.

Image from Gyazo

そこで,ミニマックス法(minimax) を用いて解を導出します. 先手は評価を 最大化 ,後手は評価を 最小化 することから名付けられました. Dの場面では,先手が手を打つため,評価が最大となるLを選択します. よって,Dの評価もLと同じ7に設定します. 同様に,EからIの評価も設定します. Bの場面では,後手が手を打つため,評価が最小となるEを選択します. よって,Bの評価もEと同じ4に設定します. 同様に,Cの評価は3に設定されます. Aの場面では,先手が手を打つため,評価が最大なるBを選択します. よって,Aの評価はBと同じ4に設定されます. このため,A - B - E - Mに遷移することが先手にとって最良の選択となります.

Image from Gyazo

1手ごとにミニマックス法による探索を実行し,先手は次の1手を決めます. 先の例では深さが3までの探索でした(先手 - 後手 - 先手 - 後手). これを深くすることで,より有利な手を導出することができます. しかし,探索する状態の組み合わせが爆発的に増加するため,効率良く探索することが求められます( アルファベータ法 など).

ノートブックの作成

Jupyter Notebook を起動し,新規にノートブックを作成してください. ノートブックのタイトルは AI-17 とします. ノートブックの作成方法は第1回の資料を参照してください.

最初に木構造を表現するtreelibをインストールします. treelibはゲーム木を表現するために用います. セルで下記のコマンドを実行してください.

> !pip install treelib

また,treelibに加え,下記のライブラリも導入しておきましょう.

from treelib import Node, Tree
import numpy as np
import itertools

実装

ゲーム木を実装してみましょう. 最初に状態(盤面)の評価を表す Evaluationクラスを定義します. Evaluationクラスは,「プレイヤー(先手または後手)」,「盤面の状態」,「盤面の評価」を保持します.

# 盤面の評価
class Evaluation():

  # 初期化
  def __init__(self, player, board, value):
    self.player = player #プレイヤー
    self.board = board # 状態
    self.value = value # 評価
    self.text = self.__str__()

  # 文字列化
  def __str__(self):
    return f"[{self.player} {self.board} {self.value}]"

  # 評価の更新
  def update(self, value):
    self.value = value
    self.text = self.__str__()

treelibでゲーム木を表現します. 先手はBlack,後手はWhiteで表現しています. また,盤面の状態は,先の図に合わせて,AからVとしています(本来は駒の配置などを表現する). 盤面の評価も,先の図と同じ値に設定しています(本来は評価関数で計算する).

# ゲーム木
tree = Tree()

# Blackの盤面(先手)
tree.create_node("A", "A", data=Evaluation("Black", "A", None))

# Whiteの盤面(後手)
tree.create_node("B", "B", data=Evaluation("White", "B", None), parent="A")
tree.create_node("C", "C", data=Evaluation("White", "C", None), parent="A")

# Blackの盤面(先手)
tree.create_node("D", "D", data=Evaluation("Black", "D", None), parent="B")
tree.create_node("E", "E", data=Evaluation("Black", "E", None), parent="B")
tree.create_node("F", "F", data=Evaluation("Black", "F", None), parent="B")
tree.create_node("G", "G", data=Evaluation("Black", "G", None), parent="C")
tree.create_node("H", "H", data=Evaluation("Black", "H", None), parent="C")
tree.create_node("I", "I", data=Evaluation("Black", "I", None), parent="C")

# Whiteの盤面(後手)
# 評価は先手にとっての盤面の価値を表すことに注意
tree.create_node("J", "J", data=Evaluation("White", "J", 3), parent="D")
tree.create_node("K", "K", data=Evaluation("White", "K", 2), parent="D")
tree.create_node("L", "L", data=Evaluation("White", "L", 7), parent="D")
tree.create_node("M", "M", data=Evaluation("White", "M", 4), parent="E")
tree.create_node("N", "N", data=Evaluation("White", "N", 6), parent="F")
tree.create_node("O", "O", data=Evaluation("White", "O", 2), parent="F")
tree.create_node("P", "P", data=Evaluation("White", "P", 3), parent="F")
tree.create_node("Q", "Q", data=Evaluation("White", "Q", 5), parent="G")
tree.create_node("R", "R", data=Evaluation("White", "R", 4), parent="G")
tree.create_node("S", "S", data=Evaluation("White", "S", 1), parent="H")
tree.create_node("T", "T", data=Evaluation("White", "T", 3), parent="H")
tree.create_node("U", "U", data=Evaluation("White", "U", 5), parent="I")
tree.create_node("V", "V", data=Evaluation("White", "V", 6), parent="I")

作成したゲーム木を表示します. 末端以外の状態の評価はNoneとなっていることに注意してください. 先の図と同じ木構造になっていることを確認できます.

# ゲーム木の表示
tree.show(data_property="text")
[Black A None]
├── [White B None]
   ├── [Black D None]
      ├── [White J 3]
      ├── [White K 2]
      └── [White L 7]
   ├── [Black E None]
      └── [White M 4]
   └── [Black F None]
       ├── [White N 6]
       ├── [White O 2]
       └── [White P 3]
└── [White C None]
    ├── [Black G None]
       ├── [White Q 5]
       └── [White R 4]
    ├── [Black H None]
       ├── [White S 1]
       └── [White T 3]
    └── [Black I None]
        ├── [White U 5]
        └── [White V 6]

ミニマックス法で,木の末端から評価を伝播させて,全ての状態(盤面)の評価を設定します. 深さが奇数のときは最大値を選択し,偶数のときは最小値を選択します.

# ミニマックス法
def minimax(tree):

  # ノードを取得
  nodes = tree.all_nodes()

  # 降順で並べ替え
  nodes = sorted(nodes, key=lambda x: tree.depth(x), reverse=True)

  for node in nodes:

    if not(node.is_root()):

      parent = tree.parent(node.identifier) # 親ノード
      depth = tree.depth(node) # 深さ

      if depth % 2 == 1:
        if parent.data.value:
          # 最大値を選択
          parent.data.update(max(parent.data.value, node.data.value))
        else:
          parent.data.update(node.data.value)
      else:  
        if parent.data.value:
          # 最小値を選択
          parent.data.update(min(parent.data.value, node.data.value))
        else:
          parent.data.update(node.data.value)

  return tree

再度,ゲーム木を表示します. 全ての状態(盤面)に評価が設定されていることがわかります.

tree = minimax(tree)
tree.show(data_property="text")
[Black A 4]
├── [White B 4]
   ├── [Black D 7]
      ├── [White J 3]
      ├── [White K 2]
      └── [White L 7]
   ├── [Black E 4]
      └── [White M 4]
   └── [Black F 6]
       ├── [White N 6]
       ├── [White O 2]
       └── [White P 3]
└── [White C 3]
    ├── [Black G 5]
       ├── [White Q 5]
       └── [White R 4]
    ├── [Black H 3]
       ├── [White S 1]
       └── [White T 3]
    └── [Black I 6]
        ├── [White U 5]
        └── [White V 6]

先手はBまたはCの評価の高い方を選択します. ここでは,評価4のBが選択されることになります. この選択を1手ごとに繰り返します.

def getMax(tree):

  # 降順で並べ替え
  nodes = tree.children(tree.root)
  nodes = sorted(nodes, key=lambda x: x.data.value, reverse=True)

  # 評価が最大の状態を選択
  max_node = nodes[0]

  return max_node
max_node = getMax(tree)
print(max_node.data)
[White B 4]

課題

Google Colaboratoryで作成した AI-17.ipynb を保存し, ノートブック(.ipynb) をダウンロードして提出しなさい. 提出の前に必ず下記の設定を行うこと.

愛知県名古屋市にある椙山女学園大学 文化情報学部 向研究室の公式サイトです. 専門は情報科学であり,人工知能やデータベースなどの技術要素を指導しています. この公式サイトでは,授業で使用している教材を公開すると共に, ベールに包まれた女子大教員のミステリアスな日常を4コマ漫画でお伝えしていきます. サイトに関するご意見やご質問はFacebookまたはTwitterでお問い合わせください.