オセロのパターン学習再開
昨日から余っているＰＣ（Linux）を利用してオセロのパターン学習を再開しています。棋譜は僕の先生である（勝手に先生と呼んでごめんなさい）ThellとvsOthaの大量の棋譜を用いてやっています。
棋譜は2年位前に拾ったものなので、どこで拾ったかは忘れましたが、80300万棋譜（約750MB）はあります。最近クソ暑いのに、ホンマ何してんねんて感じ…。
５０万棋譜計画 - OWiki URL：http://starlancer.org/~is2004/owiki/index.cgi?page=%A3%B5%A3%B0%CB%FC%B4%FD%C9%E8%B7%D7%B2%E8
速度もぼちぼち早いし、β値は0.05からスタートです。やっぱこれ位じゃないと思いっきり発散してしまう（汗
とりあえず家帰ったら参考URLを追記します。
http://www.neurosci.aist.go.jp/~kurita/lecture/neuro/node3.html
ここに掲載されている最小二乗法を用いてやっています。
棋譜は
５０万棋譜計画 - OWiki URL：http://starlancer.org/~is2004/owiki/index.cgi?page=%A3%B5%A3%B0%CB%FC%B4%FD%C9%E8%B7%D7%B2%E8
速度もぼちぼち早いし、β値は0.05からスタートです。やっぱこれ位じゃないと思いっきり発散してしまう（汗
http://www.neurosci.aist.go.jp/~kurita/lecture/neuro/node3.html
ここに掲載されている最小二乗法を用いてやっています。
最近・・・
全く将棋AIにもオセロIAにも手をつけてません。。。
久しぶりに少しいじりたくなってきた（汗
久しぶりに少しいじりたくなってきた（汗
もっと正確な評価関数！
あぁ前回からまた相当な時がたってしまいました(ﾉ´･Д･)ﾉﾐ(m´_ _)m
カナリ前の話になってしまうんですが、11月上旬にあったACM/アジア地区予選(横浜大会)に『Hanafuda Shuflle GIVEUP orz』というチーム名で出場した時の話です。何と、今までリバーシのAIについて相当勉強させてもらった、国内でもトップクラスと言われているThellとvsOthaの作者が偶然参加されておられたのです！！これにはカナリの衝撃がありました。自分の卒業研究の研究内容とか話している時に、リバーシのの話題になりThellには勉強させてもらったよ〜とか話していると・・・・。
Aさん：「コイツがThellだよ！」
俺：「えっ！？」
Aさん：「vsOthaもいるよ」
俺：「・・・」
この後はかなりリバーシの話題で盛り上がってしまいました（汗。今まで生きてきた中でこれほども世界は狭いものかと感じた一日でした。。。ちなみに・・・当ブログの存在も知っておられたみたいです｡:ﾟ(｡ﾉω＼｡)ﾟ･｡
まぁ思い出話はそれぐらいにして、今回の本題に移りたいと思います。今回『もっと正確な評価値！』としていますが、実際そんな正確な評価関数を作ることなんて不可能なんです。。。だから今回のタイトルを『もっと強い評価関数』と脳内変換を行っておいてください（汗
もっと強い評価関数と言ってますが、実は前回の評価関数でも自分も含めて初心者は普通に負けるぐらいの強さなんです・・・。（スイマセン・・。弱いんです↓↓） しかし、ThellやvsOtha、Zebraなどに勝負を挑むとコテンパンにやられてしまうぐらいヘボい評価関数なんです。そこで、もっと強い評価関数を作りたいというところで今回の話です。
作り方なんですが、現在ではLogistelloの作者であるMichael Buro氏が考案されたパターンに基づく評価が主流になっていますが、ちょっと難しいので別の方法で話を進めます。方法としては以外に単純です。リバーシ（源平碁）が誕生してから現在に至るまでのリバーシの歴史で、この手は良手（又は悪手）とされてきたような知識を評価関数に詰め込んでやれば良いのです。
主な例とすれば、
・着手可能数（手の広さ）による評価
・（発展的）開放度理論による評価
・確定石による評価
・隅、星打ちC打ちの評価
・辺（山、ウィング）の評価
・ストナーズトラップ
とまぁこんな位でしょうか？それぞれについては次回説明したいとおもいますが、これらの評価値計算を行い合計した値を評価値としてやれば良いのです。ですが、それぞれの評価の中で非常に重要なものもあれば、それほど重要でないものもあります。また、手が進むにつれ重要でなってくる評価もありますが、逆に重要でなってくる評価もあります。それらを手動（統計的にできたら一番良いです）で重み付けしてやれば、相当強い評価関数が出来上がります。強さとしては、大体ハ○ゲームの神クラスは普通にあります。
他にも有効とされる手法、手筋等たくさんありますので色々試してみるのもイイと思いますよ☆☆
次回予告：強い評価関数を作ってみる！
↓現在２つのランキングに参加しています↓
カナリ前の話になってしまうんですが、11月上旬にあったACM/アジア地区予選(横浜大会)に『Hanafuda Shuflle GIVEUP orz』というチーム名で出場した時の話です。何と、今までリバーシのAIについて相当勉強させてもらった、国内でもトップクラスと言われているThellとvsOthaの作者が偶然参加されておられたのです！！これにはカナリの衝撃がありました。自分の卒業研究の研究内容とか話している時に、リバーシのの話題になりThellには勉強させてもらったよ〜とか話していると・・・・。
Aさん：「コイツがThellだよ！」
俺：「えっ！？」
Aさん：「vsOthaもいるよ」
俺：「・・・」
この後はかなりリバーシの話題で盛り上がってしまいました（汗。今まで生きてきた中でこれほども世界は狭いものかと感じた一日でした。。。ちなみに・・・当ブログの存在も知っておられたみたいです｡:ﾟ(｡ﾉω＼｡)ﾟ･｡
まぁ思い出話はそれぐらいにして、今回の本題に移りたいと思います。今回『もっと正確な評価値！』としていますが、実際そんな正確な評価関数を作ることなんて不可能なんです。。。だから今回のタイトルを『もっと強い評価関数』と脳内変換を行っておいてください（汗
もっと強い評価関数と言ってますが、実は前回の評価関数でも自分も含めて初心者は普通に負けるぐらいの強さなんです・・・。（スイマセン・・。弱いんです↓↓） しかし、ThellやvsOtha、Zebraなどに勝負を挑むとコテンパンにやられてしまうぐらいヘボい評価関数なんです。そこで、もっと強い評価関数を作りたいというところで今回の話です。
作り方なんですが、現在ではLogistelloの作者であるMichael Buro氏が考案されたパターンに基づく評価が主流になっていますが、ちょっと難しいので別の方法で話を進めます。方法としては以外に単純です。リバーシ（源平碁）が誕生してから現在に至るまでのリバーシの歴史で、この手は良手（又は悪手）とされてきたような知識を評価関数に詰め込んでやれば良いのです。
主な例とすれば、
・着手可能数（手の広さ）による評価
・（発展的）開放度理論による評価
・確定石による評価
・隅、星打ちC打ちの評価
・辺（山、ウィング）の評価
・ストナーズトラップ
とまぁこんな位でしょうか？それぞれについては次回説明したいとおもいますが、これらの評価値計算を行い合計した値を評価値としてやれば良いのです。ですが、それぞれの評価の中で非常に重要なものもあれば、それほど重要でないものもあります。また、手が進むにつれ重要でなってくる評価もありますが、逆に重要でなってくる評価もあります。それらを手動（統計的にできたら一番良いです）で重み付けしてやれば、相当強い評価関数が出来上がります。強さとしては、大体ハ○ゲームの神クラスは普通にあります。
他にも有効とされる手法、手筋等たくさんありますので色々試してみるのもイイと思いますよ☆☆
オセロの評価値を作ってみよう！
えっと土日と横浜に行っていて昨日帰ってきたところで、マダ少しグダグダ感がありますが(＞ω＜;)まぁ何で横浜に行っていたかというと、ポルノグラフィティの横スタライブを見に行っていたからからなんですけどね♪♪いやぁ良かった良かった☆☆
という話はこれぐらいで、でわでわ今回はオセロの評価値ということで今回は始めたいと思います。まずは評価値って何じゃろなって人もいると思うのでチョチョっと説明します。
前回まで探索のことを語ってきて、評価値の事はサラッと流していました。（えっとさかのぼればこの回で少し説明しています。「価値というのは普段ゲームしているときに感じると思いますが、ゲームの途中で有利、不利、互角など感じるように、コンピュータにもそれを評価値として計算させます。」という感じで。）で、今回は実際にどのような処理をするのかについてオセロを例に挙げて語っていきたいと思います。
では、オセオでの勝ち負けってご存知ですよね？？
「えっ？石の数が多いほうが勝ちじゃねぇ〜の？」
はいその通り！！まぁほとんどの人が知っていると思います。
では、序盤〜中盤でどちらが優勢で、どちらが劣勢か判断できますか？
「・・・。」
はい、そんな感じでしょう。僕も実はオセロの優勢劣勢ほとんど判断できません。
「ハイハイ！俺できるって！！ってか石が多いほうが優勢に決まってるじゃん！！」
おぉ！！僕も最近までそう思ってました（汗。でも、実は違うんです↓↓
こんな感じで、オセロをのルール知ってる人は大勢いても、実際にオセロができる（序盤から考えてできる）人はなかなか少ないものです。。
実際にオセロで勘違いされる例としては以下のようなものがあります。
・オセロは多く取れば勝ちなので序盤からどんどん取っていく。
・オセロは隅（角）を多く取れば必ず勝てる。
・真ん中の４×４のマスから出ない方がいい！
・隅の近くを取った方が隅を取りやすい。
・辺を自分から取りに行かない方がいい！
などなどです。。というより、上の例は自分がかつて思っていたことなんですけど｡:ﾟ(｡ﾉω＼｡)ﾟ･｡
上の答えはココにあるので参考までに・・・
少し横道にそれてしまいましたが、評価値とは「ある盤面の途中を見せられて、どちらが優勢か劣勢かを点数をつける」ことを言います。じゃあ実際に評価値ってどうやって作るねんってことなんですけど、最初は単純でイイんです。隅は取れば優勢になります。隅を取るためには隅の隣は相手の石じゃないと取れません。こういう単純なことを盛り込んだモノを最初は作りたいと思います。方法としては、８×８のマスそれぞれに点数を付けて、そこに自分の石があればその点数を足して、相手の石があれば点数を引くという単純なもの。図30は各マスの点数を表しています。
図30:石の位置による評価
とまぁこんな感じでプログラムの書き方も大体創造つくと思いますが、一応載せておきます。
このプログラムでval += val_table[i][j] * board[i][j];となっているのは、白を-1、黒を1、空マスを0と定義してtable配列の中に入れているので、掛け算するだけで良いのです。そして、黒を1として定義しているので黒から見た評価値がこの関数で求めることができるのです。お分かりかと思いますが、白から見た評価値が欲しい場合は-1を掛けてやるとイイのです。
んじゃまぁ今回はこの辺にして、もっと高度な評価値計算については後ほど・・・ﾉｼ
次回予告：もっと正確な評価関数！
↓現在２つのランキングに参加しています↓
という話はこれぐらいで、でわでわ今回はオセロの評価値ということで今回は始めたいと思います。まずは評価値って何じゃろなって人もいると思うのでチョチョっと説明します。
前回まで探索のことを語ってきて、評価値の事はサラッと流していました。（えっとさかのぼればこの回で少し説明しています。「価値というのは普段ゲームしているときに感じると思いますが、ゲームの途中で有利、不利、互角など感じるように、コンピュータにもそれを評価値として計算させます。」という感じで。）で、今回は実際にどのような処理をするのかについてオセロを例に挙げて語っていきたいと思います。
では、オセオでの勝ち負けってご存知ですよね？？
「えっ？石の数が多いほうが勝ちじゃねぇ〜の？」
はいその通り！！まぁほとんどの人が知っていると思います。
では、序盤〜中盤でどちらが優勢で、どちらが劣勢か判断できますか？
「・・・。」
はい、そんな感じでしょう。僕も実はオセロの優勢劣勢ほとんど判断できません。
「ハイハイ！俺できるって！！ってか石が多いほうが優勢に決まってるじゃん！！」
おぉ！！僕も最近までそう思ってました（汗。でも、実は違うんです↓↓
こんな感じで、オセロをのルール知ってる人は大勢いても、実際にオセロができる（序盤から考えてできる）人はなかなか少ないものです。。
実際にオセロで勘違いされる例としては以下のようなものがあります。
・オセロは多く取れば勝ちなので序盤からどんどん取っていく。
・オセロは隅（角）を多く取れば必ず勝てる。
・真ん中の４×４のマスから出ない方がいい！
・隅の近くを取った方が隅を取りやすい。
・辺を自分から取りに行かない方がいい！
などなどです。。というより、上の例は自分がかつて思っていたことなんですけど｡:ﾟ(｡ﾉω＼｡)ﾟ･｡
上の答えはココにあるので参考までに・・・
少し横道にそれてしまいましたが、評価値とは「ある盤面の途中を見せられて、どちらが優勢か劣勢かを点数をつける」ことを言います。じゃあ実際に評価値ってどうやって作るねんってことなんですけど、最初は単純でイイんです。隅は取れば優勢になります。隅を取るためには隅の隣は相手の石じゃないと取れません。こういう単純なことを盛り込んだモノを最初は作りたいと思います。方法としては、８×８のマスそれぞれに点数を付けて、そこに自分の石があればその点数を足して、相手の石があれば点数を引くという単純なもの。図30は各マスの点数を表しています。
図30:石の位置による評価
とまぁこんな感じでプログラムの書き方も大体創造つくと思いますが、一応載せておきます。
#define WHITE -1 //白石 |
このプログラムでval += val_table[i][j] * board[i][j];となっているのは、白を-1、黒を1、空マスを0と定義してtable配列の中に入れているので、掛け算するだけで良いのです。そして、黒を1として定義しているので黒から見た評価値がこの関数で求めることができるのです。お分かりかと思いますが、白から見た評価値が欲しい場合は-1を掛けてやるとイイのです。
んじゃまぁ今回はこの辺にして、もっと高度な評価値計算については後ほど・・・ﾉｼ
αβ探索をもっと効率よくするには？
前回に続いてαβのことについて語りたいと思います！！
で、まぁいくら語っても探索が早くならないと意味がないので早くなる手法について語ります。単純に前回の知識から高速化するには・・・・って考えると
「枝刈りが増えれば早くなるんじゃねーの？」
ってのが１つとして出てくると思います！
まさにその通り！！ある方法を使って枝刈りが多く増えるようにすればイイんです☆☆
でまぁ今回はその枝刈りが増える方法をダラ�∪睫世靴討い�ます。
「それ何か考えたら難しそう｡:ﾟ(｡ﾉω＼｡)ﾟ･｡ 」
って思うかもしれないけど、実はメッチャ簡単！！説明は一行で終わってしまうかもしれないけど、ナゼそうなるかについて説明して結論を言いたいと思います。
まず、前回の図28のゲーム木を見て、どういう時に枝刈りが起こっているかを発見してみてください。
わかりました？？
答えとしては、「枝刈りの起きる親の親のノードで自分の評価より大きい値が既にある場合」
という感じでしょうか？日本語苦手なので間違ってたらゴメンなさい・・・。何にせよ枝刈りというのは「前回の探索より悪いのが出てきたのでこれ以上探索する必要ないや〜」って考え方なのです。だから、どうすれば枝刈りを増やせるかというと・・・・
評価が高くなるノードから探索すると良いのです！！←コレが結論
「それが分かったら探索する意味ねーじゃん！！」
あぁ〜予想通りの声が聞こえてくる 耳ﾎｼﾞﾎｼﾞ*-ｏ-(= ・ェ・=)聞ｺｴﾆｬｲﾓ〜ﾝ
まぁまさにその通りなのです。。。ゴメンなさい(ﾉ´･Д･)ﾉﾐ(m´_ _)m
上の結論は実は少し言葉が抜けてます！！
評価が高くなると思われるノードから探索すると良いのです！！←コレが本当の結論
では、どうすれば評価が高くなると思われるノードからたんさくするのか？
まず、オセロ等何でも良いのでゲームを想像してみましょう。一回悪い手（行動）をすると形勢は悪くなりますよね？また、逆に一度良い手を打つと形勢は良くなりますよね？このように何ても深く読まなくてもこの手は悪いこの手は良いのいうモノが浅い探索でわかる場合があります。
とまぁ文字ばかりの説明で目がチカチカしてきますが、上で言ったように浅い探索を予めしておき、評価が良かったノードから探索すれば良いのです。
コレで分かりました？？まぁ今回の擬似コードを書いておきます。
えっと絶対疑問の声が聞こえてくるので説明を付け加えておきます。なぜ『if(lv > 4)』の時だけ手を並べ替えるのか。
答えは単純で、４という数字は任意でかまいませんが、あまりノードが深くなってくると探索するより浅い探索をして並べ替えるリスクが高くなってしまうんです！それに、もし浅い探索をする場合に自分自身であるalpha_beta関数を使用する場合、その先でまた浅い並べ替え、呼び出されたalpha_beta関数でまた呼び出され・・・・・で無限ループに陥ってしまいます(＞ω＜;)そういう理由です。
ってわけで、中途半端な気もしますが語りたいことは語ったので今日はこのへんで[*l _ l]ﾉｼ
次回予告：オセロの評価値を作ってみよう！
↓現在２つのランキングに参加しています↓
で、まぁいくら語っても探索が早くならないと意味がないので早くなる手法について語ります。単純に前回の知識から高速化するには・・・・って考えると
「枝刈りが増えれば早くなるんじゃねーの？」
ってのが１つとして出てくると思います！
まさにその通り！！ある方法を使って枝刈りが多く増えるようにすればイイんです☆☆
でまぁ今回はその枝刈りが増える方法をダラ�∪睫世靴討い�ます。
「それ何か考えたら難しそう｡:ﾟ(｡ﾉω＼｡)ﾟ･｡ 」
って思うかもしれないけど、実はメッチャ簡単！！説明は一行で終わってしまうかもしれないけど、ナゼそうなるかについて説明して結論を言いたいと思います。
まず、前回の図28のゲーム木を見て、どういう時に枝刈りが起こっているかを発見してみてください。
わかりました？？
答えとしては、「枝刈りの起きる親の親のノードで自分の評価より大きい値が既にある場合」
という感じでしょうか？日本語苦手なので間違ってたらゴメンなさい・・・。何にせよ枝刈りというのは「前回の探索より悪いのが出てきたのでこれ以上探索する必要ないや〜」って考え方なのです。だから、どうすれば枝刈りを増やせるかというと・・・・
評価が高くなるノードから探索すると良いのです！！←コレが結論
「それが分かったら探索する意味ねーじゃん！！」
あぁ〜予想通りの声が聞こえてくる 耳ﾎｼﾞﾎｼﾞ*-ｏ-(= ・ェ・=)聞ｺｴﾆｬｲﾓ〜ﾝ
まぁまさにその通りなのです。。。ゴメンなさい(ﾉ´･Д･)ﾉﾐ(m´_ _)m
上の結論は実は少し言葉が抜けてます！！
評価が高くなると思われるノードから探索すると良いのです！！←コレが本当の結論
では、どうすれば評価が高くなると思われるノードからたんさくするのか？
まず、オセロ等何でも良いのでゲームを想像してみましょう。一回悪い手（行動）をすると形勢は悪くなりますよね？また、逆に一度良い手を打つと形勢は良くなりますよね？このように何ても深く読まなくてもこの手は悪いこの手は良いのいうモノが浅い探索でわかる場合があります。
とまぁ文字ばかりの説明で目がチカチカしてきますが、上で言ったように浅い探索を予めしておき、評価が良かったノードから探索すれば良いのです。
コレで分かりました？？まぁ今回の擬似コードを書いておきます。
int alpha_beta(盤面, int lv, int al, int be) |
えっと絶対疑問の声が聞こえてくるので説明を付け加えておきます。なぜ『if(lv > 4)』の時だけ手を並べ替えるのか。
答えは単純で、４という数字は任意でかまいませんが、あまりノードが深くなってくると探索するより浅い探索をして並べ替えるリスクが高くなってしまうんです！それに、もし浅い探索をする場合に自分自身であるalpha_beta関数を使用する場合、その先でまた浅い並べ替え、呼び出されたalpha_beta関数でまた呼び出され・・・・・で無限ループに陥ってしまいます(＞ω＜;)そういう理由です。
ってわけで、中途半端な気もしますが語りたいことは語ったので今日はこのへんで[*l _ l]ﾉｼ