c - c中的3位无符号整数

Question

我正在建立一个深层神经网络来玩connect-4，它必须在一台非常有限的机器上与其他AI机器人竞争（尚不知道具体的限制，只是我只有几个核心和少量的核心记忆）。因此，我希望以任何可能的方式优化我的训练集。目前，它代表董事会中的州：

b代表空白（无片段）

x表示“ x”个

o表示“ o”个

win获胜设置

loss丢失设置

draw用于绘制设置

本质上，我正在尝试对其进行映射，以便我的3位整数可以代替这些占用大量内存的字符串。我考虑过要使用short，但是它比16位的char差。我想这样映射它：

000-> b

001-> x

010-> o

011-> win

100-> loss

101-> draw

因为我可以用3位而不是char（每个char 8位，yikes！）来表示这些状态，所以我想尝试一下。但是我不确定如何在c中实例化这样的变量。

训练集为67557行，每行代表6x7的木板，其后有赢/输/平局条款。因此，每个字符节省5位将节省每行(5*6*7)+(5*1) = 215位和整体215*67557 = 14524755位（共1.90 MB，共2.90 MB，总空间减少了62％）。

Answer 1

您在这里有两三个要合并的不同内容。


训练文件格式
解析后的训练集的内存存储格式（如果您需要保留解析后的状态以备将来参考）
单板状态的解压缩表示形式+可选？ W / L / D标志


所有这三种格式都可以不同。培训文件可以是易于编辑的文本。当然，即使您的主程序以二进制格式读取训练集，也可以使用单独的工具从易于编辑的文本格式“编译”该二进制文件。

内部说明用于单个董事会职位：

这需要快速访问和循环。由于您是在训练神经网络，而不是直接编写AI，因此您可能不需要非常处理这种表示形式。如果只需要将每个元素应用于神经网络输入而无需做太多事情，那就没有别的格式了：直接从更紧凑的表示形式直接解压缩到神经网络输入。

但是，如果必须多次遍历单个板状态，则可以选择一些有趣的方法。正如许多人指出的那样，赢/输/平/未定标志应与董事会状态分开考虑。因此，每个板将有一个标志，而不是在每个板位置都存储该标志。


位板：例如，我已经了解过使用64位unsigned int存储所有白色棋子的象棋引擎（例如，狡猾的国际象棋引擎）。您可以对位图进行按位“或”运算，以查找所有白色部分的位置。

位图（一个用于o，一个用于x）将记录整个状态。 connect-4板具有6 * 7网格位置，因此每个位图可以是64位，但是32b太小。 popcount(board.o)告诉您板上有多少个操作系统。 assert(o & x == 0)将是一个很好的检查方法，因为不可能在同一位置出现o和x。

在结构中使用两个压缩的42b字段将是一个坏主意，因为加载/存储会很慢。即使将它们打包到48位字段中（因此它们以字节边界结尾）也将导致加载/存储速度变慢。请记住，这是我们的快速格式。我们可以使用打包格式进行长期存储。

像board[0][0] && board[0][1] && board[0][2] && board[0][3]这样的东西（尽管不是这种语法）在编译时位置恒定，在位板上非常快。一个按位与运算仅保留那些可能设置的位，然后可以与掩码进行比较以查看是否所有位都已设置。要测试||而不是&&，请省略第二步。您可以对o或x位图或o|x进行这些测试，以检查其中的任何一种。但是，如果您必须在运行时从可变位置构建遮罩，则效率不高。

要扫描棋盘上是否有赢球，您可以检查左列，然后将遮罩移位，以便检查下一个列。实际上，像这样用蛮力检查所有列可能比检查标记的邻居（寻找2合一候选）要慢。

如果位图是全64位（代表8x8电路板），则某些操作可能会更容易，但实际上您仅使用其左下角的7x6。这样，单独的列位于64位整数的单独字节中。将每一列放在一个单独的字节中可能比行更有用，因为找到一列中使用率最高的位置是您可能想做的事情。这只是该列上的find first set bit操作。从位图中提取8位块的速度更快（不需要屏蔽）。不过，您可以解压缩一个42位的位图以分隔每一列的变量。在x86上，前4个寄存器可针对第一个和第二个8位块（AX（RAX的low16）由AL和AH组成）进行字节寻址，您（或编译器）可能不是那么聪明）可以在4个寄存器中存储7列，并且仍然能够分别bsr（位扫描反向）任何列。

// Sample bitboard implementation:
struct game_state {
    struct board_state {
       uint64_t o, x;
    } board;
    enum winlose { GAME_UNDECIDED=0, GAME_WIN_O, GAME_WIN_X, GAME_DRAW } victory;
};

2位字段的数组：请勿使用。一个类似的实现将对每个位置使用一个2位的位域。 It's impossible to use with nice board[row][col] syntax in C，并且42 * 2位不适合单个寄存器。交织位板没有任何优势，尤其会使某些事情变得更糟。因为整个内容都不适合64位。 （如果要在位板版本中查找未占用的空间，请在 o|x中查找零位。在这里，您必须检查每两对2位，而不是能够逐位使用一个位来解决整个问题仍然，您可以创建一个宏来移位/屏蔽表示给定行/列的2位，但这不会产生有效的代码。
字节数组：使用这种格式循环检查给定板位置的邻居可能更快。在位板中，可以通过对板进行位移位来测试 board[i][j] && board[i][j+1]，以便将感兴趣的两条线对齐，然后按位与，然后对该位进行位测试。至少在x86上，存在具有较小字节偏移量的寻址模式，因此，给定一个板卡位置的地址，与另一个板卡位置进行“与”运算可能只需要一条指令。

在每个字节中，一位代表x，另一位代表o，如果位置是x或o，则应将另一位置1。这允许通过将多个位置与在一起进行“与”运算来检查多个位置是否都被占用，并检查占用位。否则，您必须检查每个网格中是否设置了x或o位。

// Sample byte-array implementation:
enum boardpos {
    POS_EMPTY = 0,
    POS_O = 1<<0,
    POS_X = 1<<1,
    POS_OCCUPIED = 1<<3
};
// maybe #define for these constants instead?

struct game_state {
    struct board_state {
       uint8_t pos[6][7];
    } board;
    enum winlose { GAME_UNDECIDED=0, GAME_WIN_O, GAME_WIN_X, GAME_DRAW } victory;
    // or maybe stuff the winlose info into the high bits of board.pos[0][0]?
    // Not much point, since the struct will probably be the same size after padding anyway.
};

文件格式表示：

xbbb...ooxbbw是更紧凑但仍易于使用的格式。这样，您就不必将行解析为字符串，就像将其解析为一个恒定大小的43个字符的块一样（如果每个记录用换行符分隔，则为43）。如果您的董事会职位不是赢家，输家或平局，请使用其他字符进行标记。空格或 'n'。

只需省略逗号，您的大小就会减少近一半。您不需要解析输入的逗号和内容。一个简单的游程长度编码表示法（例如 xb2o1xb1w）可能会带来更多收益。看到数字意味着重复最后一个字符多次。也许 x表示一个x，大写字母 X表示两个x。到了一个让人难以阅读的地步。 LZOP或LZ4压缩可能会很好地压缩内容。

二进制文件格式：

显然，文本表示形式是有限制的。固定大小的二进制记录可能很小，因为没有太多信息要存储。每个网格位置使用2位可能足够紧凑，但是仍然存在冗余，因为这可以表示x和o在相同位置的不可能状态。为了做得更好，您需要将整个电路板或整个行或列的状态映射到多位表示。 Wikipedia says所有游戏板上有0,42个零件的合法位置为4,531,985,219,092。刚好超过2 ^ 42。因此43位应该足以表示任何有效的板状态，包括所有尚未确定的位置。 IDK如何将游戏编码为43位整数，至少没有什么可用的（即比实际枚举所有可能的游戏并停止匹配的游戏要快）。

如果使用位板作为内部快速表示，请以文件格式打包存储，因此 o和 x板以及w / d / d状态适合12字节，如果您喜欢整数，则适合16字节。 。

// do some pre-processor stuff to choose between GNU C __attribute__ ((__packed__))
// and the MSVC #pragma pack
struct __attribute__ ((__packed__)) compact_game_state {
    struct __attribute__ ((__packed__)) compact_board_state {
       uint64_t o:42, x:42;
    } board; // sizeof = 11
    uint8_t victory;
}; // sizeof = 12

struct semi_compact_game_state {
    struct __attribute__ ((__packed__)) semi_compact_board_state {
       uint64_t o:48, x:48;
    } board; // 96 bits = 12 bytes
    enum winlose victory; // another 4 bytes
};

这些实际上是用g ++编译的： see on godbolt。

使用 endian-agnostic code进行I / O，因此在大端存储机器上不会中断。它是一种文件格式，因此，只要正确的字节放在正确的位置，对它的访问方式实际上并不重要。小尾数法可能是文件格式的不错选择，因此在小尾数法计算机上，加载/存储代码是禁止操作的。或者只是懒惰并在结构数组上执行二进制I / O，并且仅在与训练数据集具有相同字节序的机器上使用代码。

如果您不使用位板，则最好使用2位字段的数组。随机访问的速度可能很慢，但是将其转换为字节数组可能比两个单独的位域要快。屏蔽掉低2位，将其用作 { POS_EMPTY, POS_O|POS_OCCUPIED, POS_X|POS_OCCUPIED }查找表的索引。然后位移两位以将下一个场置于低位。该开发板占用84位，因此需要单独的32位或64位块。不需要进行128位双移位。赢/输/平局信息可以进入最后的2位块。

将其打包成三个uint32_t或uint64_t和uint32_t或其他内容的12字节结构。或只是一个uint8_t数组，但是很难使编译器进行一次广泛的加载。您可以将内容打包到一个11字节的结构中，但是对齐更成问题。如果节省1/12的内存大小对缓存有很大的帮助，那就去吧。跨高速缓存行的负载在x86 CPU上仅会花费几个额外的周期，并且您的负载并不频繁。 （第一个块的64位负载无论如何都不会与64b对齐，具有12B结构，但至少会在中间拆分，这是一种特殊情况，它比某些CPU上不均匀的缓存行拆分要快。 ）

我认为，将单独的位板解码成字节数组将需要分别移动每个位板。它仍然可以是无分支的，但效果不佳。

游戏数据库的内存中存储

在制图表达之间进行转换会占用CPU时间，因此如果没有用，请从文件格式转换为内部格式。

如果您保留文本文件格式并使用非紧凑型快速格式，那么只有一种单独的格式可能才有用。在这种情况下，将文件解析为压缩的2位位置（类似于该文件格式，请参见上文）。

如果您的文件格式是二进制文件，请保留该格式。 （甚至只是对文件进行内存映射。）