« 2012年12月 | トップページ | 2013年6月 »

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)

オセロゲームを作る!基本動作を考える

データを圧縮するためと無駄な探査をなくすために、向きが違うだけのオセロ盤は同じものとして扱うようにする。

盤を回転させて4通り、鏡面反転させて回転さえ手4通り、計8通りは1つの盤とみなす。
Othe09
たとえば1手目は4か所置けるが

Othe01
回転0°

Othe02
回転180°

Othe03
鏡面反転して回転270°

Othe04
鏡面反転して回転90°

Othe10
そうすると1手目の結果は1通りで、2手目は3通りになる。

また、前の手は別の盤だが、結果は同じになる場合もある。
Othe11
これと

Othe12
これは

Othe13
結果は同じ。

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

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)

« 2012年12月 | トップページ | 2013年6月 »