羊の人工知能研究 ~将棋AI開発の日々~

将棋、リバーシのAIプログラミングを中心にその開発過程及び記録を頑張って更新していきます。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ゲーム木と探索での評価値

 本日はゲームのAIの基礎、探索についての更新をしようと予定していましたが、それまでにゲーム木評価値について説明する必要がりました。。。

 まず、ほとんどの(?)ゲームはゲーム木という形でゲームの状態を表すことができます。○×ゲーム(3目並べ?)を使ってゲーム木というものを説明します。←図24参照



図24:○×ゲームのゲーム木


 かなり省略した形になりましたが、○×ゲームは上のようなゲーム木になることがわかるでしょうか?このゲーム木において両者が最善手を尽くした場合を探索するのがMinimax等に代表される探索です。しかし、ゲームの状態の数鼠算式に増えていき大変な数のゲームの状態が考えられるでしょう。単純計算すると○×ゲームの状態の数は

9×8×7×・・・×2×1 = 9! = 362880

という計算ができます。36万とか莫大な数ですよね・・・。まぁ実際は途中でゲームが終わったりするので何分の1かになるでしょうが、それでも多くの状態が考えられます。しかし、今のPCではこの○×ゲームを全て探索するのに1秒もかからないでしょう。よって、9手先(全てが埋まるか3目並ぶまで)まで全て読んでどちらも最善手を尽くした場合を考えることができるでしょう。

 しかし、リバーシや将棋となるとゲームの状態の数は天文学的数字になるでしょう!!このゲームを最後まで読んで最善手を出していては地球が終わっても計算が終わらないのでは・・・(汗 そこで、ある程度先、例えば4手先まで読んで評価値というものを計算して返してやります。評価値というのは普段ゲームしているときに感じると思いますが、ゲームの途中で有利、不利、互角など感じるように、コンピュータにもそれを評価値として計算させます。これにより、最後まで読まなくても評価の有利・不利により探索することができます。

 この○×ゲームに関しては自分が2つ並んでいて相手に妨害されていない場合は評価値が高いのではないでしょうか?逆に相手がその状態ならば低くなるはずです。途中で自分の勝ちが見つかれば非常に大きな数を評価値として返し、負けの場合は低い数を返せばいいのです。


 次回は実際にMinimaxの探索についてどのような手順で探索するかについて説明します。それ以降、Minimax以外の効率の良い探索方法も紹介していきます。


次回予告:Minimaxアルゴリズムを使って探索する



↓現在2つのランキングに参加しています↓

クリックしたら投票されるみたいなので、明るい一票をお願いします(m。_。)m
スポンサーサイト

コメントの投稿

URL
コメント
パスワード
秘密
管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://hitsujiai.blog48.fc2.com/tb.php/18-cf023e5a
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。