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

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

スポンサーサイト

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

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

 今回は『置換表の実装』についての更新予定でしたが、番組を変更してインデックスによるチェックを紹介したいと思います。というのも、昨日バレ(ryで開発が進まなかったためです・・・。『置換表の実装』の更新を楽しみにされていた方、本当に申し訳ありません。。。


 さて、今までリバーシの置けるかのチェックについては2つ紹介してきました。『繰り返しによるチェック』と『再帰によるチェック』です。しかしこれらは、プログラムを見てもらったらわかると思いますが、条件判定(ifやfor,whileに代表される繰り返し条件判定)が多用され非常に重いものとなっています。

 余談ですが、一般的に条件判定は重いとされ、高速処理を必要とするときには、for文等の繰り返しは手動展開される等の最適化が行われます。例としては次のようなものです。

<<展開前>>
for(i = 0; i < 4; i++){
  sum += i;
}
<<展開後>>
sum += 0;
sum += 1;
sum += 2;
sum += 3;

 見てもらったら大体わかると思いますが、for文の処理内容をそのまま書き出していくだけで展開できます。このことにより、for文で毎回実行されていたインクリメント条件判定が省かれ、見た目のプログラムはダラダラと長いものになっていまいますが、処理が少し軽くなります。また、ココで注意していただきたいのは、この方法は今回例に挙げた4回などの固定回数の時のみ利用可能な方法です。『for(i = 0; i < N; i++){・・・}』のようなN回繰り返す場合等繰り返し回数が処理により変わる場合は展開できません

 話を戻します。↑のように説明した2つの方法ではどうしても処理が重くなってしまい、AIに実装するときにはあまり多くの盤面を作ることができず弱いAIとなってしまいます。

 そこで登場するのがインデックスを使用する方法です。リバーシでは縦に見ても横に見ても斜めに見ても石の並びの最大長は8です。←図21参照



図21:石の並びの最大長


ですから、ここで一列(要するに連続する8マス)について考えます。一つのマスについては白石黒石の3つの状態が存在します。そうすると、全て白の状態から、全て黒の状態まで、この一列について考えられる状態の総数は3の8乗(6561)となります。要するに、この6561個の状態全てについて、それぞれにインデックス番号を振り、黒は裏返すことができるか、白は裏返すことができるかという情報をあらかじめ作成し配列に入れておき、その情報を使ってチェックしようというのが今回のチェック方法です。この情報が入った配列のことをmobility tableと呼びます。ここでインデックス番号とは、この1列を白を0空を1黒を2とする3進数(処理を簡単にするために4進数で扱う場合もあるが、今回は3進数で説明する)で現した番号のことです。←図22参照



図22:mobility tableの情報


 しかしこれを使用するためには、横の全ての列、縦の全ての列、斜め(/方向と\方向の2つ)の長さが3以上の列(2以下の時は裏返すということができないため)についての全てのインデックス番号を計算する必要があります。毎回全ての列のインデックスを更新してたのでは、明らかに前回の方法の方が早いです。ここで用いる方法は、盤面配列とともに最初からインデックス情報も用意しておき、情報が更新されたとき(石を置いて裏返ったとき)にその部分だけの更新を行えば良いのです。
↑↑中途半端ですが、今日の更新はココまで↑↑



次回予告:インデックスによるチェック(後半)



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

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

コメントの投稿

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

トラックバック

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