当前位置： >>
五子棋游戏设计与实现
南 京 工 程 学 院毕业设计说明书(论文)作 院 专 题 者： 系： 业： 目： 学 号：计算机工程学院 计算机科学与技术 五子棋游戏设计与实现指导者：讲师评阅者：2012 年 5 月南京毕业设计说明书（论文）中文摘要五子棋游戏设计与实现本课题使用的编程开发语言是 C++，这里设计和实现了一个同时具有单机 对战和网络对战功能的五子棋游戏。系统使用的是 VC++6.0 开发平台，分为一人 游戏类，两人游戏类，棋盘之间的关系参考了抽象工厂模式，并在软件中实现了 自己的消息机制，为网络对战提供不同的消息响应，软件中相当篇幅是算法的实 现，也是本课题的重点和难点，包含了五子棋程序的棋盘初始化、游戏规则、胜 负判断方法。课题最终实现了一款能够同时具有单机和网络对战功能，界面大方， 功能完善，操作简单的五子棋小游戏。关键字： 初始化，抽象工厂，消息机制，判断毕业设计说明书（论文）外文摘要Title Design Abstractand Implementation of Backgammon gamesThis topic using the programming development language is C + +, design and implementation of a stand-alone Versus and online play capabilities of Backgammon games. The system uses VC + + 6.0 development platform, is divided into a player class, two classes of games, the relationship between the board with reference to the abstract factory pattern, and the software to achieve its own message mechanism for online play response message, devotes considerable space to the software algorithm, the focus and difficulty of the subject, including the board initialization of the Backgammon procedures, the rules of the game, the outcome of judgment. The topics to achieve a final stand-alone and network multiplayer gaming features, elegant interface, fully functional, easy to operate the Backgammon game.Keywords： Initialization,theabstractfactory,messagemechanism,Judgment目录-第一章 绪论 .................................................. - 1 1.1 五子棋介绍 ............................................ - 1 1.2 开发背景 .............................................. - 1 1.3 开发环境 .............................................. - 1 第二章 软件架构 .............................................. - 2 2.1 棋盘类 ................................................ - 2 2.2 游戏模式类 ............................................ - 2 第三章 棋盘类――CTable ...................................... - 5 3.1 主要成员变量说明 ...................................... - 5 3.2 主要成员函数说明 ...................................... - 5 第四章 游戏模式类――CGame ................................... - 9 4.1 主要成员变量说明 ...................................... - 9 4.2 主要成员函数说明 ..................................... - 10 第五章 消息机制 ............................................. - 13 5.1 消息机制的架构 ....................................... - 13 5.2 各种消息说明 ......................................... - 13 第六章 主要算法 ............................................. - 19 6.1 判断胜负 ............................................. - 19 6.2 人机对弈算法 ......................................... - 21 补充说明 ..................................................... - 28 结 论 ........................................................ - 29 参考文献 ..................................................... - 30 致 谢 ........................................................ - 31 外文翻译 ..................................................... - 32南京工程学院毕业设计说明书（论文）第一章绪论1.1 五子棋介绍五子棋是起源于中国古代的传统黑白棋种之一。 现代五子棋日文称之为 “B珠” ， 英译为“Renju” ，英文称之为“Gobang”或“FIR” （Five in a Row 的缩写） ，亦有 “连五子”“五子连”“串珠”“五目”“五目碰”“五格”等多种称谓。 、 、 、 、 、 五子棋不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五子 棋既有现代休闲的明显特征“短、平、快” ，又有古典哲学的高深学问“阴阳易理” ； 它既有简单易学的特性，为人民群众所喜闻乐见，又有深奥的技巧和高水平的国际 性比赛；它的棋文化源渊流长，具有东方的神秘和西方的直观；既有“场”的概念， 亦有“点”的连接。它是中西文化的交流点，是古今哲理的结晶。1.2 开发背景当前网络上流传的五子棋游戏功能并不尽善尽美，其中最主要的问题就是人机 对战和网络对战不能够一起实现，所以我决定开发[1]一个既能够人机对战，又能够进 行网络对战的五子棋系统。1.3 开发环境1.3.1 开发环境 ? ? ? Intel? Pentium? 4 2.0GHz，1G 内存 Microsoft? Windows? 7 Microsoft? Visual C++ 6.0- 1 -南京工程学院毕业设计说明书（论文）第二章软件架构一人游戏类 二人游戏类软件的总体架构如图 2.1：游戏类指针棋盘类主界面用户 图 2.1 软件架构考虑到整个的下棋过程（无论对方是电脑抑或其他网络玩家）可以分为：己方 落子、等待对方落子、对方落子、设置己方棋盘数据这一系列过程，因此一人游戏 类、二人游戏类和棋盘类之间的关系参考了 AbstractFactory（抽象工厂）模式，以实 现对两个不同模块进行一般化的控制。[2]2.1 棋盘类整个架构的核心部分，类名为 CTable。封装了棋盘的各种可能用到的功能[3]， 如保存棋盘数据、初始化、判断胜负等。用户操作主界面，主界面与 CTable 进行 交互来完成对游戏的操作。2.2 游戏模式类用来管理人机对弈/网络对弈两种游戏模式，类名为 CGame。CGame 是一个抽 象类，经由它派生出一人游戏类 COneGame 和网络游戏类 CTwoGame，如图 2.2：抽象类 CGameCOneGame - 2 -CTwoGame南京工程学院毕业设计说明书（论文）图 2.2 CGame 类派生关系这样，CTable 类就可以通过一个 CGame 类的指针[4]，在游戏初始化的时候根 据具体游戏模式的要求实例化 COneGame 或 CTwoGame 类的对象； 然后利用多态性[5]，使用 CGame 类提供的公有接口就可以完成不同游戏模式下的不同功能了。- 3 -南京工程学院毕业设计说明书（论文）- 4 -南京工程学院毕业设计说明书（论文）第三章棋盘类――CTable3.1 主要成员变量说明3.1.1 网络连接标志――m_bConnected 用来表示当前网络连接的情况，在网络对弈游戏模式下客户端连接服务器的时 候用来判断是否连接成功；事实上，它也是区分当前游戏模式的唯一标志。 3.1.2 棋盘等待标志――m_bWait 与 m_bOldWait 由于在玩家落子后需要等待对方落子，m_bWait 标志就用来标识棋盘的等待状 态。当 m_bWait 为 TRUE 时，是不允许玩家落子的。 在网络对弈模式下，玩家之间需要互相发送诸如悔棋、和棋这一类的请求消息， 在发送请求后等待对方回应时，也是不允许落子的，所以需要将 m_bWait 标志置为 TRUE。在收到对方回应后，需要恢复原有的棋盘等待状态，所以需要另外一个变量 在发送请求之前保存棋盘的等待状态做恢复之用，也就是 m_bOldWait。 等待标志的设置，由成员函数 SetWait 和 RestoreWait 完成。 3.1.3 网络套接字――m_sock 和 m_conn 在网络对弈游戏模式下，需要用到这两个套接字对象。其中 m_sock 对象用于做 服务器时的监听之用，m_conn 用于网络连接的传输。 3.1.4 棋盘数据――m_data 这是一个 15*15 的二位数组，用来保存当前棋盘的落子数据。其中对于每个成 员来说，0 表示落黑子，1 表示落白子，-1 表示无子。 3.1.5 游戏模式指针――m_pGame 这个 CGame 类的对象指针是 CTable 类的核心内容。 它所指向的对象实体决定 了 CTable 在执行一件事情时候的不同行为，具体的内容请参见“游戏模式”一节。3.2 主要成员函数说明3.2.1 套接字的回调处理――Accept、Connect、Receive 本程序的套接字派生自 MFC 的 CAsyncSocket 类[6]，CTable 的这三个成员函 数就分别提供了对套接字[7]回调事件 OnAccept、 OnConnect、 OnReceive 的实际 处理，其中尤以 Receive 成员函数重要，它之中包含了对所有网络消息（参见“消- 5 -南京工程学院毕业设计说明书（论文）息机制”一节）的分发处理。 3.2.2 清空棋盘――Clear 在每一局游戏开始的时候都需要调用这个函数将棋盘清空，也就是棋盘的初始 化工作。在这个函数中，主要发生了这么几件事情： ? 将 m_data 中每一个落子位都置为无子状态（-1） 。 ? 按照传入的参数设置棋盘等待标志 m_bWait，以供先、后手的不同情况之 用。 ? 使用 delete 将 m_pGame 指针所指向的原有游戏模式对象从堆上删除。 3.2.3 绘制棋子――Draw 这无疑是很重要的一个函数，它根据参数给定的坐标和颜色绘制棋子。绘制的 详细过程如下： ? ? ? 将给定的棋盘坐标换算为绘图的像素坐标。 根据坐标绘制棋子位图。 如果先前曾下过棋子，则利用 R2_NOTXORPEN 将上一个绘制棋子上的最后 落子指示矩形擦除。 ? 在刚绘制完成的棋子四周绘制最后落子指示矩形。3.2.4 左键消息――OnLButtonUp 作为棋盘唯一响应的左键消息，也需要做不少的工作： ? 如果棋盘等待标志 m_bWait 为 TRUE，则直接发出警告声音并返回，即禁 止落子。 ? ? ? ? ? 如果点击时的鼠标坐标在合法坐标(0, 0)～(14, 14)之外，亦禁止落子。 如果走的步数大于 1 步，方才允许悔棋。 进行胜利判断，如胜利则修改 UI 状态并增加胜利数的统计。 如未胜利，则向对方发送已经落子的消息。 落子完毕，将 m_bWait 标志置为 TRUE，开始等待对方回应。3.2.5 绘制棋盘――OnPaint 每当 WM_PAINT 消息触发时，都需要对棋盘进行重绘。OnPaint 作为响应绘制 消息的消息处理函数使用了双缓冲技术，减少了多次绘图可能导致的图像闪烁问题。- 6 -南京工程学院毕业设计说明书（论文）这个函数主要完成了以下工作： ? ? ? 装载棋盘位图并进行绘制。 根据棋盘数据绘制棋子。 绘制最后落子指示矩形。3.2.6 对方落子完毕――Over 在对方落子之后，仍然需要做一些判断工作，这些工作与 OnLButtonUp 中的 类似，在此不再赘述。 3.2.7 设置游戏模式――SetGameMode 这个函数通过传入的游戏模式参数对 m_pGame 指针进行了初始化，代码如下： void CTable::SetGameMode( int nGameMode ) { if ( 1 == nGameMode ) m_pGame = new COneGame( this ); else m_pGame = new CTwoGame( this ); m_pGame-&Init(); } 这之后，就可以利用 OO 的继承和多态特点[8]来使 m_pGame 指针使用相同的调 用来完成不同的工作了，事实上，COneGame::Init 和 CTwoGame::Init 都是不 同的。 3.2.8 胜负的判断――Win 这是游戏中一个极其重要的算法，用来判断当前棋盘的形势是哪一方获胜。其 详细内容请参见“主要算法”一节。- 7 -南京工程学院毕业设计说明书（论文）- 8 -南京工程学院毕业设计说明书（论文）第四章游戏模式类――CGame这个类负责对游戏模式进行管理，以及在不同的游戏模式下对不同的用户行为 进行不同的响应。由于并不需要 CGame 本身进行响应，所以将其设计为了一个纯虚 类[9]，它的定义如下： class CGame { protected: CTable *m_pT public: // 落子步骤 list& STEP & m_StepL public: // 构造函数 CGame( CTable *pTable ) : m_pTable( pTable ) {} // 析构函数 virtual ~CGame(); // 初始化工作，不同的游戏方式初始化也不一样 virtual void Init() = 0; // 处理胜利后的情况，CTwoGame 需要改写此函数完成善后工作 virtual void Win( const STEP& stepSend ); // 发送己方落子 virtual void SendStep( const STEP& stepSend ) = 0; // 接收对方消息 virtual void ReceiveMsg( MSGSTRUCT *pMsg ) = 0; // 发送悔棋请求 virtual void Back() = 0; };4.1 主要成员变量说明4.1.1 棋盘指针――m_pTable- 9 -南京工程学院毕业设计说明书（论文）由于在游戏中需要对棋盘以及棋盘的父窗口――主对话框进行操作及 UI 状态设 置 ， 故 为 CGame 类 设 置 了 这 个 成 员 。 当 对 主 对 话 框 进 行 操 作 时 ， 可 以 使 用 m_pTable-&GetParent()得到它的窗口指针。 4.1.2 落子步骤――m_StepList 一个好的棋类程序必须要考虑到的功能就是它的悔棋功能，所以需要为游戏类 设置一个落子步骤的列表。由于人机对弈和网络对弈中都需要这个功能，故将这个 成员直接设置到基类 CGame 中。另外，考虑到使用的简便性，这个成员使用了 C++ 标准模板库[10]（Standard Template Library，STL）中的 std::list，而不是 MFC 的 CList。4.2 主要成员函数说明4.2.1 悔棋操作――Back 在不同的游戏模式下，悔棋的行为是不一样的。 ? 人机对弈模式下，计算机是完全允许玩家悔棋的，但是出于对程序负荷的考 虑（此原因请参见“几点补充说明”一节） ，只允许玩家悔当前的两步棋（计 算机一步，玩家一步） 。 ? 双人网络对弈模式下，悔棋的过程为：首先由玩家向对方发送悔棋请求（悔 棋消息） ，然后由对方决定是否允许玩家悔棋，在玩家得到对方的响应消息 （允许或者拒绝）之后，才进行悔棋与否的操作。 4.2.2 初始化操作――Init 对于不同的游戏模式而言，也就有不同的初始化方式。对于人机对弈模式而言， 初始化操作包括以下几个步骤： ? ? ? ? 设置网络连接状态 m_bConnected 为 FALSE。 设置主界面计算机玩家的姓名。 初始化所有的获胜组合。 如果是计算机先走，则占据天元（棋盘正中央）的位置。网络对弈的初始化工作暂为空，以供以后扩展之用。 4.2.3 接收来自对方的消息――ReceiveMsg 这个成员函数由 CTable 棋盘类的 Receive 成员函数调用， 用于接收来自对方- 10 -南京工程学院毕业设计说明书（论文）的消息。对于人机对弈游戏模式来说，所能接收到的就仅仅是本地模拟的落子消息 MSG_PUTSTEP；对于网络对弈游戏模式来说，这个成员函数则负责从套接字读取对 方发过来的数据，然后将这些数据解释为自定义的消息结构，并回到 CTable::Receive 来进行处理。 4.2.4 发送落子消息――SendStep 在玩家落子结束后，要向对方发送自己落子的消息。对于不同的游戏模式，发 送的目标也不同： ? 对于人机对弈游戏模式 ，将直接把落子的信息（坐标、颜色）发送给 COneGame 类相应的计算函数。 ? 对于网络对弈游戏模式，将把落子消息发送给套接字，并由套接字转发给对 方。 4.2.5 胜利后的处理――Win 这个成员函数主要针对 CTwoGame 网络对弈模式。在玩家赢得棋局后，这个函 数仍然会调用 SendStep 将玩家所下的制胜落子步骤发送给对方玩家，然后对方的 游戏端经由 CTable::Win 来判定自己失败。- 11 -南京工程学院毕业设计说明书（论文）- 12 -南京工程学院毕业设计说明书（论文）第五章消息机制Windows 系统拥有自己的消息机制，在不同事件发生的时候，系统也可以提供不 同的响应方式[11]。五子棋程序也模仿 Windows 系统实现了自己的消息机制，主要为 网络对弈服务，以响应多种多样的网络消息。5.1 消息机制的架构当继承自 CAsyncSocket 的套接字类 CFiveSocket 收到消息时，会触发 CFiveSocket::OnReceive 事件[12]，在这个事件中调用 CTable::Receive， CTable::Receive 开始按照自定义的消息格式接收套接字发送的数据，并对不同 的消息类型进行分发处理。网络数据CFiveSocket CFiveSocket::OnReceive 调用 CTable::ReceiveCFiveSocket::Receive图 5.1 分发处理 自定义的消息机制如图 5.1 所示， CTable 获得了来自网络的消息之后， 当 就可以使用一个 switch 结构来进行消息的分发了。5.2 各种消息说明网络间传递的消息，都遵循以下一个结构体的形式： // 摘自 Messages.h typedef struct _tagMsgStruct { // 消息 ID- 13 -南京工程学院毕业设计说明书（论文）UINT uM // 落子信息 // 消息内容 TCHAR szMsg[128]; } MSGSTRUCT; 随着 uMsg 表示消息 ID， y 表示落子的坐标， x、 color 表示落子的颜色， szMsg 随着 uMsg 的不同而有不同的含义。 5.2.1 落子消息――MSG_PUTSTEP 表明对方落下了一个棋子，其中 x、y 和 color 成员有效，szMsg 成员无效。 在人机对弈游戏模式下，亦会模拟发送此消息以达到程序模块一般化的效果。 5.2.2 悔棋消息――MSG_BACK 表明对方请求悔棋，除 uMsg 成员外其余成员皆无效。接到这个消息后，会弹 出 MessageBox 询问是否接受对方的请求（如图 5.2 所示） ，并根据玩家的选择回 返 MSG_AGREEBACK 或 MSG_REFUSEBACK 消息。另外，在发送这个消息之后，主 界面上的某些元素将不再响应用户的操作。图 5.2 请求悔棋5.2.3 同意悔棋消息――MSG_AGREEBACK 表明对方接受了玩家的悔棋请求，除 uMsg 成员外其余成员皆无效。接到这个 消息后，将进行正常的悔棋操作。 5.2.4 拒绝悔棋消息――MSG_REFUSEBACK 表明对方拒绝了玩家的悔棋请求（如图 5.3 所示） ，除 uMsg 成员外其余成员皆 无效。接到这个消息后，整个界面将恢复发送悔棋请求前的状态。- 14 -南京工程学院毕业设计说明书（论文）图 5.3 拒绝悔棋5.2.5 和棋消息――MSG_DRAW 表明对方请求和棋，除 uMsg 成员外其余成员皆无效。接到这个消息后，会弹 出 MessageBox 询问是否接受对方的请求（如图 5.4 所示） ，并根据玩家的选择回 返 MSG_AGREEDRAW 或 MSG_REFUSEDRAW 消息。另外，在发送这个消息之后，主 界面上的某些元素将不再响应用户的操作。图 5.4 请求和棋5.2.6 同意和棋消息――MSG_AGREEDRAW 表明对方接受了玩家的和棋请求（如图 5.5 所示） ，除 uMsg 成员外其余成员皆 无效。接到这个消息后，双方和棋。图 5.5 同意和棋5.2.7 拒绝和棋消息――MSG_REFUSEDRAW 表明对方拒绝了玩家的和棋请求（如图 5.6 所示） ，除 uMsg 成员外其余成员皆 无效。接到这个消息后，整个界面将恢复发送和棋请求前的状态。- 15 -南京工程学院毕业设计说明书（论文）图 5.6 拒绝和棋5.2.8 认输消息――MSG_GIVEUP 表明对方已经投子认输（如图 5.7 所示） ，除 uMsg 成员外其余成员皆无效。接 到这个消息后，整个界面将转换为胜利后的状态。图 5.7 认输5.2.9 聊天消息――MSG_CHAT 表明对方发送了一条聊天信息，szMsg 表示对方的信息，其余成员无效。接到 这个信息后，会将对方聊天的内容显示在主对话框的聊天记录窗口内。 5.2.10 对方信息消息――MSG_INFORMATION 用来获取对方玩家的姓名，szMsg 表示对方的姓名，其余成员无效。在开始游 戏的时候，由客户端向服务端发送这条消息，服务端接到后设置对方的姓名，并将 自己的姓名同样用这条消息回发给客户端。 5.2.11 再次开局消息――MSG_PLAYAGAIN 表明对方希望开始一局新的棋局，除 uMsg 成员外其余成员皆无效。接到这个 消息后，会弹出 MessageBox 询问是否接受对方的请求（如图 5.8 所示） ，并根据 玩家的选择回返 MSG_AGREEAGAIN 消息或直接断开网络。- 16 -南京工程学院毕业设计说明书（论文）图 5.8 再次开局5.2.12 同意再次开局消息――MSG_AGREEAGAIN 表明对方同意了再次开局的请求，除 uMsg 成员外其余成员皆无效。接到这个 消息后，将开启一局新游戏。- 17 -南京工程学院毕业设计说明书（论文）- 18 -南京工程学院毕业设计说明书（论文）第六章主要算法五子棋游戏中，有相当的篇幅是算法的部分。无论是人机对弈，还是网络对弈， 都需要合理算法的支持，本节中将详细介绍五子棋中使用的算法。[13]6.1 判断胜负五子棋的胜负，在于判断棋盘上是否有一个点，从这个点开始的右、下、右下、 左下四个方向是否有连续的五个同色棋子出现，如图 6.1：图 6.1 判断胜负方向这个算法也就是 CTable 的 Win 成员函数。从设计的思想上，需要它接受一个 棋子颜色的参数，然后返回一个布尔值，这个值来指示是否胜利，代码如下： BOOL CTable::Win( int color ) const { int x, // 判断横向 for ( y = 0; y & 15; y++ ) { for ( x = 0; x & 11; x++ ) { if ( color == m_data[x][y] && color == m_data[x + 1][y] && color == m_data[x + 2][y] && color == m_data[x + 3][y] && color == m_data[x + 4][y] ) { return TRUE; } }- 19 -南京工程学院毕业设计说明书（论文）} // 判断纵向 for ( y = 0; y & 11; y++ ) { for ( x = 0; x & 15; x++ ) { if ( color == m_data[x][y] && color == m_data[x][y + 1] && color == m_data[x][y + 2] && color == m_data[x][y + 3] && color == m_data[x][y + 4] ) { return TRUE; } } } // 判断“\”方向 for ( y = 0; y & 11; y++ ) { for ( x = 0; x & 11; x++ ) { if ( color == m_data[x][y] && color == m_data[x + 1][y + 1] && color == m_data[x + 2][y + 2] && color == m_data[x + 3][y + 3] && color == m_data[x + 4][y + 4] ) { return TRUE; } } } // 判断“/”方向- 20 -南京工程学院毕业设计说明书（论文）for ( y = 0; y & 11; y++ ) { for ( x = 4; x & 15; x++ ) { if ( color == m_data[x][y] && color == m_data[x - 1][y + 1] && color == m_data[x - 2][y + 2] && color == m_data[x - 3][y + 3] && color == m_data[x - 4][y + 4] ) { return TRUE; } } } // 不满足胜利条件 return FALSE; } 需要说明的一点是，由于这个算法所遵循的搜索顺序是从左到右、自上而下， 因此在每次循环的时候，都有一些坐标无需纳入考虑范围。例如对于横向判断而言， 由于右边界所限，因而所有横坐标大于等于 11 的点，都构不成达到五子连的条件， 所以横坐标的循环上界也就定为 11，这样也就提高了搜索的速度。6.2 人机对弈算法人机对弈算法完全按照 CGame 基类定义的接口标准， 封装在了 COneGame 派生 类之中。下面将对这个算法进行详细地介绍。[14] 6.2.1 获胜组合 获胜组合是一个三维数组，它记录了所有取胜的情况。也就是说，参考于 CTable::Win 中的情况，对于每一个落子坐标，获胜的组合一共有 15 * 11 * 2 + 11 * 11 * 2 = 572 种。 而对于每个坐标的获胜组合，应该设置一个[15][15][572]大小的三维数组。 在拥有了这些获胜组合之后，就可以参照每个坐标的 572 种组合给自己的局面- 21 -南京工程学院毕业设计说明书（论文）和玩家的局面进行打分，也就是根据当前盘面中某一方所拥有的获胜组合多少进行 权值的估算，给出最有利于自己的一步落子坐标。 由于是双方对弈，所以游戏的双方都需要一份获胜组合，也就是： bool m_Computer[15][15][572]; // 电脑获胜组合 bool m_Player[15][15][572]; // 玩家获胜组合 在每次游戏初始化（COneGame::Init）的时候，需要将每个坐标下可能的获 胜组合都置为 true。 此外，还需要设置计算机和玩家在各个获胜组合中所填入的棋子数： int m_Win[2][572]; 在初始化的时候，将每个棋子数置为 0。 6.2.2 落子后处理 每当一方落子后，都需要作如下处理： ? 如果己方此坐标的获胜组合仍为 true，且仍有可能在此获胜组合处添加棋 子，则将此获胜组合添加棋子数加 1； ? 如果对方此坐标的获胜组合仍为 true，则将对方此坐标的获胜组合置为 false，并将对方此获胜组合添加棋子数置为-1（不可能靠此组合获胜） 。 以玩家落子为例，代码为： for ( i = 0; i & 572; i++ ) { // 修改状态变化 if ( m_Player[stepPut.x][stepPut.y][i] && m_Win[0][i] != -1 ) m_Win[0][i]++; if ( m_Computer[stepPut.x][stepPut.y][i] ) { m_Computer[stepPut.x][stepPut.y][i] = m_Win[1][i] = -1; } } 6.2.3 查找棋盘空位- 22 -南京工程学院毕业设计说明书（论文）在计算机落子之前，需要查找棋盘的空位，所以需要一个 SearchBlank 成员函 数完成此项工作，此函数需要进行不重复的查找，也就是说，对已查找过的空位进 行标记，并返回找到空位的坐标，其代码如下： bool COneGame::SearchBlank( int &i, int &j, int nowTable[][15] ) { int x, for ( x = 0; x & 15; x++ ) { for ( y = 0; y & 15; y++ ) { if ( nowTable[x][y] == -1 && nowTable[x][y] != 2 ) { i = j = } } } } 6.2.4 落子打分 找到空位后，需要对这个点的落子进行打分，这个分数也就是这个坐标重要性 的体现，代码如下： int COneGame::GiveScore( const STEP& stepPut ) { int i, nScore = 0; for ( i = 0; i & 572; i++ ) { if ( m_pTable-&GetColor() == stepPut.color ) {- 23 -南京工程学院毕业设计说明书（论文）// 玩家下 if ( m_Player[stepPut.x][stepPut.y][i] ) { switch ( m_Win[0][i] ) { case 1: nScore -= 5; case 2: nScore -= 50; case 3: nScore -= 500; case 4: nScore -= 5000; default: } } } else { // 计算机下 if ( m_Computer[stepPut.x][stepPut.y][i] ) { switch ( m_Win[1][i] ) { case 1: nScore += 5;- 24 -南京工程学院毕业设计说明书（论文）case 2: nScore += 50; case 3: nScore += 100; case 4: nScore += 10000; default: } } } } return nS } 如代码所示，考虑到攻守两方面的需要，所以将玩家落子给的分数置为负值。 6.2.5 防守策略 落子的考虑不单单要从进攻考虑，还要从防守考虑。这一细节的实现其实就是 让计算机从玩家棋盘布局分析战况，然后找出对玩家最有利的落子位置。整个过程 如下： for ( m = 0; m & 572; m++ ) { // 暂时更改玩家信息 if ( m_Player[i][j][m] ) { temp1[n] = m_Player[i][j][m] = temp2[n] = m_Win[0][m]; m_Win[0][m] = -1; n++;- 25 -南京工程学院毕业设计说明书（论文）} } ptempTable[i][j] = 0; pi = pj = while ( SearchBlank( i, j, ptempTable ) ) { ptempTable[i][j] = 2; // 标记已被查找 step.color = m_pTable-&GetColor(); step.x = step.y = ptemp = GiveScore( step ); if ( pscore & ptemp ) // 此时为玩家下子，运用极小极大法时应 选取最小值 pscore = } for ( m = 0; m & m++ ) { // 恢复玩家信息 m_Player[pi][pj][temp1[m]] = m_Win[0][temp1[m]] = temp2[m]; } 6.2.6 选取最佳落子 在循环结束的时候，就可以根据攻、守两方面的打分综合地考虑落子位置了。 代码如下： if ( ctemp + pscore & cscore ) { cscore = ctemp + bestx = besty =- 26 -南京工程学院毕业设计说明书（论文）} 在这之后，重新改变一下棋盘的状态（6.2.2）即可。- 27 -南京工程学院毕业设计说明书（论文）补充说明? ? 考虑到程序的响应速度，人机对弈算法只对玩家的棋子进行了一步的推测。 由于计算机在落子时选取的是得分最高的一步落子，所以如果玩家在开局的 时候不改变落子步骤，那么将会获得从头至尾相同的棋局。 ? 考虑到下棋同时还要聊天，所以并未对落子时间加入任何限制，同样如果玩 家离开游戏也不会判负。 ? 对于人机对弈的悔棋处理，由于这个算法的开销相当大，每一步落子都会存 在不同的棋盘布局，所以实现从头到尾的悔棋不是很现实（将会存在过多的 空间保存棋盘布局） ，因而在人机对弈模式下，只允许玩家悔最近的两步落 子。- 28 -南京工程学院毕业设计说明书（论文）结 论通过本次毕业设计，我体会最为深刻的一点是系统架构和设计模式的重要性。 即使是对于一个并不大的程序，代码的组织都是非常重要的，因为这关系到日后的 维护以及扩展。这个游戏之中，有关网络 Socket 编程或者博弈树算法的知识都可以 直接从无所不包的 Internet 上获取，但是对于软件架构，却完全是自己的事情，几 千上万行的代码需要通过合适的方法组织起来，使程序员编写代码更加有条理，更 加符合软件工程的标准。 在刚开始编写这个程序的时候，我曾认为其中最重要的是算法部分。但是头一 个月编写程序的时候却发现程序越写越不容易维护，后来发现我们的先人早已为我 们准备好了各种精良可用的现成算法，我们所要做的就是直接“拿来主义”罢了； 软件的架构才是真正软件的核心部分，因为软件事实上是直接和效率挂钩的，因此 我们必须在编写代码之前选择一种最为合适的方法来组织这些代码，否则我们将会 失去更多的时间和效率。[15] 于是，我将以前写的代码全部删除，认真地思考了三天的时间。我也在这三天 内真正从一个学生程序员走入了软件开发的大门，我开始发现其实软件开发并不是 纯数学――正相反，数学只占了很小的一部分。它其实是一种哲学，一种有着数学 美感的哲学。- 29 -南京工程学院毕业设计说明书（论文）参考文献[01] C++面向对象程序设计， 谭浩强， 清华大学出版社. [02] C++程序设计题解与上机指导， 谭浩强， 清华大学出版社. [03] Windows 程序设计， Charles Petzold， 北京大学出版社. [04] MSDN for Visual Studio 6.0. [05] Visual C++ 6.0 网络通信协议分析与应用实现， 汪小平/钟 军， 人民邮电出版社. [06] Visual C++.net 网络编程，易军， 中国铁道出版社. [07] 深入浅出 MFC， 侯俊杰， 华中科技大学出版社. [08] C++编程思想， Bruce Eckel， 机械工业出版社. [09] Visual C++实例精通， 张军， 机械工业出版社. [10] Visual C++教程， 郑阿奇， 清华大学出版社.- 30 -南京工程学院毕业设计说明书（论文）致 谢感谢我的父母，没有您们的包容和支持，就不会有我的今天。 感谢我的指导老师 感谢 感谢 老师。同学，谢谢你在工作之余和我一起进行的测试。 的所有兄弟，谢谢你们在我离校期间为我所作的一切。- 31 -南京工程学院毕业设计说明书（论文）外文翻译Backgammon gamesRenju is a very old two-player board game with subtle tactics and strategies. It comes from Japan and is a professional variant of Go-Moku. In many countries, such as China, Estonia, Japan, Latvia, Russia, and Sweden, Renju is played on a high level of performance. Compared to Renju, the game of Go-Moku, mainly played in China and Japan, has rather simple rules. Go-Moku was solved by Allis in 1992. He proved that it is a won game for the player to move first. In this note we claim that Renju is a first-player win too. We describe our research approach and how we arrived at this game-theoretical value. 1. INTRODUCTIONIn 1992 Allis solved the game of Go-Moku by means of the computer program VICTORIA (Allis, Van den Herik, and Huntjes, 1993; Allis, 1994). The main techniques applied were proof-number search (Allis, Van der Meulen, and Van den Herik, 1994) and threat-space search (Allis, Van den Herik, and Huntjes, 1995). Since the advantage for the first player was well-known (Sakata and Ikawa, 1981), many variants of Go-Moku were developed so as to reduce the advantage of the first player, attempting to create a balanced game. Already around 1900 Japanese professional players improved the simple rules of Go-Moku by introducing that the first player (Black) is prohibited from making a double three, a double four, and an overline.After that the Renju board was diminished from 1919 (Go board size) to 1515 when it was discovered that the larger board size increases Black!s advantage. These improvements were to restrict Black!s moves so as to offset his initial advantage. In 1936 ¤ when the Japanese Federation of Renju was founded ¤ the rules of Renju were fully accomplished. Professional players believed that the new rules would result in a more evenly-balanced game. When the Renju players became stronger they found that the above-mentioned advanced new rules still gave great advantage to Black. Some Japanese players even showed a black victory in two frequently-played opening patterns (cf. Sakata and Ikawa, 1981), but their solution was incomplete because some good white moves were not analysed and later on even mistakes were found in it. In the Sakata!s book ¤ Figures 31 and 32 facing page 77 ¤ japanese authors suggested an strong 15 th move (A, see Figure 1). After- 32 -南京工程学院毕业设计说明书（论文）move A, if the White’s reply was move B (16 th move), the Black victory will be become very complicated, but not fully analysed by pro players. White’ s defence move C (16 th move) is not mentioned in this book, after this White’ s response we were not able to find the Black victory in some weeks. So move A was rejected (and considered to be not good move) and we chose another 15 move (D), which turn out a success. Another problem was, that there are 35 distinct second white moves possible, but only two main variations (adjacent to Black!s first move) were exhaustively analysed in that book. In Japan professional Renju players continued to study Renju in detail. Sakata and Ikawa (1981) published their analysis in 32 pages. We have exploited the analysis for our work and found other mistakes and lacunae (see also Allis, 1994). Nevertheless, the Japanese prediction is now confirmed, extended and corrected by our computer program which established Renju!s game-theoretical value. Our project was to carry out a complete proof about the game of Renju by a computer program and to create a database of the solved game tree. In 1988, the Renju International Federation was created. At the same time, to equalise the chances of the players at the official tournaments new opening-rules regulations were adopted. The official Renju rules and the new opening regulations are described in Section 2. However, this article focuses on establishing the game-theoretical value of Renju without the new opening-rules regulations. The game we deal with is called freeRenju, it is a quite aggressive game in which almost every black move is a threat. The remainder of this note is structured as follows. After the description of the rules in Section 2, Section 3 provides a list of terms and gives their definitions. In Section 4 we explain our experimental approach and provide empirical evidence for our claim. In Section 5 some technical details on a checking program are given and in Section 6 results are presented. Section 7 contains our conclusions.- 33 -南京工程学院毕业设计说明书（论文）Figure 1 2. THE RULES OF RENJUThe game of Renju is a professional variant of Go-Moku. The rules of Renju, although more complex than those of Go-Moku, are still rather simple (Sakata and Ikawa, 1981). The game is played on a board with 1515 points of intersections. Vertical lines are lettered from ’a’ to ’o’, and the horizontal lines are numbered from 1 to 15. The left bottom position on the board is a1. Two players, Black and White, place alternately a stone of their own colour on an empty intersection. Black starts the game and must place a black stone on the centre intersection (h8). The first player completing an unbroken line of five stones (vertically, horizontally, or diagonally) wins the game. In Renju Black has some restrictions with respect to Go-Moku, e.g, some moves are considered to be prohibited for Black. If Black makes a prohibited move either accidentally or by being forced to, White wins the game. The prohibited moves for Black are: overline, double-four, double-three (for definitions, see Section 3). White does not have prohibited moves, so White may make an overline and wins the game. If none of the players succeeds in completing a five-in-a-row, and Black did not make a prohibited move and the board is full of stones, the game is considered to be drawn. The above-mentioned rules are known as the free Renju rules. In an attempt to make the game more evenly-balanced for a fair competition in official tournaments, the following eight opening-rules restrictions have been imposed on Black (i.e., the professional Renju Rules). a. Players start the game as tentative Black and tentative White. Tentative- 34 -南京工程学院毕业设计说明书（论文）Black plays the first move on the centre intersection. b. Tentative White makes the second move diagonally, horizontally or vertically to the first move and adjacent to the first move (i.e., two different openings). c. Tentative Black plays the third move on an empty place within a zone of 55 intersections in the centre of the board (26 opening patterns). d. Tentative White has the right to change the colour of the stones (swap option). e. The player, who now has the white stones, plays the fourth move wherever (s)he wants. f. Black has to offer the opponent two possible asymmetrical fifth moves. g. White chooses one of the fifth moves which will be more advantageous to him/herself and tells Black to make the moves (s)he prefers. h. There are no restrictions on the sixth and later moves. 3.TERMS AND DEFINITIONS Below we provide a list of the terms together with their definitions. Overline: Six or more stones of the same colour in an unbroken row, either horizontally, vertically or diagonally. Five: Exact five stones of the same colour arranged in an unbroken row, either horizontally, vertically or diagonally. Straight four: Four stones of the same colour in an unbroken row (horizontally, vertically or diagonally) with both ends open. A straight four ensures a win. Four: Four stones of one colour in a row, which in one move can become a five. Three: Three stones of the same colour in an unbroken row, or with one-intersection gap between the stones that can become a straight four on the next move. Double-Four: A single move, which builds simultaneously more than one four at one time. Double-Three: A single move, which builds simultaneously more than one three at one time. Four-three: A four and a three produced simultaneously with a single move. It is the usual way for Black to create a winning formation. VCF: This acronym means: Victory by Consecutive Fours. A win that results from making fours one after another. VCT: This acronym means: Victory by Consecutive Threats. A win that results from making threats (four or three) one after another. Japanese terms:- 35 -南京工程学院毕业设计说明书（论文）Fukumi: A move which threatens to win by VCF. Who played the fukumi move has a VCF if the opponent does not defend against this move. Yobi: A positional offensive move, which threatens to win by VCT. A yobi move is not a direct forced method of attackPlaying A leads to an overline. Playing B leads to a double-four. Playing C leads to a double-three. Playing D leads to a straight four. Playing E leads to a four-three.4. THE PROGRAM AND EXPERIMENTAL APPROACHTHEThe solving program was written in Borland Pascal language. The program goal was to establish the game-theoretical value. The program generated a winning tree for Black and stored the tree in a database. The search process used transposition tables to avoid searching symmetrical positions. Moreover, the solving program used the threat-sequence search as suggested by Allis et al. (1993). There was only a very limited possibility to play no-threat moves, the first black moves after a bad opining by White (such as moves far away from the board centre). If a white defending move in such a variation also was a threat then Black countered it and did not lose a tempo in the end. The program operated an iterative-deepening search based on threat sequences up to 17 plies. The speed of the threat-sequence search was 400 nodes/second on a Pentium 200 MHz machine. The deepest variations of the iterative-deepening search (17 plies) took about 15 minutes, then a VCF line was found. It was not possible to speed up the threat-sequence search (cf. Allis, 1994) since by the overline, double-four and double-three rule the order of moves became more complex. In the solving program we had implemented an automatic- 36 -南京工程学院毕业设计说明书（论文）database builder, but all openings, fukumi, yobi, and positional moves were inputted by the hand of a human expert. In the past, the human expert assistance has been used in game solving (O. Patashnik, 1980). In total, human players produced approximately 5000 positional moves. The threat-sequence search module built all black threat sequences up to a given depth and investigated whether the position is a win for Black against every possible defence by White. After a positional black move, another module examined how Black can win if White passes. If a winning line exists then this module stores the moves of these sequences and in the next step the solving program will use these moves as white answers. All moves of the game tree were stored in the database with the exception of the last 10 plies, since 10 or fewer plies of winning sequences can be found quickly by the threat-sequence search engine. Generating the whole game tree took about 3000 hours on a Pentium 200 MHz PC. 5. THE CHECKING PROCEDUREAfter the generation of the whole game tree, the second stage of the project was checking the database. To making sure of generated database, there is necessary to develop a checking program, which plays backwards all possible white moves and then communicates with the solving program on the forward white moves (meanwhile inspecting the database). When a not-analysed white move was encountered, the solving program first took the black answer most frequently-played in that stage of the game tree. This approach gave many typical first omissions. In the checking loop, we stored white wins, black prohibited answers, and non-proved positions. The checking file contained approximately 2000 previously missing positions, which were corrected in the next proof run. The proof runs and the correction of positions were repeated several times even when the checking log did no longer contain any lacking positions. The programming of the checking program was performed by the second author in Borland Pascal programming language. This part of the solving took about 6000 hours on a Pentium 200 MHz machine. 6. CONCLUSIONSWe verified and expanded the statement of Japanese Renju experts that the game of free Renju is a theoretical win for the first player to move. The game was solved after 9000 hours of using a Pentium 200 MHz. The size of the overall database is 7 Megabyte. After the final database creation, the database was checked once more and accepted as correct by a checking program written by an independent programmer. In the last checking run, no missing variations were found by the checking program. In conclusion,- 37 -南京工程学院毕业设计说明书（论文）free Renju should be considered a solved game. The result is that the game is a first-player win. Finally, we have good reason to believe that after building a good opening book, say of 5000 moves, there’s no middle game ,provide that an appropriate endgame-analysing routine is available.五子棋游戏五子棋是一种微妙的，存在与两个玩家之间的带有战略性的棋盘游戏。它源于日本， 是围棋的一种变体。在许多国家中，如中国、爱沙尼亚、日本、拉脱维亚、俄国和 瑞典，五子棋都被看做成是一种高智能的游戏。 相对于广泛存在于中国和日本的围起来说， 五子棋有着非常简单的游戏规则。 1992 在 年 Allis 揭示了五子棋的问题，他证明这项游戏的胜利取决于先下棋的玩家。在这 篇文章中我们也赞同它的说法，认为五子棋是一个偏向于先手获胜的游戏，我们阐 述了我们研究方法和怎样实现游戏的理论价值。 1. 引言 在 1992 年 Allis 通过计算机工程 VICTORIA（Allis, Van den Herik, 和 Huntjes, 1993; Allis, 1994）的意义揭示了五子棋游戏的问题。主要的技术应用是数据取样 研究 （Allis, Van der Meulen, 和 Van den Herik, 1994） 和危险范围的研究 （Allis, Van den Herik, 和 Huntjes, 1995） 。自从先手的优势被众所周知后(Sakata 和 Ikawa, 1981)，为了减少先手的优势，许多五子棋的变体得到了发展，并尝试着建 立一个平衡的游戏。早在 1900 年左右，日本的专业选手就改善了五子棋的的简单规 则，通过引介禁止先手（黑棋）制造双三、双四和 overline 的方法。当发现大的棋 盘可以增加黑子的优势时，就减少了五子棋的棋盘的大小，从原来的 19×19 减到 15 ×15。这些限制黑子进展的改善是为了抵消它最初的优势。在 1936 年，当建立了日 本五子棋联合会后，五子棋的规则就已完全的娴熟，专业选手相信新的规则将会产 生一个更加公平的比赛。- 38 -南京工程学院毕业设计说明书（论文）当五子棋的玩家变的更强一些时，他们发现上面提到的改善后的新规则仍然给了黑 子很大的优势，一些日本选手甚至展示了在两个常见比赛中开端形式的黑子的胜利 (cf. Sakata 和 Ikawa, 1981)，但是他们的解答时不完全的，因为没有分析一些优 秀的白子的移动，并且以后甚至在其中发现错误，在 Sakata 的书中，见 77 页指出 的 31 和 32 点，日本的发起人建议一个更强有力的第 15 步的落子（见图 Figure 1 中的 A 处） 。在 A 处落子之后，如果白子的玩家的反应是在 B 处落子（第 16 步） ，那 么黑子的胜利将会变得非常的复杂，但是，赞同的玩家并没有完全地进行分析。白 子落在 C 处防御（第 16 步）在这本书中并没有提到，从白子的回应后，我们在很长 一段时间内不能发现黑子的胜利。所以排除在 A 处落子（并且不认为是一步好棋） ， 同时我们选择把棋子落在 D 处作为第 15 步，事实证明这是成功的一步。另一个问题 是将会有 35 中不同的白棋第二次可能落子的地方，但是仅仅两次主要的变动在那本 书中被彻底的分析到。在日本的专业的五子棋选手继续详细地研究五子棋。Sakata 和 Ikawa（1981）在书中的第 32 页发表了他们的分析，我们已经针对我们的工作开 展了这项分析，并且发现了一些错误和不足（也见 Allis，1994） 。尽管如此，日本 人的预言现在通过我们已确定的五子棋游戏理论价值的计算机程序看是被认可的、 延伸的和正确的。我们的工程在关于五子棋游戏方面将通过计算机程序计实现一个 完全的证明，和建立一个解决游戏图普的数据库。 在 1998 年，建立了国际五子棋联盟。与此同时，为了使选手机会的公平化，在官方 锦标赛中同过了新的开局规则规章。官方的五子棋规则和新的开局规章在第二部分 进行阐述。然而，这篇文章主要集中在没有新的开局规则的情况下证实五子棋游戏 的理论价值。我们称所要解决的游戏为五子棋，它是一个带有几分挑衅的游戏，其 中几乎黑子的每一步落子都是一个威胁。这篇文章的其余部分的结构如下。在第二、 三部分描述规则之后列出了一部分术语，并给出了他们的定义。在第四部分我们解 释了我们的试验方法，和针对我们的阐述提供了以观察和实验为依据的证据。在第 五部分给出了在检验程序时的一些技术细节，在第六章显示了结果，第七章包含了 我么的结论和意见。 2.五子棋的规则 五子棋游戏是专业 Go-Moku 的变体。五子棋的规则尽管比起那些 Go-Moku 要复杂一 些，但它仍旧很简单（Sakata 和 Ikawa, 1981） 这个游戏是在一个 15×15 的棋 ， 盘的交叉点上进行的。垂直线用字母 A 到 O 标注，水平线用数字 1 到 15 标注。棋盘 左下方的位置是 A1。黑棋白棋两位玩家轮流执他们自己颜色的棋子放在棋盘中空的 交叉点上。执黑子玩家先开始下棋，并且必须把棋子放在棋盘的正中间（H8） 。最先 完成无五子连线（垂直、水平或斜线方向）的玩家获胜。五子棋中黑子有一些限制， 例如，对于黑子来说有些落子是被认为禁止的，如果黑子落子被禁止不是偶然的就 是被迫的，那么白子就获胜了，禁止黑棋落子的情况有：overline, double-four, double-three（具体定义见第三部分） 。白子没有禁止落在的情况，所以白子也可以 制造一个 overline 来赢得游戏，如果没有选手成功的完成五子连线，并且黑子没有 被禁止落子和棋盘已满，则认为这盘游戏平局。- 39 -南京工程学院毕业设计说明书（论文）上面提到的规则被认为是五子棋的规则。在官方锦标赛中为了公平竞争尝试着使游 戏更加公正，下面 8 个开局规则规章已经强加给黑子（专业五子棋规则） 。 A． 选手开始游戏作为黑子或白子，黑子先下棋并且放在棋盘中间。 B． 第二步白子放在临近第一步棋子处对角线上、水平线或是垂直线上。 C． 第三步黑子放在以棋盘为中心向外的 55 个交叉点范围内的空子处。 D． 白子有权利改变棋子的颜色。 E． 现在拥有白子的选手下第四步，棋子可以放在他想放的棋盘上的任何处。 F． 黑子提供给对手两种不对称的可能下第五步棋。 G． 白子选择黑子提供下第五步棋方法中他认为对自己更有利的一种， 然后告诉黑子 下他喜欢的地方。 H． 从第六步起和之后都没有限制了。 3．术语与定义 下面我们提供一系列术语以及他们的定义。 Overline：六个或六个以上的同色棋子连成一线，垂直方向、水平方向或斜线方向。 Five: 精确的只有五个同色的棋子连成一线，垂直方向、水平方向或斜线方向。 Straight four: 四个同色棋子连成一线（垂直、水平或斜线方向）并且两边的位置 是空的，是一定会赢的一种情况。 Four: 四个一种颜色的棋子连成一排，再添加一个棋子就能连成五个。 Three: 三个相同颜色的棋子连成一线，或是在三个棋子间有一个空位，只要再下一 个相同的棋子在空位上就能形成 Straight four。 Double-Four: 只下一步棋，就能形成一个同时存在的不止是一排形成四子连线。 Double-Three: 只下一步棋，就形成了同时存在的不止一个三子连线。 Four-three: 只下一步棋就形成了一个四子连线和一个三子连线同时存在的情况， 对于黑子的胜利这是一种常用的办法去建立一个胜利的布局。 VCF: 这个缩写字母的意思是：通过一步步的逼近才取得的胜利。游戏胜利的取得来 自于制造一步又一步的逼近（four 或 three） 。 日本的术语： Fukumi: 想通一步棋过形成 VCF 来胁迫对手取得胜利，下棋形成 fukumi 的玩家如果 没有遭到对手的的防御就会形成 VCF。 Yobi: 一种方位上的攻击，通过 VCF 将会预示成功，yobi 形式的落子并不是一种袭 击的直接的逼迫方式。 棋子放在 A 处形成 overline 棋子放在 B 处形成 double-four 棋子放在 C 处形成 double-three 棋子放在 D 处形成 straight four 棋子放在 E 处形成 four-three 4 程序和试验方法 解决问题的程序是用 borland 公司开发的 pascal 语言。这个成学的目的是要证实游 戏的理论价值。这个程序生成了一个黑子获胜的图谱，并且把它存放在一个数据库- 40 -南京工程学院毕业设计说明书（论文）中。在搜索过程中使用转表，以避免寻找对称位置。此外，Allis 等人建议该解决方 案使用威胁序列搜索。没有威胁落子步骤的可能性是微乎其微的，第一个黑棋落子 会给白棋一个不好的印象（如把棋子放在离期盼中心很远的地方） 。如果白棋采用这 样的防御变动的话也是一种威胁，然而黑棋反驳它并且到最后都不能有一丝的差错。 基于威胁序列达到 17 层的基础上，程序采用了一种反复加深的研究方法。这种威胁 序列搜索的速度在奔腾 200 兆赫的机器上为每秒 400 点。 这种反复迭代加深搜索要花费 15 分钟才能达到最深层的变化，随之而出的便是一个 VCF 的棋局。 自从有了 overline，double-four 和 double-three 的规则加上落子的顺学便的更加 的复杂之后要使威胁序列的搜索加速已经成为不可能。在解决方案中我们采用一种 自动建立数据库的工具，但是所有的开局，fukumi，yobi 和落子的位子都是有专家 亲自输入到电脑中的。以前，专家的援助曾经用在游戏的解决方案中，总之，选手 们有大约 5000 种落子的位置。这种威胁序列搜索的建立使得所有黑子的威胁序列上 升到一个指定的深度，并且能够分析对于白子防御的所有的可能性来说，黑子所在 的位置是否都能取得胜利。在黑棋落子之后，另一种模型是检查在白棋失误下黑棋 怎样才能赢。如果存在一条即将获胜的连线时，这个模型就会存储起这些序列的位 置，并且在下一步种解决方案将会用这些位置作为白子的回应。除了最后十层之外 游戏图谱中所有的移动位置都存在了数据库中，因为 10 层或更少层的获胜序列能够 被威胁序列搜索引擎很快地发现。对于一台奔腾 200 兆赫的计算机来说，产生整个 的游戏图谱要花费大概 3000 小时。 5 检查步骤 在产生整个的游戏图谱之后，工程的第二阶段就是检查数据库。为了确保数据库的 正确性，有必要开发一个检验方案，它能演示白子所有向后退的可能和结合白子像 前进的解决方（同时检查数据库） 。当突然遇到一个未被分析过的白棋的移动，解决 方案会最先拿出在游戏图谱阶段中黑子最经常被演示的方法。这种方法给出了许多 的典型的第一遗漏。在循环检查的过程中，我们储存了白子获胜、禁止黑子回应和 未证实的位置。这个检查文件包含了以前漏掉的大约 2000 种位置，他们在下一验证 阶段被校正。验证阶段和校正位置阶段会被重复许多次，甚至当检验记录不再包含 任何缺失的位置。 这个检验方案的规划是由第二发起人用 borland 公司开发的 pascal 程序设计语言所执行的。 一部分解决方案在奔腾 200 兆赫机器处理下要花费大约 6000 小时。 6 结果 我们证实了和扩展了日本五子棋专家的陈述，它是关于自由五子棋对于先下棋的选 手是一种理论上的胜利的说法。这个游戏在用奔腾 200 兆赫的处理下的到解决。整 个数据库的大小有 7 兆字节。在完成最后的数据库的建立，又一次检查了这个数据 库和接受并认为是正确的独立程序员所写的检查程序。在最后的检查阶段，没有遗 漏任何为检查程序所发现的变化。综上所述，认为自由五子棋应该是一个已经被解 决问题了的游戏，结论就是它是一个先手获胜的游戏。 最后，我们有很好的理由去相信出版一本好的开放性书籍来提供一个适当的最后阶- 41 -南京工程学院毕业设计说明书（论文）段的分析惯例是可用的，书中没有中局比赛，但说名就 5000 种走法的看法。- 42 -
更多搜索：
All rights reserved Powered by
文档资料库内容来自网络，如有侵犯请联系客服。