二、 背景
我最开始写这个程序是为了作为学习C#和.NET编程的一个练习。Reversi-或Othello一是一个相当有趣且相当流行的游戏,它仅要求几个基本元素和简单的游戏规则。所以,它是学习一个新的编程环境的良好选择。
该程序的第一个版本是一个可玩的游戏,但是缺乏一些计算机平板游戏的常规特性,例如撤消移动的能力。因此,在又学习了.NET编程的一些技巧后,我又对该游戏进行了改进。修改后的游戏在原先的图形和人工智能方面增加了一些新特性并作了性能上的改进。
三、 使用代码
你只要编译源文件并运行结果可执行文件Reversi.exe,即可开始玩这个游戏。使用菜单或工具栏,你可以进行多方面的选择和设置。你不妨试着在游戏中间缩放窗户,改变颜色或交换边界来观察所发生的情况。
你可能注意,在你退出该游戏时,该程序将创造一文件Reversi.xml。这个文件被使用于保存多方面设置-例如游戏选项,窗户大小和位置以及进行玩家统计-它们在游戏重新开始时被重载。
四、 帮助文件
本文还提供一个Windows帮助文件,包括完整的源代码。你可以在文档的"help files"子目录找到它。为了使这个帮助文件可应用于该程序,只需简单地把文件Reversi.chm复制到可执行文件Reversi.exe所在位置即可。当然,没有它你也可以运行此游戏,但是如果点击"Help Topics"选项将显示一个错误的话-说明该游戏主程序不能发现帮助文件。
所有用于创建这个帮助文件的源文件包括在那个子目录下。你可以使用微软的HTML Help Workshop对之进行编辑并且重新编译它。
五、 兴趣点
相应的源文件已经被很好的注释过了,读者可以很容易的看懂。现在让我们分析一下本游戏中几个有趣的方面。
(一) 游戏AI
本游戏的一个很有意思的地方是计算游戏玩家的移动,所以值得讨论。本游戏使用一标准的"最小最大向前看"算法来确定玩家的最佳移动。Alpha-beta pruning被使用于改进向前搜索的效率。如果你不熟悉"最小最大向前看"算法和/或alpha-beta pruning,你可以用Google搜索来找到大量的相关信息和示例。
当然,在游戏中可能存在的太多的移动顺序将导致一个相当费时的向前搜索-要生成所有可能的移动组合需要花太长的时间。这里的例外是在游戏的结束时-此时仅剩下很少的几个方格-大约十或二十个。此时,可以进行全部的搜索并且这时可能找到玩家的最佳移动结果。
但是在大多数情况中,向前搜索深度必须被限定到一个数目(这基于游戏的难度设置)。因此,对于每一系列可能的行动和反向移动搜索,必须计算最后的游戏平板以决定哪个玩家最有机会赢得游戏。该计算是通过使用下列标准来计算一个等级:
(本文来源于图老师网站,更多请访问http://m.tulaoshi.com/bianchengyuyan/)输掉-让你的对手没有合法的移动可以迫使他输掉这一回合,从而使你更有利于能够在一行中再次(或多次)移动。
可移动性-这是一种测算-你可以做出多少次合法的行动从而留给你的对手多少次合法的行动。类似于输掉,其思想是,减少你的对手的选择,从而最大化你自己的选择。
边界-一个边界圆盘是邻近一个空的方格的地方。一般地,拥有大量的边界圆盘,会给你的对手在随后的回合中更多的可移动性。相反,拥有较少的边界圆盘意味着你的对手将在后面有较少的可移动性。这种得分反应了你的边界圆盘相对于你的对手的边界圆盘数。
稳定性-角圆盘是稳定的,它们永不会被翼侧包围。随着游戏的进展,另外的圆盘也将变为稳定的。这种得分反应了你的稳定圆盘数相对于你的对手的稳定圆盘数。
得分-这是在平板上你的圆盘数相对于你的对手的圆盘数之差。
不同的权值分别被赋给这里的每一种得分(这再次依赖于游戏的当前难度设置)。通过每一种标准得分乘以它的相应权值,然后把这些值加在一起,一个平板即被赋予一个等级。一个大的负数等级代表一个平板有利于黑棋,而一个大的正数等级代表一个平板有利于白棋。因此,对于一个可能的移动集合,计算机将为当前选定颜色一方选择最可能导致最高等级的那个移动。
一个常数maxRank被用于一场游戏的结束。它被设置为System.Int32.MaxValue-64。这可以确保任何会导致游戏结束的移动将总是比其它移动具有更高的等级(负数或正数)。
从系统的最大整数值减去64允许我们把最后的得分添加到等级上,这样赢得10个圆盘将比赢得2个圆盘具有高的等级。这可以使得计算机玩家在赢了时最大化自己的得分(或在输了时最小化对手玩家的得分)。
当前的实现还不能匹配更好的AI玩家,但是如果它和一个小人对手(至少,这个小人对手)玩得话,已经比较难了。同样,如果你用Google搜索一下,会找到许多描述此游戏策略和AI方法的资源。
(二) 游戏部件
1. 平板类
Board类描述了一个游戏平板。它使用一个二维数组来跟踪每个平板方格的内容,它可以是定义在类中的下列的常数值之一:
Black=-1
Empty=0
White=1
该类提供了两个构造器。一个用于创建一个新的空的平板,而另一个创建一个已存在平板的拷贝。
它提供象MakeMove()这样的公共方法-这个方法把一个圆盘添加到平板上,并能翻动任何可翼侧包围的对手圆盘。例如,IsValidMove()可被用来确定是否一个给定的移动对于一个给定玩家是有效的。如果该给定玩家不能作任何合法的移动,HasAnyValidMove()将返回false。
另外,它还为每一个玩家跟踪圆盘的数目-该数目被用于机器的移动AI例程。这些数目包括圆盘总数、边界圆盘数和每种颜色的安全圆盘(或未翻动的圆盘)数。
2. 移动结构
在主要的ReversiForm类中,定义了一对结构用于存储游戏移动。这两个结构都包含了一个行与列索引对以相应于一个特别的平板方格。
ComputerMove结构用于计算机AI。除了移动位置之外,它还有一个等级成员。这是被用于跟踪一次移动的好或坏-这是在向前搜索过程中决定的。
MoveRecord结构用于存储在游戏中每次移动的信息。为了允许移动的撤消/重做特性,建立了一个数组来跟踪每一轮游戏中的该平板。一次移动记录包含一个描述这次特定移动之前的游戏平板,还有用来指示哪一个玩家将做下次移动的值。针对每个玩家的每次移动建立一个相应的数组以允许游戏复位到在移动过程中的任一点的状态。
RestoreGameAt()方法实现把游戏复位到一个特定的移动数字。尽管它潜在地允许游戏可以恢复到当前移动历史中的任何移动;但是,主表单程序中的菜单和工具条选项目前仅提供了一次移动的撤消/重做或所有移动的撤消/重做。一种将来的增加可能是允许用户点击移动列表中的项来把游戏恢复相应的移动数字。
(三) 图形和用户接口
1. 游戏平板
平板上的方格被一个叫SquareControl的用户控件所描述。对于每个方格都有一个这种控件显示于游戏平板上。该控件包含信息-用于显示方格和它的内容(空的或一个黑的或白的圆盘),包括圆盘动画和任何高亮。
2. 显示圆盘
每一个圆盘被动态绘制。其基本形状是一个圆-具有某种高亮和一个阴影来给它一个伪装的3D外观。这些形状被按比例缩放,依赖于方形控制的当前尺寸。通过以这种方式对其着色,代之使用静态的图像,平板可以被动态地调整大小以匹配表单窗口的大小。
在ReversiForm内部控制的方格控件的Click事件允许用户一次移动到一个特定的方格(假定它是一个合法的移动)。同样,当这些选项激活时,MouseMove和MouseLeave事件被控制通过有效的移动或预览一次移动来更新平板显示。
3. 移动动画
(本文来源于图老师网站,更多请访问http://m.tulaoshi.com/bianchengyuyan/)圆盘反转动画是通过使用一个定义在SquareControl类中的计数器并伴随一个System.Windows.Forms.Timer定时器实现的。基本上,这是一个被操作系统所控制的线程-它周期性地引发一个你的表单应用程序能够响应的事件。
在做一次移动后,如果移动动画选项处于活动状态,每个受影响的方格控制把它的计数器初始化并且激活定时器。在每次时钟滴答响时,主表单的AnimateMove()方法被调用(见下面)。这个方法更新方格计数器并且重画它们的显示。该动画基本上包含把圆盘形状从一个圆改变成一个更扁的椭圆,然后又变回到一个完整的圆,只是以相反的颜色罢了。这个动画的光滑度和速度依赖于初始的计数值的大小(由常数SquareControl.AnimationStart所设置)和时钟多长时间滴答响一次(由主表单中的常数animationTimerInterval所设置)。
(四) 玩游戏
下列变量用于控制一次游戏过程:
//游戏参数private GameState gameState;private int currentColor;private int moveNumber;
moveNumber应该是显然的。currentColor显示现在轮着哪一个玩家移动(黑色或白色)。gameState被设置为下列枚举值之一:
//定义游戏的状态private enum GameState{ GameOver, //游戏完了(也适合于起始的状态) InMoveAnimation, //产生一次移动并且该动画是活动的 InPlayerMove, //等待用户移动 InComputerMove, //等待计算机移动 MoveCompleted //一次移动完成 //(包括动画,如果是活动的)}
大多数游戏都是在事件驱动下玩的,因此gameState的使用允许各种事件处理器来决定要采取的适当行动。例如,当用户点击平板方格,SquareControl_Click()被调用。如果游戏状态是InPlayerMove,则在那个方格上作一次移动。但是如果游戏在其它状态,则说明还没轮到用户移动,所以这次点击将被忽略。
同样,如果用户点击工具条"Undo Move"按钮,我们想要检查该游戏状态来看一下是否需要做任何事情,在把游戏复位到前一次移动之前。例如,如果状态是InMoveAnimation,那么动画定时器需要停下来,而该方格控制需要它们的计时器并且显示重置。如果状态是InComputerMove,那么该程序现在在用一个独立的线程进行一次向前搜索(见下面)-它将需要停下来。
1. 程序流程
下图说明了在一个游戏过程中的通用程序流程:
StartTurn()在每次游戏的开始当任何一个玩家做一次移动后以及无论何时执行一次撤消/重做之后被调用。它负责评估游戏状况并且为下次移动作准备。
它首先检查是否当前玩家能够作一合法的移动。如果不能,它切换到其它玩家并且检查是否那个玩家有任何合法的移动。当两个玩家都不能移动时,根据规则,游戏结束并且它将结束该游戏。
否则,该函数将为当前玩家作出移动作好准备。如果当前玩家在用户控制下,它简单地退出。然后用户通过在一个有效的方形上点按鼠标指针或通过输入一个有效的列字母和行数字可以作一次移动。这将导致一次对MakePlayerMove()的调用-它完成一些清理工作,然后调用MakeMove()来实现移动。如果当前玩家在计算机控制下,它就启动向前搜索以找到最佳移动。
2. 使用一个工作者线程
因为向前搜索是深度优先计算的,所以它被用一个工作者线程来专门实现;否则,主表单屏幕将被冻结并且在计算最佳移动时响应滞后。因此,StartTurn()创建一个工作者线程来执行CalculateComputerMove()方法并且启动它。
锁机制被用在主游戏平板对象上以防止不满足游戏条件。作为一个例子,MakeComputerMove()和UndoMove()方法都因游戏平板而改变。这两个方法首先试图把一个锁放在它上面。因此,如果一个方法碰巧被调用,而另一个正在更新该平板时,它将被强迫等待,直到那些变化完成并且该锁被释放为止。
一旦发现一个移动,CalculateComputerMove()方法完成一次回调以在主表单屏幕上运行MakeComputerMove()。这个方法锁定平板并调用MakeMove()来实现移动。
3. 实现移动
MakeMove()完成实际的平板更新,把新的圆盘放置到指定的位置。它也实现一些维护如撤消/重做移动历史和高亮搬迁任何方形等。
然后,如果移动动画选项置为Off状态,它简单地调用EndMove()-它将切换当前颜色并以一个对StartTurn()的调用启动下一个回合。
但是如果动画选项置为On状态,它将代之来初始化圆盘-使其动起来并且启动动画定时器。如以前所讨论的,该定时器将会使AnimateMove()每几个毫秒运行一次,更新显示并且相应地每次减少动画计数器。最后,该计数器将到点,而AnimateMove()将调用EndMove()来完成移动。
(五) 未来的增强
在玩家AI方面还有很大的改进余地。向前搜索算法可以被扩充-用打开的移动或一系列被预先定级别的角和边模式。可以使用选择性深度,这样查找深度可以针对对游戏有较强影响的移动(例如在角落附近)而加以扩展。另外的改进将是存储向前搜索树。这将使它被搜索到一个更深的层次,因为该程序不会在每次重新生成相同的移动。