Miyako Shogi System

■ 利きのデータを使うとき

MSSでは利きのデータを、

・ピンされている駒を探す

・王手を受けている/かけている(王に利きがある)の判定

・王移動の時、自爆しないように(利きのあるところに王は行けない)

・交換値計算でマスに利きを付けている駒を探す

・静止探索で駒に利きを付けている(取れる駒)駒を探す

・開き王手生成(逆ピン駒を探す)

・評価関数で王の周りの利きの数の計算

のために使っている。

利きデータを使わずに上記の動作をさせるには...

王手をかけている(王に利きがある)の判定と、ピンしている駒を探すのは同時に行える。

自分の飛び駒の利きを伸ばして行き、相手の駒が存在し、相手玉に影利きを付けているなら、相手ピン駒。あるいは直接、相手玉に利きを付けているなら王手。

王手をかけている→手番を渡すと、王手をかけられている→あたりまえ。

ピンしている駒は評価に使える。ピン駒のSEE値は有力な局面判定。

■ Bitboardの説明

いまさらながらこのような説明は不要かもしれないが、Bitboardの説明。

駒位置をビット位置であらわす（ここでは説明を簡単にするため81ビット演算が使えるとする）。

  盤の座標値とビット番号
９ ８ ７ ６ ５ ４ ３ ２ １
 8  7  6  5  4  3  2  1  0 一
17 16 15 14 13 12 11 10  9 二
26 25 24 23 22 21 20 19 18 三
35 34 33 32 31 30 29 28 27 四
44 43 42 41 40 39 38 37 36 五
53 52 51 50 49 48 47 46 45 六
62 61 60 59 58 57 56 55 54 七
71 70 69 68 67 66 65 64 63 八
80 79 78 77 76 75 74 73 72 九

たとえば、先手歩の初期位置だと、

９ ８ ７ ６ ５ ４ ３ ２ １
 0  0  0  0  0  0  0  0  0 一
 0  0  0  0  0  0  0  0  0 二
 0  0  0  0  0  0  0  0  0 三
 0  0  0  0  0  0  0  0  0 四
 0  0  0  0  0  0  0  0  0 五
 0  0  0  0  0  0  0  0  0 六
 1  1  1  1  1  1  1  1  1 七
 0  0  0  0  0  0  0  0  0 八
 0  0  0  0  0  0  0  0  0 九

となる。

歩を突く手を生成してみよう。**に歩がいるときの利きのテンプレートを押し付ける方法もあるのだが、シフト命令でやってみよう。この81ビット列を9ビット右シフトすると、

９ ８ ７ ６ ５ ４ ３ ２ １
 0  0  0  0  0  0  0  0  0 一
 0  0  0  0  0  0  0  0  0 二
 0  0  0  0  0  0  0  0  0 三
 0  0  0  0  0  0  0  0  0 四
 0  0  0  0  0  0  0  0  0 五
 1  1  1  1  1  1  1  1  1 六
 0  0  0  0  0  0  0  0  0 七
 0  0  0  0  0  0  0  0  0 八
 0  0  0  0  0  0  0  0  0 九

演算1回で9個の歩を動かした（どうだすごいだろ）。あとは味方の駒位置ビット列とxorして、ビット位置を端から読んでいけば合法手となる。前に動く駒はすべてこの演算で動かすことができる（飛香の飛び駒の処理は別に行う）。

次に、９三と１三にいる銀を右上に動かしてみよう。

９ ８ ７ ６ ５ ４ ３ ２ １
 0  0  0  0  0  0  0  0  0 一
 0  0  0  0  0  0  0  0  0 二
 1  0  0  0  0  0  0  0  1 三
 0  0  0  0  0  0  0  0  0 四
 0  0  0  0  0  0  0  0  0 五
 0  0  0  0  0  0  0  0  0 六
 0  0  0  0  0  0  0  0  0 七
 0  0  0  0  0  0  0  0  0 八
 0  0  0  0  0  0  0  0  0 九

この81ビット列を10ビット右シフトすると、あれ、９一は変。

９ ８ ７ ６ ５ ４ ３ ２ １
 1  0  0  0  0  0  0  0  0 一
 0  1  0  0  0  0  0  0  0 二
 0  0  0  0  0  0  0  0  0 三
 0  0  0  0  0  0  0  0  0 四
 0  0  0  0  0  0  0  0  0 五
 0  0  0  0  0  0  0  0  0 六
 0  0  0  0  0  0  0  0  0 七
 0  0  0  0  0  0  0  0  0 八
 0  0  0  0  0  0  0  0  0 九

一番右端にいる駒を右に動かすと左に回ってしまうので、1筋を0にしたものとandしておく。

９ ８ ７ ６ ５ ４ ３ ２ １       ９ ８ ７ ６ ５ ４ ３ ２ １     ９ ８ ７ ６ ５ ４ ３ ２ １   
 0  0  0  0  0  0  0  0  0 一     1  1  1  1  1  1  1  1  0 一   0  0  0  0  0  0  0  0  0 一
 0  0  0  0  0  0  0  0  0 二     1  1  1  1  1  1  1  1  0 二   0  0  0  0  0  0  0  0  0 二
 1  0  0  0  0  0  0  0  1 三     1  1  1  1  1  1  1  1  0 三   1  0  0  0  0  0  0  0  0 三
 0  0  0  0  0  0  0  0  0 四     1  1  1  1  1  1  1  1  0 四   0  0  0  0  0  0  0  0  0 四
 0  0  0  0  0  0  0  0  0 五 and 1  1  1  1  1  1  1  1  0 五 = 0  0  0  0  0  0  0  0  0 五
 0  0  0  0  0  0  0  0  0 六     1  1  1  1  1  1  1  1  0 六   0  0  0  0  0  0  0  0  0 六
 0  0  0  0  0  0  0  0  0 七     1  1  1  1  1  1  1  1  0 七   0  0  0  0  0  0  0  0  0 七
 0  0  0  0  0  0  0  0  0 八     1  1  1  1  1  1  1  1  0 八   0  0  0  0  0  0  0  0  0 八
 0  0  0  0  0  0  0  0  0 九     1  1  1  1  1  1  1  1  0 九   0  0  0  0  0  0  0  0  0 九

これを10ビット右シフトすればよい。

ここの説明が良い。

http://chessprogramming.wikispaces.com/Efficient+Generation+of+Sliding+Piece+Attacks#cite_note-1

■ げっ、_mm_slli_si128/_mm_srli_si128は8bitずつのシフトしかできない！

バレルシフタは回路を食うが、それは無いでしょ。

sse5では自由なシフトができるそうだが、幻の命令セットになったので、shld/shrdでちまちま書くか。Miyako Shogi SystemはWindowsでもLinuxでも32bitでも64bitでも動くようにしてきたが、プラットホーム決め打ちになりそうな予感。

■ 次のバージョン

Miyako Shogi Systemの目標は、

そこそこ新しい技術を取り入れる
そこそこ分かりやすいソースコード
そこそこ強い

なのだが、今日の技術からすると、古いところが多いので、次の部分を作り直す。

手生成はビットボード(SSE2による128bit演算)
利きデータは必要なときに作成
静止探索での1手または3手詰め
思考深さの予測

また、前回できなかった並列探索も実装しよう。

かなりの時間が必要だが、いつかはやらないと取り残されるからね。

■ 指し手の速度

以下の局面で、後手番の手生成速度を計測している。

(http://d.hatena.ne.jp/sakurapyon/20120415/1334454267 より)

Miyako Shogi System 1.14では、262,669,136手/秒(合法手判定あり)。(ループ演算のバグあり修正 7/11)

(CPU:AMD PhenomII X2 BE555 3.8GHz OS:Ubuntu amd64 gcc4.6)

■ AMD CodeAnalyst Performance Analyzer for Linuxのインストール

Lubuntu 12.04(amd64)でのインストール方法

ビルド環境のインストール

rootユーザーでインストールする

apt-get install qt4-dev-tools binutils-dev g++ libpopt-dev libtool autoconf automake make libelfg0-dev zlib1g-dev xterm xauth evince

http://developer.amd.com/Downloads/CodeAnalyst3_3_18_0361Public.tar.gz

よりCodeAnalystのソースを落とし、解凍する。

cd CodeAnalyst-3_3_18_0361-Public

./autogen.sh

./configure

make

make install

ビルドできたら、

sudo /opt/CodeAnalyst/bin/CodeAnalyst

おお、動いた。

■ プロファイル結果

コンピューター将棋の進歩２より次の一手問題第１問。

CS:EIP    Symbol + Offset    CPU clocks
0x41a9e0  Quiescence         52.44%
0x401ee0  MakePin            13.44%
0x417460  MoveTo             6.89%
0x404d80  GenerateOrder      5.54%
0x403840  Evalute            4.97%
0x4012e0  AttackClr          3.05%
0x400ee0  AttackSet          2.40%
0x413720  MakeEvasion        2.05%
0x4016e0  AttackJmpSet       1.57%
0x41e2e0  See                1.53%
0x401a00  AttackJmpClr       1.27%
0x41c7c0  SearchNonPv        1.18%
0x40e700  MakeChecksNoncap   1.18%
0x413b60  move_sub           0.92%
0x402180  piece_pos          0.44%
0x41d5c0  SearchPv           0.31%
0x40b300  discovered_check   0.17%
0x416ce0  MakeMove           0.09%
0x4063e0  HashProbe          0.09%
0x404c80  get_ncnt           0.09%
0x41b140  sort.constprop.0   0.04%
0x41a580  NewBoard           0.04%
0x416dc0  MakeDrop           0.04%

静止探索で半分以上消費している。ピン情報の更新も結構時間を食っていることがわかった。

■ 7/11追記

ubuntu 12.04用のdebファイルが公開されたので、上記のビルド作業は必要なし。

■ 第22回世界コンピュータ将棋選手権バージョン公開

http://blog.gigacraft.net/download.htm

駒落ちには対応していません。稲庭将棋は対策をしていません。詰将棋モードは動作しません。

■ 油断大敵

第22回世界コンピュータ将棋選手権１次予選は４勝３敗で１０位となり、２次予選には行けなかった。

棋譜はこちら。

■ 少し分析

勝った対戦：平均消費時間8分16秒,平均73.5手

負けた対戦：平均消費時間16分52秒,平均116手

先手勝率：0.5

後手勝率：0.667

勝った戦型：横歩取り,角換わり,居玉の矢倉(?)

負けた戦型：居玉の四間飛車(?),相矢倉,美濃に囲った四間飛車

急戦にはめっぽう強い。

■ 対技巧戦

第５戦、先手はMiyako Shogi System。

59手でMiyako Shogi Systemが銀を追い払う５六歩と打ったところ。

こちらは銀を金にぶつける△66銀▲66銀△66歩▲57金△65桂▲58金△52飛▲63銀△56飛

と読んでいるが、実際には、

△６六歩▲７七金△６五桂と銀取りを気にせず調子よく攻められ、

70手で

と、潰されたうえに、意味不明の▲７五歩（思考中断でスコアをINFにハッシュ登録するパスがある？）

を指して、一気に寄せられてしまった。

投了図

なんか、初歩の一手問題で、「銀取りの歩を打たれましたがどうしますか」で

「銀取りにかまわず、△６六歩▲７七金△６五桂で後手勝勢です」のような感じだ。

なぜこのような無様な読みをしたかは帰ってからよく考えてわかった。そのうちこの理由を書くことにしよう。

■ 選手権１次予選前日のセッテイング風景

パソコンの電源ケーブルを忘れるという大失態がありましたが、

電通大伊藤先生に貸してもらいセッテイングすることができました。感謝です。

自分の席より

向かいのでかいマシンはSelene。隣はApery。斜め向かいは、なのは。

「このシマは（1次）全部抜けるぜ」と言われていたのですが...orz

私の跡地には2次予選でクマ将棋が入りました。

席の配置