問題
前回はオセロの対戦AIを原始モンテカルロ法で作成しました。実際に対戦してみると「角は優先して取るべき」等といったオセロのノウハウを全く知らない乱択ベースとは思えないそれなりの強さでした。
試行回数が200回/手とはいえそれなりの強さだったのですから、試行回数を増やせばもっと強くなるはずです。
しかし単純に試行回数を400回/手、800回/手……等と増やしていくと問題が出てきます。
- 序盤や終盤は着手可能な場所が限られているものの、中盤になると数が膨大になります。試行回数をn回/手にしてるとAIの思考(試行)完了待ち時間が長くなってストレスフルです。
- 試行方法を「全体でN回試行する」「各手についてNを等分して試行する」ことにすれば中盤のストレスは減りますが、これは中盤の各手の試行回数を減らしている為、中盤の手筋は質が下がって弱くなります。
そもそも、 着手可能な手を平等に試行する必要はあるのでしょうか?
ある程度試行すれば各手の大雑把な勝率が得られますから、
勝率(大雑把)が悪そうな手について試行するよりも
勝率(大雑把)が良さそうな手について試行回数を重点的に割り振った方が効率が良いですよね。
しかし、これは少々の試行回数で割り出した勝率(大雑把)なので、
勝率(真)とはかけ離れている可能性はあります。
勝率(大雑把)が悪いからといって早々に切り捨ててしまうと、それが本当に良い手だった時に困ります。
つまり、
- 勝率の良さそうな手を重点的に試行する
- 実はもっと勝率の良さそうな手があるかも知れないので他の手も調べる
という2点を上手いことバランスを取って試行を行えば、
原始モンテカルロ法よりも少ない試行回数で効率良く精度の高い勝率を叩き出せそうですね。
でもこの2点、どう考えても矛盾してます。どうやって最適なバランスを取ればいいのでしょう?
考え方
ゲームの展開は盤面が節点で打てる手が枝である木構造だったことを思い出しましょう。
そして与えられた局面をRとして、Rから着手可能な手をm1, m2, …, mNとしましょう。
o R
___________|_____ ... _____
| | |
o m1 o m2 o mN
___|___ ___|___ ___|___
| | | | | | | | |
o o o o o o o o o
: : : : : : : : :先ずは未試行の各手について、その局面から先をランダムにシミュレートして勝敗を調べます。
この時の試行回数は1回/手とします。
後の計算の為に試行回数と勝利数を各節点に記録しておくことにします。
o R
___________|_____ ... _____
| | |
o m1 1/1 o m2 0/1 o mN 0/1
___|___ ___|___ ___|___
| | | | | | | | |
o o o o o o o o o
: : : : : : : : :次はm1, m2, …, mNの中から
- 勝率が良い手
- 切り捨てるにはまだ試行回数が不十分な手
のどれかを何らかの手法によって決めて、さらに試行回数を重ねることになります。
ここでは仮にm1が選ばれたとします。
今度はm1の子要素をランダムに選んで、その子要素からのゲームをランダムにシミュレートし、
その結果を子要素自身とm1に反映します。
o R
______________________|_____ ... _____
| | |
o m1 1/2 o m2 0/1 o mN 0/1
_________|________ ___|___ ___|___
| | | | | | | | |
o n1 1/1 | n2 o n3 o o o o o o
: : : : : : : : :以下、同様に
- 未試行の手があるならその手についてシミュレートを行う。
- 全ての手が試行済みなら、各手の勝率や試行回数から優先度を求めて、最も優先度が高い手の先の局面について調べる。
を行っていきます。
ある程度繰り返したところでAIの思考を切り上げて、
m1, m2, …, mNのうち 最も試行回数が多い手を採用 すれば良いですね
(勝率ではないことに注意。
例えば勝利数/試行回数が2/4の手と1999/4000の手なら、
勝率は前者の方が高くても確実性としては後者の方が高い)。
しかし問題は各手の優先度をどういう風に付けるかです。
これについてはWikipedia先生に便利そうな数式が載ってるので、これをありがたく使わせてもらいましょう。
具体的にはある局面におけるi番目の手の優先度を以下の式で求めます:
各項目の意味は以下の通りです:
- \( w_i \) は \( i \) 番目の手での勝利数
- \( n_i \) は \( i \) 番目の手での試行回数
- \( t \) は全ての手での試行回数
- \( c \) は「勝率が良い手」と「試行回数が不十分な手」のどちらを優先するかの度合いを決めるパラメーター
左項はi番目の手の勝率で、右項は試行回数の少ない方が大きくなる謎の値です。
後はこの考え方(=モンテカルロ木探索)を実装するだけです。
実装
上記のアルゴリズムによる探索結果は木構造です。
木構造と言っても、オセロのゲーム木とAIの探索過程を表す木は別物です。
後者の方は「探索木」と呼ぶことにしましょう。
まずはこの探索木の節点を表すデータ構造を作りましょう:
function Node(gameTree, parentNode, move) {
this.gameTree = gameTree;
this.parentNode = parentNode;
this.move = move;
this.childNodes = [];
this.wins = 0;
this.visits = 0;
this.untriedMoves = gameTree.moves.slice();
}ある節点から優先度を元に次の節点を選ぶロジックは以下の通りです(ちゃんと実装するなら優先度が同じ接点が複数ある場合はランダムに決めるべきですね):
Node.prototype.selectChild = function () {
var totalVisits = this.visits;
var values = this.childNodes.map(function (n) {
var c = Math.sqrt(2);
return n.wins / n.visits +
c * Math.sqrt(Math.log(totalVisits) / n.visits);
});
return this.childNodes[values.indexOf(Math.max.apply(null, values))];
};ある節点から未試行の手をランダムに選んで探索木を展開するロジックは以下の通りです:
Node.prototype.expandChild = function () {
var i = random(this.untriedMoves.length);
var move = this.untriedMoves.splice(i, 1)[0];
var child = new Node(force(move.gameTreePromise), this, move);
this.childNodes.push(child);
return child;
};ある節点の局面からランダムに手を打ってゲームをシミュレーションするのは以下のコードで簡単にできますね(シミュレーション結果は勝利=1、敗北=0、引き分け=0.5としてます):
Node.prototype.simulate = function (player) {
var gameTree = this.gameTree;
while (gameTree.moves.length !== 0) {
var i = random(gameTree.moves.length);
gameTree = force(gameTree.moves[i].gameTreePromise);
}
return judge(gameTree.board) * (player === BLACK ? 1 : -1) / 2 + 0.5;
};シミュレーション結果を探索木の親節点達に伝搬する処理も必要です:
Node.prototype.backpropagate = function (result) {
for (var node = this; node !== null; node = node.parentNode)
node.update(result);
};
Node.prototype.update = function (won) {
this.wins += won;
this.visits += 1;
};これで道具は揃いました。後はこれらを組み合わせた探索のアルゴリズムをコードにしましょう:
function tryMonteCarloTreeSearch(rootGameTree, maxTries) {
var root = new Node(rootGameTree, null, null);
for (var i = 0; i < maxTries; i++) {
var node = root;
while (node.untriedMoves.length === 0 && node.childNodes.length !== 0)
node = node.selectChild();
if (node.untriedMoves.length !== 0)
node = node.expandChild();
var won = node.simulate(rootGameTree.player);
node.backpropagate(won);
}
var vs = root.childNodes.map(function (n) {return n.visits;});
return root.childNodes[vs.indexOf(Math.max.apply(null, vs))].move;
}うーん。原始モンテカルロ法の時よりもデータ構造が増えて若干の面倒臭さが出てますが、
それでもα-β法の時よりは随分率直で分かり易いですね(α-β法は再帰の途中で評価基準がコロコロ変動するところがややこしい)。
動かしてみる
試行回数=2048回でAIの腕前を確認してみることにしましょう。
対戦相手は前回の原始モンテカルロ法AIにします。
前回の実装では試行回数がN回/手になっていましたが、
今回はモンテカルロ木探索AIに合わせて試行回数を各手に平等に割り振ることにします
(端数は最後の手に全部割り振ることにします)。
おー、圧勝感がありますね。
でも確率的なアルゴリズムなので偶々大勝利しただけの可能性もあります。
ちょっと早回しで対戦を繰り返してみましょう。
実行時間が掛かるので多数は試していませんが、
10回ちょっと試して8回くらい勝ってるなら、
同じ試行回数でもそれなりに腕前が向上したと言えるのではないでしょうか。
さらに改善するなら、完全にランダムな手を打ってシミュレーションするのではなく、
「角を優先する」等の評価でシミュレーションにバイアスを掛ける案がありそうです。
とはいえ、お手軽な実装でここまでできれば十分ではないでしょうか。
次回予告
モンテカルロ系AIを使うとオセロのノウハウ無しでもなかなかの強さのAIを作ることができると分かりました。
そうなるとオセロ以外のゲームでもAIを作ってみたくなりますね。
オセロよりも難しそうなゲームというとチェスや将棋や囲碁がすぐに思いつきますが、
どうせなら(自分でも)ノウハウが分かってない難しいゲームをAIにやらせてみる方が面白そうです。
そういえば以前JavaScriptでシェフィを実装しましたね……
と言う訳で次回は「JavaScriptでシェフィを実装する(AIで解くぞ編)」です。
＃人気の記事
＃タグ
