计算机博弈程序——棋局表示

棋局表示

考虑要点：

1.     占用空间

2.     操作速度

3.     使用方便与否

 

常用表示

1.     从棋盘观点出发：

中国象棋：

14种棋子+空白=15种状态  需要4位表示（2^4=16）

每个字节表示2个交点 高4位低4位分别表示棋盘奇偶行 

10*9的棋盘共需9*5 Byte=45Byte

六子棋：

2种棋子+空白=3种状态   需要2位

每字节表示4个交点 行数模四处理？？

19*19的棋盘共需19*5 Byte=95 Byte

 

 

 

2.     棋子观点出发：

中国象棋：

       用一个字节表示所有棋子坐标

每子横纵坐标各需要4字位，每子1Byte

32个棋子共32 Byte

六子棋：

不确定棋子数目，且棋子种类单一无法区分，无法表示

 

以上紧凑表示法需要空间较小，复制棋盘时间很快，但是操作耗时，需额外运算

 

3.     数组表示

中国象棋：

用10*9的数组直观表示棋盘，棋子用固定数值的1Byte表示。1~14（图示）

共需90 Byte

六子棋：

用19*19的数组表示只有0，1，2三种类型同样需要1Byte

     共需361 Byte

 

考虑的问题是，对六子棋来说361 Byte的棋局在复制和存储的时候速度和内存空间就可能有影响了

 

 

4.     比特棋盘

国际象棋：

用12个8*8的64位数表示12种棋子位置，利用速度更快的按位与和或操作判断局势

非常快！

六子棋：

只有两种棋子，比较将会是更快的

 

由于六子棋局势判断要比国际象棋复杂，比如国际象棋判断是否会被将军只需将对方棋子与己方王位置按位与，而六子棋涉及活四三二等判断，使用BIT Board仍比较复杂。然而我认为仍会比普通表示法快很多。