オセロで返る石を求める

SIMDを使わない場合

2024/08/06現在

4方向についてそれぞれ、

opponentの端を除いた6bit、および置く場所に対応したoutflankを用意する

player & outflank候補をoutflankとする

outflank(+置く場所)->flipは単に表引き

をやると速い

code:cpp

// from Egaroucid

// License: GPL-v3

// 表は省略

inline uint64_t calc_flip(const uint64_t player, const uint64_t opponent, const int place){

pos = place;

uint32_t x = place & 7;

uint32_t y = place >> 3;

outflank &= ((player & a) * 0x0101010101010101ULL) >> 56;

};

uint8_t outflank = (((player >> x) & 0x0101010101010101ULL) * 0x0102040810204080ULL) >> 56;

outflank &= player >> (place & 0x38);

return flip;

}

参考

すごく速いPRをもらった(これを2024/08/06現在は使っている)

自分で書くと、表の前計算をして、それぞれのライン+置く場所で表引きする方が速い(悲しい…)

code:c++

inline uint64_t calc_flip(const uint64_t player, const uint64_t opponent, const int place){

uint64_t line, outflank;

uint64_t mopponent = opponent & 0x7E7E7E7E7E7E7E7EULL;

int rplace = HW2_M1 - place;

pos = place;

flip = 0;

// downward

line = 0x0080808080808080ULL >> rplace;

outflank = (0x8000000000000000ULL >> clz(~opponent & line)) & player;

flip |= ((~outflank + 1) * 2) & line;

// upward

line = 0x0101010101010100ULL << place;

outflank = ((opponent | ~line) + 1) & line & player;

flip |= (outflank - (outflank != 0)) & line;

// right

line = 0x7f00000000000000ULL >> rplace;

outflank = (0x8000000000000000ULL >> clz(~mopponent & line)) & player;

flip |= ((~outflank + 1) * 2) & line;

// left

line = 0x00000000000000feULL << place;

outflank = ((mopponent | ~line) + 1) & line & player;

flip |= (outflank - (outflank != 0)) & line;

// d7 downward

line = 0x0102040810204000ULL >> rplace;

outflank = (0x8000000000000000ULL >> clz(~mopponent & line)) & player;

flip |= ((~outflank + 1) * 2) & line;

// d7 upward

line = 0x0002040810204080ULL << place;

outflank = ((mopponent | ~line) + 1) & line & player;

flip |= (outflank - (outflank != 0)) & line;

// d9 downward

line = 0x0040201008040201ULL >> rplace;

outflank = (0x8000000000000000ULL >> clz(~mopponent & line)) & player;

flip |= ((~outflank + 1) * 2) & line;

// d9 upward

line = 0x8040201008040200ULL << place;

outflank = ((mopponent | ~line) + 1) & line & player;

flip |= (outflank - (outflank != 0)) & line;

return flip;

}

CLZが遅い場合は以下が良い(CLZを使っていたMSB方向を、180度回転してLSB方向で代用)

code:c++

inline uint64_t calc_flip(uint64_t player, uint64_t opponent, const int place){

uint64_t line, outflank;

uint64_t mopponent = opponent & 0x7e7e7e7e7e7e7e7eULL;

uint64_t rplayer = rotate_180(player);

uint64_t ropponent = rotate_180(opponent);

uint64_t mropponent = ropponent & 0x7e7e7e7e7e7e7e7eULL;

int rplace = HW2_M1 - place;

pos = place;

flip = 0;

uint64_t rflip = 0;

// downward

line = 0x0101010101010100ULL << rplace;

outflank = ((ropponent | ~line) + 1) & line & rplayer;

rflip |= (outflank - (outflank != 0)) & line;

// upward

line = 0x0101010101010100ULL << place;

outflank = ((opponent | ~line) + 1) & line & player;

flip |= (outflank - (outflank != 0)) & line;

// right

line = 0x00000000000000feULL << rplace;

outflank = ((mropponent | ~line) + 1) & line & rplayer;

rflip |= (outflank - (outflank != 0)) & line;

// left

line = 0x00000000000000feULL << place;

outflank = ((mopponent | ~line) + 1) & line & player;

flip |= (outflank - (outflank != 0)) & line;

// d7 downward

line = 0x0002040810204080ULL << rplace;

outflank = ((mropponent | ~line) + 1) & line & rplayer;

rflip |= (outflank - (outflank != 0)) & line;

// d7 upward

line = 0x0002040810204080ULL << place;

outflank = ((mopponent | ~line) + 1) & line & player;

flip |= (outflank - (outflank != 0)) & line;

// d9 downward

line = 0x8040201008040200ULL << rplace;

outflank = ((mropponent | ~line) + 1) & line & rplayer;

rflip |= (outflank - (outflank != 0)) & line;

// d9 upward

line = 0x8040201008040200ULL << place;

outflank = ((mopponent | ~line) + 1) & line & player;

flip |= (outflank - (outflank != 0)) & line;

flip |= rotate_180(rflip);

return flip;

}