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/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/04/14

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

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

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

Othe15

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

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

ありがちな手として

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

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

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

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

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

2013/04/13

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

30年前だとラスト10手くらいしか読めなかったが、今のCPUだとどこまでいけるか・・・。

終盤ロジックは単純で打ち手を全部ためして一番多く取れる手を選択するだけ。

一番多くと言っても自分の番のときの話で、相手は相手で一番多く取れるように打ってくる。

Othe14

図のようになる。

一番下から最終手が白だとすると白、黒ともに自分が一番多く取れるようにたどっていく。(赤い線)

やってみたら、ラスト12手の探査に20秒くらい、ラスト13手だと2、3分。ちょっと実用的ではない。
ラスト13手の候補の数 x 20秒くらい(ラスト12手の時間)探査にかかるとすると、3手以内の場合だけ全読みをするとか調整が必要かも。

30年前の時は探査途中で中断するロジックを入れていたような気がするけど、思い出せない。

相手の色の時(図だと白の時)、その時点の最多コマ数を下回るコマ数が出たときに探査を中断してもいい気がする。
試に組み込んでみたらラスト14手全読みが20秒くらいでできた。

ロジックに間違えがないかちと自信がないが・・・。

自分の色の探索中も中断できないかな。

<追記>
探索中断を効率よく行うために、盤に優先順をつけてよさげな位置から探索するようにした。
平たく言うと4つ角から探索、そのあと辺を探索。

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

2013/04/11

オセロゲームを作る!データ構造を考える

 たくさんの打ち手をデータベースにため込むので、効率的なデータ構造を考えてみる。

まずオセロ盤データ。8×8マスで黒と白の駒と空白。一マス2ビットで表せる。

2bit×64マス= 128ビット

64マスあるので組み合わせは2の64乗・・・10京くらい?(兆の次は京だったっけか・・・)
さらに空白のマスを考えるとその60倍・・・。

オセロ盤データにIDを振るのでIDに64bit(LongInt)。

オセロ盤データが何手目のデータを持たせたい・・・60手まであるのでTinyIntかな。
1手目と2手目を同時に参照する必要はないからテーブルを分けちゃえばいいかな。

ということでテーブルを61個作成。

create table オセロ盤(1目~60手目 + 最後の盤) {
オセロ盤ID: LongInt(64bit) (プライマリキー、自動連番かな)
コマ黒前: Int(32bit) (Delphi6で作る場合32bitまでしか扱えないので) 
コマ黒後: Int
コマ白前: Int
コマ白後: Int
}

次にどこに打ったかというデータを保存するので必要な項目は
オセロ盤ID・・・どのオセロ盤に対応する手か
打つ場所・・・1 - 64のどこか(オセロだとA1 - H8というらしい)
次のオセロ盤ID・・・打った結果、どのような配置になるか
色・・・白か黒か
何手目か
最多コマ数・・・ここに打った時に何コマ取れたか
最少コマ数・・・初手から数手は最多64、最少0で落ち着きそう
何回勝ったか・・・ここに打った時の勝つ確率(勝ち数 - 負け数でいいかな?)
探索完了フラグ・・・その手から派生する全手を探索したらフラグをたてる。

オセロ盤と同じで1手目と2手目を同時に参照することはないからテーブルをわけてもいいかも。
白と黒も同時参照はないからいらない。

create table 打ち手(1手目~60手目) + (黒か白) {
 オセロ盤ID: LongInt(64bit)・・・プライマリキー
打つ場所: TinyInt(8bit)・・・プライマリキー
 次のオセロ盤ID: LongInt
 最多コマ数: TinyInt
 最少コマ数: TinyInt
 何回勝ったか: Int(32bit) 足りるか?
 探索完了フラグ: False or True(1bit)

テーブルは120個・・・1手目は黒しかありえないし、2手目は白しかありえないが・・・

DBは何にしよう。

仕事で使い慣れたOracleとかSQL Serverにしたいが趣味で使うには高すぎる。
Express版だとDBサイズが2GBまでらしい。

しかし、本気で全手探索をしたらペタバイトのディスクがいる。

とりあえず無料の MySQLでも使ってみるかな。

しかしDelphiだとODBCでしか接続方法がなくて遅そう。OracleならOCI、SQL ServerならADOが使えるのに。。。

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

オセロ(c)ゲームを作る!初回構想

 30年くらい前に一度作ったけど、CPUとかも速くなたったのでもっとすごいのが作れるかもしれない。

以前
マシン:PC9801 CPU:V30(80186) 10MHz, メモリ 640KB
開発言語: N88ベーシック + マシン語
目標: 自分に勝てるオセロ

ロジック:
序盤は適当に打って(どうやたか忘れた)、ラスト10手くらいから最後まで先読み(5分くらいかかった)。
とりあえず自分ではCPUに歯が立たなくなったので開発終了。


今回
マシン;VAIO CPU COREi7 2.4GHzくらい?(あまり気にしていない) メモリ 8GBくらい?
開発言語: 何にしよう。慣れたDELPHIにするか、PHPとかJAVAとかいまどきのにするか・・・
目標: ちまたのオセロプログラムに勝!

ロジック:
序盤の打ち方をデータベースにいっぱいためこんで、勝つ確率の高い手を打つ。
どうせなら全パターンをDBにためこみたいなぁ。

ラストはCPUパワーが上がったので、だいぶ手前から最後まで先読みできそう。
ムーアの法則によると18か月で2倍に性能が上がっているので、30年で40倍くらい?


自分自身のオセロの強さは
小学生のころ・・・団地で一番強く、近所の大人にも負けたことがなかった
中学生以降・・・オセロはだれにも負けない!という奴と勝負して勝てたことがない
         オセロは強くないという奴には負けることはなかったが・・・。
         ・・・つまり弱かった?
今・・・スマートフォンのオセロアプリにも勝てん!

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