2011/01/29
■ コンパイラ比較(その2)
コンピューター将棋の進歩2より次の一手問題第1問で、プログラムは1/27のもの。マシン、コンパイラオプション同じ。
前回のベンチマークは全幅探索なので、広大なハッシュアクセスがあり、メモリーがボトルネックになるかもしれないが、今回は枝刈がかかっているため、より実戦でのベンチマークに近い。
CPU:AMD PhenomII X2 BE555 (3.9GHz)
コンパイラ | 総思考時間 | NPS |
---|---|---|
VC2008 (WindowsXP32bit) | 38.1 | 1007732.4 |
MinGW4.5 (WindowsXP32bit) | 37.6 | 782464.0 |
icc 12.0 (Ubuntu64bit) | 36.0 | 808951.9 |
icc 12.0 (Ubuntu32bit) | 46.4 | 627760.9 |
gcc 4.4.5 (Ubuntu64bit) | 35.0 | 830302.1 |
gcc 4.4.5 (Ubuntu32bit) | 50.8 | 571748.2 |
open64 4.2.4 (Ubuntu64bit) | 38.8 | 752354.9 |
open64 4.2.4 (Ubuntu32bit) | 49.0 | 599204.7 |
本問題は不利な状況での勝負手問題で、難問。
不思議なことにVCだけノード数が違う。gccと互換コンパイラはぴたり同じ値。
コンパイラ | ノード数 | 静止探索ノード数 |
---|---|---|
VC2008 | 1801694 | 30934493 |
MinGW/gcc/icc/open64 | 1944833 | 21712966 |
どのコンパイラも九一飛成りからの進行は同じなのを確認。
※追記、手のオーダリングにバグがあったため違うノード数になっていました。最新のベンチマークはこちら
2011/01/27
■ 探索の改良
コンピューター将棋の進歩2より次の一手問題第1問で、深さ8固定。
- 枝刈なし
ノード数 | 静止探索ノード数 | NPS | 総思考時間 |
---|---|---|---|
660919 | 8460594 | 841080.0 | 58.4秒 |
aspiration windowによる反復深化探索、null-move pruning、多重反復深化だけ使用。
- 枝刈あり
ノード数 | 静止探索ノード数 | NPS | 総思考時間 |
---|---|---|---|
59615 | 485849 | 571765.2 | 3.1秒 |
総思考時間は反復深化探索すべての時間
※NPSには静止探索ノード数も含む
- 枝刈内訳(回数)
Null-prune | LMR1 | LMR2 | Futility1 | Futility2 | Futility3 |
---|---|---|---|---|---|
2057 | 2461 | 9290 | 42780 | 35465 | 309484 |
どちらも静止探索は最大12段。ただし4段目からは歩を取る成らない手は読まない、深さ8段目からは同〜の手しか読まない。
aspiration windowははじめは歩価値の2/3枚の幅で、feilしたときは桂1枚の幅に広げる。それでもfeilしたときはINFまで広げる。
Null-move pruneはdepthが2以上で行い、depthが6以上でR=3、それ以外R=2。
LMR1はPVノードでdepthが2以上でオーダリング順depth+8手目以上は1手浅く読む。
LMR2は非PVノードでdepthが2以上でオーダリング順depth+4手目以上は1手浅く読む。また、オーダリング14手目以上は2手浅く読む。
LMRは成る手、取る手、王手、キラー手では行わない。
Futility1は非PVノードでdepthが1のとき、手の簡易評価値がalpha以下のときに読まない。
Futility2は非PVノードでdepthが2のとき、手の簡易評価値+マージン(歩2枚分)がalpha以下のときに読まない。
Futility3は静止探索内で手の評価値がalpha以下のときに読まない。
Futility pruneは成る手、取る手、王手、キラー手では行わない。
PVノードでdepthが3以上でハッシュの手が無いときは多重反復深化。
非PVノードでdepthが5以上でハッシュの手が無く、現局面の評価値が桂損未満のときは多重反復深化。
まだまだ調整は必要だ。
2011/01/16
■ ブログ旧ymss部分は削除
MiyakoShogiSystem以降の部分だけにした。さすがに古い棋譜やら、メモは恥ずかしい。
■ 現時点での手の構造(int型)
ofs width 役割 0 8 from 8 8 to 16 4 piece 20 4 capture 24 1 promote 25 1 killer move 26 1 1/2手延長 27 1 1手延長
killer moveビットは手のオーダリング時に付ける。枝刈判定で使う。ハッシュの手は1番目にオーダリングするので、特に印は付けない。王手判定は局面更新時に判断する。(ハッシュの手、キラー手は局面更新せずに判断するため王手判定とならない→1手延長できない)
■ 現時点での評価関数の項目
OffensePos1[81][8][81]; // 歩桂銀金/成金角飛馬竜の位置表(対相手玉) OffensePos2[9][3][81]; // 歩桂銀の位置表(対自飛車筋) DefensePos1[81][4][81]; // 歩銀金馬の位置表(対自玉) DefensePos2[9][2][81]; // 銀金の位置表(対相手飛車筋) KingPos1[9][81]; // 玉の位置表(対自飛車筋) KingPos2[9][81]; // 玉の位置表(対相手飛車筋) KingRank[9]; // 終盤の玉の段 Mobility[6][9]; // 攻め駒の動ける量(飛車の前/後/横,角,桂馬,銀のバック) AttackPieceValue[2][16]; // 飛車の先に有る駒 PinPieceValue[16][7]; // ピン駒と王との距離 PinAttacks[4][3]; // ピン駒の利きの差 KingAttacks[13][9]; // 玉の周囲の利き KingGuardM[9]; // 玉の周囲の金銀 KingGuardK[9]; // 玉の周囲の小駒 KingSpace[9]; // 玉の自由度 KingSpaceInChk[9]; // 王手を受けたときの玉の自由度 ZoneAttacks[3][5]; // 相手陣への利き(段筋別) AttackKei; // 桂頭の利きがある加点 AttackKaku; // 角頭の利きがある加点 NoAttackPos[12]; // 自陣に利きが無いマス目数 HandValue[8][8]; // 序中盤持ち駒の価値 HandValueE[8][8]; // 終盤持ち駒の価値
■ 現時点でのハッシュ局面表
// 1エントリ16byte DWORD64 key; // ハッシュキー int move; // ハッシュ手 short score; // 探索で得た局面の評価値 BYTE depth; // 探索を行った際の残り深さ BYTE type_age; // 探索で得た値が局面の評価値そのものか上限値か下限値か (4bit) // 探索のカウンタ (4bit)
2011/01/03
■ コンパイラ比較
コンピューター将棋の進歩2より次の一手問題第1問で、8手読み全幅+静止探索。
aspiration window searchとnull-move pruningだけをかけた。
CPU:AMD PhenomII X2 BE555 (3.9GHz)
コンパイラ | 秒数 | コンパイラオプション |
---|---|---|
VC2008 (WindowsXP32bit) | 96.6 | /Ox /Ob2 /Oi /Ot /GL /GF /FD /EHsc /MD /Gy /arch:SSE2 /fp:fast /TC |
MinGW4.5 (WindowsXP32bit) | 85.8 | -O3 -march=amdfam10 -msse3 -mfpmath=sse |
icc 12.0 (Ubuntu64bit) | 81.4 | -O3 -ipo -unroll -fno-alias -axSSSE3 -ipo -static-intel |
icc 12.0 (Ubuntu32bit) | 111.0 | -O3 -ipo -unroll -fno-alias -axSSE4.1 -ipo -static-intel |
gcc 4.4.5 (Ubuntu64bit) | 81.9 | -O3 -Wno-unused-result -march=amdfam10 -mfpmath=sse -msse3 |
gcc 4.4.5 (Ubuntu32bit) | 121.8 | -O3 -Wno-unused-result -march=amdfam10 -mfpmath=sse -msse3 |
open64 4.2.4 (Ubuntu64bit) | 88.2 | -Ofast -ipa -mtune=barcelona -lm -ipa |
open64 4.2.4 (Ubuntu32bit) | 104.9 | -Ofast -ipa -mtune=barcelona -lm -ipa |
64bitで行くのが良さそう。