Stockfish引擎中打包式有符号整数乘法的实现原理疑问

Stockfish国际象棋引擎将中局分数（middlegame score）和残局分数（endgame score）打包到一个int类型中存储：中局分数存在低16位，残局分数存在高16位。这种设计支持加法、减法、取反和乘法的并行执行，但其中乘法的逻辑存在疑问：为何直接对打包后的整数执行乘法，就能同时正确计算中局分数与残局分数各自的乘积？

相关实现代码如下：

/// Score enum stores a middlegame and an endgame value in a single integer (enum).
/// The least significant 16 bits are used to store the middlegame value and the
/// upper 16 bits are used to store the endgame value. We have to take care to
/// avoid left-shifting a signed int to avoid undefined behavior.
enum Score : int { SCORE_ZERO };

constexpr Score make_score(int mg, int eg) {
  return Score((int)((unsigned int)eg << 16) + mg);
}

/// Extracting the signed lower and upper 16 bits is not so trivial because
/// according to the standard a simple cast to short is implementation defined
/// and so is a right shift of a signed integer.
inline Value eg_value(Score s) {
  union { uint16_t u; int16_t s; } eg = { uint16_t(unsigned(s + 0x8000) >> 16) };
  return Value(eg.s);
}

inline Value mg_value(Score s) {
  union { uint16_t u; int16_t s; } mg = { uint16_t(unsigned(s)) };
  return Value(mg.s);
}

#define ENABLE_BASE_OPERATORS_ON(T)                                \\
constexpr T operator+(T d1, int d2) { return T(int(d1) + d2); }    \\
constexpr T operator-(T d1, int d2) { return T(int(d1) - d2); }    \\
constexpr T operator-(T d) { return T(-int(d)); }                  \\
inline T& operator+=(T& d1, int d2) { return d1 = d1 + d2; }       \\
inline T& operator-=(T& d1, int d2) { return d1 = d1 - d2; }

ENABLE_BASE_OPERATORS_ON(Score)

/// Only declared but not defined. We don't want to multiply two scores due to
/// a very high risk of overflow. So user should explicitly convert to integer.
Score operator*(Score, Score) = delete;

/// Division of a Score must be handled separately for each term
inline Score operator/(Score s, int i) {
  return make_score(mg_value(s) / i, eg_value(s) / i);
}

/// Multiplication of a Score by an integer. We check for overflow in debug mode.
inline Score operator*(Score s, int i) {

  Score result = Score(int(s) * i);

  assert(eg_value(result) == (i * eg_value(s)));
  assert(mg_value(result) == (i * mg_value(s)));
  assert((i == 0) || (result / i) == s);

  return result;
}

解答 #

我们可以从数学角度拆解这个逻辑：

• 假设中局分数为mg，残局分数为eg，那么打包后的整数S可以表示为：S = eg * 65536 + mg（左移16位等价于乘以2¹⁶=65536）。
• 当用S乘以整数i时，根据乘法分配律展开：i * S = i*eg * 65536 + i*mg。
• 这个结果刚好就是把i*eg（残局分数乘i）和i*mg（中局分数乘i）重新打包后的数值——i*eg自然占据高16位，i*mg占据低16位。

当然这里有个关键前提：在Stockfish的实际使用场景中，i*mg和i*eg的结果不会超出16位有符号整数的范围，否则会出现跨位溢出（比如i*mg过大导致进位到高16位，破坏残局分数的结果）。代码中的assert语句就是用来验证这一点，确保乘法操作没有破坏高低位的独立性。

内容的提问来源于stack exchange，提问作者Chayim Friedman