2012/05/29
■ 利きのデータを使うとき
MSSでは利きのデータを、
・ピンされている駒を探す
・王手を受けている/かけている(王に利きがある)の判定
・王移動の時、自爆しないように(利きのあるところに王は行けない)
・交換値計算でマスに利きを付けている駒を探す
・静止探索で駒に利きを付けている(取れる駒)駒を探す
・開き王手生成(逆ピン駒を探す)
・評価関数で王の周りの利きの数の計算
のために使っている。
利きデータを使わずに上記の動作をさせるには...
王手をかけている(王に利きがある)の判定と、ピンしている駒を探すのは同時に行える。
自分の飛び駒の利きを伸ばして行き、相手の駒が存在し、相手玉に影利きを付けているなら、相手ピン駒。あるいは直接、相手玉に利きを付けているなら王手。
王手をかけている→手番を渡すと、王手をかけられている→あたりまえ。
ピンしている駒は評価に使える。ピン駒のSEE値は有力な局面判定。
2012/05/26
■ Bitboardの説明
いまさらながらこのような説明は不要かもしれないが、Bitboardの説明。
駒位置をビット位置であらわす(ここでは説明を簡単にするため81ビット演算が使えるとする)。
盤の座標値とビット番号 9 8 7 6 5 4 3 2 1 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 九
たとえば、先手歩の初期位置だと、
9 8 7 6 5 4 3 2 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 六 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ビット右シフトすると、
9 8 7 6 5 4 3 2 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 五 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して、ビット位置を端から読んでいけば合法手となる。前に動く駒はすべてこの演算で動かすことができる(飛香の飛び駒の処理は別に行う)。
次に、9三と1三にいる銀を右上に動かしてみよう。
9 8 7 6 5 4 3 2 1 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ビット右シフトすると、あれ、9一は変。
9 8 7 6 5 4 3 2 1 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しておく。
9 8 7 6 5 4 3 2 1 9 8 7 6 5 4 3 2 1 9 8 7 6 5 4 3 2 1 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でも動くようにしてきたが、プラットホーム決め打ちになりそうな予感。
2012/05/20
■ 指し手の速度
以下の局面で、後手番の手生成速度を計測している。
(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)
2012/05/19
■ 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
おお、動いた。
■ プロファイル結果
コンピューター将棋の進歩2より次の一手問題第1問。
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%
静止探索で半分以上消費している。ピン情報の更新も結構時間を食っていることがわかった。
2012/05/13
■ 第22回世界コンピュータ将棋選手権バージョン公開
http://blog.gigacraft.net/download.htm
駒落ちには対応していません。稲庭将棋は対策をしていません。詰将棋モードは動作しません。
2012/05/06
■ 少し分析
勝った対戦:平均消費時間8分16秒,平均73.5手
負けた対戦:平均消費時間16分52秒,平均116手
先手勝率:0.5
後手勝率:0.667
勝った戦型:横歩取り,角換わり,居玉の矢倉(?)
負けた戦型:居玉の四間飛車(?),相矢倉,美濃に囲った四間飛車
急戦にはめっぽう強い。
■ 対技巧戦
第5戦、先手はMiyako Shogi System。
59手でMiyako Shogi Systemが銀を追い払う5六歩と打ったところ。
こちらは銀を金にぶつける△66銀▲66銀△66歩▲57金△65桂▲58金△52飛▲63銀△56飛
と読んでいるが、実際には、
△6六歩▲7七金△6五桂と銀取りを気にせず調子よく攻められ、
70手で
と、潰されたうえに、意味不明の▲7五歩(思考中断でスコアをINFにハッシュ登録するパスがある?)
を指して、一気に寄せられてしまった。
投了図
なんか、初歩の一手問題で、「銀取りの歩を打たれましたがどうしますか」で
「銀取りにかまわず、△6六歩▲7七金△6五桂で後手勝勢です」のような感じだ。
なぜこのような無様な読みをしたかは帰ってからよく考えてわかった。そのうちこの理由を書くことにしよう。
2012/05/02
■ 選手権1次予選前日のセッテイング風景
パソコンの電源ケーブルを忘れるという大失態がありましたが、
電通大伊藤先生に貸してもらいセッテイングすることができました。感謝です。
自分の席より
向かいのでかいマシンはSelene。隣はApery。斜め向かいは、なのは。
「このシマは(1次)全部抜けるぜ」と言われていたのですが...orz
私の跡地には2次予選でクマ将棋が入りました。
席の配置