AI実装手法のメモ

月日が経つのは早いもので、前回の投稿が約１年前ということに驚きを隠せません。
ごいたオンラインも、もうそれくらい長い間稼働しているのですね。

最近ごいたソフトウェアをこそこそと作成しているので、開発ブログのほうも更新しましょう。

まずは、ずっと前にメモしたAI実装手法のメモを公開します。

ちなみに、全プレイヤーが最善手を目指して打つという前提で考えています。

ごいたAI的な用語

手の評価
手の評価とは、この受け・攻めまたはなしを行った場合に、自分のチームが何点獲得するかを数値化することを指します。
自分のチームが20点上がりするなら、 +20
相手チームが30点上がりするなら、 -30
自分が上がる場合と、相方が上がる場合とで評価に差をつけることも考えられますが、一旦これは考えないことにします。

予測
相手の残っている手駒を予想することです。

盤面
ごいたの場のことです。打ち出し(1手目)、序盤(2〜4)、中盤(5〜7)、終盤(8〜)に分けて考えることにします。

ごいたのプレイヤーが入手可能な情報

ごいたAIに渡せる情報の一覧を整理します。

場の情報

  • 自分の手駒 8個
  • 場に出された駒 0〜24 (駒は32個あるが、24を超える＝誰かが上がる)
  • 自分が出した駒の伏せ内容

行動履歴情報

  • 各プレイヤーの受け・攻め・なしの履歴

不明情報

  • 対戦相手2人と相方の手駒
  • 自分以外の伏せ駒

ごいたAIに使用できる手法

完全読み

手駒の情報がすべて判明している場合に、すべての取りうる手を試して、プレイヤー全員が最善手を打った場合に、誰かが上がるまで盤面を進め、何点獲得できるかを読みます。

Min-Max法(α-β法)などを使用して、ゲーム木探索を行います。

全員の手駒情報が判明している場合にしか使えないので、相手の手駒を予測する手法と組み合わせて使用することになります。

特徴

  • 隠された情報の予測精度が高くなればなるほど有効な手法。
  • 序盤から完全読みを行うことは、可能性が多くなりすぎるため、現実的な計算時間では終わらないので、12駒程度(6手番)が過ぎた段階までは使えない。

用途

  • 棋譜の解析を行う場合に、手の評価をする
  • 手駒を予測する手法と組み合わせて、予測した結果で手の評価をする

先読み

完全読みとは異なり、何手番分読むかを決めて、先の展開を考えることです。

AIが内部的にごいたの盤面を進めて、進めた結果自分に有利か不利かを評価し、手を評価する。

特徴

  • 最終盤面まで進めないため、計算時間が少なく済む。
  • 読みの精度は途中の盤面を評価する手法の精度に大きく依存する。

用途

  • 序盤の手を評価する。

モンテカルロ法

ランダムに試行を重ねることで、妥当な結果を確率的に導き出す手法です。

相手の駒をランダムに予測して、何十回、何百回と完全読みを行うことで、どの手を採用した場合に最善となりそうかを予測します。

特徴

  • 正確なアルゴリズムがなくとも、ある程度妥当な結果を導き出せる。
  • 数多くの試行を行うため、計算時間が少ない評価手法と組み合わせる必要がある。

用途

  • 終盤の完全読み
  • 中盤の読み

ルールベース評価

いくつかのルールを設けて手の評価を行う手法です。

評価ルールを全てリストアップして実装していくことになります。例えばしが4枚あればしから攻める手を評価値高めにするとか。

評価ルールを何個も実装していくと、どのルールの評価をどのような配分で採用するべきか、調整が難しくなります。その場合は、GA(遺伝的アルゴリズム)などを使用して、最適なルールの優先度を決めるのが良いと思います。

特徴

  • ルールで決めた通りに手を評価する
  • ルールを網羅するのが大変

用途

  • 打ち出し(1手目)の評価
  • 5しの場合の判断
  • 王玉や4しなど、明らかに有効な手順が明確に決まる場面
  • 打ち方に特徴のあるコンピューターごい打ちを再現する場合(ゲームの敵キャラとか)

機械学習(ディープラーニング)

場の情報などを与えて、有利不利の評価をする手法です。

何の情報を与えて、何を評価させるかというのを考えることも重要なので、用途例を。

初手の打ち出し評価
初手の持ち駒だけを評価します。

5しの続行判断
これも持ち駒だけを評価します。

盤面評価
現在の場面で自分がどの程度有利か評価します。

手駒予想
自分意外のプレイヤーの残り手駒を予想します。

自分の残り手駒、場の状態などを与えて、それが良いか悪いかを教えてあげる作業を10万回〜100万回程度行うことで、盤面評価が出来るように学習させます。

特徴

  • 入力する情報と、評価軸をしっかりと定めることで、うまく評価してくれることが期待できます。
  • どんな評価がどの程度正確にできるかは未知数。

用途

  • ルールベースの手法では評価精度を高められない場面の評価
  • 人間を超える評価基準を持たせる

まとめ

5し判断、打ち出し、序盤〜終盤と、場面によって有効な手法があるので、うまく作る必要があります。
基本的に機械学習は、人間の感覚とは外れた、良い手を評価できる可能性があるので、全ての場面で期待が持てます。

  • ５し判断: ルールベース or 機械学習
  • 打ち出し: ルールベース or 機械学習
  • 序盤・中盤: 相手の持ち駒予測 + モンテカルロ法 + 先読み
  • 終盤: 相手の持ち駒予測 + モンテカルロ法 + 完全読み