- アブストラクトゲームとコンピューター
- アブストラクトゲームとコンピューター2
- アブストラクトゲームとコンピューター3
- nimをプレーするコンピューター・プログラム
- Abstract Strategy Games Online Project
ゲームの探索空間 †
現在、アブストラクトゲームをプレーするコンピューターの取る戦略は、 評価関数によって、ひとつひとつの局面を静的に判断し着手を決定します。 その局面に至る経緯は考慮しません。
また、合法着手について先読みをおこないます。当然、先読みの深さ(何手先まで読めるか)によって強さが異なってきます。ゲームが複雑になればなるほど、同じコンピューターのリソース(=メモリやCPU時間)を使って、先読みできる深さも少なくなります。 以下は、代表的なアブストラクトゲームでのゲーム探索空間です。*1
| 三目並べ | 10&super{3};未満 |
| チェッカー | 10&super{30}; |
| オセロ | 10&super{60}; |
| チェス | 10&super{120}; |
| 将棋 | 10&super{220}; |
| 囲碁 | 10&super{360}; |
表:メジャーなゲームの探索空間
最適の手を求めて1 ゲーム木 †
二人完全情報0和ゲームでは、各手番で選択した手によって出現する局面を場合分けして、樹形図を作ることができます。現在の局面から出現するすべての局面の関係をゲーム木と呼びます。ゲーム木を用いて、最善(と思える)手を選択するアルゴリズム、 Mini-Max, α-β, Nega-Max, Nega-Alphaについて、プログラム事例を中心に紹介します。
ここで紹介するプログラム例は、いずれも、深さ優先の探索をするシンプルな実装です。*2 一般的なアルゴリズムの教科書にある実装方式に加えて、指定の深度になると、読みを打ちきる判断と、局面が静かになるまで探索を延長するための仕組み、また対象の経路での探索深度を返す工夫がしてあります。
Mini-Max法 †
二人完全情報0和ゲームで、最適の手を探索する基本的なアルゴリズムは、Mini-Max法です。 Mini-Maxでは、探索対象範囲内の起こりうる局面をすべて抽出し、ゲーム木を作り、 ゲーム木の端(node)の評価値を、先手後手、それぞれが自分にとって最良の選択をしたとして、現在局面から次の手の評価をします。
図1は、nimの一種で分割nimと呼ばれる種類のゲームを使った、ゲーム木の例です。手番のプレーヤーは、棒を1または2本取り、最後の1本の棒をとったプレーヤーが勝ちというルールです。ゲーム木は、すべてのプレーヤーの選択肢と局面の繊維を樹形図として書き表しています。
図2は、図1に先手が勝つ末端のノードに1、後手が勝つ末端のノードに-1を値として割り振り、前の手番での価値を計算して作ったゲーム木です。このゲームは、単純なゲームなので、すべての場合を探索しつくすことが容易で、勝ちと負けで二元的にすべてのノードを評価できました。
一般のMini-Max法では、ゲームが複雑な場合は、勝ちに+∞を、負けに-∞を与え、引き分けノードに0として計算します。ゲーム木は、ゲーム開始時からに限らず、任意の局面からの木を作ることができますので、手番のプレーヤーをMax、相手プレーヤーをMiniと呼んで各ノードを評価します。
決着がつかない状況での途中の局面での評価は、評価関数を作成して、手番(Maxノード)のプレーヤーにとって有利な場合に正の値を、相手(Minノード)プレーヤーが有利な場合に負の値を割り振ることで、評価値が最も高い手を選択します。
Mini-Max法は、このようにゲーム木を作成して、価値の高い手を選択するアルゴリズムです。
Abstract Strategy Games Online Projectでの実装例
def minimax(mu,depth) # min-max処理汎用method
if depth >= @max_depth
unless extendable?(mu,depth)
val = value(mu,depth)
val = -val unless label(mu)
return val, depth
end
end
childs = children(mu,depth)
if childs == []
val = value(mu,depth)
val = -val unless label(mu)
return val, depth
end
mdepth = depth
unless label(mu) # minノード
e = Max2
childs.each {|u|
m, d = minimax(u,depth+1)
log_detail(mu,depth+1,m)
if m < e
e = m
mdepth = d
end
}
return e, mdepth
else # maxノード
e = Min2
childs.each {|u|
m, d = minimax(u,depth+1)
log_detail(mu,depth+1,m)
if m > e
e = m
mdepth = d
end
}
return e, mdepth
end
end
α-β法 †
Mini-Maxでは、木構造のすべてのnodeを評価しなければなりません。 α-βでは、明らかに選択されない手については、nodeと枝の評価をしない工夫がされています。
図を見ながら、下記のプログラムの動作を確認してみてください。(図は、クリックすると拡大します。)
Abstract Strategy Games Online Projectでの実装例
def alphabeta(mu,alpha,beta,depth) # αβ処理汎用method
if depth >= @max_depth
unless extendable?(mu,depth)
val = value(mu,depth)
val = -val unless label(mu)
return val, depth
end
end
childs = children(mu,depth)
if childs == []
val = value(mu,depth)
val = -val unless label(mu)
return val, depth
end
mdepth = depth
unless label(mu) # minノード
childs.each {|u|
e, d = alphabeta(u,alpha,beta,depth+1)
log_detail(mu,depth+1,e)
if e < beta
beta = e
mdepth = d
end
return beta, mdepth if beta <= alpha
}
return beta, mdepth
else # maxノード
childs.each {|u|
e, d = alphabeta(u,alpha,beta,depth+1)
log_detail(mu,depth+1,e)
if alpha < e
alpha = e
mdepth = d
end
return alpha, mdepth if beta <= alpha
}
return alpha, mdepth
end
end
KnuthとMooreの改善 †
Nega-MaxとNega-Alphaの基本的なアルゴリズム構造は、Mini-Max, α-βと同じです。 局面の評価基準を手番プレーヤーにすることで、プログラム構造をシンプルにしています。どのようにシンプルになったかは、前述のソースと比較してみてください。
ここで用いている局面評価関数(AI#value)は、Nega-* で使うことを基準としているため、 下記methodes内のvalue呼び出しで、符号反転はおこなっていません。逆に、前述の方式内での、value呼び出しの値をminiノードのときに符号反転する処理をしています。これは、一般の解説書などと異なる実装です。
Nega-Max †
Abstract Strategy Games Online Projectでの実装例
def negamax(mu,depth) # min-max処理汎用method
if depth >= @max_depth
unless extendable?(mu,depth)
val = value(mu,depth)
return val, depth
end
end
childs = children(mu,depth)
if childs == []
val = value(mu,depth)
return val, depth
end
mdepth = depth
e = Min2
childs.each {|u|
m, d = negamax(u,depth+1)
m = -m
log_detail(mu,depth+1, m)
if m > e
e = m
mdepth = d
end
}
return e, mdepth
end
Nega-Alpha †
Abstract Strategy Games Online Projectでの実装例
def negaalpha(mu,alpha,beta,depth) # αβ処理汎用method
if depth >= @max_depth
unless extendable?(mu,depth)
val = value(mu,depth)
return val, depth
end
end
childs = children(mu,depth)
if childs == []
val = value(mu,depth)
return val, depth
end
mdepth = depth
childs.each {|u|
e, d = negaalpha(u, -beta, -alpha, depth+1)
e = -e
log_detail(mu,depth+1,e)
if e > alpha
alpha = e
mdepth = d
end
return alpha, mdepth if beta <= alpha
}
return alpha, mdepth
end
最適の手を求めて2 †
手の探索をする上で、コンピューターがおこなわなければならないことや、効果を高めるための工夫が研究されています。*3 ここでは、その一部を紹介いたします。
評価関数 †
手の優劣を決めるためには、読み進めたゲームの局面を評価する必要があります。 読み進めた結果局面が、「勝ち」,「引き分け」,「負け」になっているなら、 評価は単純です。コンピューターは、こうした状況も定量化して評価しますので、 勝ち=+∞, 引き分け=0, 負け=-∞、などとしてあつかいます。実際のプログラム中では、 ∞の値は、十分に大きな数*4を具体的に割り当てます。
一方、勝敗決着がついていない局面では、コンピューターは何らかの基準に基づいて形勢判断をしなければなりません。人の場合でも、将棋や囲碁でも、形勢判断の精度が上がり、しかもより短時間で判断できるようになれば、上達することができます。 しかし、形勢判断はゲームにとって最も難しい要素の一つです*5
チェス型のゲームを例に取ると、コンピューターが局面判断をする場合、 駒の損得、駒の効き、特定の駒の位置、 といった評価を、個別に計算し積み上げていくことになります。 他にも、上級者はさまざまな要素を組み合わせて形勢判断をしていますので、 コンピューターも強くするには、これらの材料を増やす工夫が考えられます。
しかし、形勢判断のための材料が増えれば、(一般には)精度が上がりますが、 計算量が増加してしまいます。評価関数の実行に時間がかかることは、 単位時間に読める局面の数が減ることになりますので、 読みを深くして精度を高めることとトレードオフの関係にあります。 高速で、正確な評価関数を作ることがAIを強くすることにとって不可欠な要素です。
Abstract Strategy Games Online Projectの実装では、 複数のゲームに対応できるよう、基本評価関数と、ゲーム個別の評価関数を分離して、 います。基本評価では、勝ち、負け、引き分けだけの判断をおこなっています。
深度延長 †
読みの対象となる、すべての局面を均一の深さで評価しても、中々強くはなりません。 人間の場合、上級者は明確に読む手と読まない手を区別して、 無駄な手の形勢判断に時間を使わないようにしています。コンピューターでも、 この手法は有効で、重要な手だけを絞って深読みさせれば、 より効果的に時間を使うことができます。
では、どういった手が重要な手なのでしょうか。 AIにおいての深度延長の仕組みは、 水平線効果*6を避ける目的があります。 水平線効果とは、固定の深度しか読まないようなプログラムでは、 読み進めた局面での判断が、 次の短手数の内に評価がまったく変わってしまうような状況で、 読み深度の制限から間違った判断をしてしまう現象のことです。
例えば、チェス型のゲームの場合、駒を取る/取られる場合、 すぐ後に駒を取り返せるように、別の駒の効きで守ることが一般的です。 このような、取り合いの局面の途中で、読みを打ち切ってしまうと、 どちらかの手番のプレーヤーが極端な駒得・損をしたような評価をしてしまいます。
そこで、一手毎に評価が大きく変わるような局面から、 (駒の取り合いがなくなる)静かな局面まで深度延長すれば、 より正確な形勢判断がおこなえます。
その他にも、形勢評価が微妙な候補手が複数ある場合は、 それぞれの手をさらに読み進めるなどの処理を加えるなど、 ゲームの性質によって、深度延長を効果的におこなうと、 より強いAIを実現できます。
しかし、(対象ゲームによりますが)深読みの対象とする手を抽出するのは、 簡単なものから複雑なものまでさまざまです。 深度延長判断にも計算量が必要なことは、忘れてはいけません。 深度延長の判断に時間がかかるのは、本末転倒の結果になってしまいます。 また、深度延長判断は、形勢評価関数と共通処理が含まれていることもありますので、 実装を工夫することで無駄を削減することができるかもしれません。
Abstract Strategy Games Online Projectでは、 深度延長判断と評価関数を分離しています。それぞれ、 ゲーム固有の評価が必要であることと、深度延長判断は、 評価関数よりも呼び出される回数が多いため、処理を軽くする必要があるためです。
探索のための工夫 †
先に取り上げたMini-Max法やα-β法は、深さ優先で手を読み進めます。 一般の大局では持ち時間が決まっていて、一定時間内に着手が義務づけ られています。深さを優先する読み方では、読みを打ちきらなければ ならない場合、特定の手だけが評価され、未評価な手が残ってしまう ことになります。
これらの問題を解決する方法として、 反復深化深さ優先探索やSSS法*7といった方法が考案されています。
知識を使う †
評価関数を駆使して、すべての手を計算するやり方だと、 読み進められる局面の数を多くするのは難しいことです。 人間も、序盤には定跡、中盤には手筋、終盤には終盤定跡を駆使して評価時間を短くし、 間違いを減少させる工夫をしています。コンピューターについても、この手法はとても 有効です。
コンピューター将棋やチェスにおいても、定跡データベースを充実させることは、 早くから取り組まれていました。 また、チェスのように終盤に向けて駒が減って 読むべき手が減少するゲームでは、終盤データベースも有効です。チェスでは、 残り5駒になった局面の解析はすべて完了しています。 市販のソフトウェアなどでも、 終盤データベースを組み込んで使えるようになっているものもあります。 とはいえ、残り5駒の全データを入れると膨大なディスクが必要になります。 ですので、利用者の好みで、残り駒数を制限してデータを導入できる工夫がされています。
SEE ALSO †
- Abstract Strategy Games Online Project
- Abstract Strategy Games Online Project/1
- Checkersの仲間
- Chess(欧米他)
- Othello＆Reversi
- Tic-tac-toe
- nimをプレーするコンピューター・プログラム
- アブストラクトゲームとコンピューター
- アブストラクトゲームとコンピューター3
- アブストラクトゲームと数学
- 参考文献/bit別冊 ゲームプログラミング
- 参考文献/イメージと読みの将棋観
- 参考文献/コンピューターゲームのアルゴリズム＆ネットワーキング
- 参考文献/コンピュータ将棋 あなたも挑戦していみませんか
- 参考文献/先を読む頭脳
- 囲碁
- 将棋
- 用語
- 第20回世界コンピュータ将棋選手権
- 閲覧室