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++标准不建议这么做,而内联函数是个不错的选择,用来实现频繁调用的短小功能。
棋盘的数据结构就讨论到此了,打算下篇开始讲“提子”——这是常规算法部分的难点,提子算法设计得好坏将极大影响程序的性能。
分享到:
相关推荐
人工智能学习应用实验作业,围棋博弈,使用的是java语言实现
DarkForest这是一个幻影围棋计算机博弈程序,一个可以和人类下棋的程序。幻影围棋介绍:幻影围棋是一项欧洲的棋类游戏,因为下棋规则是基于围棋,但又是在围棋的基础上加入了信息不完全的限制——看不到对方的落子,...
- 围棋规则、围棋死活题介绍、算法实现以及优化、围棋棋盘编码、参数组合优化 等内容可参考paper文件夹中的pdf文件。 【备注】 1.项目代码均经过功能验证ok,确保稳定可靠运行。欢迎下载使用体验! 2.主要针对各个...
围棋C语言程序实现源代码.docx围棋C语言程序实现源代码.docx
围棋C语言程序实现源代码.pdf围棋C语言程序实现源代码.pdf
css grid布局+原生js操作dom动态生成围棋棋盘 之前写的过于简陋了 目前站台不支持删除 不要下载了
分析了幻影围棋计算机博弈系统的模型与结构,结合Alpha-Beta搜索算法和蒙特卡洛算法的优势,依据棋盘状态采用不同的搜索算法,调用搜索引擎产生下子,在此基础上开发实现了一个幻影围棋博弈系统,能有效的交互和处理...
人工智能 五子棋 围棋 博弈树 实验 课程设计
在html页面中使用javascript脚本,动态添加div元素,实现一个19*19的围棋棋盘,资源包含各坐标点的背景图片以及js完整代码。
1、有基本的布局、画布等 2、有按钮跳转等功能 3、使用画图工具画了围棋棋盘以及几颗棋子(算是定式) 4、app的base_media图片换为了原神刻晴(可用windows自带的画图来调整尺寸大小),跳转界面也是刻晴
简单围棋博弈神经网络,用pytorch写成,无图形界面。没什么注释,但是应该能看懂
微信小程序项目实例——双人五子棋 双人五子棋是一款游戏小程序 两位选手可以在15x15的棋盘上 进行五子棋竞技 小程序设置了悔棋功能
基于minigo的幻影围棋,支持人机,机机博弈程序
[纯C语言 + Win32 API]一步一步写个围棋程序之八:棋盘来了
围棋棋盘3D模型适用于棋盘模型设计
Java Applet 围棋源程序 使用最简单的思想解决围棋吃子问题. 作者保留所有权利,禁止转载!
关于人工智能方面围棋博弈的研究内容,复旦大学,硕士论文,严达骏,
幻影围棋棋源代码,参加计算机博弈比大赛亚军的代码。
C++围棋程序实现报告.pdfC++围棋程序实现报告.pdf