« 2013年7月 | トップページ | 2013年10月 »

2013/09/29

オセロゲームを作る!盤面を画像認識で評価

 オセロの盤面を回帰分析で評価しようと色々な分析の本を立ち読みしまくっていたらニューラルネットワークというおもしろそうな手法を見つけた。

人間の脳のニューロンを模したAIとか遺伝的とか言われているロジックで回帰分析で解けないような問題も解ける場合があるという。

画像認識などにも使われているのでオセロの盤面を画像認識で評価してみようと思う。

とりあえずエッジや角・Xの駒の並びパターンが出てこなくて評価が難しい序盤戦の盤面をパターン認識させて評価してみようと思う。

評価するのは6手目~20手目前後・・・何手目までパターン認識できるかはやってみて決める。

ちなみに1手目は1種類、2手目は3種類しか手がないので評価しない。2手目は3種類均等に打つようにしている。

オセロの本によると2手目~11手目くらいは鼠定石、牛定石、兎定石、虎定石という具合に名前がついていた。

鼠定石

牛定石

虎と兎は4手目にどこに打つかで決まるそうな。

虎・兎定石

4手目を右下に置くと虎、真下に置くと兎。

今のところ勝率は 虎・兎 > 牛 > 鼠

4手目は61種類、5手目は340種類しか手がないのでランダムにちらす(多少勝率が良い手に寄せているけど)

オセロの場合は最終的には勝つか負けるか、何手差かなどの答えがあるので教師あり学習方式を使うことにする。

ニューラルネットワークの中でも構造が単純なバックプロパゲーション法で作ることに。
画像認識などでよく使われている方式。

入力層・中間層 x 1・出力層の3層構造にする。

入力信号は128個。8 x 8 の 64マスの駒の状態を 入力1~64が駒が黒の場合ON、65~128は駒が白の場合にON、駒がない場合はOFFにする。

ただこれだと信号が1次元なので隣接するマスの状態を表現できていないが、良い方法が思いつかない。

中心のマスとその周りの8個のマスを入力にして隣接するマスを表現するという手を思いついたが・・・。
その場合は64コマ×9個×2個(白黒)の入力になる。

とりあえずお試しで単純な128個の入力でやってみる。

1つの盤面につき90°ずつ回転させ、さらに鏡面反転させて8通りを覚えさせる。

中間層は何個でもいいらしい(最適な数を出すのはむずかしいらしい)ので8個・・・盤面が 8 x 8だからという無理やりな理由。

出力層は-64コマ~64コマのコマ差分の129個作ろうかと思ったが、はずしたときに関係のない数になる可能性があるので1個にして0.0~1.0の出力を 129分割して出す事に。

しかし問題が。はじめは出力信号をコマ差にしようと思ったが序盤ではどの手もコマ差が-64~64の範囲という雑な棋譜ばかりなので使えなかった。
しかたがないので各手の勝率を出力信号にすることに変更。

で、結果は・・・朝から回しているけど学習が終わらない。

どうやったら効率よく学習するかテスト的に九九を教えてみる。

入力層は9個、中間層3個、出力層1個。全部答えが正しく出るまで学習を回してみる。

1.1 x 1~9 x 9を1回ずつ学習させるパターンを繰り返す

2.1 x 1~9 x 9を正しく答えが出すまで1つずつ学習を繰り返す
  9 x 9を覚えた時には 1 x 1を忘れているので、最初からやり直し

どちらも正しく答えを出した場合は学習させない。

という方法をとったら2のほうが早く学習が終わった。 速いと言っても20万回くらいかかった。

プログラム的にも2のほうは入力信号のセット回数が少ないので効率がいい。

ただオセロの場合は教えている答えが正しい保証がないので適当な回数で学習を切り上げることにする(1手あたり1000回くらい)

それでも遅い・・・序盤戦だけでも500万手くらいあるので全部教えるには何日もかかりそう。

ニューラルネットワークの参考書を色々立ち読みしたところ、オライリーのゲーム開発者のためのAI入門がよかった。

| | コメント (0) | トラックバック (0)

2013/09/27

オセロゲームを作る!回帰分析ルーチン作成

EXCELの回帰分析では手作業で大変なのと行数、列数に制限があるので自分で作ることに。

が・・・難しい。

偏微分とか行列計算とか完全に忘れている。

高校に戻って勉強しなおさないといけない。

基礎から順番に書いてくれている参考書を見つけたので勉強してみる。

統計学を学ぶための数学入門

四則演算⇒集合⇒確率⇒三角関数⇒指数・対数⇒微分・積分⇒乱数⇒行列 という具合。

集合も三角関数も行列もすっかり忘れていた。四則演算はさすがに大丈夫。

逆行列計算とか正規乱数生成とか回帰直線の計算とかのサンプルプログラムも巻末に載っている(C++だけど)。

追記

本棚の昔の本に重回帰分析のプログラムが載っていた。

技評のアルゴリズム辞典

サンプルプログラムがPascalなので見やすい。C++とかJavaとかはよくわからない。

27年前に買った本なので、もうないかも。


| | コメント (0) | トラックバック (0)

2013/09/23

オセロゲームを作る!盤面を評価する

 終盤全読みは、コーディングの無駄を省いてさらに1手ほど深く読めるようになった。
また、勝つか負けるかだけ読むようにして、いまのところ19手先・・・42手目からは完全読みするようにできた。

しかし、この19手読みは速いときは1分かからないけど読み間違えると十数分・・・ひどいときは1時間くらいかかってしまう場合がある。

最速で先読みするには、正解の手を最初から最後まで打たないといけない。
正解の手を打つには今の盤面を評価するしかない。

盤面評価ロジックを考えるのがめんどくさいのでDBに定石データをためる方式にしたのに、結局やらなくては先に進めないというジレンマ・・・。

とりあえず図書館にオセロの本があったので借りて、どんな盤面がいいのか勉強をしてみる。
(なぜか本屋にはオセロの本がまったくなかった)

よいと言われる形

オセロの良い形

エッジの部分の形で「山」と「囲み」

悪いと言われる形

オセロの悪い形

これもエッジの部分。「ウィング」とかいうらしい。

どっちつかず

オセロの双方C型

白・黒どちらが有利かわからないらしい。

これらや角の石、Xの石(角の斜め隣)のパターンの出現回数を数えて得点計算する。

ほかに確定石の数、石の全部の数、打てる手数、開放度を数える。

打てる手数は、その盤面で白・黒両方を計算。
厳密にはどちらかが打つと手数がわかるけど、通常はそんなに増えたり減ったりしないので誤差とする。

開放度は石が空きマスに接している数らしい。少ないほうが良い。

ほかに空きマスが奇数のエリアが偶数箇所のほうが有利という話も本にあったが、とりあえず空きマスを数えるのが面倒なので保留。

これらを得点化する重み計算を回帰分析で計算してみる。

回答は最終的な石差。プラスなら勝ち、マイナスなら負け。

DBから20万~40万手くらい取りだしてEXCELで計算してみた。ただEXCELの制限で変数は16個しか使わせてくれなかった。

有利・不利なパターンを30パターンくらいピックアップしたが足りないのでまとめることにする。

また白・黒わけなくてもよさそうなものは合算して編巣を減らした。
(確定石の数は白マイナス黒とか・・・結果的に白と黒は同じものは全部引き算してもよさそうだった)

49手目の回帰分析

オセロの回帰分析49手目

E1Wとかが白のエッジの形、C1は角。係数がプラスになっているのはいい手、マイナスは悪い手。
自分の点数はプラス、相手はマイナスにしているので重みは同じ符号になっている。

角の重みが低いのは盤面を解析するのに90°ずつ回転させ、さらに鏡面反転させているので1コマ角にあると2回かぞえられてしまうから、実際は2倍の重みになる。

コマ数はマイナスになっているので49手目でも自分の駒が多いと悪いらしい。

R2は0.75。

41手目の回帰分析
オセロの回帰分析41手目

R2は0.56・・・ギリギリ使える?
41手目では全読みさせていないので、データ精度が悪い。

ここで出た係数をプログラムに組み込み1手目が正解になるか検証してみたが、ならない・・・。

5番目以内には最良手がくるから、適当にやっていたときよりはましだけど、全読み改善にはあまりつながらない・・・。
EXCELだと変数に16個制限があるしデータサンプルも100万行の制限があるので、とりあえず自前で回帰分析するか・・・。

| | コメント (0) | トラックバック (0)

« 2013年7月 | トップページ | 2013年10月 »