羊の人工知能研究 ~将棋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

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

 今回は『置換表の実装』についての更新予定でしたが、番組を変更してインデックスによるチェックを紹介したいと思います。というのも、昨日バレ(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

チェックと裏返し処理を一度にする

 今回は『チェックと裏返し処理を一度にする』というタイトルですが、一見意味のないようなことに思えますが、実はとても意味のある処理です。

 『checkを行ってmoveをする』のとどう違うのかというと、実は一気にすると少し処理が軽くなるんです!!実現方法としては『再帰を使ったチェック』と『再帰を使った裏返し』を足したような感じです。処理の簡単な図解としては次の図15のような感じです。



図15:チェックと裏返し処理を一度にする処理の図解


 わかりずらいですが、上の図のようにチェックに裏返すための機能を付けただけなので、再帰を1回するだけで、チェックと裏返すという操作が一気にできてしまいます。また、裏返せないときは末端から裏返せない(FALSE)が返って来るのでそのときは何もしなければよいだけなのです。これならば、check関数を実行してmove関数を実行するのと比べて1度の再帰で一気に2つの操作を実現することができます。

 また、今回紹介した『チェックと裏返し処理を一度にする』という操作はAIを作るときにとても有効です。しかし、現在私のリバーシはチェックや裏返しに繰り返しや再帰などのアルゴリズムを使っておらず、別のものを使っています。それがインデックスによる方法です。それは次回から紹介していきたいと思います。



参考ソースファイル
2次元配列の場合
board11.h [DL]
board11.c [DL]

1次元配列の場合
board12.h [DL]
board12.c [DL]



次回予告:将棋の基盤①



↓読んだらクリックお願いします↓


繰り返し&再帰による裏返し

 今回は裏返す方法について紹介します。

 まずは繰り返しによる裏返し。!基本は繰り返しによるチェックとほとんど同じ!!move_subという一方向にだけ裏返す関数を作り、それをmoveという関数から8方向について呼び出すだけです。処理内容としては、チェックの時の処理に加えて、自分の石に書き換えるという処理、指定した場所に自分の石を置くという2つを付け加えるだけです☆また、move関数は裏返したい方向にチェックをし、裏返せると判断したら裏返すという処理を行います。

 次に再帰による裏返しを紹介します。これも再帰によるチェックとほとんど同じ!!これも、!!move_subという一方向にだけ裏返す関数を作り、それをmoveという関数から8方向について呼び出すだけです。move関数は繰り返しの時と全く同じで、check_subは裏返せるということを前提として処理をするので相手の色の間再帰し、自分の色に書き換えるだけです。


 今回はすごく簡潔に書きましたが、チェックを理解していれば容易にできますので、わからなかったらチェックの方を理解しましょう。



参考ソースファイル
<繰り返し>
2次元配列の場合
board7.h [DL]
board7.c [DL]

1次元配列の場合
board8.h [DL]
board8.c [DL]

<再帰>
2次元配列の場合
board9.h [DL]
board9.c [DL]

1次元配列の場合
board10.h [DL]
board10.c [DL]



次回予告:チェックと裏返し処理を一度にする



↓読んだらクリックお願いします↓



再帰によるチェック

 今回は前回と違って再帰によるチェックの方法を解説します。

 再帰は慣れないと難しいが、繰り返しを使うより簡単に設計できるばあいがあります。重要なのは末端での処理をどうするかということです。

 今回も『挟めれば置くことができる』という超基本的なルールを元に考えます。

 再帰といっても、考え方は同じです。今回もまず一方向について裏返す処理をつくります。←図13参照



図13:checkSubのフローチャート(再帰)


 これは、このフローチャートを見れば大体わかるように、相手の石なら再帰呼び出しをしてその戻り値を返し、自分の石が来たらtrue(置ける)を返す、それ以外ならfalse(置けない)を返すようになっています。基本は前回と同じですよね・・・(汗

 あとはこれを前回と同じようにcheck関数から各方向について呼び出す
だけです。

 と、今回と前回との違いはcheckSubのアルゴリズムだけであり、各関数の役割、呼び出し方(引数、返り値)は変わっていません。


 今回と前回で2つの裏返すアルゴリズムを紹介しました。このリバーシなどの人工知能アルゴリズムでは計算速度がかなり重要なポイントです。自分でこの2つのアルゴリズムについて計算速度の計測を行ってみました。

 予想では再帰のほうが、関数呼び出しによるスタック操作が重いと感じ遅いと思っていましたが、繰り返しよりも少し早い結果となっていました。VCを使っているので再帰関数が繰り返しに最適化されたかわかりませんが・・・

 まぁこのように一つの操作についても様々なアルゴリズムを考案し、速度計測をし、地道な努力をするのがこの研究の重要なポイントとなってくるのではないでしょか!



参考ソースファイル

2次元配列の場合
board5.h [DL]
board5.c [DL]

1次元配列の場合
board6.h [DL]
board6.c [DL]



次回予告:将棋基礎の基礎(そろそろしないとね・・・)



↓無料でクリエイター診断できます結構イイ↓



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