読者です 読者をやめる 読者になる 読者になる

daruma3940の日記

理解や文章に間違い等あればどんなことでもご指摘お願いします

minmaxそしてalphabeta法について自分の言葉で表現してみる

コンピューター将棋


この文章は間違っています
僕なりの解釈でしかも文章だけで説明するのは難しかったみたい
普通に簡単にαβ法を理解したいという人は
オセロゲーム開発 ~アルファベータ法(alpha-beta search)~
こういうページ見てください

まあちょっとした僕のお遊びに付き合っていただけ程度で読んでいただければ...

あとここを直せばうまく説明できるよ~ということを発見した人は誰かご指摘お願いします

将棋では
自分は最善を尽くして次の一手を考え、相手も最善を尽くして次の一手を考える。
これが将棋の大前提であり、先読みにおける基本中の基本である
相手が互角の相手であれば相手がミスするだろうと思いながら適当な先読みは行ったりしない。

基本的にコンピューターにはあいまいなことは分からない。分かるのは数値だけである
将棋を指すプログラムにとって重要なことは
局面の優劣というあいまいなものを数値化し、プログラムにもわかるようにすることである。

局面を与えるとその局面の優劣を点数(評価値と呼ばれる)化する関数のことを評価関数と呼ぶ。
評価関数の中身についてはここでは触れない。ブラックボックスとして扱う

評価値は先手が有利なほどプラスに大きくなっていき、後手が有利なほどマイナスに大きくなっていくものとする。

ここで先ほどの「先手は最善を尽くして次の一手を指し、後手も最善を尽くして次の一手を指す。」という先読みの大前提を評価値的に捉えてみる。
これは
先手の手番では評価値をできるだけ大きくしようとし、後手の手番では評価値をできるだけ小さくしようとするというように考えることができる。

これは先手が先読みをするときは
評価値を
最大→最小→最大→最小...
というようにしていく差し手を考えるということになる。
これをminMAX法と呼ぶ

これが評価値という概念から見た先読みである。
コンピューターはこのような方法を基本原理として先読みを行っていく。

ここから先は先読みの効率化について述べていく

ーーーーーーーーーーーーーαβ法

αβ法とはα値とβ値というのを探索に導入し、その値がある条件を満たせばそれ以上の先読みを打ち切ることにより探索を効率化する方法である。

α値 β値というものについて軽く説明しておく。
またここから先は先読みのことを探索 探索を行う関数のことを探索関数と呼ばさてもらう。
また先読みの説明の都合上「とある差し手で進めた局面が持つ評価値」を「とある指し手が持つ評価値」と表現させてもらう。

~~自分を先手としたとき

alpha値 
現時点でもっとも評価値を上げることができる指し手の持つ評価値
この値よりも高い値を持つ指し手が現れると革命が起こり
最強が塗り替えられる(alpha値は最強を塗り替えた差し手の評価値になる。)

beta値
最強を塗り替えることのできるほどの評価値を持つ差し手であってもこの値を超えてしまうような評価値を持つ指し手というのはただの幻覚である。
実際に指されることはないので現実に戻ってくるべし。
(このような差し手は先手はベストを尽くすが後手が最善を尽くさなかった場合に起こりうる。)

~~自分を後手としたとき
beta値
現時点で最も評価値を下げることのできる差し手の値になり、
この値よりも低い値が現れた場合はbeta値は塗り替えられる
(あれ?これだとbeta値はalpha値よりも小さくなってしまう..)

alpha値
この値をしたまわるような評価値を持つ指し手というのはただの幻覚で実際に指されることはない。
(この値を下回るような差し手は後手はベストを尽くすが先手が最善を尽くさなかった場合に起こりうる。)

この先手後手から見たalpha,betaの意味を組み合わせると
先手の手番では評価値をできるだけ大きくしようとし、後手の手番では評価値をできるだけ小さくしようとするという原理を実装できていることがわかると思う。

このようにalpha,betaの値を用意すると、探索の中で探したい差し手は

最強を塗り替えられるだけの強さを持ちながら幻覚ではないような差し手

つまり

先手の場合はalpha値は超えるがbeta値は超えないような差し手で
後手から見た場合はbeta値は下回るがalpha値は下回らないような差し手である。

つまりこれらの条件は先手項手一致でalpha値を超えはbeta値を下回るような手を探索で探したいのである

ここでalpha値を超えないまたはbeta値を超えるような差し手はあまりよくない手ということになる。
しかしある局面のとある差し手の評価値の値がalpha値を超えないから、beta値を超えるからという理由だけでその局面全体の探索を打ち切る理由にはならない。
この場合は手番のことも考慮しなければならない。
ここでもう一度先読みの基本原理を思い出そう

「先手の手番では評価値をできるだけ大きくしようとし、後手の手番では評価値をできるだけ小さくしようとする」

つまり先手の場合はalpha値を下回った評価値を持つ指し手が現れてもほかの差し手がalpha値を超えてくれれば良いだけであるのでここで探索を打ち切るのは早とちりである
しかしbeta値を上回った指し手が出てきた場合先手の手番では評価値をできるだけ大きくしようとするのでこの局面での最大の評価値は少なくともbeta値を超えてしまうので探索はここで打ち切られる。

項手の場合は評価値をできるだけ小さくしようとするので評価値がalpha値を下回った場合この局面での最小の評価値は少なくともalpha値を下回ってしまうので探索はここで打ち切られる。

これがalpha beta cutである。

ざっと文章で説明するならばこんなものである。
図による説明の方がいい人は下のようなページを見るべし。

MinMaxとαβ法

う~~~んあんまり自信ないなぁ....