コンピュータ将棋の内部解説 指し手生成部
Novice_miniの指し手生成部を解説する。
Novice_miniはこちらからDLして参考にして頂きたい。
コンピュータ将棋プログラム「Novice」開発室 プログラミング初心者用の将棋ソフトソース公開
指し手生成部はsearch.hにある。
gen_move() が盤上の駒を動かす手、gen_utu() が持ち駒を打つ手の生成部である。
Novice_miniは盤面情報を一次元配列で持っており、持ち駒には二次元配列を使っている。
ではソースコードの解説をしていく。
if(turn==0){
for(a=0;a<111;a++){
if(board[a]>0 && board[a]<16){
if(board[a]==SHI || board[a]==SRY){
・
・
・
まずここであるが、
turn は、今から指し手を生成する側(先手 or 後手)。
for(a=0;a<111;a++){
は、盤上の状況を一つずつ調べていくためのループである。
if(board[a]>0 && board[a]<16){
は、board[a]にある駒(または空白)が自分のものであるかの確認。
あとはboard[a]の駒に応じて指し手を生成していく。
for(b=0;b<12;b++){
if(CanGo[b][board[a]]==1){
int To=a+Direct[b];
if(board[To]==WAL || (board[To]>0 && board[To]<16))continue;
if(board[a]==SFU || board[a]==SKY){
・
・
・
飛び駒(香・角・飛・馬・龍)に関しては個々に生成したが、それ以外は一般化することが出来る。
その部分が上のソースである。
これは事前にCanGoに12方向(通常8方向+先手桂馬2方向+後手桂馬2方向)を登録しておき、元の位置からその方向に動けるかを12方向について調べるものである。
CanGoはKomaMove.hにて定義してある。
int CanGo[12][31]={//その方向に進めるか否か(進めるなら1、進めないなら0を返す)
// 11
{
0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1,
0,0,0,1,1,0,0,1,1,1,1,1,0,0,1
},
・
・
・
たとえば、これは元の位置から11の方向、つまり右斜め下に動けるかについての情報を入れた配列である。
Novice_miniでは
先手の駒はSFU=1、SKY=2、SKE=3・・・SUM=14、SRY=15
後手の駒はEFU=16、EKY=17、・・・・・・・・・・・・・・・ERY=30 と定義されている。
なので、この場合CanGo[0][1]は先手の歩が右斜め下のマスに動けるかを示している。
故にCanGo[0][1]は0を返し(先手歩は右斜め下には動けない)、CanGo[0][4]は1を返す(先手銀は右斜め下に動ける)のである。
そして、CanGoを参照した際に、1が返ってきたら(その方向に動けたら)
元の位置座標にDirect[](移動量)を足して動ける可能性のある先の座標をToに保存する。
これが
if(CanGo[b][board[a]]==1){
int To=a+Direct[b];
の部分。
しかし、もしboard[To](移動先)が自分の駒だったり、壁(盤外)ならば進めないので、そこで次の移動先を検討する。
これが
if(board[To]==WAL || (board[To]>0 && board[To]<16)) continue;
の部分。
移動できるのが分かったら、
構造体に指し手の情報を保持して次の指し手を探す。
teBuf[teNum].From=a; (移動元)
teBuf[teNum].To=To; (移動先)
teBuf[teNum].Koma=board[a]; (移動する駒)
teBuf[teNum].Cap=board[To]; (その移動で取る相手の駒種(取らないなら0))
teBuf[teNum].Utu=0; (その手が駒を打つ手か否か。)
teBuf[teNum].Pro=0; (成るか否か)
teNum++;
基本的には、これがNovice_miniの指し手生成の大枠である。
あとはこれに成らなければならない場所(例えば先手歩なら1筋など)では成る手のみを生成したりする条件を足したものなどの部分である。
ここで示したのは、盤面を配列で管理した場合の一例のものである。そして、その中でも遅いものであると言える。そのため改善点が多く有るため、この記事を読んでいる方には色々と改良して高速化できることを是非体験してもらいたい。
※現状のNoviceでは速度向上のために、構造体の数を減らす、最低限のループにする、など
複数の改良を施している。(初期局面で 約30万/sec→約120万/sec まで向上。)