ゲーム木探索入門 part05 交互手番MCTSの実装【PokéAI】
前回は原始モンテカルロ法というもっとも単純な探索手法を試しました。原始モンテカルロ法では、ルート局面(行動を決定したい局面)でとれる行動それぞれについて、その行動をとった直後の局面からランダムにゲームを進めた際の勝率を比較して行動を決定します。この手法でもただランダムに行動を決定するよりはましですが、最初の行動以外すべてランダムであるため、大量の悪手を含んだゲーム進行の結果得られる勝率を元に行動を決定するため貧弱な手法といえます。勝率の推定を改善する手法として、モンテカルロ木探索(MCTS)があります。MCTSはもともと囲碁AIのために開発された手法です。囲碁とポケモンバトルの主な違いは、自分と相手が交互に行動を選択する、伏せられている情報がない、ランダム性がないという点です。よりポケモンバトルに近い性質のゲームへの応用も研究されており今後試しますが、今回は囲碁向けのMCTSアルゴリズムをできるだけ少ない変更でポケモンバトルに応用します。
アルゴリズム
MCTSの基本的な説明は囲碁関係の文献を参照してください(本にするときはポケモンバトルに即してちゃんと書きます…)。書籍だと囲碁ディープラーニングプログラミングがわかりやすいです。AlphaGoの文脈でMCTSが解説されることも多いですが、今回の実装に深層学習の要素はないので注意してください。 原始モンテカルロ法に引き続き、本来のポケモンバトルにはない仮定として、相手のパーティ構成がわかっている、ランダム性がないという条件でMCTSを実装します。 これらの仮定を置くことで囲碁にゲームの性質を近づけることができますが、囲碁では交互に行動を選択する一方で、ポケモンバトルでは同時に行動を選択するという違いについては何らかの対処をしないとMCTSを実装することができません。 この課題に対しては、自分が行動を選択し、次に相手が行動を選択するという近似を行います。シミュレータの状態と自分が選んだ行動の組み合わせを状態とみなし、この状態を入力として相手は行動を選ぶと考えます。
MCTS実装のコア部分を示します。完全なコードはこちら。 ポイントは、ノードが持つ状態としてシミュレータの状態のほかに、相手が選んだ行動を含ませる点です。相手が選んだ行動が入っているノードの子ノードは、相手と自分の行動の組み合わせでシミュレータを1ターン進めた状態を保持することになります。
// シミュレータの状態simに対し、プレイヤーsideidの行動を決定する go(sim: Sim, sideid: SideID): string | null { const root = new MCTSNode(new PRNG(), sim, sideid, undefined); const playoutPolicy = new AIRandom2({ switchRatio: this.playoutSwitchRatio }); // ルート局面から木構造をたどってプレイアウトを繰り返す for (let i = 0; i < this.playoutCount; i++) { let backupNodes: MCTSNode[] = []; let node = root; backupNodes.push(node); while ((!node.canAddChild()) && (!node.isTerminal)) { node = this.selectChild(node); backupNodes.push(node); } if (node.canAddChild()) { node = node.addRandomChild(); backupNodes.push(node); } let winner: SideID; if (node.isTerminal) { winner = node.winnerIfTerminal!; } else { // プレイアウトする const copySim = node.gameState.clone(); if (node.opponentMove !== undefined) { // 片側の行動だけ決まっている状態なので、もう片方を埋めて1ターン進める const leafChoice = playoutPolicy.go(copySim, node.sideid); const bothChoice = node.sideid === 'p1' ? [leafChoice, node.opponentMove] : [node.opponentMove, leafChoice]; copySim.choose(bothChoice); } let { winner: playoutWinner } = playout(copySim, [playoutPolicy, playoutPolicy]); winner = playoutWinner || sideid;// 引き分けは珍しいので、とりあえずsideid側の勝ち扱い } for(let i = backupNodes.length-1; i >= 0; i--) { backupNodes[i].recordWin(winner); } } // ルート局面の子ノードで勝率最大のノードを選択 let bestMove: string | null = null; let bestPct: number = -1.0; for (const [move, node] of root.children.entries()) { const pct = node.winningPct(sideid); if (pct > bestPct) { bestPct = pct; bestMove = move; } } return bestMove; } // MCTSのノードを表現するオブジェクト class MCTSNode { winCounts: {[sideid in SideID]: number}; numRollouts: number; children: Map<string|null, MCTSNode>; unvisitedMoves: (string|null)[]; isTerminal: boolean; winnerIfTerminal?: SideID; constructor(public prng: any, public gameState: Sim, // シミュレータの状態 public sideid: SideID, // このノードの手番プレイヤー // このシミュレータの状態に対し、すでに相手が行動を決定している場合その行動 public opponentMove?: string | null ) { this.winCounts = {'p1': 0, 'p2': 0}; this.numRollouts = 0; this.children = new Map(); const isTerminal = this.gameState.getEnded(); this.isTerminal = isTerminal; if (isTerminal) { this.winnerIfTerminal = this.gameState.getWinner(); this.unvisitedMoves = []; } else { this.winnerIfTerminal = undefined; const choices = enumChoices(gameState.getRequest(sideid)); if (choices.length > 0) { this.unvisitedMoves = choices.map((c) => c.key); } else { this.unvisitedMoves = [null]; // パスの1手だけを選択肢とみなす } } } // まだ子ノードを生成していない選択肢から1つランダムに選んで子ノードを作成 addRandomChild(): MCTSNode { const unvisitedLength = this.unvisitedMoves.length; const index = unvisitedLength === 1 ? 0 : this.prng.next(unvisitedLength); const move = this.unvisitedMoves[index]; this.unvisitedMoves.splice(index, 1); // moveを適用した後の状態を生成 // シミュレータは決定論的に動作するという仮定 let newNode: MCTSNode; const opponentSideId = invSideID(this.sideid); if (this.opponentMove !== undefined) { // 自分と相手の行動が揃ったので1ターン進める const copySim = this.gameState.clone(); const bothChoice = this.sideid === 'p1' ? [move, this.opponentMove] : [this.opponentMove, move]; copySim.choose(bothChoice); // シミュレータに行動を与えて進める newNode = new MCTSNode(this.prng, copySim, opponentSideId, undefined); // undefinedが相手の行動未定を表す } else { // シミュレータはまだ動かせない。相手の行動を決めるフェーズに進む newNode = new MCTSNode(this.prng, this.gameState, opponentSideId, move); } this.children.set(move, newNode); return newNode; } }
今回のアルゴリズムにおける、自分が行動を選択し、次に相手が行動を選択するという近似には問題点があります。じゃんけんのようなゲームを考えるとわかりますが、相手の行動が決まっている状態のノードで自分の行動を決めると、相手の手に応じて都合のいい行動を選ぶ結果になり、行動を同時に選ぶ場合と比べ非対称な先手と後手が生じます。この問題を考慮したアルゴリズムを今後利用する予定です。
実験
MCTSと原始モンテカルロ法の強さを比較する実験を行います。
使用するパーティ等の条件は原始モンテカルロ法の時と同じです。
まずは、ランダム、原始モンテカルロ法とともに、MCTSのプレイアウト回数を変えて強さを比較しました。ランダムプレイアウト中に交代を選ぶ確率は10%です。MCTSの探索において未知の行動を探索するか既知の勝率の高い行動をより深く探索するかのバランスを決める温度パラメータは1.0としました。温度パラメータについては0.5, 1.0, 2.0で別途比較し、大きな差はありませんが1.0が最も強いという結果でした。比較結果を示します。
手法 | プレイアウト回数 | 平均レート |
---|---|---|
ランダム | - | 1396 |
原始モンテカルロ法 | 100 | 1506 |
MCTS | 30 | 1474 |
MCTS | 100 | 1509 |
MCTS | 300 | 1537 |
MCTS | 1000 | 1579 |
計算時間はプレイアウト回数に比例します。また、原始モンテカルロ法とMCTSで、プレイアウト回数が同じならほぼ同じ計算時間となります。MCTSにおいてプレイアウト回数を増やせば増やすほど強くなること、また同じプレイアウト回数では原始モンテカルロ法と同等以上の強さになることがわかりました。
次に、プレイアウト回数1000回での原始モンテカルロ法とMCTSの比較を行いました。
手法 | プレイアウト回数 | 平均レート |
---|---|---|
ランダム | - | 1424 |
原始モンテカルロ法 | 1000 | 1530 |
MCTS | 1000 | 1546 |
やはりMCTSのほうが若干高いレートとなっています。
さらにプレイアウト回数を増加させたときに強くなるかどうか、MCTSのみで比較を行いました。
手法 | プレイアウト回数 | 平均レート |
---|---|---|
MCTS | 1000 | 1481 |
MCTS | 3000 | 1519 |
プレイアウト回数3000回は、1000回の場合より強くなることがわかりました。計算に30時間を要したため、これ以上の回数を試すのは困難です。
今回は、ポケモンバトルを交互手番のゲームに近似してMCTSを実装しました。原始モンテカルロ法と比べ、同じプレイアウト回数(計算時間)でより強い可能性が高いことがわかりました。 木構造を探索する思考過程を可視化できないか検討しています。