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

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

スポンサーサイト

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

オセロの評価値を作ってみよう!

 えっと土日と横浜に行っていて昨日帰ってきたところで、マダ少しグダグダ感がありますが(>ω<;)まぁ何で横浜に行っていたかというと、ポルノグラフィティの横スタライブを見に行っていたからからなんですけどね♪♪いやぁ良かった良かった☆☆

 という話はこれぐらいで、でわでわ今回はオセロの評価値ということで今回は始めたいと思います。まずは評価値って何じゃろなって人もいると思うのでチョチョっと説明します。

 前回まで探索のことを語ってきて、評価値の事はサラッと流していました。(えっとさかのぼればこの回で少し説明しています。「価値というのは普段ゲームしているときに感じると思いますが、ゲームの途中で有利、不利、互角など感じるように、コンピュータにもそれを評価値として計算させます。」という感じで。)で、今回は実際にどのような処理をするのかについてオセロを例に挙げて語っていきたいと思います。

 では、オセオでの勝ち負けってご存知ですよね??

「えっ?石の数が多いほうが勝ちじゃねぇ~の?」

 はいその通り!!まぁほとんどの人が知っていると思います。
 では、序盤~中盤でどちらが優勢で、どちらが劣勢か判断できますか?

「・・・。」

 はい、そんな感じでしょう。僕も実はオセロの優勢劣勢ほとんど判断できません。

「ハイハイ!俺できるって!!ってか石が多いほうが優勢に決まってるじゃん!!」

 おぉ!!僕も最近までそう思ってました(汗。でも、実は違うんです↓↓

 こんな感じで、オセロをのルール知ってる人は大勢いても、実際にオセロができる(序盤から考えてできる)人はなかなか少ないものです。。

 実際にオセロで勘違いされる例としては以下のようなものがあります。
・オセロは多く取れば勝ちなので序盤からどんどん取っていく。
・オセロは隅(角)を多く取れば必ず勝てる。
・真ん中の4×4のマスから出ない方がいい!
・隅の近くを取った方が隅を取りやすい。
・辺を自分から取りに行かない方がいい!


 などなどです。。というより、上の例は自分がかつて思っていたことなんですけど。:゚(。ノω\。)゚・。
 上の答えはココにあるので参考までに・・・

 少し横道にそれてしまいましたが、評価値とは「ある盤面の途中を見せられて、どちらが優勢か劣勢かを点数をつける」ことを言います。じゃあ実際に評価値ってどうやって作るねんってことなんですけど、最初は単純でイイんです。隅は取れば優勢になります。隅を取るためには隅の隣は相手の石じゃないと取れません。こういう単純なことを盛り込んだモノを最初は作りたいと思います。方法としては、8×8のマスそれぞれに点数を付けて、そこに自分の石があればその点数を足して、相手の石があれば点数を引くという単純なもの。図30は各マスの点数を表しています。



図30:石の位置による評価


 とまぁこんな感じでプログラムの書き方も大体創造つくと思いますが、一応載せておきます。

#define WHITE -1  //白石
#define EMPTY 0 //石なし
#define BLACK 1 //黒石

//石の位置による評価値
int val_table[8][8] = {
{120, -20, 20, 5, 5, 20, -20, 120},
{-20, -40, -5, -5, -5, -5, -40, -20},
{ 20, -5, 15, 3, 3, 15, -5, 20},
{ 5, -5, 3, 3, 3, 3, -5, 5},
{ 5, -5, 3, 3, 3, 3, -5, 5},
{ 20, -5, 15, 3, 3, 15, -5, 20},
{-20, -40, -5, -5, -5, -5, -40, -20},
{120, -20, 20, 5, 5, 20, -20, 120}
};

//2次元配列のポインタ(board)を受け取って
// 黒から見た評価値を返す関数

int eval(int **board)
{
int i, j, val = 0;

for(i = 0; i < 8; i++){
for(j = 0; j < 8; j++){
val += val_table[i][j] * board[i][j];
}
}
return val;
}


 このプログラムでval += val_table[i][j] * board[i][j];となっているのは、白を-1黒を1空マスを0と定義してtable配列の中に入れているので、掛け算するだけで良いのです。そして、黒を1として定義しているので黒から見た評価値がこの関数で求めることができるのです。お分かりかと思いますが、白から見た評価値が欲しい場合は-1を掛けてやるとイイのです。

 んじゃまぁ今回はこの辺にして、もっと高度な評価値計算については後ほど・・・ノシ


次回予告:もっと正確な評価関数!



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

スポンサーサイト

αβ探索をもっと効率よくするには?

 前回に続いてαβのことについて語りたいと思います!!

 で、まぁいくら語っても探索が早くならないと意味がないので早くなる手法について語ります。単純に前回の知識から高速化するには・・・・って考えると

枝刈りが増えれば早くなるんじゃねーの?」

ってのが1つとして出てくると思います!

 
まさにその通り!!ある方法を使って枝刈りが多く増えるようにすればイイんです☆☆

でまぁ今回はその枝刈りが増える方法をダラ②説明していきます。

「それ何か考えたら難しそう。:゚(。ノω\。)゚・。 」

って思うかもしれないけど、実はメッチャ簡単!!説明は一行で終わってしまうかもしれないけど、ナゼそうなるかについて説明して結論を言いたいと思います。

 まず、前回の図28のゲーム木を見て、どういう時に枝刈りが起こっているかを発見してみてください。



わかりました??


答えとしては、「枝刈りの起きる親の親のノードで自分の評価より大きい値が既にある場合」

という感じでしょうか?日本語苦手なので間違ってたらゴメンなさい・・・。何にせよ枝刈りというのは「前回の探索より悪いのが出てきたのでこれ以上探索する必要ないや~」って考え方なのです。だから、どうすれば枝刈りを増やせるかというと・・・・

評価が高くなるノードから探索すると良いのです!!←コレが結論



「それが分かったら探索する意味ねーじゃん!!」


あぁ~予想通りの声が聞こえてくる 耳ホジホジ*-o-(= ・ェ・=)聞コエニャイモ~ン
まぁまさにその通りなのです。。。ゴメンなさい(ノ´・Д・)ノミ(m´_ _)m
上の結論は実は少し言葉が抜けてます!!

評価が高くなると思われるノードから探索すると良いのです!!←コレが本当の結論

 では、どうすれば評価が高くなると思われるノードからたんさくするのか?

 まず、オセロ等何でも良いのでゲームを想像してみましょう。一回悪い手(行動)をすると形勢は悪くなりますよね?また、逆に一度良い手を打つと形勢は良くなりますよね?このように何ても深く読まなくてもこの手は悪いこの手は良いのいうモノが浅い探索でわかる場合があります。

 とまぁ文字ばかりの説明で目がチカチカしてきますが、上で言ったように浅い探索を予めしておき、評価が良かったノードから探索すれば良いのです。


コレで分かりました??まぁ今回の擬似コードを書いておきます。

int alpha_beta(盤面, int lv, int al, int be)
{
int val;

if(lv == 0)return 評価値(盤面);

if(lv > 4)浅い探索で手を並べ替える;

while(打てる手がある){
手を差して次の盤面を作る;
val = -alpha_beta(盤面, lv - 1, -be, -al);
盤面を1手戻す;
//枝狩り
if(val >= be)return al;
//最高値
if(al < val)al = val;
}
return al;
}


えっと絶対疑問の声が聞こえてくるので説明を付け加えておきます。なぜ『if(lv > 4)』の時だけ手を並べ替えるのか。

答えは単純で、という数字は任意でかまいませんが、あまりノードが深くなってくると探索するより浅い探索をして並べ替えるリスクが高くなってしまうんです!それに、もし浅い探索をする場合に自分自身であるalpha_beta関数を使用する場合、その先でまた浅い並べ替え、呼び出されたalpha_beta関数でまた呼び出され・・・・・で無限ループに陥ってしまいます(>ω<;)そういう理由です。


ってわけで、中途半端な気もしますが語りたいことは語ったので今日はこのへんで[*l _ l]ノシ


次回予告:オセロの評価値を作ってみよう!



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

αβアルゴリズムによる探索超高速化

 就職活動も無事終わったし久しぶりに書くかって感じで(゚ー゚;Aアセアセ

前回(何ヶ月前やねん・・・)NegaMaxについての説明を長々としましたが、まぁ余り深く探索できないのでほとんどの場合はαβアルゴリズムを応用したアルゴリズムを使って探索をしています。(まぁ元をたどれば全てMinimaxの応用なんだけどな)

 まっ早速ダラ②いきましょう!!NegaMaxと違うところは『余計な探索をしない!!』というところだけで、他はNegaMaxのソース自体を丸々使ってほど同じ!!

 それでは、NegaMaxで必要ない探索とは何なのかゲーム木を使って説明したいと思います。


図28:今回のゲーム木


 上は前回同様NegaMaxを使って探索をした場合です。この探索でαβを使うと探索する必要のないノードがたくさんあります。図28の場合で探索する必要のないノードは下の図29で×が付いているノードです。


図29:今回のゲーム木


 えっとマズはこの必要のないノードを探索しないことを枝刈りと言います。コレはゲーム木の枝を切る(刈る)というところからきているハズですウン。 で、なぜ枝狩りが起きるかと言うと、結局はNegaMaxのアルゴリズムが理解できてて、数字を見てみれば想像できる人もいるかもしれません。

 例えば左の2のノードが枝狩りされているかと言うと、このノードの親の親に当たるノードの一回目の探索で2という評価が出てきています。そして各ノードでは子の最小値を反転させた値が評価となります。そして、その右のノードの一回目の探索で0という評価が出てきています。その時点で、このノードの評価値が0以上という値が決定します。ということで、親のノードではこのノードが最高値となる事がナイのでこれ以上の探索は無意味となり、この時点での探索打ち切りとなります。他のノードでも全く同じ考え方です。

 今回の例では少ししか枝狩りされませんでしたが、もっと深く探索する場合では探索の早い段階で枝狩りが起きることにより無駄なノードを早くから枝狩りすることができます。一般的にはαβのアルゴリズムにすることにより、同じ探索時間で深さを2倍にできるとまで言われています。この探索方法はAIの基本と呼べるモノなのでこれから先のアルゴリズムでの基本知識として頭に叩き入れておいていただきたいです。

 でまぁ、最後に今回のαβアルゴリズムの擬似コードを書いて終わりにしたいと思います。
int alpha_beta(盤面, int lv, int al, int be)
{
int val;

if(lv == 0)return 評価値(盤面);

while(打てる手がある){
手を差して次の盤面を作る;
val = -alpha_beta(盤面, lv - 1, -be, -al);
盤面を1手戻す;
//枝狩り
if(val >= be)return al;
//最高値
if(al < val)al = val;
}
return al;
}


こんなところかねαβは!重要な所は赤色になってますので、あとは・・・ノシ


次回予告:不明です。。風の吹くまま・・・



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

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