開始行:
- [[アブストラクトゲームとコンピューター]] - アブストラクトゲームとコンピューター2 - [[アブストラクトゲームとコンピューター3]] - [[nimをプレーするコンピューター・プログラム]] - [[Abstract Strategy Games Online Project]] //---- //''Table of Contents'' //#contents() * ゲームの探索空間 [#g1819817] 現在、アブストラクトゲームをプレーするコンピューターの取... 評価関数によって、ひとつひとつの局面を静的に判断し着手を... その局面に至る経緯は考慮しません。 また、合法着手について先読みをおこないます。当然、先読み... 以下は、代表的なアブストラクトゲームでの''ゲーム探索空間'... |[[三目並べ>Tic-tac-toe]]|RIGHT:&nbsp;&nbsp;10&super{3};... |[[チェッカー>Checkersの仲間]]|RIGHT:&nbsp;&nbsp;10&super... |[[オセロ>Othello＆Reversi]]|RIGHT:&nbsp;&nbsp;10&super{6... |[[チェス>Chess(欧米他)]]|RIGHT:&nbsp;&nbsp;10&super{120}... |[[将棋]]|RIGHT:&nbsp;&nbsp;10&super{220};&nbsp;&nbsp;| |[[囲碁]]|RIGHT:&nbsp;&nbsp;10&super{360};&nbsp;&nbsp;| ''表:メジャーなゲームの探索空間'' * 最適の手を求めて1 ゲーム木 [#ac509262] 二人完全情報0和ゲームでは、各手番で選択した手によって出現... Mini-Max, α-β, Nega-Max, Nega-Alphaについて、プログラム事... ここで紹介するプログラム例は、いずれも、深さ優先の探索を... 一般的なアルゴリズムの教科書にある実装方式に加えて、指定... ** Mini-Max法 [#ababa7db] #ref(./gametree_1.jpg,right,around,分割nimのゲーム木 - ク... 二人完全情報0和ゲームで、最適の手を探索する基本的なアルゴ... Mini-Maxでは、探索対象範囲内の起こりうる局面をすべて抽出... ゲーム木の端(node)の評価値を、先手後手、それぞれが自分に... 図1は、nimの一種で分割nimと呼ばれる種類のゲームを使った、... #clear #ref(./gametree_2.jpg,right,around,分割nimのゲーム木 - ク... 図2は、図1に先手が勝つ末端のノードに''1''、後手が勝つ末端... 一般のMini-Max法では、ゲームが複雑な場合は、勝ちに''+∞''... 決着がつかない状況での途中の局面での評価は、評価関数を作... Mini-Max法は、このようにゲーム木を作成して、価値の高い手... #clear [[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 ** α-β法 [#s3c69344] &ref(./gametree_3.jpg,α-βカットの例1 - クリックで拡大,40%); &ref(./gametree_4.jpg,α-βカットの例2 - クリックで拡大,40%); &ref(./gametree_5.jpg,α-βカットの例3 - クリックで拡大,40%); Mini-Maxでは、木構造のすべてのnodeを評価しなければなりま... α-βでは、明らかに選択されない手については、nodeと枝の評価... 図を見ながら、下記のプログラムの動作を確認してみてくださ... #clear [[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の改善 [#g9aa7933] Nega-MaxとNega-Alphaの基本的なアルゴリズム構造は、Mini-Ma... 局面の評価基準を手番プレーヤーにすることで、プログラム構... ここで用いている局面評価関数(AI#value)は、Nega-* で使うこ... 下記methodes内のvalue呼び出しで、符号反転はおこなっていま... *** Nega-Max [#u7be468f] [[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 [#j62d81d6] [[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 [#be59960a] 手の探索をする上で、コンピューターがおこなわなければなら... ** 評価関数 [#t43c3864] 手の優劣を決めるためには、読み進めたゲームの局面を評価す... 読み進めた結果局面が、「勝ち」,「引き分け」,「負け」にな... 評価は単純です。コンピューターは、こうした状況も定量化し... 勝ち=+∞, 引き分け=0, 負け=-∞、などとしてあつかいます。実... ∞の値は、十分に大きな数((プログラム高速化のため、実数型よ... 一方、勝敗決着がついていない局面では、コンピューターは何... しかし、形勢判断はゲームにとって最も難しい要素の一つです(... チェス型のゲームを例に取ると、コンピューターが局面判断を... 駒の損得、駒の効き、特定の駒の位置、 といった評価を、個別に計算し積み上げていくことになります。 他にも、上級者はさまざまな要素を組み合わせて形勢判断をし... コンピューターも強くするには、これらの材料を増やす工夫が... しかし、形勢判断のための材料が増えれば、(一般には)精度が... 計算量が増加してしまいます。評価関数の実行に時間がかかる... 単位時間に読める局面の数が減ることになりますので、 読みを深くして精度を高めることとトレードオフの関係にあり... 高速で、正確な評価関数を作ることがAIを強くすることにとっ... [[Abstract Strategy Games Online Project]]の実装では、 複数のゲームに対応できるよう、基本評価関数と、ゲーム個別... います。基本評価では、勝ち、負け、引き分けだけの判断をお... ** 深度延長 [#p432d5b2] 読みの対象となる、すべての局面を均一の深さで評価しても、... 人間の場合、上級者は明確に読む手と読まない手を区別して、 無駄な手の形勢判断に時間を使わないようにしています。コン... この手法は有効で、%%%重要な手%%%だけを絞って深読みさせれ... より効果的に時間を使うことができます。 では、どういった手が%%%重要な手%%%なのでしょうか。 AIにおいての深度延長の仕組みは、 水平線効果((地平線効果とも呼びます))を避ける目的がありま... 水平線効果とは、固定の深度しか読まないようなプログラムで... 読み進めた局面での判断が、 次の短手数の内に評価がまったく変わってしまうような状況で、 読み深度の制限から間違った判断をしてしまう現象のことです。 例えば、チェス型のゲームの場合、駒を取る/取られる場合、 すぐ後に駒を取り返せるように、別の駒の効きで守ることが一... このような、取り合いの局面の途中で、読みを打ち切ってしま... どちらかの手番のプレーヤーが極端な駒得・損をしたような評... そこで、一手毎に評価が大きく変わるような局面から、 (駒の取り合いがなくなる)%%%静かな局面%%%まで深度延長すれ... より正確な形勢判断がおこなえます。 その他にも、形勢評価が微妙な候補手が複数ある場合は、 それぞれの手をさらに読み進めるなどの処理を加えるなど、 ゲームの性質によって、深度延長を効果的におこなうと、 より強いAIを実現できます。 しかし、(対象ゲームによりますが)深読みの対象とする手を抽... 簡単なものから複雑なものまでさまざまです。 深度延長判断にも計算量が必要なことは、忘れてはいけません。 深度延長の判断に時間がかかるのは、本末転倒の結果になって... また、深度延長判断は、形勢評価関数と共通処理が含まれてい... 実装を工夫することで無駄を削減することができるかもしれま... [[Abstract Strategy Games Online Project]]では、 深度延長判断と評価関数を分離しています。それぞれ、 ゲーム固有の評価が必要であることと、深度延長判断は、 評価関数よりも呼び出される回数が多いため、処理を軽くする... ** 探索のための工夫 [#m3f77bb3] 先に取り上げたMini-Max法やα-β法は、深さ優先で手を読み進め... 一般の大局では持ち時間が決まっていて、一定時間内に着手が... られています。深さを優先する読み方では、読みを打ちきらな... ならない場合、特定の手だけが評価され、未評価な手が残って... ことになります。 これらの問題を解決する方法として、 ''反復深化深さ優先探索''や''SSS法''(([[参考文献/コンピュ... ** 知識を使う [#m0524d27] 評価関数を駆使して、すべての手を計算するやり方だと、 読み進められる局面の数を多くするのは難しいことです。 人間も、序盤には定跡、中盤には手筋、終盤には終盤定跡を駆... 間違いを減少させる工夫をしています。コンピューターについ... 有効です。 コンピューター将棋やチェスにおいても、定跡データベースを... 早くから取り組まれていました。 また、チェスのように終盤に向けて駒が減って 読むべき手が減少するゲームでは、終盤データベースも有効で... 残り5駒になった局面の解析はすべて完了しています。 市販のソフトウェアなどでも、 終盤データベースを組み込んで使えるようになっているものも... とはいえ、残り5駒の全データを入れると膨大なディスクが必要... ですので、利用者の好みで、残り駒数を制限してデータを導入... * SEE ALSO [#j9f2f3fb] #related * Feedback [#u1caae51] &facebooklike(400x180,action="like",scrolling="yes",show_... #vote(おもしろい[5],役に立つ[5],興味ない[0],理解できない[... //#pcomment_nospam(noname)

終了行:
- [[アブストラクトゲームとコンピューター]] - アブストラクトゲームとコンピューター2 - [[アブストラクトゲームとコンピューター3]] - [[nimをプレーするコンピューター・プログラム]] - [[Abstract Strategy Games Online Project]] //---- //''Table of Contents'' //#contents() * ゲームの探索空間 [#g1819817] 現在、アブストラクトゲームをプレーするコンピューターの取... 評価関数によって、ひとつひとつの局面を静的に判断し着手を... その局面に至る経緯は考慮しません。 また、合法着手について先読みをおこないます。当然、先読み... 以下は、代表的なアブストラクトゲームでの''ゲーム探索空間'... |[[三目並べ>Tic-tac-toe]]|RIGHT:&nbsp;&nbsp;10&super{3};... |[[チェッカー>Checkersの仲間]]|RIGHT:&nbsp;&nbsp;10&super... |[[オセロ>Othello＆Reversi]]|RIGHT:&nbsp;&nbsp;10&super{6... |[[チェス>Chess(欧米他)]]|RIGHT:&nbsp;&nbsp;10&super{120}... |[[将棋]]|RIGHT:&nbsp;&nbsp;10&super{220};&nbsp;&nbsp;| |[[囲碁]]|RIGHT:&nbsp;&nbsp;10&super{360};&nbsp;&nbsp;| ''表:メジャーなゲームの探索空間'' * 最適の手を求めて1 ゲーム木 [#ac509262] 二人完全情報0和ゲームでは、各手番で選択した手によって出現... Mini-Max, α-β, Nega-Max, Nega-Alphaについて、プログラム事... ここで紹介するプログラム例は、いずれも、深さ優先の探索を... 一般的なアルゴリズムの教科書にある実装方式に加えて、指定... ** Mini-Max法 [#ababa7db] #ref(./gametree_1.jpg,right,around,分割nimのゲーム木 - ク... 二人完全情報0和ゲームで、最適の手を探索する基本的なアルゴ... Mini-Maxでは、探索対象範囲内の起こりうる局面をすべて抽出... ゲーム木の端(node)の評価値を、先手後手、それぞれが自分に... 図1は、nimの一種で分割nimと呼ばれる種類のゲームを使った、... #clear #ref(./gametree_2.jpg,right,around,分割nimのゲーム木 - ク... 図2は、図1に先手が勝つ末端のノードに''1''、後手が勝つ末端... 一般のMini-Max法では、ゲームが複雑な場合は、勝ちに''+∞''... 決着がつかない状況での途中の局面での評価は、評価関数を作... Mini-Max法は、このようにゲーム木を作成して、価値の高い手... #clear [[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 ** α-β法 [#s3c69344] &ref(./gametree_3.jpg,α-βカットの例1 - クリックで拡大,40%); &ref(./gametree_4.jpg,α-βカットの例2 - クリックで拡大,40%); &ref(./gametree_5.jpg,α-βカットの例3 - クリックで拡大,40%); Mini-Maxでは、木構造のすべてのnodeを評価しなければなりま... α-βでは、明らかに選択されない手については、nodeと枝の評価... 図を見ながら、下記のプログラムの動作を確認してみてくださ... #clear [[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の改善 [#g9aa7933] Nega-MaxとNega-Alphaの基本的なアルゴリズム構造は、Mini-Ma... 局面の評価基準を手番プレーヤーにすることで、プログラム構... ここで用いている局面評価関数(AI#value)は、Nega-* で使うこ... 下記methodes内のvalue呼び出しで、符号反転はおこなっていま... *** Nega-Max [#u7be468f] [[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 [#j62d81d6] [[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 [#be59960a] 手の探索をする上で、コンピューターがおこなわなければなら... ** 評価関数 [#t43c3864] 手の優劣を決めるためには、読み進めたゲームの局面を評価す... 読み進めた結果局面が、「勝ち」,「引き分け」,「負け」にな... 評価は単純です。コンピューターは、こうした状況も定量化し... 勝ち=+∞, 引き分け=0, 負け=-∞、などとしてあつかいます。実... ∞の値は、十分に大きな数((プログラム高速化のため、実数型よ... 一方、勝敗決着がついていない局面では、コンピューターは何... しかし、形勢判断はゲームにとって最も難しい要素の一つです(... チェス型のゲームを例に取ると、コンピューターが局面判断を... 駒の損得、駒の効き、特定の駒の位置、 といった評価を、個別に計算し積み上げていくことになります。 他にも、上級者はさまざまな要素を組み合わせて形勢判断をし... コンピューターも強くするには、これらの材料を増やす工夫が... しかし、形勢判断のための材料が増えれば、(一般には)精度が... 計算量が増加してしまいます。評価関数の実行に時間がかかる... 単位時間に読める局面の数が減ることになりますので、 読みを深くして精度を高めることとトレードオフの関係にあり... 高速で、正確な評価関数を作ることがAIを強くすることにとっ... [[Abstract Strategy Games Online Project]]の実装では、 複数のゲームに対応できるよう、基本評価関数と、ゲーム個別... います。基本評価では、勝ち、負け、引き分けだけの判断をお... ** 深度延長 [#p432d5b2] 読みの対象となる、すべての局面を均一の深さで評価しても、... 人間の場合、上級者は明確に読む手と読まない手を区別して、 無駄な手の形勢判断に時間を使わないようにしています。コン... この手法は有効で、%%%重要な手%%%だけを絞って深読みさせれ... より効果的に時間を使うことができます。 では、どういった手が%%%重要な手%%%なのでしょうか。 AIにおいての深度延長の仕組みは、 水平線効果((地平線効果とも呼びます))を避ける目的がありま... 水平線効果とは、固定の深度しか読まないようなプログラムで... 読み進めた局面での判断が、 次の短手数の内に評価がまったく変わってしまうような状況で、 読み深度の制限から間違った判断をしてしまう現象のことです。 例えば、チェス型のゲームの場合、駒を取る/取られる場合、 すぐ後に駒を取り返せるように、別の駒の効きで守ることが一... このような、取り合いの局面の途中で、読みを打ち切ってしま... どちらかの手番のプレーヤーが極端な駒得・損をしたような評... そこで、一手毎に評価が大きく変わるような局面から、 (駒の取り合いがなくなる)%%%静かな局面%%%まで深度延長すれ... より正確な形勢判断がおこなえます。 その他にも、形勢評価が微妙な候補手が複数ある場合は、 それぞれの手をさらに読み進めるなどの処理を加えるなど、 ゲームの性質によって、深度延長を効果的におこなうと、 より強いAIを実現できます。 しかし、(対象ゲームによりますが)深読みの対象とする手を抽... 簡単なものから複雑なものまでさまざまです。 深度延長判断にも計算量が必要なことは、忘れてはいけません。 深度延長の判断に時間がかかるのは、本末転倒の結果になって... また、深度延長判断は、形勢評価関数と共通処理が含まれてい... 実装を工夫することで無駄を削減することができるかもしれま... [[Abstract Strategy Games Online Project]]では、 深度延長判断と評価関数を分離しています。それぞれ、 ゲーム固有の評価が必要であることと、深度延長判断は、 評価関数よりも呼び出される回数が多いため、処理を軽くする... ** 探索のための工夫 [#m3f77bb3] 先に取り上げたMini-Max法やα-β法は、深さ優先で手を読み進め... 一般の大局では持ち時間が決まっていて、一定時間内に着手が... られています。深さを優先する読み方では、読みを打ちきらな... ならない場合、特定の手だけが評価され、未評価な手が残って... ことになります。 これらの問題を解決する方法として、 ''反復深化深さ優先探索''や''SSS法''(([[参考文献/コンピュ... ** 知識を使う [#m0524d27] 評価関数を駆使して、すべての手を計算するやり方だと、 読み進められる局面の数を多くするのは難しいことです。 人間も、序盤には定跡、中盤には手筋、終盤には終盤定跡を駆... 間違いを減少させる工夫をしています。コンピューターについ... 有効です。 コンピューター将棋やチェスにおいても、定跡データベースを... 早くから取り組まれていました。 また、チェスのように終盤に向けて駒が減って 読むべき手が減少するゲームでは、終盤データベースも有効で... 残り5駒になった局面の解析はすべて完了しています。 市販のソフトウェアなどでも、 終盤データベースを組み込んで使えるようになっているものも... とはいえ、残り5駒の全データを入れると膨大なディスクが必要... ですので、利用者の好みで、残り駒数を制限してデータを導入... * SEE ALSO [#j9f2f3fb] #related * Feedback [#u1caae51] &facebooklike(400x180,action="like",scrolling="yes",show_... #vote(おもしろい[5],役に立つ[5],興味ない[0],理解できない[... //#pcomment_nospam(noname)

ページ名: