`
coolsooner
  • 浏览: 1302943 次
文章分类
社区版块
存档分类
最新评论

围棋博弈程序的实现与思考(4)——棋盘的数据结构

 
阅读更多

UCT算法算是介绍完了,以后主要讲实践。

由于在面向对象的编程语言中,本人只会C++和Objective-C(以后也许会写一些iOS开发相关的博文),出于性能的考虑,选择C++是必然的。记得当初开题答辩时,一老师问道,既然考虑性能,为什么不用C,而用C++?对于这种明知故问无厘头的问题,我只能回答:机器码性能更好。后来才知道陈志行老师的”手谈“是用汇编写的……

本篇还是谈谈棋盘的数据结构吧!(这里就不谈整个程序的架构了,因为本来就设计得不好)

通常而言围棋棋盘是19X19大小的,但计算机围棋就各种大小都有了(不会超过19路是肯定的,原因……)。所以程序要支持可变大小的的棋盘,能想到的有两种方法:

1)通过一个变量表示棋盘大小,在程序运行时动态分配棋盘空间。

2)用C++的模板,将横盘大小作为棋盘类的模板参数。

第1)种方法需要在程序运行时刻动态申请推空间,而第2)种方法则是在程序运行时由OS分配栈空间,效率上大优于第1)种。考虑到在程序中,棋盘大小不会频繁变动,而效率因素是很重要的,因此采用第2)种方法!(我的程序Foolish Go中误采用了第1)种方法……)

下面来讨论棋盘数据的具体存储方法:

棋盘是为了表明当前棋局状态的所有信息,考虑现实中的棋盘,有哪些信息呢?

1)棋盘上每一个交叉点的状态(黑子,白子,空点)。2)当前的落子方。3)劫位。

在横盘类中同样需要表示这3个信息,需要仔细考虑的是,怎样表示棋盘上每一个交叉点的状态?

交叉点状态应该是什么类型呢?布尔?但是有3种状态,布尔表示不过来~整型?

整型确实可以,也确实有程序用短整型表示交叉点状态。但从节省棋盘内存空间的角度考虑,整型是不够的!

没错,还是布尔!不过要两个~

我的程序Foolish Go借鉴了GNU Go(没记错的话)的做法——用两个棋盘——一个黑棋盘,一个白棋盘来表示棋局状态,其实质是用两个布值表示一个交叉点状态。来计算一下棋盘的大小:9 * 9 * 4bit = 324bit,补8的话就是328bit。

什么?一个布尔值占8bit?MS是的……但是可以自己写代码打包啊,让数组中的每一个布尔值都占1bit!而通过位运算的读写操作是不会太费时的。

什么?懒得写!嗯,我也懒得写,但还是有办法——C++的STL中有个叫bitset模板类的,数组长度作为模板参数……不用担心,它是静态分配内存空间的~(我的Foolish Go用了vector<bool>,虽说vector<bool>是vector模板对bool作了特化,也进行了打包,但它是动态分配空间的……)这样做除了节省内存空间,另一个好处是减少深拷贝棋盘的时间复杂度。

这里有一个问题,棋盘是二维的,而我们用一维的数组,这就需要一维的数组下标与二维数组间的转化。用一个函数做这个工作显然是必须的,但性能是个问题。用C语言的利器,宏函数?可以,但太难看了,C++标准不建议这么做,而内联函数是个不错的选择,用来实现频繁调用的短小功能。

棋盘的数据结构就讨论到此了,打算下篇开始讲“提子”——这是常规算法部分的难点,提子算法设计得好坏将极大影响程序的性能。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics