一设计目标... 3 二数据结构及算法设计基本的博弈树搜索 (alpha-beta 剪枝 ) 关于动态估值函数开局策略可行位置的快速计算... 6 三详细设计类图类摘要类 Avail

Size: px

Start display at page:

Download "一设计目标... 3 二数据结构及算法设计基本的博弈树搜索 (alpha-beta 剪枝 ) 关于动态估值函数开局策略可行位置的快速计算... 6 三详细设计类图类摘要类 Avail"

螺何
5 years ago
Views:

1 Java 小作业黑白棋的设计与实现姓名笪庆学号时间 2009 年 5 月 1

2 一设计目标... 3 二数据结构及算法设计基本的博弈树搜索 (alpha-beta 剪枝 ) 关于动态估值函数开局策略可行位置的快速计算... 6 三详细设计类图类摘要类 AvailableTable 类 ComputerPlayer 类 JFrameBoard 类 JPanelBoard 类 JPanelStatus 类 OpeningBook 其他的类四心得体会

3 一设计目标使用 java 语言编写具有图形界面的可以实现人机对弈的黑白棋程序二数据结构及算法设计 1 基本的博弈树搜索 (alpha-beta 剪枝 ) 对于像黑白棋这样的棋类游戏, 一种经典的解决方案便是搜索策略中的博弈搜索, 而且通常使用 alpha-beta 剪枝在不影响结果的情况下来减小搜索空间假设下棋的双方为 MAX 和 MIN, 则搜索的目的是为 MAX 方寻求下一步棋子应该放置的位置, 我们用某一时刻的棋盘状态来标记每一个搜索树中的节点, 则我们从当前状态出发, 通过深度遍历来搜索空间状态叶子节点通过估值函数计算其估值, 并作为其倒退值返回给其父节点 ; 对于非叶子节点,MAX 节点选取其具有最大倒退值的子节点的估值作为其估值,MIN 节点选取其具有最小倒退值的子节点的估值作为其估值这样一来, 由于根节点是 MAX 节点, 其具有最大倒退值的子节点的状态便是机器应该选择的下一步到达的棋盘状态通常来说对整个状态空间进行搜索是不现实的, 我们常常通过限定搜索树深或搜索节点的个数来限制搜索空间控制在可计算的范围之内来使得机器思考的时间在人能够容忍的范围之内在以上所述的博弈树搜索之中, 存在很多的冗余搜索, 这就是为什么我们需要 alpha-beta 剪枝的原因, 例如当我们发现 MAX 的某一个子节点的倒退值不可能比其某个兄弟节点的倒退值还大的时候, 这个时侯对这个节点的继续搜索其实是没有任何意义的, 对于 MIN 节点的情形也与之类似基本的基于 alpha-beta 剪枝的搜索算法框架如下 : alpha-beta-search(depth,nodetype,alpha,beta) If(depth == maxdepth 已无子节点可扩展 ) return 该节点的估值计算该节点的所有子节点 ; for( 每一个扩展的子节点 ) v = alpha-beta-search(depth+1,!nodetype,alpha,beta); if(nodetype == MAX) if( v > alpha ) V = alpha; if( alpha >= beta) Return beta; 3

4 if(nodetype == MIN) if( v < beta ) v = beta; if( beta <= alpha) return alpha; if(nodetype == MAX) return alpha; else return beta; 通常情况下, 即使通过了 alpha-beta 剪枝有时候搜索代价还是很大, 有很多文献都针对 alpha-beta 剪枝做了很多改进和优化一种最简单的优化是对子节点进行排序, 排序的内容通常是对子节点的估值, 这样可以尽早的扩展具有最大倒退值的子节点 ( 对父节点是 MAX 而言,MIN 则反之 ), 使得对后面的子节点进行扩张时可以进行尽可能多的剪枝, 这种方法可以有效的减少搜索空间, 但是对子节点进行估值和排序也是需要代价的, 而且对子节点的估值并不能够反映出其倒退值, 所以这种改进对于时间复杂度上并没有显著提升, 但是空间复杂度明显降低还有一些更深入的改进,Logistello( 曾经的世界排名第一的黑白棋程序 ) 的作者 Michael Buro 提出了一种概率剪枝 (probcut, 不知道是不是这么翻译 ) 的方法, 他通过浅层搜索的方法计算每一个子节点的倒退值, 再计算这些估值大于 beta 值的概率 ( 对父节点是 MAX 节点而言 ), 若其大于一个预设的概率阈值, 则该节点可以被 cut 掉对 Logistello 实现而言, 默认为搜索 8 层, 浅层搜索 4 层除了传统的 alpha-beta 搜索外,Coplan 在 1992 提出了一种算法 negac* 用来替代 alpha-beta, 在这个算法中, 搜索的是 alpha-beta 算法中搜索树的一颗子树, 而且易于实现, 但是有局限性从实现复杂度和时间限制上考虑, 我还是选择了常用的 alpha-beta 算法来实现我的搜索 2 关于动态估值函数这一部分负责对搜索树的叶子节点计算其估值, 估值越大则意味着 MAX 方获胜的概率越大, 估值函数的设计一直是棋类游戏程序设计的重点和关键所在在黑白棋的估值函数设计上, 可以从很多角度提出不同的计算方法一种最简单便是计算棋子的个数, 这种方法没有考虑到不同位置上的棋子对整体棋局的影响的差异, 就人类下棋的经验而言, 四个角通常非常重要, 很少出现四个角全占了而输掉棋局的情况, 在这种思想的考虑下, 人们提出了基于 WPC(weighted piece counter) 的计算方法, 即为棋盘上不同位置上设立不同的权值来计算, 例如下面的一个 WPC 矩阵 : 4

5 计算估值时, 若相应的位置被 MAX 方所占, 则加上相应的权值 ; 若被 MIN 方所占, 则减去相应的权值上面的 WPC 只是很简单的一种对于人类知识的一种总结, 事实上, 很多学者都在研究如何利用机器学习的方法不依赖专家知识求解出一些对于黑白棋而言更好的 WPC, 本程序的 WPC 使用 Simon M. Lucas 和 Thomas P. Runarsson 在其合作发表的 Temporal Difference Learning Versus Co-Evolution for Acquiring Othello Position Evaluation 中通过对比即时差分学习 (TDL,Temporal Difference Learning) 和协同进化 (CEL,Co-Evolution) 对于计算黑白棋的估值函数时得到的一个最佳 WPC, 如下 : 另外一个计算方法是行动力, 即某一个状态下 MAX 与 MIN 方的可行位置数目之差以上的计算方法只是静态的计算方法, 即其计算方式不依赖于具体的棋盘状态, 而实际上这种方法是不科学的, 因为例如对于四个角的周围的三个位置在 WPC 中都为负值, 这是为了避免给对方放入角的机会, 但是当 MAX 方自己占了一个角后, 这个负值就没有意义了, 有时候还会带来相反的效果, 所以我们有必要对权值做动态更新 Jean-Marc Alliot 和 Nicolas Durand 在 a genetic algorithem to improve an Othello program 中提出了一种更新策略, 如下图 : 5

6 更新策略如下 :1 若某一个角已被 MAX 所占, 则其周围的三个位置的权值都设为 0( 例如上图中的 H8); 2 若某一个角已被 MAX 所占, 若与其相连的连续同色棋子需要给与额外奖励, 因为这些是不可能再被翻转的棋子 ( 例如上图中的 H8,G8,F8); 3 若 MIN 方出现了 2 中描述的情况, 则需要给与罚款来减少其估值, 从而避免这些情况 3 开局策略在很多篇文献中都有提到开局策略对棋局的影响是巨大的, 事实也是如此在 Kyung-Joong Kim 和 Sung-Bae Cho 的 Evolutionary Othello Players Boosted by Opening Knowledge 中, 使用了 99 种 well-defined 的开局, 每种开局都如下面的形式 : C4C3 C4C3D3C5B2 C4C3D3C5B3 C4C3D3C5B3F4B5B4C6D6F5 C4C3D3C5B4 C4C3D3C5B4D2C2F4D6C6F5E6F7 C4C3D3C5B4D2D6 C4C3D3C5B4D2E2 C4C3D3C5B4E3 C4C3D3C5B5 C4C3D3C5B6C6B5 我们早这个程序中使用了同样的技术, 即开局查表的方法去 99 种完美开局来搜索前几步 ( 实际上由于对称性, 我们的开局表应该有 99 4=396 种 ) 对于匹配的所有方案中, 我们随机的选择一个随机选择的方案貌似不大严谨, 其实在所有可行方案中随机选择一个总使得所选步骤为前缀的方案个数从概率上来说总是最多的, 从而增大下一次匹配成功的概率, 所以是很有意义的 4 可行位置的快速计算在博弈树的算法中, 每次扩展子节点之前都需要计算当前的执棋方的可行位置, 通常 naive 的方法是扫描每一个对方棋子的 8 个方向看是否可下, 而为了取得定某个位置是否可下, 我们不得不反方向扫描某个长度才能确定, 这样的代价在单个函数而言是很少的, 但是如果在博弈树中的每一个节点扩展时都要进行此操作, 则该计算的总的代价还是可观的, 所以, 一种快速计算执棋方的可行位置的算法是非常有必要的下面介绍在本程序中使用的基于查表的可行位置的快速计算方法 ( 特别提出的是, 关于这个算法的思想来自于许佳同学的提示, 特此鸣谢!) 我们很容易发现这样一个事实, 即可行位置一定和一个可以将对方棋子翻转的位置有关, 而翻转这一事件仅仅可能发生在某一行, 列或斜线上, 而对于黑白棋而言, 只有 =46 中, 其中斜线上长度为 1,2 的 8 种可以忽略, 因 6

黑白棋的设计与实现 061221015 笪庆为在这条直线上是不可能出现翻转的所以可行的直线只有 46-8=38 种而在这 38

那么对整个棋盘执行 38 此该操作即可按行计算按列计算按斜线计算为了能够快速计算我们需要对 1 8

种直线通过计算其编码来得到其解的位置这样直接通过数组下表便可以找到其解编码方案如下 0 空 1 黑棋 2 白棋对于下图所示的直线状态

6561 种情况下黑棋和白旗的可行位置存于 4 个文本文件中分别存储着对应与这 6561 种状态的黑棋的可行位置数

7 黑白棋的设计与实现笪庆为在这条直线上是不可能出现翻转的所以可行的直线只有 46-8=38 种而在这 38 种直线上长度最大的就是 8 这就提示我们如果我们能够对于长度为 8 的单行能够根据该行的状态迅速计算执棋方的可行位置的话那么对整个棋盘执行 38 此该操作即可按行计算按列计算按斜线计算为了能够快速计算我们需要对 1 8 棋盘上的所有状态对应的黑白方的可行位置事先计算出来共有 38=6561 种并为每种状态进行编码使得对 8 8 的棋盘中的 38 种直线通过计算其编码来得到其解的位置这样直接通过数组下表便可以找到其解编码方案如下 0 空 1 黑棋 2 白棋对于下图所示的直线状态其编码值为 =432 我们直接去表中查找下标为 432 的解即可具体实现是我们用 naive 的方法生成这 6561 种情况下黑棋和白旗的可行位置存于 4 个文本文件中分别存储着对应与这 6561 种状态的黑棋的可行位置数黑棋的可行位置和白棋的可行位置数和白棋的可行位置对于直线上长度小于 8 的可以通过后面补零来处理此外在具体实现时我们可以通过存储一个 3 8 的数组 a[i][j] = i 3j 来避免乘法操作来加速计算 7

8 三详细设计 1 类图 8

9 2 类摘要在本文中一共设计了 9 个类, 下面来依次介绍这 9 个类的具体实现 2.1 类 AvailableTable 一个用于处理计算当前棋盘某方的可行位置的类, 通过查表的方法来实现快速计算在这个表中, 记录着对于 1 8 的单行棋盘上所有的状态 ( 共有 6561 种 ) 所对应的白方和黑方的可行位置具体通过 4 张表实现, 对于待计算的棋盘上的每一行 ( 或列, 斜线 ), 按 3 进制计算其在表中的索引字段摘要 int[] black_len int[][] e3 int[] size int[][] start 用于存储每种状态中黑棋的可行位置数用于快速计算索引的二维矩阵, 使得计算幂可以通过查表快速实现用于斜线方向上可行位置计算的每一条目的长度用于斜线方向上可行位置计算的下标数组 int[][] table_black 用于存储每种状态中黑棋的可行位置 int[][] table_white 用于存储每种状态中白棋的可行位置 int[] white_len 用于存储每种状态中白棋的可行位置数构造方法摘要 AvailableTable() 构造方法, 完成四张表的读入以及一些快速计算索引的整型数组的初始化工作 9

10 方法摘要 java.util.array List<Position> int Availble(int[][] chess, int side) 通过查表的方法由当前棋盘状态以及需计算一方的标志快速计算其可行位置 DiffAvailble(int[][] chess, int side) 计算双方的行动力之差, 用于搜索中叶子节点的静态估计值的计算 readtable() 从文本文件读入可行位置表 ( 共 4 张, 由其他程序事先生成 ), 并存储在四个数组中 2.2 类 ComputerPlayer AI 黑白棋手, 通过开局策略和基于动态估值函数的博弈树来计算其下棋步骤字段摘要 AvailableTable OpeningBook atable book 可行位置表, 用于可行位置的快速计算开局表, 用于开局的搜索 int[][] chess int maxdepth int myside int solution_x int solution_y 记录棋盘状态的二维矩阵博弈树的最大搜索深度 AI 棋手所执棋方标志记录搜索结果, 即将下棋位置的横坐标记录搜索结果, 即将下棋位置的纵坐标 double[][] weight 记录棋盘格权值的二维矩阵 10

11 构造方法摘要 ComputerPlayer() 构造方法, 用于权值矩阵, 开局表, 可行位置表的初始化, 最大搜索深度, 所执棋方的设置等工作方法摘要 double boolean int int evaluation() 棋盘状态的动态估值函数 findsolution(int[][] chess, int i, int j) 求解方法, 此方法向外界提供一个接口用于从当前棋盘状态以及人类所下的上一步棋计算下棋位置 flip(java.util.arraylist<position> change, int i, int j, int side) 翻转棋盘, 用于当一颗棋子新放入值棋盘时, 将按照黑白棋的规则需要翻转的棋子翻转同时将被翻转的棋子翻入 change 表中, 用于后续的恢复 getfirsrmove() 从 open 表中随机选取一步作为开局, 用于 AI 先走的情形 getsolution_x() 返回计算其下棋位置的横坐标 getsolution_y() 返回计算其下棋位置的纵坐标 recover(java.util.arraylist<position> change, int i, int j, int side) 恢复方法, 用于将一颗新棋子放入棋盘后带来的棋盘状态的改变的恢复 reload() 重新初始化开局表, 用于游戏的重新开始 double search(double alpha, double beta, int side, int depth) 主搜索函数, 完成博弈树的 α-β 的极大极小搜索 setmaxdepth(int maxdepth) 设置最大搜索深度 setmyside(int myside) 设置 AI 所执棋方标志 11

12 2.3 类 JFrameBoard 程序的主窗体字段摘要 javax.swing.jmenuitem javax.swing.jmenuitem javax.swing.jmenubar javax.swing.jcheckboxmenu Item about back bar black 'about' 菜单项 'back' 菜单项窗口中菜单栏 'black' 可选菜单项, 设置 AI 为黑方 JPanelBoard board javax.swing.jmenu depth JPanelBoard 对象, 用于棋盘的显示更新以及人机交互 'depth' 菜单 javax.swing.jmenuitem exit 'exit' 菜单项 javax.swing.jmenu function javax.swing.jmenu games javax.swing.jmenu help 'function' 菜单 'game' 菜单 'help' 菜单 javax.swing.jmenuitem how 'how' 菜单项 javax.swing.jcheckboxmenu Item[] seadep 搜索深度的可选菜单项, 设置博弈树的最大搜索深度, 范围为 1 至 10 javax.swing.jmenu set 'setting' 菜单 javax.swing.jmenuitem start 'start' 菜单项 12

13 JPanelStatus status JPanelStatus 对象, 用于局势状态的更新与显示 javax.swing.jcheckboxmenu Item white 'white' 可选菜单项, 设置 AI 为白方构造方法摘要 JFrameBoard() 构造方法, 用于菜单项以及面板的组织方法摘要 back() setblack() 'back' 的事件响应方法设置 AI 执黑棋的事件响应方法 setdepth(int k) 设置搜索深度的事件响应方法 setwhite() start() 设置 AI 执白棋的事件响应方法 'start' 的事件响应方法 2.4 类 JPanelBoard 用于棋盘的显示更新以及人机交互的类, 扩展 JPanel 类, 实现了 MouseListener 接口字段摘要 java.awt.image available java.awt.image back 可行位置图片背景棋格图片 java.awt.image.bufferedimage background 背景图片 background 13

14 java.awt.image black int[][] chess ComputerPlayer cpu java.awt.graphics g java.awt.graphics2d g2 boolean isback int myside int num 黑色棋子图片记录棋盘状态的二维整型数组 AI 棋手 cpu 指向当前面板的 Graphics 指向背景图片的 BufferedImage 中的 Graphics2D 悔棋标志 AI 所执棋方标志当前棋盘中棋子的个数 int num_flip 记录每一步中被翻转的棋子个数, 用于增量计算棋盘中黑白棋子的个数从而避免每次重新计算 boolean over JPanelStatus status java.awt.image white 游戏结束标志 JPanelStatus 对象的引用白色棋子图片构造方法摘要 JPanelBoard() 构造方法, 在这个方法中, 将读入用于显示的各种图片和 AI 棋手的创建方法摘要 boolean addchessman(int i, int j, int side) 向棋盘中放入一颗棋子, 完成相关棋子的翻转 14

15 boolean availablelocation(int side) 计算可行位置的坐标, 并使用其他方法将其显示出来 back() 悔一步棋 clearavailable() 在面板中清除可行位置的提示信息 drawlocation(int i, int j) 在可行位置出绘出提示图片 flip(int i, int j, int side) 翻转棋盘, 用于当一颗棋子新放入值棋盘时, 将按照黑白棋的规则需要翻转的棋子翻转 load() 初始化操作, 从构造方法中抽象出来的, 用于后来重开棋局的复用 mouseclicked(java.awt.event.mouseevent e) MouseListener 接口中的方法, 在这个类中并未实现 mouseentered(java.awt.event.mouseevent e) MouseListener 接口中的方法, 在这个类中并未实现 mouseexited(java.awt.event.mouseevent e) MouseListener 接口中的方法, 在这个类中并未实现 mousepressed(java.awt.event.mouseevent e) MouseListener 接口中的方法, 用于用户在棋盘中点击事件的响应 mousereleased(java.awt.event.mouseevent e) MouseListener 接口中的方法, 在这个类中并未实现 paint(java.awt.graphics g) 重写 JPanel 的 paint 方法, 用于显示图片 reload() 重开棋局处理 setdepth(int k) 设置最大搜索深度 setside(int side) 设置 AI 执棋方标志 setstatus(jpanelstatus status) 设置对 JPanelStatus 对象的引用 showresult() 显示结果 start() 用于 AI 执黑棋时先走一步 15

16 2.5 类 JPanelStatus JPanelStatus 类, 用于局势状态棋谱的更新与显示字段摘要 int bl javax.swing.jlabel blacknum 用于显示黑子棋子个数用于显示黑子棋子个数的标签 JPanelBoard board int count int myside JPanelBoard 对象的引用用于控制棋谱打印换行的计数器设置 AI 所执棋方标志 java.util.arraylist<position> pos_record 以坐标的形式保存棋谱, 用于悔棋操作 javax.swing.jtextarea record java.lang.string recordtext javax.swing.jbutton start int wh javax.swing.jlabel whitenum 记录下棋记录的文本域用于文本域中文本存储 'START' 按钮用于显示白子棋子个数用于显示黑子棋子个数的标签构造方法摘要 JPanelStatus() 构造方法, 用于组件的创建以及组织 16

17 方法摘要 java.util.arraylist<position> addrecord(int i, int j) 向棋谱中增加一条记录 back(int black_num, int white_num, int index) 用于悔棋后棋谱的刷新 getpos_record() 得到记录棋谱的 list reload() 用于重新开始游戏的初始化 setboard(jpanelboard board) 设置 JPanelBoard 对象的引用 setmyside(int myside) 设置 AI 所执棋方标志 setnum(int flip_num) 通过每次放入棋子后翻转的棋子个数计算黑白子的个数 start() 用于 'START' 按钮的事件响应 2.6 类 OpeningBook 开局表类, 这个类通过查找 99 中 well-defined 的开局, 给出开局时几步的下棋位置字段摘要 boolean isend 判断开局表是否用完 java.util.arraylist<java.lang.string> opening 用于存储开局的 list int p java.util.random random 用于标志当前已走步数的变量随机数, 用于在匹配的开局中随机抽取一个 17

18 int x int y 查得的下棋位置的横坐标查得的下棋位置的横坐标构造方法摘要 OpeningBook() 构造方法, 用于开局表的读入以及初始化方法摘要 getfirsrmove() 用于 AI 先走时选出第一步 int int getx() gety() 得到查得的下棋位置的横坐标得到查得的下棋位置的纵坐标 boolean readopening(java.lang.string filename) 从文件读入开局表 searchbook(int i, int j) 搜索开局表中, 随机选择匹配的下棋位置 2.7 其他的类除了以上的类之外, 还有 JFrameHowTo 类 ( 用于显示帮助信息的窗体 ) Position 类 ( 用于记录下棋位置的一个类 ) 和 Othello 类 (main 方法所在类, 用于整个程序的 Frame 的创建 ), 由于很简单, 里面也没有什么重要的方法, 故不再赘述 18

19 四心得体会在这次小作业的编写过程中, 我曾经进行过很多尝试, 例如不采用直接函数递归求解 alpha-beta, 而是在内存中构造并保存一颗树, 这样使得下一次搜索时可以有效的利用上一次的搜索子树, 但是这种方法在最大搜索深度为 5 的时候就回堆溢出, 于是我有不得不手动对内存进行管理, 即对于上次搜索中已无用的节点所占的内存, 并不让 java 自带的 garbage collector 来进行回收, 而是用其去维持一棵 garbage Tree, 使得在程序扩展子节点时先去这个 garbage Tree 中取出一个可用节点而不是执行 new 操作, 这样确实给程序带来了改进, 但是堆溢出的情况还是随着搜索深度的增加而出现, 使得不得不放弃这种实现 ; 我也曾经不满足与 java 的速度, 一度将核心搜索代码用 C++ 语言重写, 并编写成动态链接库文件 (dll), 通过 jni 技术在 java 中直接使用 dll 中提供的接口, 效果也没有我想象中的那么好, 后来我有重写了 c++ 程序, 用指针操作重写了整个搜索部分, 速度略有提高, 但比其 java 并没有显著提高, 使得我也放弃了这部分实现 ; 关于估值函数的计算, 不久前我找到了有关用神经网络中的多层感知机的相关资料, 还没有来得及实现, 未免觉得有点遗憾还好即使在现在的实现上, 这个黑白棋的棋力还是很强的, 速度也很快, 使得我稍感欣慰 19

Figure 1: Game Tree 为了方便讨论, 我们这里设这里讨论的博弈树是一棵有限树, 设有两个棋手甲与乙进行这场博弈, 这样, 博弈树分为三类结点 : 1. 奇数层的非叶子结点 :

Figure 1: Game Tree 为了方便讨论, 我们这里设这里讨论的博弈树是一棵有限树, 设有两个棋手甲与乙进行这场博弈, 这样, 博弈树分为三类结点 : 1. 奇数层的非叶子结点 : 从极大极小算法到主要变例搜索孙锴 1 综述人机对弈在计算机诞生前就开始了发展, 时至今日, 人机对弈领域提出的搜索算法数目已经非常之多, 但从根本上看, 许多搜索算法之间的内在的核心思想是一致的本文介绍将从极大极小搜索

一 设计目标... 3 二 数据结构及算法设计 基本的博弈树搜索 (alpha-beta 剪枝 ) 关于动态估值函数 开局策略 可行位置的快速计算... 6 三 详细设计 类图 类摘要 类 Avail

一设计目标... 3 二数据结构及算法设计基本的博弈树搜索 (alpha-beta 剪枝 ) 关于动态估值函数开局策略可行位置的快速计算... 6 三详细设计类图类摘要类 Avail