2013/10/14

きれいなソースコード = メンテナンス性が良い ≠ 速い

 速いプログラムを書こうとするとソースが汚くなりメンテナンス性が落ちる。

1手深く探索するには現状より10倍以上速度が改善しないといけないので、それ以下のロジック改造はメンテナンス性をおとすだけなので採用していない。

ただ、最終的には使いたいロジックは色々あるのでメモで残す。

1.盤面を128ビットデータで扱う
 現状は 0~63の64個のInt配列で盤面を扱っているが、データベースには128ビットで保存している。

メリット
・DBから読みだした後、Int配列に展開しなくてい
・盤面のコピーが速い
 ・・・いまはコピーするよりひっくり返したコマを戻すほうが速いのでそうしている。
・コマをひっくり返すのが速い(上記の理由でひっくり返す履歴をとっているので)

実装してみたところ、盤面コピーの部分だけでも3~4倍速くなった。
ただ、プログラムがメンテ不能になる。
駒をひっくり返したりする部分は改修が多いので、その都度Int型に戻してデバッグしてbit型に改修して・・・とけっこう手間なのでやめた。

2.ひっくり返すコマの探索をマスごとに行う
 現状は8方向に探索しているが、マスごとにどの方向に何マス探索するか設定しておく

メリット
・探索する必要がない方向、マスを省略できる。

たとえば左上の角だと探索する方向は右、右下、下の3方向。8分の3の探索数で済む。
これを全60マス分決めておく。

プログラムのメンテナンス性は落ちなさそうだが、実装が激しくめんどくさいのでやっていない
盤面をビットで扱う場合は劇的に速くなりそう。

3.四則演算は使わない
 速いプログラミングの基本なだがアセンブラを使わなくなると忘れがち
・足し算はINC命令を使う。+3よりINCを3回したほうが速い
・掛け算は左ビットシフト命令を使う。
・割り算は右ビットシフト命令を使う。

オセロは8×8マスなので使う機会が多い。×8(3 bitシフト)、×64(6 bitシフト)。
掛け算より100倍から200倍は速くなる。
ほかの人がプログラムを見るとわけわからんかも。

4.マスの座標系さんは定数を使う
 64マスしかないので、なるべく値はプログラムべた書きにする
・マスの回転、鏡面反転は全部定数テーブルで行う
 マス0の回転は右回りで0 → 7 → 63 → 56とか。

最初から実装してしまたので計算とどちらが速いのか検証していない。

なんか色々思いついたのがあったのに忘れた・・・。

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

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/07/20

ブックススケジューラー Ver.3.4.1.1リリース

 すみません、NGワードがちゃんと動いていませんでした。

その修正だけです。

それとWindows 8.1 プレビュー版(32bit)で動くことが確認できたのでWin8を対応OSに入れました。


ブックススケジューラーのダウンロードはこちら 


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

2013/07/15

ヴァルヘルIPコンフィグ Ver.1.15.16リリース

Windows 7でデフォルトゲートウェイを初期化できない不具合を修正しました。

あとWindows8.1プレビュー版が公開されて、VirtualBoxが対応してくれたので、さっと動かしてみました。

さっと見た感じはWindows7と違わないようです。

ただそのまま動かすと管理者権限で動かないようで、右クリックで「管理者権限で実行」を選ぶ必要があります。

ヴァルヘルIPコンフィグのダウンロードはこちら

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

2013/07/06

ブックススケジューラー Ver.3.4.1リリース

NGワードを指定できるようにしました。

メニューから編集(E) - 各種設定 - NGワードタブです。

初期値では「コミックセット」「巻セット」を指定してあります。

Ngword

個人的な設定で、キーワードに「ガンダム」を入れているので不要なのが色々ひっかかるので、これで除外しています。


ブックススケジューラーのダウンロードはこちら 

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

2013/06/17

オセロゲームを作る!終盤の全読みロジックその2

 やっと20万~30万手くらいのデータがたまった。

 週に1回ペースでディスククラッシュが続き、週に2回くらいしかバックアップを取っていなかったので何度も3,4日前の状態にもどって全然進まず。
 3年近く使い続けたPCなので寿命とみてHDDを交換したら壊れないは劇的に速くなるはディスク容量は倍(1TB)になるはでいいことばかり。

ほかのオセロソフトとの対戦ではとりあえず20手目くらいまではDB内の棋譜データに沿った打ち方ができるが、それ以降はDBにない状態に。
中盤ロジックは適当なので、その状態になると大負けに。

同じ手を打つようなソフトだと何度か対戦するうちにデータベースに棋譜データがためって勝てるけどデータ不足。


解析の進捗が想定以上にスローペースなので終盤の全読みロジックを見直すことに。

1000回くらいの平均をとると最終11手読みで30秒くらい、12手読みで1分強、13手読みで3分~4分。
4コアのPCなので4つ同時に動かしても1日2000件~3000件しか進まず。

全読みロジックでは相手の手で現在の最良手より良い手を出した場合検索を中断するようにしている。

しかし、おぼろげな記憶では30年前に作った時は自分の手で現在の最良手より悪い手を出した時も中断していたような気がするので真面目に検討してみた。

結論から言うと中断して問題なかった。中断するロジックとしないロジックで何パターンも比較したが結果は同じになった。

そのロジックを入れると劇的に速くなった。2手分ほど同じ時間で余分に読めるようになった。

まだ数十回しかやっていながだいたい、最終13手読みで1分弱、14手で1分~2分、15手で3分くらい。
ただ中断ロジックがまったく効かないパターンだと15手で10分かかった場合も。

中断ロジックを効率的に使うために最初の探索は最適手で打つ必要がある。

とりあえず中盤戦用の盤面ポイントのロジックでいい順に打つようになったらかなりの確率で最適手を最初に打てるようになった。
いいかげんな盤面ポイントなのではずれることも多いけど。

結局は中盤ロジックもきっちり作らないとだめかもしれない。

本棚から昔買ったオライリーの「アルゴリズムクイックリファレンス」という本が出てきたので読んでみた。

いまやっている終盤ロジックはミニマックス法と言って、相手の時も自分のときも中断していいと書いてあった。

ミニマックス法よりプログラムがすっきりして効率的なNegMax法というのがあるらしい。

が、自分のソースコードをNegMax法に置き換えるとMiniMax法より複雑になりそうな感じ。なんか作りが間違っているのかも。

色々載ってて真面目に全部読めばいいことがあるかも。


オライリーサイトにはPDF版もあった。Kindleで持ち運べていいかも。

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

2013/06/16

ばぶまん - VALHELL AV MANAGER - Ver.1.4.28リリース

 MPEG4の動画ファイルのサムネイルを取得できるように調整しました。

iOS, AndroidのDLNAクライアントはDivXのファイルを再生できないので、MPEG4でエンコードすることが増えました。
MPEG4は色々とファイルの種類が多いので、全部には対応できていないと思われます。

テレビで見るときはPS3、手元で見るときはiPhoneやKindleFireと色々と使っていると、同じMPEG4でも端末によって見れたり見れなかったり・・・Gomencoderのデフォルト設定エンコードだと全部で見ることができました。

動作確認はGomencoderで作ったデフォルト設定のエンコードファイルです。

Windows Vista SP1用に色々特殊な処理をしていたのがWindows7でも影響してMPEG4が読み込めなくなっていたので、Vista関係の処理をすべて取り除きました。そのためVistaでは動かないかもしれません。

ばぶまん のダウンロードはこちら

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

2013/04/14

オセロゲームを作る!序盤戦

 適当にコマを打ってたくさん棋譜データをためればいいかと思ったが、1分に10件くらいしか進まない。

さらに絶対にその手はないだろうという手も発生する。

Othe15

こんな手は使わないのでデータの無駄。

多少は考えて打つようにしないといけない。

ありがちな手として

1.各マスに得点をつける。
  角が100点、角のまわりはマイナス100点とか。

2.周りに相手の色が囲むように打つ。

3.相手の打てる場所を少なく、自分の打てる場所は多くなるように打つ。

序盤だとこんなもんかと。

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

より以前の記事一覧