3

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

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

C++

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 绝对在我的尝试清单上。谢谢

4

6 回答 6

9

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

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

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

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

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

于 2010-04-16T20:40:11.043 回答
3

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

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

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

0b10100000 >> 4 == 0b11111010

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

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

board[x][y]

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

于 2010-04-16T21:28:21.087 回答
2

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

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

于 2010-04-16T20:32:24.483 回答
0

如果您不能只使用一个完整字节来表示一个正方形，那么空间是否足够考虑？这将使访问更容易在程序上进行，并且由于不需要位操作，因此很可能更快。

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

于 2010-04-16T20:37:08.783 回答
0

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

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

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

于 2010-04-16T20:38:20.190 回答
0

作为一名国际象棋选手，我可以告诉你：一个位置不仅仅是每个棋子的位置。您必须考虑其他一些事情：

  1. 下一步必须移动哪一边？
  2. 白色和/或黑色城堡国王和/或皇后区可以吗？
  3. 一个典当可以被拿走吗？
  4. 自上一次兵移动和/或捕获移动以来已经过去了多少移动？

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

于 2010-04-16T21:28:33.493 回答