羊の人工知能研究 ~将棋AI開発の日々~

将棋、リバーシのAIプログラミングを中心にその開発過程及び記録を頑張って更新していきます。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

インデックスによるチェック(後半)

 今回は前回の続き!前回説明するのを忘れていたが、インデックスを使用したチェックには壁が必要ない!だから単純に8×8の要素を持つ2次元配列又は、64の要素を持つ1次元配列で表現できる

 まず、前回あやふやに説明したインデックスの更新について説明します。繰り返しになりますが、インデックスは0:白,1:空,2:黒とする3進数8桁の整数で表現する。インデックスは横,縦,右上(左下),右下(左上)の4種類が存在し、盤面の1つのセルの状態が変わるとそれについて4つのインデックスの更新が必要になる。インデックスの取り方は人によって様々だが、私は以下のようなインデックスを取って計算している。



図23:4つのインデックス


 上を見たらわかるように、インデックスは4種類、計38(8+8+11+11)からなっている。ここで、index1[4]の場合だと、左から順番に3進数の8桁目,7桁目,・・・,1桁目となっている。例えば、左から順にととなっていると、空黒黒白黒白空空なので、3進数で表すと12202011となる。説明する必要もないとおもうが、10進数に変換すると、

1×37+2×36+2×35+0×34+2×33+0×32+1×31+1×30=3103

となり、index1[4]=3103;となる。要するにインデックス番号3103となり、mobility tableの3103番目を参照するとどこに置くと裏返せるという情報が参照できる。

 更新については、次の図24の場合を例に挙げて説明する



図24:例


 先ほど説明したようにこの状態のときindex1[4]は3103となっている。この状態で黒がG5に石を置いた場合を考える。まず置いた情報を更新する必要がある。それは実は簡単で、





となるわけだから、計算式は


1×37+2×36+2×35+0×34+2×33+0×32+1×31+1×30

1×37+2×36+2×35+0×34+2×33+0×32+2×31+1×30


となる。差分としては、1×31足せばよいことがわかる!!また、白を置いた場合は1×31引けばよいことがわかるだろうか?これをあと、縦のindex2[6]、右上のindex3[8],index4[4]についても同じように更新すればよいだけである。あと、裏返る場所については黒が裏返す場合石は白→黒となるので、2×3nを足せばよい。また逆に、白が裏返す場合石は黒→白となるので、2×3nを引けばよい。(nはインデックスのを3進数から10進数に変換するときの指数である。)

 これらのことより、このインデックスを使う利点は、チェックするときそのセルについての4つのインデックスを調べるだけ要するに、4つのif文だけでチェックができます。しかし、毎回のインデックスの更新にかかるオーバーヘッドはありますが、断然処理が早くなります。

 かなり曖昧な説明になってしまったが、後はソースの方で確認してください。(解読するのが大変かも・・・)


参考ソースファイル

1次元配列の場合(mobility tableの初期化のみ)
board13.h [DL]
board13.c [DL]


次回予告:インデックスを使って裏返す



↓現在2つのランキングに参加しています↓

クリックしたら投票されるみたいなので、明るい一票をお願いします(m。_。)m
スポンサーサイト

コメントの投稿

URL
コメント
パスワード
秘密
管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://hitsujiai.blog48.fc2.com/tb.php/16-8e5c3726
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。