C++，用一个字节存储两个变量

Question

我正在研究国际象棋棋盘的表示，我计划将其存储在 32 字节数组中，其中每个字节将用于存储两个棋子。 （这样每块只需要 4 位）

这样做会导致访问板的特定索引的开销。 您认为该代码可以优化还是可以使用完全不同的访问索引的方法？

我同样

char getPosition(unsigned char* c, int index){
    //moving pointer
    c+=(index>>1);

    //odd number
    if (index & 1){
        //taking right part
        return *c & 0xF;
    }else
    {
        //taking left part
        return *c>>4;
    }
}


void setValue(unsigned char* board, char value, int index){
    //moving pointer
    board+=(index>>1);

    //odd number
    if (index & 1){
        //replace right part
                 //save left       value only 4 bits
        *board = (*board & 0xF0) + value;
    }else
    {
        //replacing left part
        *board  = (*board & 0xF) + (value<<4);
    }
}


int main() {

    char* c = (char*)malloc(32);

    for (int i = 0; i < 64 ; i++){
        setValue((unsigned char*)c, i % 8,i);
    }

    for (int i = 0; i < 64 ; i++){
        cout<<(int)getPosition((unsigned char*)c, i)<<" ";

        if (((i+1) % 8 == 0) && (i > 0)){
            cout<<endl;
        }


    }


    return 0;
}

对您关于国际象棋表示以及上述方法的优化作为一个独立问题的看法感兴趣。

非常感谢

编辑

感谢您的回复。不久前，我创建了跳棋游戏，其中使用 64 字节棋盘表示。这次我尝试了一些不同的方法，只是想看看我喜欢什么。内存并不是什么大问题。 Bit-boards 绝对在我的尝试清单上。谢谢

Answer 1

这就是过早优化的问题。您的棋盘原本需要 64 个字节来存储，现在需要 32 个字节。这真正给您带来了什么？您是否真的分析了情况以查看是否需要保存该内存？

假设您使用了最不理想的搜索方法之一，直接 AB 搜索到深度 D，没有启发式，并且您在搜索之前在某个位置生成了所有可能的移动，那么您的棋盘所需的绝对最大内存将是 sizeof(board) * W * D。如果我们假设相当大的 W = 100 和大 D = 30，那么您将在深度 D 的内存中拥有 3000 个板。64k 与 32k...真的值得吗？

另一方面，您增加了访问 board[location] 所需的操作量，并且每次搜索将调用数百万次。

在构建国际象棋人工智能时，您最终要寻找的主要内容是 CPU 周期，而不是内存。如果您的目标是手机或其他设备，这可能会有所不同，但即使如此，在达到足够的深度以导致任何内存问题之前，您也会更加担心速度。

至于我更喜欢​​哪种表示形式......我喜欢位板。没有进行大量认真的测量，但我确实比较了我制作的两个引擎，一个位板和一个阵列，位板一个速度更快，并且可以比另一个引擎到达更大的深度。

Answer 2

让我第一个指出潜在的错误（取决于编译器和编译器设置）。错误就是为什么过早优化是邪恶的：

   //taking left part
    return *c>>4;

如果 *c 是负数，那么 >>>可以重复负高位。即二进制：

0b10100000 >> 4 == 0b11111010

对于某些编译器（即 C++ 标准将其留给编译器来决定 - 是否携带高位，以及 char 是有符号还是无符号）。

如果您确实想继续处理您的打包位（让我说您可能不应该打扰，但这取决于您），我建议将打包位包装到一个类中，并覆盖 [] ，这样可以

board[x][y] 

给出你是解压的部分。然后您可以轻松地打开和关闭打包，并且在任何情况下都具有相同的语法。如果您内联运算符重载，它应该与您现在的代码一样高效。

Answer 3

嗯，64 字节是非常小的 RAM。你最好只使用 char[8][8] 。也就是说，除非您计划存储大量棋盘。执行 char[8][8] 可以更轻松（且更快）地访问板并对其执行更复杂的操作。

如果您仍然对以打包表示形式存储板感兴趣（无论是为了练习还是存储大量板），我说您在位操作方面“做得正确”。如果您想使用 inline 关键字提高速度，您可能需要考虑内联访问器。

Answer 4

当您不能仅使用完整字节来表示正方形时，空间是否足够考虑？这将使程序上的访问更容易遵循，而且由于不需要位操作，因此很可能更快。

否则，为了确保一切顺利，我将确保所有类型都是无符号的：getPosition 返回无符号字符，并用“U”（例如 0xF0U）限定所有数字文字，以确保它们始终被解释为无符号。您很可能不会遇到任何符号性问题，但为什么要在某些行为异常的架构上冒险呢？

Answer 5

不错的代码，但如果您真的对性能优化如此深入，您可能应该更多地了解您的特定 CPU 架构。

AFAIK，您可能会发现将棋子存储在 8 个字节中会更有效。即使深度递归 15 次，L2 缓存大小也几乎不会成为约束，但 RAM 未对齐可能。我猜想正确处理棋盘将包括 Expand() 和 Reduce() 函数，以在算法的不同部分期间在棋盘表示之间进行转换：有些在紧凑表示上可能更快，有些反之亦然。例如，缓存和涉及通过两个相邻单元的组合进行散列的算法可能有利于紧凑结构，但其他一切都没有。

如果性能如此重要的话，我还会考虑开发一些辅助硬件，例如一些 FPGA 板或一些 GPU 代码。

Answer 6

作为一名国际象棋棋手，我可以告诉你：走位不仅仅取决于每颗棋子的位置。你必须考虑其他一些事情：

1. 哪一方接下来必须采取行动？
2. 白色和/或黑色城堡可以是国王和/或皇后区吗？
3. 典当可以被带走吗？
4. 自上次棋子移动和/或吃子移动以来已经经过了多少步？

如果您用来表示仓位的数据结构不能反映此信息，那么您就有大麻烦了。