计算机博弈原理与方法学概述

东北大学机器博弈研究室第二章计算机博弈原理与方法学概述徐心和徐长明东北大学机器博弈研究室2010.01东北大学机器博弈研究室主要内容2.1棋类介绍与分类2.2计算机博弈的基本原理2.3棋局要素的数据结构2.4棋局评估2.5博弈树展开与分析2.6计算机博弈求解的基本搜索方法2.7开局库与残局库2.8结语东北大学机器博弈研究室原理与方法学涵义•研究“带有普遍性的、最基本的、可以作为其它规律基础的规律，具有普遍意义的道理”，研究在计算机博弈“学科上所采用的研究方式、方法的综合”。•这里还仅仅是局限于完全信息的棋类博弈。•这是一次探索性的归纳与提升，肯定还有不少缺陷与不足，今后还需要不断地完善和补充。•由于目前国际象棋的资料比较丰富，有关方法学的内容主要还是来自国际象棋的计算机博弈。东北大学机器博弈研究室2.1棋类介绍与分类•首先需要了解我们研究的对象——棋类•不含牌，棋牌性质有很大的区别•一般说来：棋类——完全信息动态博弈牌类——不完全信息动态博弈东北大学机器博弈研究室典型棋类介绍•中国象棋•国际象棋•围棋•五子棋、六子棋•各种民间棋类•中国的：牛角棋，一字棋，二虎棋，三通棋•国外的：点格棋，苏拉卡尔塔，亚马逊•单人游戏：华容道东北大学机器博弈研究室人们为什么喜欢下棋？1.目的在决出胜负，比出高低，并关联某种收获（物质的，精神的）；2.规则简单明确，成功与失败的判定标准简单；3.博弈过程透明、公平，不包含任何机会或偶然性（不公平点——先手优势）；4.智力和经验决定胜负，问题的解决在认识意义上不需要过多的知识；5.变化无穷（很难走出同样的棋谱），激发创新，一种智力游戏。东北大学机器博弈研究室中国象棋（ChineseChess）•棋盘9×10•棋子：红黑各7个兵种，16子•各兵种的行棋规则和活动范围•胜负判定准则•长将、长拖…•时间约束•60步不吃子判和东北大学机器博弈研究室国际象棋（Chess）王KingK(1)、后QueenQ(1)、车RookR(2)、象BishopB(2)、马KnightN(2)、兵PawnP(8)东北大学机器博弈研究室•车：横冲直撞•马：不怕蹩腿•象：可以过河•王：每步一格，不受区域限制•王一旦被杀，即为输棋•后=车+象，威力最大•兵：第一步可以走两格，吃过路兵；之后前走斜吃•王车易位（长易位，短易位）；兵升变•相对子力值：Assigningthepawnavalueof1,thevaluesoftheotherpiecesareapproximatelyasfollows:knight3,bishop3,rook5,andqueen9.东北大学机器博弈研究室围棋（Go/I-Go）•棋盘19×19•轮流下子，谁占的地盘多谁胜。•先下手为强，贴目（5-7）。•规则最简单，计算机博弈难度最大。•当前侧重解决1/4棋盘Go9×9东北大学机器博弈研究室五子棋（FIR-FiveInARow）•起源于中国•发展在日本（连珠棋）•Renju/Go-Moku•棋盘15×15•已被证明先手胜•禁手•换手•金球制改进球制东北大学机器博弈研究室六子棋（Connect6）•吴毅成教授发明•棋盘19×19•6子连珠为胜•先手下一子，然后每手下两子，削减先手优势•复杂度显著提高•台湾已经盛行•欧洲也很关注东北大学机器博弈研究室一字棋•走子的距离不限，至少走一步，至多走到终点。不准逆行。可以走动任何一个棋位上的一个或多个棋子。但是必须停留在同一个目标棋位上。最后到达目的地的为胜（负）.东北大学机器博弈研究室二虎棋•布阵之后双方轮流走子，开局第一着棋由虎方先走。•犬方每次只走一个子到临近空棋位。虎方同。•虎方可跳吃，每次只吃一子。•虎方吃够一定数量的犬方棋子就算获胜；•犬方以围困虎方为目的，当虎方的全部棋子无法走动时才算犬方获胜。东北大学机器博弈研究室三通棋•全盘含有64个小正三角形，即64个棋位。•双方棋子各32枚。•开局后双方轮流布子，每方每着棋布子1枚。•乙方有一次（只有一次）连续下两着棋的权利。•当一方首先实现三通的时候终局并获胜。东北大学机器博弈研究室点格棋（DotsandBoxes）•将邻近的两点连成一边，四边构成方格；•最后一个占边者获取这个格子。并要再连一边。•最后占据方格多者为胜。•关注死格（deadbox）双环（doublecross）长链（longchain）短链（shortchain）环（circle）等。东北大学机器博弈研究室苏拉卡尔塔（Surakarta）•双方轮流走棋，不可不走；•除了吃子之外，每个棋子每步只能走一格，可以沿垂直或对角方向；•沿着弧吃子，而且必须经过一个完整的弧。•吃掉所有对方棋子一方获胜。东北大学机器博弈研究室亚马逊（Yamazons）•1988,WalterZamkauskas,Argentina发明.•每方4个国际象棋的“后”•每个着法包括移动和设障•各方争取更大的活动范围•也是一种憋死牛的游戏•无子可动一方判负东北大学机器博弈研究室华容道——滑块类游戏•ChineseSlidingBlockPuzzle。•在国外将华容道和魔方、独粒钻石并列，被誉为“智力游戏界三大不可思议”。•一次移动一个人物到空格区域，直到将曹操（最大的方块）移动到下面中央的箭头处。东北大学机器博弈研究室棋的分类•按参与人数分类（Player）：双人：象棋，围棋，五子棋……单人：华容道多人：跳棋•双人弈棋占绝大多数•一般说来，参与人数越多，对手就越多，情况就越发复杂。东北大学机器博弈研究室按兵种多少分类（Pieces）•单一兵种（Stone）：围棋、五子棋、六子棋•多兵种（Chessman）：国际象棋、中国象棋东北大学机器博弈研究室按着法分类（Move）•走子类：开局前双方摆好，开局后轮流走动棋子。如象棋、国际象棋、跳棋等，牛角棋，苏拉卡尔塔，亚马逊；•添子类：开局前盘面无子，开局后轮流放入棋子。如围棋、五子棋、六子棋、点格棋等；•吃子类：对局过程中可以吃掉对方的棋子。如象棋、国际象棋、围棋等；•混合类：在填子的过程中可以吃子（围棋）；在走子过程中可以吃子，还可以填子（日本将棋）。•通常情况弈棋双方轮流施着，各走（下）一步（Move）。但是有的棋类在一定条件下一方是可以连续施着的，即连续走多步，可称为轮（Turn）。如跳棋、西洋跳棋、黑白棋（Reversi,Othello）、点格棋（DotsandBoxes）等。东北大学机器博弈研究室日本将棋东北大学机器博弈研究室按胜负判决分类（Win-Lose-Draw）•擒获首领：象棋，国际象棋等•摆成形状：连珠类——井字棋，五子棋，六子棋等•占领地域：围棋，点格棋等•剩余子粒：黑白棋，苏拉卡尔塔等•活动余地：亚马逊等•到目标地：跳棋，一字棋，牛角棋等东北大学机器博弈研究室2.2计算机博弈的基本原理•所谓基本原理就是：带有普遍性的、最基本的、可以作为其它规律基础的规律，具有普遍意义的道理。•分析下棋：•棋类要素——了解棋盘、棋子、棋规（着法与胜负规则）•弈棋要素——用着法推演局面，从有利局面选择当前着法•局面评估——指标分析，需要具体棋种的特殊知识东北大学机器博弈研究室状态演化方程：11nnnqSSQSqqqSSFF0210...FqqqqQ....321....31qqQodd....42qqQevn——棋谱(红方)(黑方)2.2.1弈棋过程分析东北大学机器博弈研究室2.2.2如何让计算机下棋？•棋类要素的数字化——恰当的数据结构棋盘、棋子、棋规（着法规则，胜负规则）•用着法推演局面——博弈树展开•从有利局面选择当前着法——博弈搜索•局面评估——指标定义与综合东北大学机器博弈研究室棋局状态展开示意图东北大学机器博弈研究室本方本方本方对方对方Ply1Ply3Ply4Ply2Ply0展开深度为4的博弈树根节点为当前局面叶节点为展开终点双方轮流出手偶数层为本方奇数层为对方东北大学机器博弈研究室•节点为局面，树枝为着法，根节点为当前局面，叶节点为展开相应深度的终点局面。•如果叶节点还不是能够给出胜-负-和的最终局面，则要进行叶节点评估（Evaluation）。以便从有利局面选择当前着法。这便是博弈搜索的职能。•搜索引擎根据极大-极小的搜索算法，找到对于本方而言最好的结局。然后找到最佳路径（PrincipalVariation–主要变例），从而找到相应的根着法（RootMove），即是本轮搜索所要给出的当前着法。•不难看出，评估和搜索将成为博弈软件的重要部分。博弈树搜索东北大学机器博弈研究室计算机博弈软件的构成2.2.3东北大学机器博弈研究室2.3棋局要素的数据结构2.3.1计算机博弈数据结构研究的内容所有的棋局元素，包括棋盘、棋子、棋局、着法、规则、知识等通过数字化（编码）成为数据元素，而各种数据元素又以特定的关系构成相应的数据结构进行存储和处理。东北大学机器博弈研究室棋类要素的数字化•以牛角棋为例•编码——数据结构•棋盘编码（棋位编码）•棋子编码•初始局面的表示•棋位向量：(100000023)•棋子向量：(089)2034567891１２３东北大学机器博弈研究室2.3.2计算机博弈数字化原则与意义•数据结构问题在计算机博弈中的重要性是不言而喻的。•在展开和搜索博弈树期间，数以千百万计的着法和棋局被生成、存储、撤销，合理的数据结构可以显著地提高搜索速度和深度，节省内存空间，改进博弈效果。•数据结构还对编程有着直接的影响。在采用宽度优先的搜索算法中，新被扩展的节点应该采用队列结构；而在深度优先的搜索算法中，则应该采用栈结构。•编码问题要面向棋种，面向算法，面向编程。•许多情况下适当的冗余是必要的。东北大学机器博弈研究室2.3.3哈希变换与哈希表•众多棋类的成功经验表明，棋局的存储最好是采用Zobrist哈希技术加以实现，即将棋局转换为哈希数（HashNumber）。•哈希技术的基本原理是将棋盘上双方棋子的代码和坐标位置转换为对应的64位随机数，将棋盘上全部棋子所对应的随机数异或求和，这个64位的哈希数便作为给定棋局的索引值（Zobrist键值），用作棋局的存储与查询。•哈希数的最大优点就在于它求的是64位数的异或和，当在着法的作用下，棋局发生了变化，只要将相应变化棋子的哈希数再异或一次，便可以转变成新局面所对应的哈希数。东北大学机器博弈研究室位棋盘（BitBoard）•在着法生成和棋局评估的过程中，时常仅仅关心一些棋子的分布，这时可以用比特棋盘（亦称位棋盘）表示棋子的某种状态，它其实是棋子状态条件的布尔表示。如棋盘中哪些棋位上有红子？哪些棋位上有黑车等等。比特棋盘的定义为•式中为棋位（i,j）的布尔条件。nmjibB,falsestruesbjijiji,,,01jis,东北大学机器博弈研究室2.4棋局评估•如果在叶子节点不能给出胜-负-和的结果，那“有利局面”的选择就只能依靠局面的评估了。•通常设计的评估函数需要考虑如下不同类型的知识，如子力、位置、空间、机动、拍节、威胁、形状、图案等方面，并通过量化后加权组合而成。东北大学机器博弈研究室2.4.1子力(Material)•在象棋和国际象棋中，它是所有子力价值的和；在围棋或黑白棋中，通常计算双方棋盘上棋子的数量。•黑白棋有个有趣的反例：棋局只由最后的子数决定，而在中局根据子力来评价却是很差的思路，因为好的局势下子数通常很少。•像五子棋、六子棋一类的游戏，子力是没有作用的，因为局面好坏仅仅取决于棋子在棋盘上的相互位置，看它是否能够发挥作用。东北大学机器博弈研究室2.4.2位置(Position)•棋子落于不同的棋位其作用可能差别很大。•象棋中的车占中路，兵过河，马卧槽都是具有威胁性的位置。相反如果马窝心，兵下底又都不甚理想。•围棋中的星位也是兵家必争之地。•不同的位置给予不同的分值，以表示不同的价值。东北大学机器博弈研究室2.4.3空间(Space)•在某些棋类中，棋盘可以分为本方控制的区域和对方控制的区域，以及有争议的区域。•在围棋中，这个思想被充分体现。•而包