演習3 - オセロAIの作成

5. 演習3 - オセロAIの作成#

前節、オセロAIの作成では、オセロAIの基本であるゲーム木の探索方法について、盤面評価値に基づくアルファベータ探索や、プレイアウトの結果に基づくモンテカルト木探索等について解説した。

今回の演習では、この延長として、より強いオセロのAIを作成してみよう。

5.1. 演習内容#

今回の演習ではオセロプレイヤーのクラスを実装し、レベル別のオセロAIに対して1勝でも多く勝利することを目指す。以下が実装すべきMyPlayerクラスの雛形である。複雑なAIを実装しない限りは、はオセロ環境が渡されてくるMyPlayerクラスのplay関数のみを編集すれば十分だろう。

import numpy as np

from othello import Env, Action, Player
from players.base import BasePlayer


class MyPlayer(BasePlayer):
    def __init__(self):
        pass

    def reset(self) -> None:
        """
        ゲーム開始時に行いたい処理を記述
        """

    def play(self, env: Env) -> Action:
        """
        この関数を主に更新する、以下はランダムに着手する例
        """
        actions = env.legal_actions()
        return np.random.choice(actions)

より詳細な課題作成の流れについては以下の説明に従うと入手できるテンプレート・レポジトリのREADME.mdに従うこと。

5.1.1. 対戦相手のレベル#

対戦相手の詳細な実装については公開しないが、概ね以下の方針に従った実装になっている。

レベル1: モンテカルロ木探索系のAI
レベル2: アルファ・ベータ探索系のAI
レベル3: NegaScout法に基づくAI

なお、上記のAIは、レベルが上がるに従って、思考時間が長くなれば強くなるように実装されているが、今回は各AIが一手につき0.1秒だけ考慮するので、必ずしもレベルが高いほど強いとは限らない。

5.1.2. ローカル環境でのテスト#

本演習の採点はGitHub Classroomを使って行う。講義中で演習用のClassroomのURLを指示するので、そのURLをブラウザで開き、テンプレート・レポジトリを自分のGitHubアカウントと紐付けること。

その後、レポジトリをcloneして、ローカル環境でplayer.pyを編集してテストを実施する。テンプレート・レポジトリには、ランダムに着手するAIであるrandom.pyとミニマックス探索に基づくminimax.pyが提供されているので、それらとテストプレイすることができる。

テストプレイにはpytestを用いる。テンプレート・レポジトリのフォルダをターミナル環境で開き、以下のコマンドを実行する。

# ランダムAIとミニマックスAIの両方と対戦
pytest

また、どちらか一方とだけ対戦したい場合には-kの後にrandomあるいはminimaxを指定すれば良く、--n_match引数により対戦回数も変更できる。

# ミニマックスAIと20回対戦
pytest -k minimax --n_match 20

5.1.3. 本番環境でのテスト#

Github Classroomでは、演習用のレポジトリにコードをプッシュする度にテストが実行される。

本番環境では、各レベルのAIとランダムな手番で10回テストプレイが実行される。この対戦の結果、いずれのレベルであっても1勝すると1点が入る。

また、1回の対戦時間は15秒で終了するようになっており、もし時間切れとなった場合には自動的に負けとなる。各AIはおよそ0.1秒で手を指すようにプログラムされているので、それを考慮の上、自分のAIの考慮時間を調整すること。

5.2. 課題の進め方#

5.2.1. ゲームAIの概観#

前節、オセロAIの作成では

人間の事前知識に基づいたセルの評価に基づく手法 (ミニマックス探索など)
人間の事前知識に依らない手法 (モンテカルロ木探索など)

の2タイプのAIについて紹介した。

オセロゲームの場合、任意の盤状態において着手できる合法手は10前後であるため、手の探索が十分に高速なAIで、かつ考慮時間が数十秒あれば、アルファベータ探索のような枝刈りを用いることで手を終局までの盤面をおおよそ読み切ることができる。

また、アルファベータ探索に用いる盤の評価値についても、前節で紹介したセルの評価値に加えて、

相手が着手できる合法手の数 (少ない方が良い)
確定石の数 (多い方が良い)

などの指標を含めることが考えられる。

原始モンテカルロやモンテカルロ木探索は、オセロよりも着手できる合法手が多いゲーム (将棋や囲碁など)で、なおかつ盤面の直感的な評価が難しいものに有効な手法である。

また、近年、囲碁AIとして注目を集めたAlphaGoや、その発展形であるAlphaZeroは、モンテカルロ木探索と深層学習による着手の選択、盤面の評価を組み合わせた手法である。

これら2つのタイプのAIの側面を考慮した上で、どのようなAIを実装するのかを検討してみてほしい。

5.2.2. 課題の始めに試すこと#

まずは、テンプレート・レポジトリに与えられているミニマックス探索に基づくAI(players/minimax.py)が与えられているので、このプログラムをMyPlayerに反映して、各レベルのAIに対して、どの程度の勝率になるのかをチェックしておこう。

その上で、これを改良して、より強いAIを作っていくのが良い。

また、前節でモンテカルロ木探索に基づく着手の手法は紹介済みであるので、このコードをMyPlayerに移植するだけでも、それなりの強さのAIを作ることができる。

5.2.3. より強いAIを作るために#

今回の演習では、1回のテストプレイの制限時間が15秒であり、対戦相手の考慮時間を除くと、1手の考慮に掛けられる時間は多くとも0.4秒程度である。

その上、GitHub Actionsの実行環境では、それほど早いCPUを使うことはできないので、アルファベータ探索のような長い考慮時間であれば十分に強いと思われるAIでも、その性能を十分発揮できるとは限らない。

よって、ミニマックス系かモンテカルロ系のどちらについても、効率的により良い手を見つけるにはどうすれば良いかを考える必要があるだろう。

ミニマックス系#

ミニマックス系に関しては、まず、アルファベータ探索による枝刈りは必須だろう。単純なアルファベータ探索を実装するだけでも、ミニマックス探索と比較して(計算時間にもよるが)相当多くの手を読むことができる。

また、アルファベータ探索は、枝刈りにより処理を効率化する(つまり、それ以上評価を進めても、最大評価とならない盤面の探索をしない)手法であるため、最初の方の探索で高い評価値が得られる手順が見つかれば、相当数の盤面を調べなくて済む。この考えに基づけば、前節の実装で示したような、単に合法手を順々に調べていくようなやり方は必ずしも効率的ではない。

加えて、アルファベータ探索による枝刈りよりも、さらに効率的 (だが複雑)な枝刈りの手法としてNegaScout法がある。NegaScout法は、アルファベータ探索におけるアルファ値やベータ値が、およそ最善と考えられる場合には、その値が大きく変化することは少ない、という経験則に基づいた手法である。

最後に、より良い手を見つけるために、セルの評価値に基づく盤面の評価を改善することが考えられる。オセロには、相手が着手できなければパスになるというルールがあるため、なるべく相手の合法手の数が少なくなるように指す方が有利になると考えられる。また確定石と呼ばれる確実に自分の色の石になるマスが決まるため、確定石の数がより多くなるように指す方が当然有利だろう。

モンテカルロ系#

モンテカルロ系に関して、前節のモンテカルロ木探索に基づく手法には1つ大きく改善すべき点がある。

前節の実装では、新しい手を考える時に、その都度新しくUCTのノードを作り、その子ノードに対する評価していた。しかし、多くの場合、モンテカルロ木探索で着手した結果は、それほど悪い手ではなく、探索中には相手の手も考慮しているため、相手が探索中に考えた手を指してくる可能性が高い。その意味で、過去の探索結果を捨ててしまうような上記の実装は効率的とは言えない。

そこで、過去の探索において2手先の盤面に対応するノードを着手時にキャッシュしておき、次に手番が回ってきたときに、キャッシュしたノードの中に対応するノードが見つかれば、そこから探索を再開する、という方法が考えられる。これにより、仮に1回の着手時に行うプレイアウトの回数が100回などに制限されていたとしても、実際にはより多くの回数プレイアウトを行ったのと同等の評価結果を得ることができる。

また、オセロは60手で確実にゲームが終わるためプレイアウトの効率は比較的良いものの、終局までプレイアウトをしないと盤面の評価値を更新できないことはマイナスとも言える。そこでプレイアウトを終局まで行う代わりに、その局面がどのくらい勝ちやすい局面なのかを機械学習する方法が考えられる。一例として、十分に多くの試行回数により得られた盤面の評価値やその時点の最善手を学習データとして用意しておき、盤面の状態を入力、スカラの評価値や最善手を出力とするような機械学習モデルを作ることもできるだろう。

最後に、上記の盤面の勝ちやすさの判定に加えて、どの手に着手するかも機械学習によって決定する、ということもできる。これはAlphaZeroが使用している方法で、モンテカルロ木探索と深層学習器による盤面の評価、着手の決定を組み合わせてプレイアウトを繰り返し、より良い評価関数と着手方策を強化学習により手法である (ただしAlphaZero的な方法で強いAIを作るには、学習の工夫とともに大量の訓練時間が必要になる!)。