これまでのあらすじ
まともなオセロの対戦AIの作成を開始したものの、
「4手先を読む」だけでも検討にかかる時間が長く、
とても快適に遊べるとは言えない状態でした。
これでは肝心のAIの形勢判断を調整する以前の問題であり、
先読みする手数を増やしてAIの「腕前」を上げることも困難です。
先読みする手数を減らせば快適に遊べるようにはなりますが、
それでは「目先のことしか考えない」弱いAIにしかなりません。
どうにかしてAIの動作速度を改善できないものでしょうか。
ボトルネックはどこにあるのか
これまでのオセロの作成過程を振り返ってみましょう。
最初に4×4の最小盤面で一人二役で遊ぶものを実装しました。
これはほとんどの部分が関数型で書かれた明瞭簡潔な実装だったのですが、
その引き換えに全局面を事前に計算するという超富豪的な実装になっていました。
この問題に対しては各局面の計算を遅延評価することで性能を改善しました。
遅延評価を導入したのは
4×4の最小盤面ですら既に取り得る局面の数が多い
からです。
ということは当然
8×8の通常盤面では桁違いに多数の局面が存在する
はずで、
たかが4手先と思っても
4手先ですら存在する局面の数が多過ぎる
と言うことです。
そして、AIは
先読みした全ての局面を評価
してから次に指すべき手を判断しています。
実際、ゲーム中盤の適当な局面から4手先に存在する局面は大抵1〜2万通り存在します。
遅延評価によってゲーム中に到達し得ない局面の計算は省略できましたが、
今回の問題は次の手を選ぶために評価すべき局面が多数あることなので、
遅延評価は救いになりません。
そうすると、取り得る手法は
いかにして評価すべき局面の数を減らすか
の一点に絞られます。
しかし、そうは言っても結局のところN手先までの全ての手を再帰的に評価しなければ次に指すべき手を決められないのでは……?
手の価値の計算を考え直す
例えば現在の局面で自分の指せる手が3通りあり、
さらに各手を指した後に相手の指せる手が3通りづつあるというシチュエーションを考えてみましょう:
me ( )
___________|___________
| | |
opponent ( ) ( ) ( )
___|___ ___|___ ___|___
| | | | | | | | |
me ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )ここから最善手を選ぶためには、まず現在の局面で指せる手の価値を求める必要があります。
左から右に手の価値を順次求めて行くとして、
一番左の手の価値が求まったとしましょう:
me ( )
___________|___________
| | |
opponent (3) ( ) ( )
___|___ ___|___ ___|___
| | | | | | | | |
me (5) (7) (3) ( ) ( ) ( ) ( ) ( ) ( )この段階で先程調べた一番目の手の価値から
現在の局面で指せる最善手の価値は少なくとも3以上である
ということが分かります。
何故なら自分の手番では最大の価値の手を最善手とするからです。
me ( ) >= 3
___________|___________
| | |
opponent (3) ( ) ( )
___|___ ___|___ ___|___
| | | | | | | | |
me (5) (7) (3) ( ) ( ) ( ) ( ) ( ) ( )次に二番目の手の価値を求めることを考えましょう。
二番目の手の価値を求めるにはその先の各手(下図のA/B/C)の価値を調べる必要があります。
me ( ) >= 3
___________|___________
| | |
opponent (3) ( ) ( )
___|___ ___|___ ___|___
| | | | | | | | |
me (5) (7) (3) ( ) ( ) ( ) ( ) ( ) ( )
: : :
A B CまずAの価値を調べてみて、その価値が1であると分かったとしましょう。
相手の手番では最小の価値の手を(相手にとっての)最善手とします。
つまり、この時点で
二番目の手の価値は最大でも1以下である
ことが確定しました。
BとCの価値が何であれこの事実は揺るぎません。
me ( ) >= 3
___________|___________
| | |
opponent (3) ( ) <= 1 ( )
___|___ ___|___ ___|___
| | | | | | | | |
me (5) (7) (3) (1) ( ) ( ) ( ) ( ) ( )
: : :
A B Cそして、既に
「現在の局面で指せる最善手の価値は少なくとも3以上である」
ことが分かっている以上、
「価値が最大でも1以下である二番目の手」
は最善手ではあり得ません。
ということは
二番目の手を指すことは無いと確定した 以上、
二番目の手について正確な価値を求める必要はない
ということが言えます。
なのでAの価値をそのまま二番目の手の価値ということにしても支障はありません。
me ( ) >= 3
___________|___________
| | |
opponent (3) (1) <= 1 ( )
___|___ ___|___ ___|___
| | | | | | | | |
me (5) (7) (3) (1) ( ) ( ) ( ) ( ) ( )
: : :
A B Cつまり、
これまでの調査結果から評価を省略できる局面が分かる
のです。
この場合はBとCの評価を省略できることが分かりました。
これまでの図では省略していましたが、
実際にはBやCの先に数多の局面が存在しているので、
それらも含めてまるごと局面の評価を省略できます。
me ( ) >= 3
___________|___________
| | |
opponent (3) (1) <= 1 ( )
___|___ ___|___ ___|___
| | | | X X | | |
me (5) (7) (3) (1) ( ) ( ) ( ) ( ) ( )
_______| |_______
| | | | | |
( ) ( ) ( ) ( ) ( ) ( )
: : : : : :後はこの理屈
(= α-β法)
をコードに落とし込めばAIの高速化が期待出来るのではないでしょうか。
実装
ミニマックス法の復習
前回のAIの実装では
- 「ある局面から指せる手の価値を列挙する」関数
calculateRatings - 「ある局面の価値を求める」関数
ratePosition
を分割して実装しました:
function calculateRatings(gameTree, player) {
return gameTree.moves.map(function (m) {
return ratePosition(force(m.gameTreePromise), player);
});
}
function ratePosition(gameTree, player) {
if (1 <= gameTree.moves.length) {
var choose = gameTree.player == player ? Math.max : Math.min;
return choose.apply(null, calculateRatings(gameTree, player));
} else {
return scoreBoard(gameTree.board, player);
}
}これをα-β法の形に変形していきましょう。
手の価値の列挙(枝狩り込み)
まず calculateRatings ですが、
誰の手番で指す手について考えているのかで判断基準が変わってややこしいので、
- 「自分の手番で指す手の価値を列挙する」関数
calculateMaxRatings - 「相手の手番で指す手の価値を列挙する」関数
calculateMinRatings
の2つに分けて実装することにします。
calculateMaxRatings では自分の手番で指す手の価値を考えます。
基本的には calculateRatings と同様で次の手の価値を順次求めていくのですが、
以下の点が異なります:
- ここでは最大の価値を持つ手を調べるので、
次の手の価値が順次求まるにつれて、
次の次の手の価値を読む際に興味のある価値の下限が上がっていきます。 - ある手の価値が上限以上だと判明した場合、
現在の局面から辿れる範囲に上層が求める最善手の候補は存在しないため、
残りの手の価値を求めても意味がないので手の価値の列挙を中断します。
これらを踏まえると以下のように定義できます:
function calculateMaxRatings(gameTree, player, lowerLimit, upperLimit) {
var ratings = [];
var newLowerLimit = lowerLimit;
for (var i = 0; i < gameTree.moves.length; i++) {
var r = ratePositionWithAlphaBetaPruning(
force(gameTree.moves[i].gameTreePromise),
player,
newLowerLimit,
upperLimit
);
ratings.push(r);
if (upperLimit <= r)
break;
newLowerLimit = Math.max(r, newLowerLimit);
}
return ratings;
}同様に calculateMinRatings について定義しましょう。
これは反対に相手の手番で指す手の価値について考えるので、
- ここでは最小の価値を持つ手を調べるので、
次の手の価値が順次求まるにつれて、
次の次の手の価値を読む際に興味のある価値の上限が下がっていきます。 - ある手の価値が下限以下だと判明した場合、
現在の局面から辿れる範囲に上層が求める最善手の候補は存在しないため、
残りの手の価値を求めても意味がないので手の価値の列挙を中断します。
となります。これらを踏まえると以下のように定義できます:
function calculateMinRatings(gameTree, player, lowerLimit, upperLimit) {
var ratings = [];
var newUpperLimit = upperLimit;
for (var i = 0; i < gameTree.moves.length; i++) {
var r = ratePositionWithAlphaBetaPruning(
force(gameTree.moves[i].gameTreePromise),
player,
upperLimit,
newUpperLimit
);
ratings.push(r);
if (r <= lowerLimit)
break;
newUpperLimit = Math.min(r, newUpperLimit);
}
return ratings;
}局面の価値の算出
次に ratePosition をα-β法に対応したratePositionWithAlphaBetaPruning
について考えましょう。
と言っても、
ややこしいところは全部calculateMaxRatings とcalculateMinRatings に押し込見ましたから、
ここでは手番のプレイヤーに応じて
「最大値を求める」のか
「最小値を求める」のかを適宜切り換えるだけです。
function ratePositionWithAlphaBetaPruning(gameTree, player, lowerLimit, upperLimit) {
if (1 <= gameTree.moves.length) {
var judge =
gameTree.player == player
? Math.max
: Math.min;
var rate =
gameTree.player == player
? calculateMaxRatings
: calculateMinRatings;
return judge.apply(null, rate(gameTree, player, lowerLimit, upperLimit));
} else {
return scoreBoard(gameTree.board, player);
}
}最終的な手の選択
前回実装した「最も良い手を選ぶ」関数 findTheBestMoveByAI
の定義は以下の通りでした:
var AI_LEVEL = 4;
function findTheBestMoveByAI(gameTree) {
var ratings = calculateRatings(
limitGameTreeDepth(gameTree, AI_LEVEL),
gameTree.player
);
var maxRating = Math.max.apply(null, ratings);
return gameTree.moves[ratings.indexOf(maxRating)];
}α-β法バージョンへの対応は ratings の算出部分だけを切り換えれば済みます。
calculateMaxRatings と calculateMinRatings を定義する時はlowerLimit と upperLimit が予め与えられているものとして考えていましたが、
最初は下限も上限も不明な状態から価値の算出を始めるので、
下限と上限の初期値はそれぞれ-∞と∞となります。
実際には-∞や∞を直接扱うことはできませんから、
取り扱うことができる最小の数値と最大の数値を代替として使いましょう。
function findTheBestMoveByAI(gameTree, playerType) {
var ratings = calculateMaxRatings(
limitGameTreeDepth(gameTree, AI_LEVEL),
gameTree.player,
Number.MIN_VALUE,
Number.MAX_VALUE
);
var maxRating = Math.max.apply(null, ratings);
return gameTree.moves[ratings.indexOf(maxRating)];
}遊んでみる
それでは遊んでみましょう!
うむ。明らかに高速化後の方がサクサク動いてます。
こいつは良いですね。
これでようやくまともにゲームができる状態になったのではないでしょうか。
やりましたね。
次回予告
まともにゲームができるところまで作り上げることができたので、
今までおざなりにしてた「AIの強さ」にそろそろ手を入れたいところです。
しかし、これには色々と問題があります:
- 「AIの強さ」を定量化できないと
「ぼくのかんがえたさいきょうのAI」がどれぐらい強いのかさっぱり分からない。 - かといって人間が判定するにしても
「これは雑魚だなー」
「これは手強かったかも」
程度の大雑把な分類しかできない。 - そもそもこれまでにテストプレイとして何十回もオセロをやってきたので、
もう手動で手を打つのは面倒臭い。
となると、
AIの実装を複数用意して総当たり戦を行う
のが妥当なところではないでしょうか。
と言う訳で次回は「AI vs AI編」です。
＃人気の記事
＃タグ
