博弈树的启发式搜索.doc

《博弈树的启发式搜索.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、博弈树的启发式搜索问题A方、B方必须是完备博弈，它有三个条件：1、A，B双方轮流博弈。博弈的结果只有三种情况：A胜，B败；A败，B胜；A，B平手。2、任一方都了解当前的棋局和历史的棋局。3、任一方都分析当前的棋局，并能作出有利于自己，而不利于对方的策略。我们描述博弈过程采用与/或树1、博弈的初始棋局作为初始节点2、‘或’节点与‘与’节点逐层交替出现。自己一方扩展节点之间是‘或’，对方扩展节点之间是‘与’。双方轮流扩展。3、所有能使自己获胜的终局都是本原问题，相应的节点是可解节点。本问题其实是一个构造博弈树的

2、问题。对给定的棋局，该棋局中A，B方的棋子数相等，并且轮到A方下。这样构成一个初始棋局，称一个状态。当A或B下一个棋子后，又形成一个新的状态。任何一方都希望自己取得胜利，因此当某一方有多个方案可供选择时，他总是跳最有利于自己而最不利对方的方案。此时我们站在A的立场上看，可供A选择的方案之间是‘或’的关系，可供B的方案之间是‘与’的关系。因为主动权在A上，A必须考虑任何一个可能被B选中的方案。极大极小分析方法的特点：1、它是为其中一方寻找一个最优的行动方案的方法2、为了当前最优的方案，需要对各个方案能产生的后

3、果进行比较，具体地说就是考虑每个方案实施后，对方可能采取的行动，并计算可能的得分4、为了计算得分，需要根据问题的特性定义一个估价函数，用来计算当前博弈树端节点的得分，该得分也称静态估值5、当端节点估值后，再推算父节点的得分，推算方法是对于‘或’节点，选择子节点中最大的得分作为自己的得分，对于‘与’节点，选择子节点中最小的得分作为自己的得分，父节点得得分也称倒退值6、若某一个行动方案能获得最大得倒退值，则它就是当前最好得方案在本问题中，假设棋盘为4*4的矩阵，A方的棋子为1，B方的棋子为－1，空格为0。我们定

4、义估价函数为：在某一棋局状态，A方棋子可能占满的整行，整列，整斜线总和与B方棋子可能占满的整行，整列，整斜线总和的差。这儿的可能是指棋局上留出的空格让A方或B方全摆放它的棋子。显然如果A方的大。它的下棋选择的策略范围就大。对某个棋局用极大极小分析后，得出A下一步的最佳策略，同时也给出B的最不利A的策略，这样一直循环，直到棋局上无空格，如果棋局上A已经胜出了。那么就意味着B如何采取对A最不利的策略，A也能胜出，表明A处于必胜状态。程序说明：编写语言：Matlab6.5主函数：Chess.mChkVictory

5、.m函数：计算某个棋局状态中A方是否已经胜出算法：对矩阵的列，行，斜线求和。若和为4，则A已经胜出，否则返回0ChkLines.m函数：计算中某个棋局状态中A方或B方全占满的行，列，斜线数总和算法：对矩阵的列，行，斜线求和。把矩阵中和为4的行数，列数，斜线数总和返回CalFunc.m函数：计算估价函数值算法：对某个棋局状态，首先把该棋局状态的空格塞满A方的棋子，算出现在A方棋子占满整行，整列，整斜线的总数。然后在原来的棋局状态的空格塞满B方的棋子，算出B方棋子占满整行，整列，整斜线的总数。然后求两者差。该启

6、发函数将引导A方如何下棋子，做到作出有利于自己，而不利于对方的策略。Excute.m函数：执行棋局分析Chess.m函数：读input.txt文件，运行棋局分析函数，写output.txt文件