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

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

スポンサーサイト

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

将棋の現状

 将棋の更新を最近していなかったので現時点の進行状況の報告ということで・・・。今のところ、猿になるかコンピュータになるかが決まるAI部分に着工しており、AIの基礎の部分はリバーシの時に使っていたPVS探索アルゴリズムを採用し、ハッシュ(置換表)を使って将棋特有の大量重複する枝をバッサバッサ刈っています。

 AIの指標として重要な探索速度は今のところ評価関数が駒特だけということもあると思いますが、AIを前提に考えたデータ構造で最初から設計したおかげで約2500K・node/secというWZebraもビックリの恐ろしい数値を記録することができました。

 データ構造としては関数ポインタ配列をかなり多用した構造になっており、移動できるかのチェック成ることができるかのチェック移動手の生成等全てをこれで行っています。

 今後の予定としては、基本的な探索速度の上昇を目指しMoveOrdering(αβにおける探索順の並び替え?)、その他詰み詰めろ必死王手の手の生成王手回避の手の生成等の終盤に関わる部分から作っていこうと思っています。それが完成すると、中盤及び評価関数、定石に入っていく予定です。探索方法も単純なPVSではまずいと思うのでそれは追々・・・・。


次回予告:終盤のアルゴリズム



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

おかげさまで現在プログラミング部門のランキング2位を死守しておりますm(。_。;))m
スポンサーサイト

ゲーム木と探索での評価値

 本日はゲームのAIの基礎、探索についての更新をしようと予定していましたが、それまでにゲーム木評価値について説明する必要がりました。。。

 まず、ほとんどの(?)ゲームはゲーム木という形でゲームの状態を表すことができます。○×ゲーム(3目並べ?)を使ってゲーム木というものを説明します。←図24参照



図24:○×ゲームのゲーム木


 かなり省略した形になりましたが、○×ゲームは上のようなゲーム木になることがわかるでしょうか?このゲーム木において両者が最善手を尽くした場合を探索するのがMinimax等に代表される探索です。しかし、ゲームの状態の数鼠算式に増えていき大変な数のゲームの状態が考えられるでしょう。単純計算すると○×ゲームの状態の数は

9×8×7×・・・×2×1 = 9! = 362880

という計算ができます。36万とか莫大な数ですよね・・・。まぁ実際は途中でゲームが終わったりするので何分の1かになるでしょうが、それでも多くの状態が考えられます。しかし、今のPCではこの○×ゲームを全て探索するのに1秒もかからないでしょう。よって、9手先(全てが埋まるか3目並ぶまで)まで全て読んでどちらも最善手を尽くした場合を考えることができるでしょう。

 しかし、リバーシや将棋となるとゲームの状態の数は天文学的数字になるでしょう!!このゲームを最後まで読んで最善手を出していては地球が終わっても計算が終わらないのでは・・・(汗 そこで、ある程度先、例えば4手先まで読んで評価値というものを計算して返してやります。評価値というのは普段ゲームしているときに感じると思いますが、ゲームの途中で有利、不利、互角など感じるように、コンピュータにもそれを評価値として計算させます。これにより、最後まで読まなくても評価の有利・不利により探索することができます。

 この○×ゲームに関しては自分が2つ並んでいて相手に妨害されていない場合は評価値が高いのではないでしょうか?逆に相手がその状態ならば低くなるはずです。途中で自分の勝ちが見つかれば非常に大きな数を評価値として返し、負けの場合は低い数を返せばいいのです。


 次回は実際にMinimaxの探索についてどのような手順で探索するかについて説明します。それ以降、Minimax以外の効率の良い探索方法も紹介していきます。


次回予告:Minimaxアルゴリズムを使って探索する



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

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

インデックスを使って裏返す

 今日は前回の応用インデックスを使って裏返す方法を説明します。これも、インデックスを使うことにより無駄な処理をせずに裏返すという操作をすることができます。

 方法は、mobility tableに裏返すための情報を追加するだけ。前回は8つの場所について黒白がそれぞれ裏返せるかの情報を入れただけでしたが、そこにその点について右方向、左方向にそれぞれ何個の石を裏返すことができるかという情報をいれるのです。簡単ですね!

 これがあると、4つのインデックスについて2つの方向、計8つについて指定された回数だけ繰り返して裏返すだけです。相手の石であるかとか、壁であるかとか全く関係ありません

 後は、ソースの方で!!今回はチェック、裏返しについてのソースです。


参考ソースファイル

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



ついに本命の思考部分です
次回予告:Minimaxアルゴリズムを使って探索する



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

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

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

 今回は前回の続き!前回説明するのを忘れていたが、インデックスを使用したチェックには壁が必要ない!だから単純に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

置換表の実装とハッシュの基礎

 今回は将棋では必須とも言える置換表についての更新です。

 将棋の盤面において、『王』等を動かして、前回の位置に戻したりしていると、無限に同じ手を繰り返すような場合が考えられる。また、AIを考えるときに、今までに探索した盤面が出てくると無駄な処理になってしまう。そこで、置換表という方法を使い一度探索した盤面は置換表に登録しておき、今後その盤面が出てきた場合は前回探索したときに評価を返す仕組みを作ります。

 置換表にはハッシュという方法を使用し実現します。ハッシュには様々な種類が存在しますが、今回はチェインハッシュによる置換表の説明をします。←図23参照



図23:チェインハッシュの構造


 ここで、ハッシュ法というのは、探索に用いられるデータ構造の一つで、特徴としては、データの個数によらずに挿入、探索、削除の操作を実質的にO(1)つまり一定時間で行える優れています。原理としては、キー値を、データが格納される位置(配列の添え字の値)に直接関連付けてしまうというものです。ハッシュの簡単な例を次に示します。

 大きさ11のハッシュ表でキー値は格納する値を11で割った余りとします。そこに例えば7、23、68を格納すると次の図24のようになります。



図24:ハッシュの構造


 上のように格納する値7,23,68をそれぞれ11で割った余りはそれぞれ、7、2、1となりそれぞれその場所に格納される。そうすると探索する際に、例えば23が格納されているか調べてみる。キー値はデータを11で割った余りなので、ハッシュ番号1をを参照する。すると23が格納されていることがわかる。

 しかしココで、34を格納する場合キー値は1になるので23とキー値が重複してしまいデータが上書きされてしまう。これを衝突という。そこで先ほど紹介したチェインハッシュというデータ構造を使う。チェインハッシュは連結リストをハッシュの大き分だけ使ったような構造で、衝突が発生した場合リストの最後尾にデータを追加するような構造になっている。探索する場合は、キー値を計算しポインタでつながれたデータを順番に探索していくような手順になります。


 将棋の話に戻しますが、この置換表を将棋に実装する場合、キー値のとしては盤面の駒の位置と持ち駒からなるべく衝突が起こらないような計算方法(計算時間のかからない単純なもの)を考える必要がある。

 この置換表の実装が完了するとようやくAIのほうに取り掛かることができる。しかし、この置換表で手を抜くと強いAIは期待できないので実装は慎重に行いたい。



次回予告:探索による思考



↓現在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

打ち歩詰め&Undo機能


今度こそ
ルール完成


 前回の更新で完成していなかった『打ち歩詰め』が完成しました。打ち歩詰めチェックの手順としては、手持ちの歩で相手に王手をかけた場合その歩を王以外の駒で取ることができれば打ち歩詰めではないので置くことができます。王以外の駒で取ることができない場合、王が逃げる場所があれば>打ち歩詰めではない逃げ場所がなければ最終的に打ち歩詰めとうい判定になります。

 実際に打ち歩詰めを行ったときの実行画面を以下の図20に示します。



図20:打ち歩詰めの実行画面


 実際にあらゆるパターンで打ち歩詰めのチェックをしたわけではありませんが、一応完成ということで(汗


 あと今回の更新で新たに追加したUndo機能については、毎回駒を移動したり打ったりした情報をSASHITE構造体にまとめスタックにプッシュしていき、undo関数が呼び出されたときにスタックの情報をポップし元に戻す方法をとっています。←図21参照



図21:Undo機能


 今まで実行画面を見せてきましたがこの実行画面についてのコマンド入力方法の説明が抜けていました(人・∀・)


というわけで突然
コマンド入力方法の説明


・「○手 > 」 とプロンプトが表示されている場合はカンマ形式で『77,76』という風に入力します。この意味としては、座標7七の駒を座標7六に移動するという入力になっています。

・手持ちの駒を打つ場合は『0,76』という風な感じに入力します。大体分かるかと思いますが、手持ちの場合は最初の値を0にし、次の値にどこに打つかを入力します。また、最初の値を0にした場合、「1:角 2:飛 3:香 4:歩 5:桂 6:銀 7:金 > 」という感じのプロンプトが表示され、どの駒を置くかを聞かれます。該当する番号を入力するだけです。

・Undoについては入力を「0,0」とするとUndoされます。



次回予告:置換表を実装



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

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

ルール完成!?

ルール完成!!!?


 一応現在のところ前回の予告通りの『持ち駒の利用』『成る』、の他に『二歩』と『打ち歩詰め』のルールを実装することができました。しかし、王を取る(詰む)と終了というルールをまだ実装していないので、それだけ実装すれば基本完成かな??(イヤ勘違いしてました・・まだ打ち歩詰め完全に完成してません↓↓↓)

 あと現在CUIで実現しているため、成った状態を表現する方法に悩んだ・・・。『歩』は『』でいいが、『香』『桂』『銀』はどのようにすれば良いものか(´・ω・汗)ゞ まぁCUIは今のうちだけなので自分にだけ分かればイイや~と思い、『香』は『』、『桂』は『』、『銀』は『』という風にこじ付けに近いがこのように表現している。。。



図19:ルール一応完成


 また、2歩のチェックには先手、後手にそれぞれ2歩フラグ用の配列を用意しフラグが立っている場合は手持ちから置く事ができない。そして、歩を取った場合、成った場合にはフラグを下ろして歩が置けるようにしている。



次回予告:置換表を実装



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

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

駒の移動

 今回は駒の移動機能が完成したのでそれについての更新。

 予定通り、駒へのポインタテーブルの値の交換により、駒の移動を実現することができた。←図17参照



図17:駒の移動


 また、相手の駒を取る処理も出来上がっています。取ったときは自分の持ち駒リストに追加し、次に利用できる状態にしている。実行画面の下のほうに出ているのが先手,後手のそれぞれの持ち駒リストです。←図18参照



図18:相手の駒を取る


 ここである座標の駒をある座標に移動できるかのチェックを行った後に移動することを前提としているので、移動できるかのチェック関数を設ける必要がある。

 そこで、移動できるかのチェックは駒ごとに別々のチェック関数を作り、それを関数ポインタ配列から呼び出すことにより処理の単純化を行った。駒構造体には成り状態も含めて(全部で14種類)1~14のIDが割り振られている(ここで王と玉は同じ種類と考えている)。そのIDを配列のインデックスとして呼び出す構造にしている。



次回予告:持ち駒の利用&成る



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

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

将棋の基盤

 今回は将棋の現在の進行状況について報告します。

 今のところ『盤面の基礎』+『ある駒をある場所に移動できるかのチェック』までの完成(?)となってます。リバーシの知識を十分に生かしてAIのことを考えて盤面のデータ構造を考えながら作っています。目に見える完成度としては『盤面と駒の表示』ができるのみです。



図16:将棋進行状況1


 データ構造はハッキリと決定はしていませんが現在のじょうたいは、盤面の1つ1つの駒をKOMA構造体とし、盤面ではその駒へのポインタの配列とし、移動する際はそのポインタを交換するような構造にしています。

 他、自分の盤面上の駒及び手持ちの駒双方向リストで扱い、それを使いAIで自分の移動できる駒、手持ち打つことのできる駒を次々に打っていく事ができる構造になっている(つもり)です。

 次は『駒の移動』ができたときに将棋の方の更新をしたいと思います。。。



というわけで・・・
次回予告:駒の移動



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


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

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

 『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]



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



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



改将棋基礎の基礎

 アベントさんから指摘を受け前回の壁の件について訂正したいと思います。

 前回2マスの厚みの壁を設ける必要があると断言してしましましたが、『2段目以内に駒を進めるときは必ず成らなくてはいけない』というルールが存在し2マスの厚みの壁を設ける必要がありません。。。
(もっと将棋の勉強をしましょう・・・↓↓↓)

 これにより下の図14のように1重のだけを設ける設計で将棋AIを作っていきたいと思います。



図14:(改)将棋の基本盤面





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


将棋基礎の基礎

 今日は将棋AIの更新!!と行きたいところだけどなかなか難しくて進みません。。。現在の進行状況を報告します。

 今の予定としては、AIのことを考え駒を双方向リストで扱う予定です。将棋の場合、『駒をどう動かすか?』というのが一つの手になるので、全ての駒を双方向リストにして扱うと楽ではないかという理由(汗)

 盤面は、リバーシと同じように盤面を配列として扱う。2次元配列を使うか、1次元配列を使うかだが、配列のインデックス計算の量の考えるとやはり1次元配列のほうを使いたくなる。

 そして、盤面の周りに壁を設けるわけだけど、リバーシの場合と違って変な動きをする駒が多数存在する。『桂馬』や『飛車』『角将』に代表する『飛び駒』等である。『飛び駒』の場合はそれらを、別リストとして扱い、一歩しか動けない駒との処理を完全区別する。が、問題は『桂馬』です。桂馬は2マス先の右か左に動けるという特殊な動きをするので、壁を考えると前後に最低2マスの厚みの壁を設ける必要があることがわかる。左右の壁については、特に気にする必要がないと思うが、一応左右についても2マスの厚みの壁を設けることにする。これはタダ、縦と横のサイズを同じにしたかったという単純な理由も含まれている・・・



図13:将棋の基本盤面




今後の予定
盤面を作る
駒を双方向リストで扱う
Undo(一手戻せるようにする)

これはAIを作る時に重要になってくるポイントで、毎回駒を進めて打っていくわけだが、全ての操作を1つの盤面で行います。なぜなら、毎回盤面を作っていては重すぎてやっていられないからです。そこで、前回打った手を戻して前の盤面に戻すという操作が重要になってくる。



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

再帰によるチェック

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

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

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

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



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


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

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

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


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

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

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



参考ソースファイル

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

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



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



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



繰り返しによるチェック

 裏返せるかどうかのチェック方法にはさまざまな方法があるが今回は繰り返しを使ったチェック方法を紹介します。

 でも、どんなチェック方法においても同じことは『挟めれば置くことができる』という超基本的なルール。←図8参照



図8:石を挟んだ状態


 これをプログラムとして実装するには次の方法が一般的ではないだろうか。まず、1方向について考えます。その1方向について調べていき、相手の石の間繰り返し最後に自分の石があれば裏返せるという関数(checkSub)を作る。←図9参照



図9:checkSubのフローチャート
増分についてはコチラで説明しています。


 次に、この関数を各方向(8方向)について呼び出す関数(check)を作れば完成である。←図10参照



図10:checkのフローチャート


 このように2つの関数を使うと簡単にチェックを作ることができる。これは1次元配列のときも②次元配列のときも、壁のある場合に使用できる方法である。

 しかし、ここでハマることが頻繁にあります。それは置いた場所の次に自分の石がある場合です。checkSubを注目すると、まず引数として置いた座標と調べる方向の増分を渡す。ここでの繰り返しは後判定になっていて、まず増分を増やすことになる。次に自分の色が来たので、繰り返しから抜けて、条件判定で裏返せる(true)という判定になってしまいます。←図11参照



図11:失敗例


 ここでこの問題を解消するには、checkSubを呼び出す時に『次の石が相手の石の場合』という条件を付ける必要がある。また、この条件を入れることで次の石のチェックはできていることになるので、checkSubを呼び出すときの座標に増分を足しておくと無駄な処理がなくなります。



図12:checkの改良版フローチャート
クリックすると大きな画像が見れます




参考ソースファイル

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

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



次回予告:再帰によるチェック



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



1次元配列の盤面表現

 今回は1次元配列のときの盤面表現についてです。

 1次元配列の場合は次の図5のように8×8の盤の回りに2次元配列の時とは少し違った歪な形の壁を設けます。



図5:1次元配列の盤面表現


 この歪な形の壁にはちゃんとした意味があります。次の図6のように1次元配列で盤面を表現した場合、配列の番号は0~90の合計91の要素を持つ配列を宣言することになります。



図6:1次元配列の配列要素番号


 上の図6より、次のことがわかります。ある点、例えば配列番号50から見て、左上は40であり-10した番号になると思います。同じように上は-9、右上は-8・・・右下は+10という風になり、これをまとめると下の図7のようになります。



図7:8方向への配列番号の増分


 ここで、これで本当に機能するのかと疑問に思った方もいるんじゃないでしょうか?

 例えば、配列番号44(H4)について考えてみみようと思います。左上,上,左、左下,下方向については-10,-9,-1,+8をすると,34(G3),35(H3),43(G4),52(G5),53(H5)であり、問題ありません。残りの右上,右,右下方向についても同じように考えてみます。各-8,+1,+10をすると、それぞれ36(壁),45(壁),54(壁)であり、正常に壁が機能していることがわかります。



参考ソースファイル
board2.h [DL]
board2.c [DL]




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

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