第1次AIブーム(推論・探索の時代) その3 ボードゲーム

AI

G検定記事はこちら。
https://www.simulationroom999.com/blog/jdla-deep-learning-for-general-2020-1/

スポンサーリンク

はじめに

AIはボードゲームでも利用される。
(オセロ、チェス、将棋、囲碁など)
これらの実現手段の概要を記載する。

スポンサーリンク

ボードゲームの探索規模

これも基本は探索木になる。
迷路の探索木に似ているが、「行動」と「結果」の連続した探索木となるが、局面が複雑化するタイプになると、それだけ膨大なツリーとなる。
探索木の規模は以下となる。

オセロ$${10^{60}}$$
チェス$${10^{120}}$$
将棋$$10^{220}$$
囲碁$$10^{360}$$
スポンサーリンク

ヒューリスティックな知識

単純な総当たりな探索では時間が掛かるため、ゴールまでのコストという概念を用いて、
最適化を行う必要が出てくる。
これを「ヒューリスティックな知識」と言う。

スポンサーリンク

Mini-Max法

上記のコストを点数として考え、以下の状態を優先的に狙う手法

  • 相手を不利(最小点数)
  • 自分を有利(最大点数)


完全情報零和ゲームに向いているとされている。
完全情報零和ゲームとは、すべての情報が開示されており、次のゲームに前のゲームの結果が影響しないものである。

Mini-Max法で探索木を縮小させる手法が存在しており、それをαβ法と呼ぶ。

  • 最小点数探索中に大点数の枝をカット → αカット
  • 最大点数探索中の小点数の枝をカット → βカット
スポンサーリンク

まとめ

  • すべての結果が分かれば確実に勝てるという考え方。
  • しかし、相当な計算能力が必要とされる。
    • オセロ < チェス < 将棋 < 囲碁
  • 計算能力を削減するためにMini-Max法αβ法が考え出された。

コメント

タイトルとURLをコピーしました