最新

Miyako Shogi System

コツコツ改良、へこたれない
2014| 1|
2013| 12|
2012| 01| 02| 04| 05| 06| 07| 08| 09| 10|
2011| 01| 02| 03| 04| 05| 07| 08| 10| 11| 12|
2010| 02| 03| 06| 07| 08| 09| 10| 12|

2011/01/29

コンパイラ比較(その2)

コンピューター将棋の進歩2より次の一手問題第1問で、プログラムは1/27のもの。マシン、コンパイラオプション同じ

前回のベンチマークは全幅探索なので、広大なハッシュアクセスがあり、メモリーがボトルネックになるかもしれないが、今回は枝刈がかかっているため、より実戦でのベンチマークに近い。

CPU:AMD PhenomII X2 BE555 (3.9GHz)

コンパイラ総思考時間NPS
VC2008 (WindowsXP32bit)38.11007732.4
MinGW4.5 (WindowsXP32bit)37.6782464.0
icc 12.0 (Ubuntu64bit)36.0808951.9
icc 12.0 (Ubuntu32bit)46.4627760.9
gcc 4.4.5 (Ubuntu64bit)35.0830302.1
gcc 4.4.5 (Ubuntu32bit)50.8571748.2
open64 4.2.4 (Ubuntu64bit)38.8752354.9
open64 4.2.4 (Ubuntu32bit)49.0599204.7

本問題は不利な状況での勝負手問題で、難問。

不思議なことにVCだけノード数が違う。gccと互換コンパイラはぴたり同じ値。

コンパイラノード数静止探索ノード数
VC2008180169430934493
MinGW/gcc/icc/open64194483321712966

どのコンパイラも九一飛成りからの進行は同じなのを確認。

※追記、手のオーダリングにバグがあったため違うノード数になっていました。最新のベンチマークはこちら

2011/01/27

探索の改良

コンピューター将棋の進歩2より次の一手問題第1問で、深さ8固定。

  • 枝刈なし
ノード数静止探索ノード数NPS総思考時間
6609198460594841080.058.4秒

aspiration windowによる反復深化探索、null-move pruning、多重反復深化だけ使用。

  • 枝刈あり
ノード数静止探索ノード数NPS総思考時間
59615485849571765.23.1秒

総思考時間は反復深化探索すべての時間

※NPSには静止探索ノード数も含む

  • 枝刈内訳(回数)
Null-pruneLMR1LMR2Futility1Futility2Futility3
2057246192904278035465309484

どちらも静止探索は最大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/10

うーん

このブログは非公開で、自分だけの開発の備忘録と思っていたのだが、ログを見ると結構他所から見られているようなので、事実上の公開というところか。(まぬけ)

グーグルさんはホスト名があるところなら片っ端からクロールするように変更したようだ。

2011/01/04

探索の改良

glaurung22を参考に探索を全面的に書き換えた。PVノードと非PVノードの探索を分けた。PVノードと非PVノードでは枝刈のやり方が変わるため、これは分かりやすい。

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で行くのが良さそう。

コンパイラ比較(その2)

コンパイラ比較(その3)

2011/01/02

次の一手

USIへの対応も完成し、評価関数の自動学習もそこそことなってきたため、いよいよ次の段階へと進もう。

  1. 探索の改良
  2. 時間管理
  3. 高速1手詰め

というところか。

リンクはご自由に (Miyako Shogi System Kyoto Japan)

ダウンロードのページ

Lighttpd

DreamPlug