你在这里混淆了两三件不同的事情。
- 训练文件格式
- 解析后训练集的内存存储格式(如果您需要保留已解析状态以供将来参考)
- 单个棋盘状态的未打包表示+可选的W/L/D标志
这三种格式都可以不同。训练文件可以是文本,便于编辑。当然,即使您的主程序以二进制格式读取训练集,该二进制也可以由单独的工具从易于编辑的文本格式“编译”而成。
用于处理单个棋盘位置的内部表示:
这需要快速访问和循环。由于您正在训练神经网络,而不是直接编写人工智能,因此您可能不需要经常使用此表示。如果您只需要将每个元素应用于神经网络输入,则没有必要使用单独的格式:直接从更紧凑的表示中解压缩到神经网络输入。
然而,如果您需要多次循环单个棋盘状态,则有一些有趣的选择。正如许多人指出的那样,胜利/失败/平局/未决标志应该与棋盘状态分开考虑。因此,每个棋盘将有一个标志,而不是在每个棋盘位置存储标志。
位棋盘: 我已经阅读了有关国际象棋引擎(例如Crafty)使用64位无符号整数存储所有白色兵的位置的文章。例如,您可以对位图进行按位或运算,以找到任何种类的白色棋子在哪里。
位图(一个用于o
,一个用于x
)将记录整个状态。 连接4个棋盘具有6 * 7网格位置,因此每个位图可以为64位,但32b太小。popcount(board.o)
告诉您棋盘上有多少个 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位整数的单独字节中。 每列在单独的字节中可能比行更有用,因为您可能想要查找列中使用的最高位置。 这只是在列上进行查找第一个设置位操作。 从位图中提取8位块速度更快(不需要屏蔽)。 您可以将42位位图解包到每个列的单独变量中。 在x86上,前4个寄存器对于第一个和第二个8位块是字节可寻址的(AX(RAX的低16位)由AL和AH组成),您(或编译器,但他们可能不会这么聪明)仍然可以将7列存储在4个寄存器中,并能够单独bsr
(位扫描反转)任何列。
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位比特位。在C语言中,无法使用漂亮的board[row][col]
语法,并且42 * 2位无法放入单个寄存器中。交织位板没有优势,并且使一些事情变得更糟,尤其是因为整个东西无法适应64位。(如果您想在位板版本中查找未占用的空间,则需要在o|x
中查找零位。在这里,您必须检查每对2位,而不能使用一个位来将整个问题适合到一个寄存器中。尽管如此,您可以创建一个宏来移动/屏蔽表示给定行/列的2位。它不会生成高效的代码。
字节数组:对于循环检查给定棋盘位置的邻居,使用此格式可能会更快。在位板中,通过位移棋盘以使两个感兴趣的位排成一行,然后进行按位与运算,最后测试该位,即可测试board[i][j] && board[i][j+1]
。至少在x86上,有小字节偏移的寻址模式,因此,给定一个棋盘位置的地址,与另一个棋盘位置进行按位与运算可能只需要一条指令。
在每个字节中,一个位表示x,另一个位表示o,另一个位应设置为如果位置是x或o。这允许检查多个位置是否都被占用,并检查已占用的位。否则,您必须检查每个网格中的x或o位是否已设置。
enum boardpos {
POS_EMPTY = 0,
POS_O = 1<<0,
POS_X = 1<<1,
POS_OCCUPIED = 1<<3
};
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;
};
文件格式表示:
一种更紧凑但仍易于使用的格式是xbbb...ooxbbw
。然后,您不需要将行解析为字符串,只需作为大小为43个字符(如果每个记录由换行符分隔,则为43)的恒定大小块进行解析。如果有任何不是胜利、失败或平局的棋盘位置,请使用另一个字符来标记。空格或'n'
。
省略逗号可以将大小减少近一半。您不想在逗号和其他东西上解析输入。从简单的运行长度编码符号中可能会有潜在的进一步收益,例如xb2o1xb1w
。看到数字意味着重复最后一个字符那么多次。也许x
表示一个x,大写X
表示两个x。这已经到了人类难以阅读的地步。LZOP或LZ4压缩可能能够很好地压缩。
二进制文件格式:
显然,文本表示有其限制。 固定大小的二进制记录可以非常小,因为需要存储的信息不多。每个网格位置使用2位可能已经足够紧凑,但仍存在冗余,因为它可以表示x和o同时出现在同一位置的不可能状态。为了做得更好,您需要将整个棋盘或整行或整列的状态映射到多位表示中。维基百科说,所有棋盘上填充0至42个棋子的合法位置总共有4,531,985,219,092个。这只是2 ^ 42的稍微超过。因此,43位应该足以表示任何有效的棋盘状态,包括所有未决定的位置。我不知道如何将游戏编码为43位整数,至少没有可用的方法(即比枚举所有可能的游戏并在匹配的那个停止更快的方法)。
如果您使用位棋盘作为内部快速表示,请将它们紧密存储在文件格式中,使得
o
和
x
棋盘以及w/d/d状态只占用12个字节,或者如果您喜欢整数,则为16个字节。
struct __attribute__ ((__packed__)) compact_game_state {
struct __attribute__ ((__packed__)) compact_board_state {
uint64_t o:42, x:42;
} board;
uint8_t victory;
};
struct semi_compact_game_state {
struct __attribute__ ((__packed__)) semi_compact_board_state {
uint64_t o:48, x:48;
} board;
enum winlose victory;
};
这些代码可以通过g++编译:
在godbolt上查看。
使用
端无关代码进行I/O,这样就不会在大端机器上出现问题。这是一个文件格式,因此实际上访问方式并不重要,只要正确的字节放在正确的位置即可。对于文件格式,小端可能是一个好选择,在小端机器上,load/store代码是一个空操作。或者只需懒惰地对一组结构进行二进制I/O,并仅在与训练数据集具有相同字节序的机器上使用您的代码。
如果您不使用位棋盘,最好使用一个由2位字段组成的数组。随机访问可能很慢,但将其转换为字节数组可能比分别用于两个位字段更快。屏蔽掉低2位,将其用作索引进入查找表
{POS_EMPTY,POS_O | POS_OCCUPIED,POS_X | POS_OCCUPIED}
。然后按2位进行位移,将下一个字段带入低位。棋盘占用84位,因此可以在单独的32位或64位块中执行操作。不需要进行128位双重移位。胜利/失败/平局信息可以放在最后的2位块中。
将此打包成一个12字节的三个uint32_t结构,或一个uint64_t和一个uint32_t结构。或者只是一个uint8_t数组,但这样更难让编译器执行一次宽加载。你可以将东西打包到一个11字节的结构中,但对齐更成问题。如果节省1/12的内存大小对缓存有用的话,请去做。在x86 CPU上,跨越高速缓存线的负载只会多花费几个周期,并且您不会经常进行加载。(使用12B结构,第一块的64位加载不会对齐到64b,但至少会分成两半,这是一种特殊情况,在某些CPU上比不平衡的高速缓存线分裂更快。)
将单独的位板解码为字节数组需要分别移动每个位板,我想。它仍然可以是无分支的,但不太好看。
棋谱数据库的内存存储
在表示之间进行转换需要CPU时间,因此如果没有用处,就从文件格式转换为内部格式。
如果您使用的是文本文件格式,并且使用非紧凑快速格式,则为此单独创建格式可能仅有用。在这种情况下,将文件解析为打包的2位位置(例如该文件格式,请参见上文)。
如果您的文件格式是二进制的,请保留它。(甚至只需内存映射文件。)
x,b,b,b...o,o,x,b,b,win
,并且我认为最好的起点是迭代它并用优化后的设置替换当前设置。 - asdf