mcts
1.0.0
このチュートリアルでは、モンテカルロ木探索アルゴリズムとコードの各部分について説明します。最近、ゲームの開発に MCTS を適用しました。
コードは一般的なものであり、基本的な Python に精通していることのみを前提としています。私たちのゲームに関して説明しました。これをプロジェクトやゲームに使用したい場合は、以下で説明する機能を少し変更する必要があります。
ゲームへのプレイストア リンクは次のとおりです: Sudo Tic Tac Toe。
ゲーム (モード 1) のルールは次のとおりです。
ご覧のとおり、このゲームには非常に高い分岐要素があります。最初の動きでは、ボード全体が空になります。つまり81個の空きがあります。最初のターンには 81 の可能な動きがあります。ルール 4 を適用することによる 2 番目のターンには、8 または 9 つの可能な動きがあります。
最初の 2 つの動きでは、81*9 = 729 通りの組み合わせが考えられます。したがって、ゲームが進むにつれて可能な組み合わせの数が増加し、その結果分岐要素が高くなります。私たちのゲームのどちらのモードでも、分岐係数は非常に高くなります。このような高い分岐係数を持つゲームの場合、ミニマックス アルゴリズムを適用することはできません。 MCTS アルゴリズムはこの種のゲームで機能します。
また、ゲームをプレイしていただければわかると思いますが、AI が行動を起こすまでにかかる時間はわずか 1 秒ほどです。したがって、MCTS は高速に実行されます。 MCTS はゲームの両方のモードに適用されています。
以下では、Python での MCTS コードを示します。まず、numpy とdefaultdict をインポートする必要があります。
import numpy as np
from collections import defaultdict以下に示すように MCTS クラスを定義します。
class MonteCarloTreeSearchNode ():
def __init__ ( self , state , parent = None , parent_action = None ):
self . state = state
self . parent = parent
self . parent_action = parent_action
self . children = []
self . _number_of_visits = 0
self . _results = defaultdict ( int )
self . _results [ 1 ] = 0
self . _results [ - 1 ] = 0
self . _untried_actions = None
self . _untried_actions = self . untried_actions ()
returnクラスは以下のメンバー関数で構成されます。 main() 関数を除く以下の関数はすべてメンバー関数です。
def untried_actions ( self ):
self . _untried_actions = self . state . get_legal_actions ()
return self . _untried_actions指定された状態からの未試行のアクションのリストを返します。ゲームの最初のターンでは、81 の可能なアクションがあります。 2 番目のターンでは、8 または 9 になります。これはゲームによって異なります。
def q ( self ):
wins = self . _results [ 1 ]
loses = self . _results [ - 1 ]
return wins - loses勝敗の差を返します
def n ( self ):
return self . _number_of_visits各ノードが訪問された回数を返します。
def expand ( self ):
action = self . _untried_actions . pop ()
next_state = self . state . move ( action )
child_node = MonteCarloTreeSearchNode (
next_state , parent = self , parent_action = action )
self . children . append ( child_node )
return child_node 現在の状態から、実行されたアクションに応じて次の状態が生成されます。このステップでは、すべての可能な状態が Children 配列に追加され、child_node が返されます。現在の状態から考えられる状態はすべてchildren配列に追加され、この状態に対応するchild_nodeが返されます。
def is_terminal_node ( self ):
return self . state . is_game_over ()これは、現在のノードがターミナルかどうかを確認するために使用されます。ゲームが終了するとターミナルノードに到達します。
def rollout ( self ):
current_rollout_state = self . state
while not current_rollout_state . is_game_over ():
possible_moves = current_rollout_state . get_legal_actions ()
action = self . rollout_policy ( possible_moves )
current_rollout_state = current_rollout_state . move ( action )
return current_rollout_state . game_result ()現在の状態から、ゲームの結果が出るまでゲーム全体がシミュレーションされます。このゲーム結果が返されます。たとえば、勝ちになった場合、結果は 1 になります。それ以外の場合、負けた場合、結果は -1 になります。そして引き分けの場合は0です。ゲーム全体がランダムにシミュレートされる場合、つまり各ターンで可能な動きのセットから動きがランダムに選択される場合、それはライト プレイアウトと呼ばれます。
def backpropagate ( self , result ):
self . _number_of_visits += 1.
self . _results [ result ] += 1.
if self . parent :
self . parent . backpropagate ( result )このステップでは、ノードのすべての統計が更新されます。親ノードに到達するまで、各ノードの訪問数は 1 ずつ増加します。結果が 1 の場合、つまり勝ちになった場合、勝ちは 1 増加します。それ以外の場合、結果が負けの場合は損失になります。 1ずつ増加します。
def is_fully_expanded ( self ):
return len ( self . _untried_actions ) == 0すべてのアクションは _untried_actions から 1 つずつポップされます。空になると、つまりサイズがゼロになると、完全に拡張されます。
def best_child ( self , c_param = 0.1 ):
choices_weights = [( c . q () / c . n ()) + c_param * np . sqrt (( 2 * np . log ( self . n ()) / c . n ())) for c in self . children ]
return self . children [ np . argmax ( choices_weights )]完全に展開されると、この関数は子の配列から最適な子を選択します。式の最初の項は活用に対応し、2 番目の項は探索に対応します。
def rollout_policy ( self , possible_moves ):
return possible_moves [ np . random . randint ( len ( possible_moves ))]可能な技の中からランダムに技を選択します。これはランダム再生の例です。
def _tree_policy ( self ):
current_node = self
while not current_node . is_terminal_node ():
if not current_node . is_fully_expanded ():
return current_node . expand ()
else :
current_node = current_node . best_child ()
return current_nodeロールアウトを実行するノードを選択します。
def best_action ( self ):
simulation_no = 100
for i in range ( simulation_no ):
v = self . _tree_policy ()
reward = v . rollout ()
v . backpropagate ( reward )
return self . best_child ( c_param = 0. )これは、可能な限り最良の動きに対応するノードを返す最良のアクション関数です。展開、シミュレーション、バックプロパゲーションのステップは、上記のコードによって実行されます。
def get_legal_actions ( self ):
'''
Modify according to your game or
needs. Constructs a list of all
possible states from current state.
Returns a list.
''' def is_game_over ( self ):
'''
Modify according to your game or
needs. It is the game over condition
and depends on your game. Returns
true or false
''' def game_result ( self ):
'''
Modify according to your game or
needs. Returns 1 or 0 or -1 depending
on your state corresponding to win,
tie or a loss.
''' def move ( self , action ):
'''
Modify according to your game or
needs. Changes the state of your
board with a new value. For a normal
Tic Tac Toe game, it can be a 3 by 3
array with all the elements of array
being 0 initially. 0 means the board
position is empty. If you place x in
row 2 column 3, then it would be some
thing like board[2][3] = 1, where 1
represents that x is placed. Returns
the new state after making a move.
''' def main ():
root = MonteCarloTreeSearchNode ( state , None , action )
selected_node = root . best_action ()
return これが main() 関数です。ルート ノードを初期化し、best_action 関数を呼び出して最適なノードを取得します。これはクラスのメンバー関数ではありません。他のすべての関数は、クラスのメンバー関数です。
MCTS は 4 つのステップで構成されます。
アイデアは、ツリーの葉ノードに到達するまで、最適な子ノードを選択し続けることです。このような子ノードを選択する良い方法は、UCT (ツリーに適用される上限信頼限界) 式を使用することです。
wi/ni + c*sqrt(t)/ni
wi = i 番目の移動後の勝利数
ni = i 番目の移動後のシミュレーションの数
c = 探査パラメータ (理論的には √2 に等しい)
t = 親ノードのシミュレーションの合計数
UCT を適用して後継ノードを見つけることができなくなった場合、リーフ ノードから考えられるすべての状態を追加してゲーム ツリーを拡張します。
拡張後、アルゴリズムは子ノードを任意に選択し、選択されたノードからゲームの結果の状態に到達するまでゲーム全体をシミュレートします。プレイアウト中にノードがランダムに選択される場合、それはライト プレイアウトと呼ばれます。高品質のヒューリスティックまたは評価関数を作成することで、重いプレイアウトを選択することもできます。
アルゴリズムがゲームの終了に達すると、状態を評価してどのプレイヤーが勝ったかを判断します。これはルートまで上向きに移動し、訪問されたすべてのノードの訪問スコアを増加させます。また、そのポジションのプレーヤーがプレイアウトに勝った場合、各ノードの勝利スコアも更新します。
独自のゲームを作成する予定がある場合は、次の質問について考える必要があります。
須藤三目並べ
ご質問やご提案がございましたら、お気軽に [email protected] までご連絡ください。
