プチ将棋

３ヶ月ぶりにしれっと更新してみます。

去年から、Bonanzaを5×6マスの将棋盤に対応させる、ということをやってきました。

前回の更新で、コマンドプロンプト上で対局できるようにはなっていたのですが、
プチ将棋という将棋GUIで対局できるようにしてみました。

プチ将棋は、
「任意の大きさの盤面と開始局面で対局することのできる将棋GUIプログラム」です。

（リンク先より抜粋）

USIプロトコルに対応している思考エンジンを登録することで、
思考エンジンとの対局が可能です。

さらに、任意の大きさの盤面と開始局面に対応した、
sspという思考エンジンまで用意されています。
sspは、こちらのページの、「任意盤面、マルチプロトコル対応GUI プチ将棋」の
「インストール方法」からダウンロードできます。

ということで、Bonanza 56shogiとsspを対局させてみました。
（注　fv.bin不使用、評価関数は自作。
わたしの勉強のため、探索部分を簡略化してます）
持ち時間はなし、１手２０秒です。

初期配置。

途中図。

Bonanza 56shogi、２枚の自陣角で受ける。

結果は１４４手（！）で、sspの勝ち。

せっかくなので、棋譜を貼っておきます。
プチ将棋にコピペすれば並べることができます。

開始日時：2015/01/23 9:45:34
先手：56bona
後手：ssp
後手の持駒：なし
５ ４ ３ ２ １
+---------------+
|v飛v銀v玉v金v角|一
|v歩v歩v歩v歩v歩|二
| ・ ・ ・ ・ ・|三
| ・ ・ ・ ・ ・|四
| 歩 歩 歩 歩 歩|五
| 角 金 玉 銀 飛|六
+---------------+
先手の持駒：なし
*成り段=3
先手番
手数----指手---------消費時間--
1 ３四歩(35) (00:20/00:00:20)
2 ２三歩(22) (00:20/00:00:20)
3 １四歩(15) (00:20/00:00:40)
4 ５三歩(52) (00:20/00:00:40)
5 ４四歩(45) (00:20/00:01:00)
6 ５四歩(53) (00:20/00:01:00)
7 ５四歩(55) (00:20/00:01:20)
8 ５四飛(51) (00:20/00:01:20)
9 ３五銀(26) (00:20/00:01:40)
10 ２二金(21) (00:20/00:01:40)
11 ５五歩打 (00:21/00:02:01)
12 ５三飛(54) (00:20/00:02:00)
13 ４五角(56) (00:20/00:02:21)
14 ５二飛(53) (00:20/00:02:20)
15 ２六飛(16) (00:20/00:02:41)
16 ３三歩(32) (00:20/00:02:40)
17 ２四歩(25) (00:20/00:03:01)
18 ３二銀(41) (00:20/00:03:00)
19 ２三歩(24) (00:20/00:03:21)
20 ２一金(22) (00:20/00:03:20)
21 ２四銀(35) (00:20/00:03:41)
22 ３四歩(33) (00:20/00:03:40)
23 ３四角(45) (00:20/00:04:01)
24 ５三飛(52) (00:20/00:04:00)
25 ４五金(46) (00:20/00:04:21)
26 ３三歩打 (00:20/00:04:20)
27 １六角(34) (00:20/00:04:41)
28 ５一飛(53) (00:20/00:04:40)
29 ４六玉(36) (00:20/00:05:01)
30 ２二歩打 (00:20/00:05:00)
31 ２二歩成(23) (00:20/00:05:21)
32 ２二角(11) (00:20/00:05:20)
33 ３四歩打 (00:20/00:05:41)
34 ３四歩(33) (00:20/00:05:40)
35 ２三歩打 (00:20/00:06:01)
36 ３五歩成(34) (00:20/00:06:00)
37 ３五銀(24) (00:20/00:06:21)
38 １一角(22) (00:20/00:06:20)
39 ２四銀(35) (00:20/00:06:41)
40 ３三歩打 (00:20/00:06:40)
41 ５六玉(46) (00:20/00:07:01)
42 ４一玉(31) (00:20/00:07:00)
43 ４六玉(56) (00:20/00:07:21)
44 ２二歩打 (00:20/00:07:20)
45 ２二歩成(23) (00:20/00:07:41)
46 ２二金(21) (00:20/00:07:40)
47 ２三歩打 (00:20/00:08:01)
48 ２一金(22) (00:20/00:08:00)
49 ５六玉(46) (00:20/00:08:21)
50 ３一玉(41) (00:20/00:08:20)
51 ３六飛(26) (00:20/00:08:41)
52 ５三飛(51) (00:20/00:08:40)
53 ３五歩打 (00:20/00:09:01)
54 ２二歩打 (00:20/00:09:00)
55 ３四歩(35) (00:20/00:09:21)
56 ３四歩(33) (00:20/00:09:20)
57 ３四角(16) (00:20/00:09:41)
58 ３三歩打 (00:20/00:09:40)
59 ２二歩成(23) (00:20/00:10:01)
60 ２二金(21) (00:20/00:10:00)
61 １六角(34) (00:20/00:10:21)
62 ２三歩打 (00:19/00:10:19)
63 １五銀(24) (00:20/00:10:41)
64 ２一金(22) (00:20/00:10:39)
65 ２四歩打 (00:20/00:11:01)
66 ２四歩(23) (00:20/00:10:59)
67 ２四銀(15) (00:21/00:11:22)
68 ２三歩打 (00:20/00:11:19)
69 ３五銀(24) (00:20/00:11:42)
70 ２二金(21) (00:20/00:11:39)
71 ２四歩打 (00:20/00:12:02)
72 ５一飛(53) (00:20/00:11:59)
73 ２五角(16) (00:20/00:12:22)
74 ２四歩(23) (00:20/00:12:19)
75 ２四銀(35) (00:20/00:12:42)
76 ４一玉(31) (00:20/00:12:39)
77 ３五銀(24) (00:20/00:13:02)
78 ２一金(22) (00:20/00:12:59)
79 ３四歩打 (00:20/00:13:22)
80 ３四歩(33) (00:20/00:13:19)
81 ３四角(25) (00:20/00:13:42)
82 ３三角(11) (00:20/00:13:39)
83 １六飛(36) (00:20/00:14:02)
84 ２二角(33) (00:20/00:13:59)
85 ２四銀(35) (00:20/00:14:22)
86 ３三歩打 (00:20/00:14:19)
87 １三歩(14) (00:20/00:14:42)
88 １三歩(12) (00:20/00:14:39)
89 ２五角(34) (00:20/00:15:02)
90 ２三歩打 (00:20/00:14:59)
91 ３五銀(24) (00:20/00:15:22)
92 ３一玉(41) (00:20/00:15:19)
93 １四歩打 (00:20/00:15:42)
94 １四歩(13) (00:20/00:15:39)
95 １四飛(16) (00:20/00:16:02)
96 １二歩打 (00:20/00:15:59)
97 １五飛(14) (00:20/00:16:22)
98 １三角(22) (00:20/00:16:19)
99 ３六角(25) (00:20/00:16:42)
100 ３五角成(13) (00:20/00:16:39)
101 ３五金(45) (00:20/00:17:02)
102 ２六銀打 (00:20/00:16:59)
103 ２五飛(15) (00:20/00:17:22)
104 ３五銀成(26) (00:20/00:17:19)
105 ３五飛(25) (00:20/00:17:42)
106 ３四金打 (00:20/00:17:39)
107 １五飛(35) (00:20/00:18:02)
108 ４四金(34) (00:20/00:17:59)
109 ２六角打 (00:20/00:18:22)
110 ４三銀(32) (00:20/00:18:19)
111 ５四銀打 (00:20/00:18:42)
112 ５四金(44) (00:20/00:18:39)
113 ５四歩(55) (00:20/00:19:02)
114 ４四銀打 (00:20/00:18:59)
115 ４六玉(56) (00:20/00:19:22)
116 ３四歩(33) (00:20/00:19:19)
117 ２五金打 (00:20/00:19:42)
118 ５五歩打 (00:20/00:19:39)
119 １六歩打 (00:20/00:20:02)
120 ５六歩成(55) (00:20/00:19:59)
121 ５六玉(46) (00:20/00:20:22)
122 ５五歩打 (00:20/00:20:19)
123 ４六玉(56) (00:20/00:20:42)
124 ３三銀(44) (00:20/00:20:39)
125 ５五玉(46) (00:20/00:21:02)
126 ２四歩(23) (00:20/00:20:59)
127 １四金(25) (00:20/00:21:22)
128 ３五歩成(34) (00:20/00:21:19)
129 ３五角(26) (00:20/00:21:42)
130 ２五歩成(24) (00:20/00:21:39)
131 ２五角(36) (00:20/00:22:02)
132 ５四飛(51) (00:20/00:21:59)
133 ４五玉(55) (00:20/00:22:22)
134 ４四銀(33) (00:20/00:22:19)
135 ４四角(35) (00:20/00:22:42)
136 ４四飛(54) (00:20/00:22:39)
137 ３五玉(45) (00:20/00:23:02)
138 ３四歩打 (00:20/00:22:59)
139 ３六玉(35) (00:01/00:23:03)
140 ５四角打 (00:01/00:23:00)
141 ２六玉(36) (00:01/00:23:04)
142 ４六飛成(44) (00:01/00:23:01)
143 ３六銀打 (00:01/00:23:05)
144 ３五歩成(34) (00:01/00:23:02)
145 投了
まで144手で後手の勝ち

他にも何局か指させてみたのですが、sspに全然勝てませんでした…。

探索部分をかなり簡略化しているので、評価関数はともかく探索部分だけでもBonanzaと同等にすれば、sspにはかなり勝つんじゃないかと思っているので、がんばります。

ちなみにこれを書いている現在、未実装の探索手法は、
・置換表
・Principal Variation Search (PVS)
・null move pruning
・futility pruning
・killer move
・extension、reduction
・multi PV
・並列処理

さらに１手詰、３手詰ルーチン、dfpnも未実装です。

未実装だらけです。ははは。（乾いた笑い）

「実装」というより、探索手法について理解して（ここが大事）、

そのままくっつけるだけなのですが。

おまけとして、探索について勉強する上で、参考になったものをいくつか。

・Chess Programming Wiki
困ったらとりあえずここで検索。

・CiNii 論文 -  3.コンピュータ将棋における全幅探索とfutility pruningの応用(<ミニ小特集>コンピュータ将棋の新しい動き)
Futility pruningについて解説されてます。擬似コードもあるのでわかりやすいです。

・将棋：ＳＥＥ - スズメレンダラー・クマ将棋の開発日記
SEE（static exchange evaluation）について。
リンク先の図がとてもわかりやすいです。

それでは。

Bonanza 56shogi とりあえず対局できるようにしてみた

はい。こんな感じです。

Windowsのコマンドプロンプト上で、
指し手を入力するかたちで対局できるようにしてみました。

探索は単純なAlphaBetaです。
探索の最大深さ７なら、数秒で指し手を決めてくれます。

評価関数は、駒割 ＋ 敵玉との相対位置によるボーナス（歩、金、銀）
というふうにしてみました。

とりあえず対局できるようにはなりましたが、
画像をご覧のとおり、将棋倶楽部２４で中級のわたしが勝ててしまうレベルです。

本将棋（ふつうの将棋）より狭いとはいえ、
ごーろく将棋 56shogiがどれくらい深いゲームなのか知りたいので、
Bonanza 56shogiプロジェクトをこの調子で進めていきたいです。
（なんたらプロジェクトっていうとカッコいいと思ってます）

次は、置換表 ＋ 反復深化にとりかかろうと思ってます。

それでは。

【 2014/10/22 18:43 追記 】
うっかりミスで、敵玉との相対位置によるボーナスが加算されてませんでした。
それを修正して、さらに、飛・角の利きのあるマスの数のボーナスを追加したところ、
こんな感じで３連敗しました。

玉の顔面受けで飛角両取りを食らうの図

腰掛銀で好形かと思いきや、角を詰まされるの図

４回目はなんとか勝てました。ははは。

乱数を入れてないので、今のところはまったく同じ順で勝つことができてしまいます。

探索部分をもとのBonanzaと同じものにしたときに、
どれくらいの強さになるのか楽しみです。

それでは。

Bonanza 56shogi 指し手生成

できました。

指し手生成祭り開催 - Bonanzaソース完全解析ブログを参考に、
局面は適当につくりました。

ちなみに、自殺手（１五玉）を生成していますが、
これは本家Bonanzaでも生成します。
詳しいことは指し手生成祭り開催 - Bonanzaソース完全解析ブログに書いてあります。

5M回ループを回して指し手生成関数を呼び出して、実行時間が3076msでした。

指し手生成の回数は、約1.62M/secということになりますが、

生成される手が指し手生成祭り開催 - Bonanzaソース完全解析ブログの局面は199手で、

ごーろく将棋 56shogi のこの局面は60手です。

本将棋の指定局面に換算するために、

1.62M回を単純に0.3倍( 60 ÷ 199 ≒ 0.3 )すると、

約0.486M/secになります。

指し手生成祭り開催 - Bonanzaソース完全解析ブログによると、

『この局面を素のBonanzaで計測してみましたが、
私の普段使っているマシン(Core2Duo2.8GHz)で、1.1M/secぐらいでした。
素のBonanzaからは多少改造してあるソースで測定したので
参考スコアということでお願いします。』

ということで、だいたい速度が半分になってしまっています。

いまつかっているノートPCが、Core2Solo 1.4GHzと、スペックが低いということと、
どの程度かわかりませんが改造してあるソースということなので、
参考スコアが素のBonanzaより少し早くなっているのかもしれません。
（だったらいいな）

それにしても遅い気がしますが。うーむ。

ビットボードが３つから１つに減っているのですが、
（５×６＝３０マスで、32bit整数型１つにおさまる）
どうしても増えてしまう処理があります。

例えばということで、先手の角が移動する手を生成する関数のソースを引用します。

厳密にいうと、角が移動する手の中で、
１.中段までの移動（成ることができない移動）で駒をとる手　
　　　　　　　　　　　　＋
２.駒をとる手もとらない手も含む、駒を成る手（敵陣への移動 or 敵陣からの移動）
を生成します

Bonanza (gencap.c)

  bb_piece = BB_BBISHOP;
  while ( BBTest( bb_piece ) )
    {
      ifrom = LastOne( bb_piece );
      Xor( ifrom, bb_piece );

      AttackBishop( bb_desti, ifrom );
      bb_desti.p[0] &= bb_movable.p[0];
      if ( ifrom < A6 )
	{
	  bb_desti.p[1] &= bb_movable.p[1];
	  bb_desti.p[2] &= bb_movable.p[2];
	}
      else {
	bb_desti.p[1] &= bb_capture.p[1];
	bb_desti.p[2] &= bb_capture.p[2];
      }

      while ( BBTest( bb_desti ) )
	{
	  ito = LastOne( bb_desti );
	  Xor( ito, bb_desti );

	  utemp = ( To2Move(ito) | From2Move(ifrom)
		    | Cap2Move(-BOARD[ito]) | Piece2Move(bishop) );
	  if ( ito < A6 || ifrom < A6 ) { utemp |= FLAG_PROMO; }
	  *pmove++ = utemp;
	}
    }

56shogi

bb_piece = BB_BBISHOP;
  while ( BBTest (bb_piece ) )
    {
      ifrom = LastOne( bb_piece );
      Xor( ifrom, bb_piece );
      
      AttackBishop( bb_desti, ifrom );
      bb_desti_a = bb_desti & bb_movable & bb_w_position;
      bb_desti_b = ( ifrom < A4 ) ? bb_desti & bb_movable & ~bb_w_position
                                  : bb_desti & bb_capture & ~bb_w_position;
      bb_desti = bb_desti_a | bb_desti_b;
      
      while ( BBTest(bb_desti) )
        {
          ito = LastOne( bb_desti );
          Xor( ito, bb_desti );

          utemp = ( To2Move(ito) | From2Move(ifrom)
                      | Cap2Move(-BOARD[ito])
                      | Piece2Move(bishop) );
          if ( ito < A4 || ifrom < A4 ) { utemp |= FLAG_PROMO; }
          *pmove++ = utemp;
        }
    }

Bonanzaではp[0]が後手陣、p[2]が先手陣になっていまして、
敵陣／自陣の区別が容易です。

56shogiでは、
bb_w_position（後手陣だけビットが立っているビットボード）を用意して、
それと論理積をとっています。

こういう処理があるので、ビットボードが１つになっても、
それほど高速にならないだろうなと思っていたのですが、
それにしても半分は遅いような気がします。ぐぬぬ。

もしかしてもしかして、unsigned short int( 16bit )３つの構造体を用意して、
下位10bitだけつかって上位6bitは余らせる、
なんてことをしたほうが高速だったんでしょうか。

それならソースをほとんど書き換えなくてよくなるんですが。ぐぬぬぬぬ。

とりあえず、bb_w_positionのビットを反転させたビットボードを
あらかじめ用意しておくようにすれば、
ビット反転の処理が省略できるので、
少し速度がマシになるでしょうか。

とにもかくにも、指し手生成ができるようになったことは、とてもうれしいです。
去年のいまごろ、Windows付属のメモ帳でプログラミングをはじめたころは、
Bonanzaのソースを読んで、書き換えるなんて想像もしていなかったので。

ちなみに、いまは王手を生成する部分(genchk.c)を書き換えてます。

しばらくは、王手生成、王手回避手生成、１手詰ルーチン、３手詰ルーチンを
書き換えることになると思います。

５×６将棋盤でのrotated bitboardの実装方法というか、
Bonanzaのどの部分を書き換えたかという記事を、いま書いているのですが、
きちんと書こうとすると、とても長くなりそうで参ってます。

ぼちぼち、ゆっくり書いていこうと思います。

それでは。

Bonanza 56shogi つくってます

ここしばらく、Bonanzaを「ごーろく将棋」のルールに対応させることに
チャレンジしてます。

ちなみに「ごーろく将棋」とは、５×６マスのあたらしいミニ将棋です。
こちらのページで遊べます。

とりあえず駒の利きを求められるようになったのでブログを更新してみました。

相手の駒があっても、きちんと途中で利きが止まります。

本将棋（ふつうの将棋）やチェスと違って、
「ごーろく将棋」は縦と横のマスの数が違うので、
いろいろ苦労しました。

とにかく進捗したよ、わーい、ということです。

ビットレイアウトをどうしたとか、
Bonanzaのどの部分を書き換えたとかは、
また記事にする、と思います。たぶん。

それでは。

近況

Bonanzaを5*6マスのごーろく将棋に書き換えてみよう
↓
ビット操作、ビットレイアウト、指し手生成に必要な配列の初期化は
だいたいできたっぽいので、そろそろ指し手生成にチャレンジだ
↓
そのまえにCSA形式の棋譜をとりこめるようにしないとデバッグできないぞ
↓
BonanzaのCSA形式のデータ読み込み部分のソースがよくわからん
$ANSWERってなに？CSA標準棋譜ファイル形式 (V2.2)に載ってないよ？
↓
Bonanzaソース完全解析ブログで、
CSA形式のデータ読み込み部分のソース解説までされてる！すごい！←いまここ

ごーろく将棋

「ごーろく将棋」のサイトを引っ越しました。

【2015/11/5 追記　さらに引っ越したのでリンク先を変更しました】

ごーろく将棋 56shogi

COMのレベル（レベル１とレベル２しかないけど）と、

二枚落ちなどのハンデを選択できるようにしてみました。

遊んでみていただけるとうれしいです。

遊んでみた感想をいただけると、とてもうれしいです。

COMのレベル１は、

こまお

を参考にさせていただいています。

もちろんそのままというわけではなくて、

自分なりに工夫してみたのですが、

「自然に弱くする」のはなかなか難しかったです。

それについては、そのうちまた別の記事にしたいと思っています。

さて、今後しばらくは、

より強いレベルのCOMをつくることを目標にしたいと思います。

もっと自然に弱い、レベル０をつくるのもおもしろそうなのですが、とりあえず。

最近は、オープンソース
（ 2014/6/6 17:25追記　
ソースコードは公開されていますが、営利目的での利用は制限されているので、いわゆる「オープンソース」ではないようです。）

のBonanzaを、

ごーろく将棋のプログラムに改変できたらと思いまして、

Bonanzaソース完全解析ブログを少しずつ読んでいます。

しかし道遠しという感じで、

今年度中にできたらなー、という気持ちになってます。

いきなりBonanzaのごーろく将棋版をつくるのは難しすぎるので、

JavaScriptでbitboardを実装してみる
↓
指し手生成の部分をBonanzaのマネをしてつくってみる
↓
探索部分をBonanzaのマネをしてつくってみる

みたいなステップでやっていくのが妥当かなという感じでしょうか。

それでも簡単なステップではないですががが。

あと、前回の記事で、

「ごーろく将棋は先手有利、もしかしたら必勝かも」

なんて書いてしまいましたが、

もう少し研究してみたところ、

そうでもないかもしれない感じがしてきました。

はっきりいってよくわかりません。

「これで後手ダメだな」と思っていた変化があったのですが、

しらべてみると、後手もまずまず、どころか後手有利かも、

となってしまったりして、なかなか結論がでてません。

もし「ごーろく将棋」を研究されて、

必勝法を発見した、というかたがいらっしゃいましたら、

ご連絡をおまちしております。

（もちろんわたしも研究します）

（ちなみにわたしは将棋倶楽部２４で現在９級なので、自分のことながら
　あまり期待できません）

（でもがんばります）

それでは。

あたらしいミニ将棋を考えて、COMと対局できるものをつくりました。（ 仮 ）

こんな感じです。

こちらのページで対局することができます。
＜2014.6.13 10:50 追記　ページを引っ越したのでリンク先を変更しました＞

【2015/10/30 追記】　さらに引っ越したのでリンクを変更しました。現在はこんな感じです

バグなどあれば、この記事にコメントしていただけるとうれしいです。

さて、思考エンジンですが、

・探索部分

３手先読み　＋　駒がぶつかっているあいだは精算するまで読む

・評価関数

基本は駒得（駒に点数をつけて単純に足す）

歩、と金、金、銀は、敵玉との距離が近いほど価値が高くなるように補正

飛、角の利いているマスの数によって加点

というふうにしました。

将棋初級者のかたの練習相手になればいいかな、

というぐらいの強さになっていると思います。たぶん。

というか、今のわたしの技術では強いものがつくれないんですけども。

この初期配置はかなり先手有利（というか必勝かも）なのですが、

あと６つほど考えている初期配置があるので、

その中から選べるようにしたいと思っています。

ほかにも、

・強くする or 弱くする　→　レベルを選べるようにする

・千日手に対応する

・トライルール

・打ち歩詰めは禁則にするかどうか。するなら実装。
盤面が狭く、出現頻度が高いので禁則にしないかも。

・setIntervalで、どちらの手番かずっと確認している処理をなんとかする
（setTimeoutの存在を知りませんでした。それにしてもあほです。）

など、やることがたくさんあるのでがんばります。

電王戦をたのしく観ていたら、こんなに更新が遅くなってしまいました。ははは。
（ごめんなさい）

それでは。