α-β剪枝技巧的发现-Read

东北大学机器博弈研究室第一讲计算机博弈原理与方法学概述徐心和东北大学机器博弈研究室2009.5东北大学机器博弈研究室主要内容•棋类介绍与分类•计算机博弈的基本原理•计算机博弈软件的构成•棋局评估•博弈树展开与分析•机器博弈的方法学特点——基于搜索•计算机博弈的学科关系东北大学机器博弈研究室棋类介绍•既然提到“原理与方法学”的高度进行研究，就是要研究“带有普遍性的、最基本的、可以作为其它规律基础的规律，具有普遍意义的道理”，研究在机器博弈“学科上所采用的研究方式、方法的综合”。•因此需要进一步了解我们研究的对象——棋类•不含牌，棋牌性质有很大的区别•一般说来：棋类——完全信息动态博弈牌类——不完全信息动态博弈东北大学机器博弈研究室典型棋类介绍•中国象棋•国际象棋•围棋•五子棋、六子棋•各种民间棋类•中国的：牛角棋，一字棋，二虎棋，三通棋•国外的：点格棋，苏拉卡尔塔，亚马逊•单人游戏：华容道东北大学机器博弈研究室人们为什么喜欢下棋？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）：双人：象棋，围棋，五子棋……单人：华容道多人：跳棋•双人弈棋占绝大多数东北大学机器博弈研究室按着法分类（Move）•走子类：开局前双方摆好，开局后轮流走动棋子象棋，国际象棋，跳棋，牛角棋，苏拉卡尔塔，亚马逊•填子类：开局前盘面无子，开局后轮流放入棋子围棋，五子棋，点格棋•混合类：开局前盘面无子，开局后轮流放入棋子，一定条件后轮流走动棋子五道棋：填子，走子，吃子日本将棋：走子、吃子、填子东北大学机器博弈研究室日本将棋东北大学机器博弈研究室按胜负判决分类（Win-Lose-Draw）•擒获首领：象棋，国际象棋•摆成形状：连珠类——井字棋，五子棋，六子棋•占领地域：围棋，点格棋•剩余子粒：苏拉卡尔塔•活动余地：亚马逊•到目标地：一字棋，牛角棋东北大学机器博弈研究室计算机博弈的基本原理•所谓基本原理就是：带有普遍性的、最基本的、可以作为其它规律基础的规律，具有普遍意义的道理。•分析下棋：•棋类要素——了解棋盘、棋子、棋规（着法与胜负规则）•弈棋要素——用着法推演局面，从有利局面选择当前着法•局面评估——指标分析，需要具体棋种的特殊知识东北大学机器博弈研究室如何让计算机实现弈棋？•棋类要素的数字化——恰当的数据结构棋盘、棋子、棋规（着法规则，胜负规则）•用着法推演局面——博弈树展开•从有利局面选择当前着法——博弈搜索•局面评估——指标定义与综合东北大学机器博弈研究室棋类要素的数字化•以牛角棋为例•编码——数据结构•棋盘编码（棋位编码）•棋子编码•初始局面的表示•棋位向量：(100000023)•棋子向量：(089)2034567891１２３东北大学机器博弈研究室当前棋局着法生成器全部可行着法棋局演化全部紧后棋局用着法推演局面——博弈树展开着法生成的基本方法：棋盘扫描，模板匹配，预置表．．．东北大学机器博弈研究室博弈思维过程展开博弈树红方走棋红方走棋蓝方走棋红方先手东北大学机器博弈研究室如何表示博弈树？树枝为着法节点为局面东北大学机器博弈研究室计算机博弈软件的构成东北大学机器博弈研究室象棋博弈软件的基本构成•人机界面•棋局表示与数组管理•着法生成与博弈树展开•棋局评估函数•博弈搜索引擎•开局库•残局库东北大学机器博弈研究室棋局评估（以象棋为例）立足红方向上进攻东北大学机器博弈研究室评估函数•在难以判断输赢的情况下识别棋局的好坏，可行的办法就是对局面进行量化•通过为棋局“打分”，评判棋局的好坏。•由于评估需要大量的象棋知识，仁者见仁，智者见智；•评估函数的设计便成为机器博弈中最为人性化和模糊化的部分。•目前对于评估函数取得共识的观点，应该包括如下部分：东北大学机器博弈研究室固定子力评估值—e1(m)•车-600，•炮-285，马-270•相-120，士-125•兵、卒-20•帅、将无穷大值，具体数值可以给6000•红方为正值，黑方为负值东北大学机器博弈研究室棋子位置评估值—e2(m,i,j)•各兵种在棋盘的不同位置上权值不同•可由三维数组给出：•三维数组可以按兵种分解为若干个二维数组，而且要区分红方和黑方xmmejime,22),,(x分别为各兵种代码东北大学机器博弈研究室红车位置评估值(m=r)2()141412181618121414162018242624182016121212181818121212121816222222161812121412181818121412121614202020141612610814141481064861412146848481681684821061412146102mre车坐大堂分值最高！东北大学机器博弈研究室2()48161241216844102816816281041214162018201614128241824202418248616141816181416641216141214161242686106862428848824024424420040000040mhe马窝心和马卧槽大不相同！红马位置评估值(m=h)东北大学机器博弈研究室当头炮分值较高！2()64010121004622041440222201081002200241042000002820002042624020002420004086106804024666420002666200mce红炮位置评估值(m=c)东北大学机器博弈研究室红兵位置评估值(m=p)2()036912963018365680120805636181426426080604226141020303440343020106121818201818126208080802002040200000000000000000000000000000mpe可见进入九宫的兵顶大车！东北大学机器博弈研究室棋子灵活度评估值—e3•对各兵种而言，每多一个可走位置就加上一定分值。•如设定：兵-15士-1象-1车-6马-12炮-6将-0东北大学机器博弈研究室棋子配合评估值—e4•重点是车马炮的配合与牵制。•过河兵牵手可加120分。•连环马、担子炮、霸王车等都可以考虑加分。将帅安全评估值—e5•此项多从盘势上加以考虑。•多子归边、空头炮、当头炮、沉底炮、将帅位置等，都要给予一定的惩罚或奖励分。东北大学机器博弈研究室评估函数的计算•本方为正值，对方为负值，其代数和即为当前局面评估值。•显然，总值为正对我方有利，负值对对方有利。绝对值的大小说明双方棋势的差距。•不难看出，评估函数中涉及到的权值系数可能多达上千个，都需要认真选择与权衡。——系统开发难点。NkNkTlRlkRkReEE111,NkNkTlBlkBkBeEE111,东北大学机器博弈研究室博弈树展开与分析•博弈树代表的是从当前棋局（根节点）的演化和发展，是进行棋局分析的基础。•树枝代表着法，节点代表棋局。•分支多少用分支因子表示，节点的层数代表展开的深度。•分支因子大，展开层数多，是博弈树规模庞大的原因。•将博弈树全部展开（从初始棋局到分出胜负）的节点数，为该种棋树的复杂度。•全部可行棋局的数量为状态复杂度。•由于博弈树中有大量的重复状态，所以树的复杂度远高于状态复杂度。东北大学机器博弈研究室状态演化方程：11nnnqSSQSqqqSSFF0210...FqqqqQ....321....31qqQodd....42qqQevn——棋谱(红方)(黑方)棋局演化过程东北大学机器博弈研究室棋局状态展开示意图东北大学机器博弈研究室本方本方本方对方对方Ply1Ply3Ply4Ply2Ply0展开深度为4的博弈