ChessVista开发日记之二:核心问题

发布时间:2010-10-14浏览:

核心提示:ChessVista开发日记之二:核心问题

ChessVista的基本架构了,现在要看看接下来有哪些核心问题、关键任务要解决。

 

对于一个国际象棋程序,或者也可以说是对所有的棋类博弈程序来说吧,通常有哪些关键的问题要解决呢?首先,核心算法——即局面表示、着法生成、搜索算法和局面评估——应该是最关键的部分,此外,针对ChessVista的设计目标,还应包括设计博弈引擎的加载、通讯,设计图形界面用的棋盘控件这两个任务。

 

由于国际象棋游戏是所谓的“信息完备”游戏,即对于所有游戏参与者来说,面对的局面是同一个,而且任何一方所掌握的棋盘、棋子的信息是一样的(相对而言,纸牌类游戏、麻将就不是“信息完备”的,因为你不知道对方手里的牌),所以核心算法也仅针对这类游戏设计,暂不考虑非“信息完备”类游戏。

 

局面表示

局面是指某个特定时刻,棋盘上棋子的数量和位置的一个“快照”。与我们实际情况下使用的棋盘、棋子不同,在程序中必须要有特定的数据结构来表示它们,并且还要具备有效的算法来获取、处理这些信息。

 

一个高效的局面表示方法和处理算法非常重要,因为一旦游戏双方的对弈开始,在后面的整个过程中,局面数据是不可或缺的信息,包括着法生成、搜索算法、局面评估和界面显示都离不开它。举例来说,当对方走了一步棋,ChessVista的引擎必须知道对方走了那个棋子、之前的位置在哪里、新的位置在哪里,然后它要判断自己有哪些子可以走、可以走到哪里、哪一种走法是最优的,最后它还要把走的结果反映到当前局面上,并通知界面做出相应的修改,可以看出,这些过程中,随时都要用到棋盘和棋子的局面数据。

 

当前局面的维护以及基本的局面算法都由ChessVista的棋盘服务负责并提供相应的API。

 

着法生成

一旦一方的引擎确定了一步走法,ChessVista必须根据国际象棋的规则判断该走法是否合法,因为若不做这样的检查,任何一个引擎都可以通过某种方式欺骗程序。

 

另一方面,当一个引擎得到走棋的通知,它必须遍历当前局面,判断自己有哪些棋子可以走,同样要根据规则判断哪些走法是合法的,为后面的搜索算法提供基础。

 

虽然上述过程一个是由ChessVista的对弈服务负责,一个由引擎自己负责,但他们依据的都是同一个算法——着法生成,而且实践也证明,在国际象棋的整个设计中,着法生成是最复杂、最费时的事。

 

搜索算法

人类棋手在从众多可选着法中,决定选择某一个时,通常会在大脑中进行推演,只有尽可能缜密地推演出后继自己和对手的着法,才能最大限度地选出最好的着法。对于程序来说,这一方法同样是不二选择,只不过是不同的程序使用的搜索算法不同罢了。

 

实际应用中,针对国际象棋的搜索算法有很多种,各有优缺点,这些不同的算法和设计中会遇到的种种值得思考的事,在后面会进一步探讨。

 

局面评估

最后,当要判断出某一着法是否优于另一种时,或者要判断当前局面是处于优势还是劣势时,必须要有一种评估局面的方法,在象棋程序中,“子力平衡”通常是一个关键的评估因素。

 

考虑到引擎必须在有限的时间内做出评估,选出“最佳”(这里仅指在一定约束条件下做出的最佳判断)着法,局面评估通常要考虑和搜索算法同时轮流进行,才能保证即使是在有限时间下,也一定有解(有一个不是最佳的解,也比没有解要强,好像敏捷开发中的迭代也是这个理 ^_^)。

 

博弈引擎

ChessVista环境和引擎相当于一个小型的C/S结构,初步设想将引擎设计为ChessVista环境的进程内模块,即设计为DLL,由ChessVista环境动态加载。双方之间的通讯采用通用的UCI引擎协议,因此要考虑设计一个UCI协议解析模块,由ChessVista的博弈引擎服务负责,并提供相应接口。同时,还要确定出环境和引擎之间的交互接口规范。

 

棋盘控件

考虑到棋盘扩展的设计目标,将棋盘单独做成一个独立控件,用它来实现棋盘扩展的可视部分逻辑。

 

好了,在ChessVista这幅图上,重要的拼图都已经找出来了,后面,我们就会进入逐个核心问题的实际设计、开发中了,在这个令人激动的探索中,希望大家能一起探讨,共同进步。
 


前一篇:定做程序设计
后一篇:指尖创造网络灵动
分享到: